pith. sign in

arxiv: 2605.26107 · v1 · pith:LD2IXRUZnew · submitted 2026-05-25 · 🧮 math.PR · cs.PF

Radial Extremality for LRU Caching and the Fill--Holst Conjecture

Christopher D. Long This is my paper

Pith reviewed 2026-06-29 20:17 UTC · model grok-4.3

classification 🧮 math.PR cs.PF
keywords LRU cachehit rateuniform distributionradial derivativeFill-Holst conjecturemove-to-frontstochastic orderindependent reference model
0
0 comments X

The pith

For every LRU cache capacity C, the uniform popularity vector uniquely minimizes the stationary hit rate on the interior simplex, with strict increases along every ray away from it.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that in the independent reference model, the hit rate H_C of an LRU cache of size C is minimized at the uniform popularity distribution among all interior points, and increases strictly when moving away from uniform along any straight-line segment. This is shown by deriving an explicit formula for the radial derivative that is always positive away from uniform, using the exponential-age representation of the cache's stationary distribution. The result establishes the radial restriction of the Fill-Holst conjecture, which concerns stochastic ordering of search costs under the move-to-front rule. Consequently, miss probabilities and nondecreasing stack-depth costs decrease strictly along such rays. The argument is specific to radial directions and does not claim full majorization monotonicity, which is already known to fail.

Core claim

For the independent reference model with popularity vector p in the interior of the simplex, the LRU hit rate H_C(p) for capacity C satisfies that the uniform vector is its unique global minimizer, and H_C increases strictly along every nonconstant line segment from the uniform vector to any other interior point. The proof supplies an explicit positive pair-square expression for the radial derivative. Equivalently, the stationary search-cost distribution under move-to-front improves strictly in stochastic order along every such ray, so all miss probabilities and all nonconstant nondecreasing stack-depth costs decrease strictly.

What carries the argument

The radial derivative of H_C, expressed via a positive pair-square formula obtained from the exponential-age representation of the LRU stationary distribution.

If this is right

  • Miss probabilities for LRU decrease strictly along every nonconstant ray from the uniform vector.
  • All nonconstant nondecreasing stack-depth costs decrease strictly along such rays.
  • The stationary search-cost distribution for move-to-front improves in the usual stochastic order along every such ray.
  • The radial restriction of the Fill-Holst Schur-concavity conjecture holds for move-to-front search-cost tails.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The radial positivity may be useful for analyzing performance under small perturbations of access patterns in systems that approximate uniform traffic.
  • Numerical verification of the derivative sign on sample rays could provide an independent check of the pair-square formula.
  • The same radial argument might adapt to other replacement policies whose stationary distributions admit similar age representations.

Load-bearing premise

The stationary distribution of the LRU cache admits the standard exponential-age representation that yields an explicit formula for the radial derivative.

What would settle it

A concrete popularity vector p and capacity C together with a point q on the ray from uniform through p such that the numerical hit rate at q is smaller than at p.

read the original abstract

For the independent reference model with popularity vector $p\in\Delta_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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 0 minor

Summary. The paper proves that, in the independent reference model with popularity vector p in the interior of the simplex, the LRU hit rate H_C(p) for cache size C (1 ≤ C < N) is uniquely minimized at the uniform vector. Along every non-constant ray emanating from the uniform vector, H_C increases strictly. The argument invokes the standard exponential-age representation of the LRU stationary distribution to produce an explicit positive pair-square formula for the radial derivative of H_C. Equivalently, the result establishes the radial restriction of the Fill–Holst conjecture on stochastic ordering of move-to-front search-cost tails (hence monotonicity of all LRU miss probabilities and nondecreasing stack-depth costs along such rays). The paper notes that full majorization monotonicity fails for LRU and isolates the positivity that survives on rays from uniformity.

Significance. If the derivation is correct, the result is a precise and useful contribution to the theory of caching and stochastic ordering. It supplies an explicit, parameter-free positivity certificate for the radial derivative, thereby confirming the extremal role of uniformity along the only directions where the property can hold. The restriction to rays is correctly acknowledged and the explicit formula strengthens the claim beyond a pure existence argument.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive report, the accurate summary of our results, and the recommendation to accept. The referee's assessment aligns with our view that the explicit radial derivative formula provides a precise confirmation of the extremal role of uniformity along rays.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation begins from the externally standard exponential-age representation of the LRU stationary distribution (an input not defined in terms of the target radial derivative or minimizer claim) and produces an explicit positive pair-square formula for the radial derivative of H_C along rays from uniform. No step reduces a claimed prediction or uniqueness result to a fitted parameter, self-citation chain, or definitional renaming; the central claim is obtained by direct algebraic sign analysis of that formula rather than by construction from the result itself. The paper explicitly notes the radial (not full majorization) scope and the known failure of stronger monotonicity, confirming the argument is not self-referential.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claim rests on the independent reference model and the exponential-age representation of LRU, both standard but external to the derivation.

