Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

App. B, pp. 17–19 — ET-LRU attains the finite-horizon Bellman optimum from every well-formed belief state

Proved
TailOptCaching.ETLRU.value_etlru_eq_optValue

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

cachingdynamic-programmingoptimal-policyp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Let σ\sigmaσ be any ET-LRU policy (Definition 1, any tie-break). For every horizon MMM, every starting stage kkk and every well-formed post-decision state zzz, the expected total TEL of the next MMM arrivals under σ\sigmaσ equals the finite-horizon value-to-go function of App. B:

VMσ(z)=VM⋆(z).V^\sigma_M(z) = V^\star_M(z).VMσ​(z)=VM⋆​(z).

This is the induction of the proof of Theorem 2: at the last arrival every policy is optimal, and if ET-LRU is optimal from arrival k+1k + 1k+1 on, choosing the myopic minimizer of (8) at arrival kkk loses nothing.

Formalization Note. The state is required to be well formed (in particular 0<λi≤λˉi0 < \lambda_i \le \bar\lambda_i0<λi​≤λˉi​); every state the model reaches is, and planning computations found the claim false from unreachable states with λi>λˉi\lambda_i > \bar\lambda_iλi​>λˉi​.

Preamble
import Mathlib
import Definitions.Def_TailOptCaching_ETLRU_Model

open scoped ENNReal
Formal statement
namespace TailOptCaching.ETLRU

theorem value_etlru_eq_optValue (P : Params) (σ : Policy) (hσ : IsETLRU P σ) (M k : ℕ)
    (z : State) (hz : WellFormed P z) :
    value P σ M k z = optValue P M z := by sorry

end TailOptCaching.ETLRU
Source
Zhang, Li, Moallemi & Peng, Tail-Optimized Caching for LLM Inference, arXiv:2510.15152v1, pp. 17–19, App. B (proof of Theorem 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