Radial Extremality for LRU Caching and the Fill--Holst Conjecture
2026-05-25 • Performance
Performance
AI summaryⓘ
The authors study how well a type of cache called LRU (Least Recently Used) performs when storing items with varying popularities. They show that when all items are equally popular, the cache hit rate is at its lowest compared to any other popularity setup. Moving away from uniform popularity always increases the hit rate in a predictable way. Their proof also confirms part of a known conjecture about related search costs in a similar system called move-to-front. This means that certain performance measures consistently improve as item popularity becomes less uniform.
LRU cachestationary hit ratepopularity vectoruniform distributionindependent reference modelmove-to-front rulesearch cost distributionSchur-concavitycache miss probabilitymajorization
Authors
Christopher D. Long
Abstract
For the independent reference model with popularity vector $p\inΔ_N^\circ$, let $H_C(p)$ denote the exact stationary hit rate of an LRU cache of capacity $C$. We prove that, for every $1\le C<N$, the uniform popularity vector is the unique global minimizer of $H_C$ on the interior simplex. More sharply, along every nonconstant segment from the uniform vector to an interior point, the LRU hit rate is strictly increasing. The proof uses the standard exponential-age representation of the stationary LRU cache and gives an explicit positive pair-square formula for the radial derivative. Equivalently, for the move-to-front rule, the stationary search-cost distribution improves strictly in the usual stochastic order along every nonconstant ray away from uniform. This proves the radial restriction of the Fill--Holst Schur-concavity conjecture for move-to-front search-cost tails. In particular, all LRU miss probabilities and all nonconstant nondecreasing stack-depth costs decrease strictly along such rays. The result is radial rather than Schur-convex: full majorization monotonicity for LRU is known to fail, and the proof identifies the special positivity that survives on rays from the uniform vector.