axioms (2)
  • domain assumption Requests follow the independent reference model with popularity vector p in the open probability simplex.
    Defines the setting in which H_C(p) is defined and the radial derivative is taken.
  • domain assumption The stationary LRU cache state admits the standard exponential-age representation.
    Invoked to obtain the explicit pair-square formula for the radial derivative.

pith-pipeline@v0.9.1-grok · 5744 in / 1233 out tokens · 32371 ms · 2026-06-29T20:17:43.921177+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

12 extracted references · 11 canonical work pages · 1 internal anchor

  1. [1]

    Identity of King and Flajolet & al. Formulae for LRU Miss Rate Exact Computation

    C. Berthet, Identity of King and Flajolet & al. formulae for LRU miss rate exact computation, arXiv:1607.01283, 2016

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  2. [2]

    H. Che, Y. Tung and Z. Wang, Hierarchical Web caching systems: modeling, design and experimental results,IEEE Journal on Selected Areas in Communications20(2002), no. 7, 1305–1314.doi:10.1109/JSAC.2002.801752

    work page doi:10.1109/jsac.2002.801752 2002

  3. [3]

    Fagin, Asymptotic miss ratios over independent references,Journal of Computer and System Sciences14(1977), no

    R. Fagin, Asymptotic miss ratios over independent references,Journal of Computer and System Sciences14(1977), no. 2, 222–250.doi:10.1016/S0022-0000(77)80014-7

    work page doi:10.1016/s0022-0000(77)80014-7 1977

  4. [4]

    Fagin and T

    R. Fagin and T. G. Price, Efficient calculation of expected miss ratios in the independent reference model,SIAM Journal on Computing7(1978), no. 3, 288–297. doi:10.1137/0207025

    work page doi:10.1137/0207025 1978

  5. [5]

    J. A. Fill and L. Holst, On the distribution of search cost for the move-to-front rule,Random Structures & Algorithms8(1996), no. 3, 179–186. doi:10.1002/(SICI)1098-2418(199605)8: 3<179::AID-RSA2>3.0.CO;2-V

    work page doi:10.1002/(sici)1098-2418(199605)8: 1996

  6. [6]

    Flajolet, D

    P. Flajolet, D. Gardy and L. Thimonier, Birthday paradox, coupon collectors, caching algorithms and self-organizing search,Discrete Applied Mathematics39(1992), no. 3, 207–229. doi: 10.1016/0166-218X(92)90177-C 12

    work page doi:10.1016/0166-218x(92)90177-c 1992

  7. [7]

    Hildebrand, On a conjecture of Fill and Holst involving the move-to-front rule and cache faults,Probability in the Engineering and Informational Sciences13(1999), no

    M. Hildebrand, On a conjecture of Fill and Holst involving the move-to-front rule and cache faults,Probability in the Engineering and Informational Sciences13(1999), no. 3, 377–385. doi:10.1017/S0269964899133084

    work page doi:10.1017/s0269964899133084 1999

  8. [8]

    P. R. Jelenkovi´ c, Asymptotic approximation of the move-to-front search cost distribution and least-recently-used caching fault probabilities,The Annals of Applied Probability9(1999), no. 2, 430–464.doi:10.1214/aoap/1029962750

    work page doi:10.1214/aoap/1029962750 1999

  9. [9]

    Frank King III, Analysis of demand paging algorithms, inInformation Processing 71: Proceedings of IFIP Congress 71, Ljubljana, Yugoslavia, North-Holland, Amsterdam, 1972, pp

    W. Frank King III, Analysis of demand paging algorithms, inInformation Processing 71: Proceedings of IFIP Congress 71, Ljubljana, Yugoslavia, North-Holland, Amsterdam, 1972, pp. 485–490

    1972

  10. [10]

    A. M. Makowski and S. Vanichpun, Comparing locality of reference—some folk theorems for the miss rate and the output of caches, inPerformance Evaluation and Planning Methods for the Next Generation Internet, A. Girard, B. Sans` o and F. J. V´ azquez-Abad (eds.), Springer, Boston, MA, 2005, pp. 333–365.doi:10.1007/0-387-25551-6_13

    work page doi:10.1007/0-387-25551-6_13 2005

  11. [11]

    A. W. Marshall, I. Olkin and B. C. Arnold,Inequalities: Theory of Majorization and Its Applications, second edition, Springer, New York, 2011.doi:10.1007/978-0-387-68276-1

    work page doi:10.1007/978-0-387-68276-1 2011

  12. [12]

    Vanichpun and A

    S. Vanichpun and A. M. Makowski, Comparing strength of locality of reference: popularity, majorization, and some folk theorems, inProceedings of IEEE INFOCOM 2004, vol. 2, Hong Kong, 2004, pp. 838–849.doi:10.1109/INFCOM.2004.1356972 13

    work page doi:10.1109/infcom.2004.1356972 2004