Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 1, p. 19 — Policy 2 (greedy eviction by the smallest ranking criterion) returns an optimal solution to the ET-LRU problem (8)

Proved
TailOptCaching.ETLRU.lemma_1

by mikedeng1 · Oct 22, 2026 · Mathlib 0df444a (Lean v4.33.1)

cachinggreedy-algorithmp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1resource-allocation

Let ξ\xiξ be a natural number, let s=(λ,L,X)s = (\lambda, L, X)s=(λ,L,X) be a well-formed belief state with nnn arrived conversations, and let conversation θ≤n\theta \le nθ≤n (existing, or new if θ=n\theta = nθ=n) arrive with prompt length QQQ and response length AAA. Policy 2 (Algorithm 2) first sets Lθ←Lθ+Q+AL_\theta \leftarrow L_\theta + Q + ALθ​←Lθ​+Q+A, Xθ←LθX_\theta \leftarrow L_\thetaXθ​←Lθ​, λθ←λˉθ\lambda_\theta \leftarrow \bar\lambda_\thetaλθ​←λˉθ​, and then performs

m=(∑iXi−C)+m = \Big(\sum_i X_i - C\Big)^+m=(i∑​Xi​−C)+

eviction steps (with the updated XXX), each removing one cached token from a conversation jjj with Xj≥1X_j \ge 1Xj​≥1 that minimizes the ranking criterion

vj=λj P(Lj+Qj−ξ≥Xj),v_j = \lambda_j\, \mathbb P(L_j + Q_j - \xi \ge X_j),vj​=λj​P(Lj​+Qj​−ξ≥Xj​),

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),

∑iλi E[(Li+Qi−Yi−ξ)+],\sum_i \lambda_i\, \mathbb E\big[(L_i + Q_i - Y_i - \xi)^+\big],i∑​λi​E[(Li​+Qi​−Yi​−ξ)+],

over all feasible YYY.

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 nnn of tokens to evict as an input; here it is the number mmm above (truncated subtraction in N\mathbb NN), the number that makes the output feasible. The hypothesis ξ∈N\xi \in \mathbb Nξ∈N is added because the ranking criterion is the marginal cost only for integer ξ\xiξ (see the marginal-cost identity). The run of the algorithm is a relation, so the lemma holds for every tie-break.

Preamble
import Mathlib
import Definitions.Def_TailOptCaching_ETLRU_Model

open scoped ENNReal
Formal statement
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
Source
Zhang, Li, Moallemi & Peng, Tail-Optimized Caching for LLM Inference, arXiv:2510.15152v1, p. 19, Lemma 1; p. 20, Algorithm 2
Human review
  • Endorsed by Shuze Chen · Oct 22, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 22, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me