Theorem 2, p. 9 — Expected-Tail-Optimized LRU is an optimal online caching policy for Tail Excess Latency in the stochastic conversation model
ProvedTailOptCaching.ETLRU.theorem_2Theorem 2 (Optimality of Expected-Tail-Optimized LRU). In the stochastic conversation model — conversations born at rate , returning at rates while active, with exponentially distributed lifetimes tracked through belief rates, known prompt-length laws, arbitrary response-length laws, cache capacity and threshold — let be any ET-LRU policy (Definition 1) and let be any caching policy whose decisions always satisfy (9), (10) and the capacity constraint. Then for every number of requests and every well-formed starting belief state ,
where is the Tail Excess Latency of the -th request.
ET-LRU is myopic: it minimizes only the expected TEL of the next turn. The theorem says that, in this model, myopia loses nothing over any horizon. With and homogeneous rates it specializes to the optimality of LRU for average latency.
Formalization Note. Policies are Markov and deterministic: they map the stage, the belief state and the current arrival to a cache vector. The well-formedness hypothesis ( for arrived conversations, , , nothing beyond the arrived conversations) holds for the empty start and for every reachable state; it cannot be dropped, since the claim fails from some states with . The law of the decay factor is generalized to any probability law on depending on the belief rates, which contains the paper's law. Values are in .
import Mathlib import Definitions.Def_TailOptCaching_ETLRU_Model open scoped ENNReal
namespace TailOptCaching.ETLRU
theorem theorem_2 (P : Params) (σ : Policy) (hσ : IsETLRU P σ)
(π : Policy) (hπ : Admissible P π) (M : ℕ) (z : State) (hz : WellFormed P z) :
value P σ M 0 z ≤ value P π M 0 z := by sorry
end TailOptCaching.ETLRU
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.