プロンプトキャッシュの模型

有効期間 $\tau \gt 0$、書き込みの倍率 $w \gt 1$、読み取りの倍率 $r$（$0 \le r \lt 1$）を固定する。キャッシュの状態は、モデルの名前 $\mu$ とトークン列 $p$ の組（項目）から、期限の時刻への部分写像 $C$ である。項目 $(\mu, p)$ が時刻 $t$ に生きているとは、$C(\mu, p)$ が定義されていて $C(\mu, p) \gt t$ であることをいう。

時刻 $t$ に、モデル $\mu$、トークン列 $x$（長さ $n$）、ブレークポイントの位置 $b$（$1 \le b \le n$）の要求を処理すると、次のことが起こるとする。

1. 命中の長さ $\ell$ を、時刻 $t$ に生きている項目 $(\mu, p)$ で、$p \sqsubseteq x$ かつ $|p| \le b$ を満たすものの長さ $|p|$ の最大値と定める。そのような項目が無ければ $\ell = 0$ とする。
2. 使用量を、読み取り $\ell$、書き込み $b - \ell$、通常の入力 $n - b$ と定める。
3. コスト（基準の入力単価を 1 とした入力の料金）を $r\ell + w(b - \ell) + (n - b)$ と定める。
4. 項目 $(\mu, x[1..b])$ の期限を $t + \tau$ にする（新しく書くか、更新する）。$\ell \gt 0$ のとき、命中した項目 $(\mu, x[1..\ell])$ の期限も $t + \tau$ にする。

キャッシュを使わない要求のコストは $n$ とする。