Retaining language-model prefix states trades recomputation against storage time.
Optimizing each cached block independently can overcount savings: a resident block is usable only when the required preceding prefix is also available.
Prefix-Certificate Retention (PCR)
We introduce Prefix-Certificate Retention (PCR), an exact finite-trace formulation for static, grouped, reset-on-access timeouts.
Usable-prefix rewards become nodes whose prerequisites are timeout thresholds and preceding hit certificates.
The resulting maximum-weight closure reduces to one minimum cut, with graph size linear in the number of block lookups and timeout choices.
Breakpoint Theorem
A breakpoint theorem extends the construction to all nonnegative timeouts without discretization error.
Dynamic Program for Ordered Timeouts
We also derive a linear-time-in-grid-size dynamic program for ordered timeouts and bounds that certify the cost of this restriction.
Experiments
Exhaustive small-instance checks and chronological replay of 39,632 public Mooncake requests validate the formulation.
On the fixed grid, ordered timeouts attain the unrestricted training optimum in 118 of 120 trace-grouping-price cases.
Heterogeneous retention improves several held-out memory-time tradeoffs, but finer training optimization does not uniformly improve transfer.
Contribution
The contribution is a tractable optimization model and an auditable benchmark for retention policies; the experiments measure usable prefix blocks and storage time, not GPU latency.