Lemma 1, p. 19 — Policy 2 (greedy eviction by the smallest ranking criterion) returns an optimal solution to the ET-LRU problem (8)
ProvedTailOptCaching.ETLRU.lemma_1Let be a natural number, let be a well-formed belief state with arrived conversations, and let conversation (existing, or new if ) arrive with prompt length and response length . Policy 2 (Algorithm 2) first sets , , , and then performs
eviction steps (with the updated ), each removing one cached token from a conversation with that minimizes the ranking criterion
recomputed after every eviction, ties broken arbitrarily. Lemma 1: the resulting cache vector is feasible for (9), (10) and the capacity constraint, and it minimizes the objective of (8),
over all feasible .
Lemma 1 shows that ET-LRU can be implemented token by token with a min-heap, without solving (8) as an integer program.
Formalization Note. Algorithm 2 takes the number of tokens to evict as an input; here it is the number above (truncated subtraction in ), the number that makes the output feasible. The hypothesis is added because the ranking criterion is the marginal cost only for integer (see the marginal-cost identity). The run of the algorithm is a relation, so the lemma holds for every tie-break.
import Mathlib import Definitions.Def_TailOptCaching_ETLRU_Model open scoped ENNReal
namespace TailOptCaching.ETLRU
theorem lemma_1 (P : Params) (hξ : ∃ m : ℕ, P.ξ = m) (s : State) (hs : WellFormed P s)
(θ q a : ℕ) (hθ : θ ≤ s.n) (z : State)
(hz : GreedyRun P
((∑ i ∈ Finset.range (nAfter s θ), Function.update s.X θ (s.L θ + q + a) i) - P.C)
(post P s θ q a (Function.update s.X θ (s.L θ + q + a))) z) :
Feasible P s θ q a z.X ∧
∀ Y, Feasible P s θ q a Y → nextTEL P z ≤ nextTEL P (post P s θ q a Y) := by sorry
end TailOptCaching.ETLRU
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.