Pith. sign in

REVIEW 2 major objections 4 minor 37 references

Stochastic Caching via Subset Entropy

T0 review · 2 major / 4 minor · reviewed 2026-07-11 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Subset entropy H of the request distribution sets the competitive ratio of stochastic caching: O(H) for Top-k and LFU, O(H^3) for LRU.

desk verdict Clean, well-proved refinement of stochastic caching via a new entropy parameter; first o(k) LRU bound under i.i.d., with the usual i.i.d. and non-matching-lower-bound caveats. read the letter →

arxiv 2607.03947 v1 pith:S7QR23W4 submitted 2026-07-04 cs.DS

Ravi Kumar , Roie Levin , Joseph (Seffi) Naor , Debmalya Panigrahi This is my paper · ORCID
classification cs.DS
keywords onlinealgorithmsstochasticcachingpagingsubsetentropycompetitiveanalysisbeyondworst-caseLRULFU
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Worst-case stochastic analysis of caching recovers the same O(log k) bound that randomized online algorithms achieve on adversarial sequences, because the uniform distribution is the hardest. This paper introduces k-subset entropy H—the maximum Shannon entropy of the distribution conditioned on any subset of size at most the cache size k—and shows that H is the right fine-grained parameter. When requests are i.i.d. from a known distribution D, the natural Top-k policy that permanently caches the k most probable pages is O(H)-competitive against the offline optimum. When D is unknown, the classic LFU rule matches the same O(H) ratio (after a negligible additive burn-in), while LRU is O(H^3)-competitive. Because H is at most log k and is far smaller for any distribution that is not nearly uniform on a large set, the results quantify precisely how much easier caching becomes once the request distribution carries usable structure.

What carries the argument

k-subset entropy H(D,k) = max_{|S|<=k} H(D_S), the highest Shannon entropy obtainable by conditioning D on any set of size at most the cache size; it is used both to upper-bound algorithm cost and, via a carefully zeroed dual solution to the expected knapsack-cover LP, to lower-bound OPT by Omega(p(tail)/H).

What would settle it

Construct an i.i.d. distribution whose measured k-subset entropy is H and whose empirical ratio of LRU (or Top-k) cost to offline OPT exceeds Omega(H^3) (respectively Omega(H)) by a large constant factor on long request sequences.

Watch

Extended reading notes

Core claim

The competitive ratio of stochastic caching is governed by the k-subset entropy H(D,k) of the request distribution: Top-k (known D) and LFU (unknown D) are O(H)-competitive, and LRU is O(H^3)-competitive, against the offline optimum. H equals Theta(log of the size of the largest nearly-uniform subset of size at most k embedded in D), recovering the classical O(log k) bound only for near-uniform distributions and giving strictly better guarantees otherwise.

Load-bearing premise

Every page request is drawn independently from one fixed distribution; any dependence between successive requests or change in the distribution over time would invalidate the stated ratios.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper studies the classical stochastic caching (paging) problem under i.i.d. page requests from a fixed distribution D. It introduces k-subset entropy H = H(D, k), the maximum Shannon entropy of D conditioned on any subset of size at most k, and uses it to give fine-grained competitive-ratio bounds. For known D the natural Top-k algorithm (permanently caching the k highest-probability pages) is shown O(H)-competitive against the offline optimum (Theorem 6 / Lemma 8 via a novel dual-fitting argument that produces a feasible dual for every realization). For unknown D, LFU is also O(H)-competitive (Theorem 18) while the classic LRU algorithm is O(H^3)-competitive (Theorem 9). Supporting characterizations of H (Lemma 5), an efficient exact algorithm for computing it (Appendix E), and a matching-style lower bound of Omega(H p(T)) on LRU cost (Appendix F) are supplied. The broader claim is that entropy-style parameters can refine stochastic analyses of other online problems.

Significance. If the claims hold, the work supplies the first non-trivial beyond-worst-case competitive ratios for the three most common caching policies under i.i.d. inputs, parameterized by a clean information-theoretic quantity that is always at most O(log k) and can be substantially smaller. The dual construction that lower-bounds OPT for every realization, the level-wise coupon-collector analysis of LRU, and the burn-in argument for LFU are technically non-trivial and appear self-contained. The explicit acknowledgment that H need not be tight for every distribution, together with the complete proofs in the appendices, strengthens credibility. The suggested research program of entropy-parameterized stochastic analysis for sorting, matching, load balancing, etc., is plausible and of independent interest to the online-algorithms community.

major comments (2)
  1. Lemma 8 / Appendix B: the dual-zeroing construction correctly produces a feasible dual for every realization and yields the claimed Omega(p(T)/H) lower bound on E[OPT] under the i.i.d. model. The argument is load-bearing for all three main theorems; the only residual gap is that the same dual does not automatically give matching lower bounds for every D (already noted by the authors in footnote 1 and Appendix F). No algebraic error is apparent, but a short remark clarifying that the O(H) factor is an artifact of the uniform-over-levels dual rather than an information-theoretic necessity would help readers.
  2. Section 4 / Theorem 9: the O(H^3) bound for LRU rests on three successive H-factors (one from OPT, two from the level-wise analysis of q_i). Appendix F shows that LRU cost can be Omega(H p(T)), so the analysis is at best a factor-H^2 away from tight. While the paper correctly states the result it proves, a major revision of the LRU section that either removes one H or supplies a matching Omega(H^2) example would make the central claim sharper; the current gap is not fatal but is the weakest quantitative link.
minor comments (4)
  1. Page 1 and Section 1.1: 'Aho, Delling, and Ullman' should be 'Aho, Denning, and Ullman'.
  2. Throughout: inconsistent spacing around math operators (Top- k, O(H 3), etc.) and occasional missing punctuation after display equations.
  3. Section 2.2 / Lemma 5: the factor-revealing LP is elegant; a one-sentence pointer that the dual solution is essentially the truncated harmonic series would aid readability.
  4. Appendix E: the interval property is useful; stating the resulting O(n k) dynamic program explicitly would make the claim self-contained.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: competitive ratios are derived from first-principles dual fitting, concentration, and coupon-collector arguments under the stated i.i.d. model; subset entropy is an independent parameter, not fitted or self-defined from the claimed bounds.

full rationale

The paper defines k-subset entropy (Def. 4) purely information-theoretically as the max Shannon entropy of any conditional distribution on a set of size at most k. Lemma 5 then characterizes it (via a factor-revealing LP dual) as Theta(log min{k, n_max}), where n_max is the size of the largest dyadic probability level; this is independent of any caching algorithm. Theorems 1/6, 2/9 and 3/18 bound the competitive ratios of Top-k, LRU and LFU by O(H), O(H^3) and O(H) respectively. The upper bounds follow from direct expectation calculations (Top-k cost = 2 p(T); LRU cost via level-wise coupon-collector and Poisson-style tail bounds on the number of distinct pages; LFU via a burn-in of O(H) requests per head page). The matching lower bound on OPT is obtained by a dual-fitting construction (Lemma 8 / App. B) that starts from a stationary dual for the expected LP, zeros variables on atypical long intervals (event E(t)), and shows that the expected dual objective remains Omega(p(T)/H). All steps are self-contained probabilistic arguments under the explicit i.i.d. hypothesis; no free parameters are fitted to data, no uniqueness theorem is imported from prior work by the same authors, and no known empirical pattern is merely renamed. The only self-citations are ordinary bibliographic references to classical caching results (Aho et al., Fiat et al., Sleator-Tarjan, etc.). Consequently the derivation chain does not reduce to its inputs by construction.

Assumptions & free parameters 0 free parameters · 4 assumptions · 1 invented entities

The paper rests on standard probabilistic method and LP-duality machinery plus the classical i.i.d. request model. The sole invented object is the subset-entropy parameter itself, which is given an independent combinatorial characterization (Lemma 5) and an efficient algorithm (Appendix E).

assumptions (4)
  • domain assumption Page requests are drawn independently from a fixed discrete distribution D on n pages (Section 2.1).
    All competitive-ratio statements are expectations over this product measure; the dual-fitting and concentration arguments collapse without independence.
  • domain assumption Competitive ratio is the ratio of expected online cost to expected offline OPT cost, both taken over the same distribution D (and algorithm randomness).
    Standard definition in stochastic online algorithms; used throughout Theorems 1–3.
  • standard math Weak duality for the knapsack-cover LP of caching (formulation in Section 3).
    Invoked to convert a feasible dual of expected value Omega(p(T)/H) into a lower bound on OPT.
  • standard math Standard Chernoff, Markov and coupon-collector tail bounds.
    Used for interval-length concentration (Lemma 22) and for the LRU miss-probability analysis (Lemma 12).
invented entities (1)
  • k-subset entropy H(D,k) independent evidence
    purpose: Information-theoretic parameter that upper-bounds the competitive ratio of stochastic caching algorithms.
    Defined as the maximum Shannon entropy of D conditioned on any set of size at most k; shown to equal Theta(log min(k,n_max)) and used as the sole distribution-dependent factor in all three main theorems.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Stochastic Caching via Subset Entropy." pith.science (2026). https://pith.science/paper/S7QR23W4

@misc{pith2026260703947,
  author       = {Pith},
  title        = {Pith review of: Stochastic Caching via Subset Entropy},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/S7QR23W4}},
  note         = {Machine review of arXiv:2607.03947}
}
abstract

A classic approach to beyond worst-case algorithm design is to impose stochastic assumptions on the input. However, a limiting feature of stochastic analyses is that, by the min-max principle, performance on worst-case distributions mirrors that of randomized algorithms on worst-case inputs. In other words, the same shortcoming of worst-case analysis -- its inability to distinguish "easy" and "hard" instances -- reappears as an inability to distinguish "easy" and "hard" distributions. This raises a natural question: Can we characterize "easy" input distributions with useful beyond worst-case bounds? A canonical example is the stochastic caching problem (Aho et al. 1971). When the page requests are drawn i.i.d. from the uniform distribution, the best achievable competitive ratio is $O(\log k)$, matching the performance of the best randomized algorithm on worst-case instances (Fiat et al. 1991). However, when the input distribution has less entropy, intuition suggests that we should be able to do better by exploiting the information provided by the distribution. We formalize this by defining a new information-theoretic parameter called subset entropy which we use to give a fine-grained characterization of the competitive ratio of stochastic caching, including a new analysis for the well-known LRU algorithm on stochastic inputs. While our technical results are for the caching problem, we believe the broader principle -- parameterizing algorithmic performance by an entropy measure of the input -- is of independent interest and might apply to other online/stochastic optimization problems. Indeed, for problems such as (comparison-based) sorting, online matching, load balancing, etc., the hardest stochastic instances involve high-entropy distributions. We hope our work is a step toward a broader theory of fine-grained algorithmic performance for this class of problems.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

37 extracted references · 1 linked inside Pith

  1. [1]

    https://algorithms-with-predictions.github.io/

    Algorithms with predictions ( ALPS ). https://algorithms-with-predictions.github.io/

  2. [2]

    Aho, Peter J

    Alfred V. Aho, Peter J. Denning, and Jeffrey D. Ullman. Principles of optimal page replacement. J. ACM , 18(1):80--93, 1971

    1971

  3. [3]

    Page replacement for general caching problems

    Susanne Albers, Sanjeev Arora, and Sanjeev Khanna. Page replacement for general caching problems. In SODA , pages 31--40, 1999

    1999

  4. [4]

    A primal-dual randomized algorithm for weighted paging

    Nikhil Bansal, Niv Buchbinder, and Joseph Naor. A primal-dual randomized algorithm for weighted paging. J. ACM , 59(4):19, 2012

    2012

  5. [5]

    Randomized competitive algorithms for generalized caching

    Nikhil Bansal, Niv Buchbinder, and Joseph Naor. Randomized competitive algorithms for generalized caching. SICOMP , 41(2):391--414, 2012

    2012

  6. [6]

    Learning-augmented weighted paging

    Nikhil Bansal, Christian Coester, Ravi Kumar, Manish Purohit, and Erik Vee. Learning-augmented weighted paging. In SODA , pages 67--89, 2022

    2022

  7. [7]

    Modeling locality: A probabilistic analysis of LRU and FWF

    Luca Becchetti. Modeling locality: A probabilistic analysis of LRU and FWF . In ESA , pages 98--109, 2004

    2004

  8. [8]

    Laszlo A. Belady. A study of replacement algorithms for a virtual-storage computer. IBM Systems Journal , 5(2):78–101, 1966

    1966

Show all 37 references
  1. [9]

    Online Computation and Competitive Analysis

    Allan Borodin and Ran El - Yaniv. Online Computation and Competitive Analysis . Cambridge U. Press, 1998

    1998

  2. [10]

    Competitive paging with locality of reference

    Allan Borodin, Sandy Irani, Prabhakar Raghavan, and Baruch Schieber. Competitive paging with locality of reference. JCSS , 50(2):244--258, 1995

    1995

  3. [11]

    K-server via multiscale entropic regularization

    S \'e bastien Bubeck, Michael B Cohen, Yin Tat Lee, James R Lee, and Aleksander Madry. K-server via multiscale entropic regularization. In STOC , pages 3--16, 2018

    2018

  4. [12]

    Competitive analysis via regularization

    Niv Buchbinder, Shahar Chen, and Joseph Naor. Competitive analysis via regularization. In SODA , pages 436--444, 2014

    2014

  5. [13]

    The design of competitive online algorithms via a primal--dual approach

    Niv Buchbinder, Joseph Seffi Naor, et al. The design of competitive online algorithms via a primal--dual approach. Foundations and Trends in Theoretical Computer Science , 3(2--3):93--263, 2009

    2009

  6. [14]

    A short note on an inequality between KL and TV

    Cl \'e ment L Canonne. A short note on an inequality between KL and TV . arXiv , 2202.07198, 2022

    2022 arXiv

  7. [15]

    Devanur, Kamal Jain, and Robert D

    Nikhil R. Devanur, Kamal Jain, and Robert D. Kleinberg. Randomized primal-dual analysis of RANKING for online bipartite matching. In SODA , pages 101--107, 2013

    2013

  8. [16]

    Online generalized caching with varying weights and costs

    Guy Even, Moti Medina, and Dror Rawitz. Online generalized caching with varying weights and costs. In SPAA , pages 205--212, 2018

    2018

  9. [17]

    Karp, Michael Luby, Lyle A

    Amos Fiat, Richard M. Karp, Michael Luby, Lyle A. McGeoch, Daniel Dominic Sleator, and Neal E. Young. Competitive paging algorithms. J. ALG , 12(4):685--699, 1991

    1991

  10. [18]

    Franaszek and Terry J

    Peter A. Franaszek and Terry J. Wagner. Some distribution-free aspects of paging algorithm performance. J. ACM , 21(1):31--39, 1974

    1974

  11. [19]

    Elastic caching

    Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, and Debmalya Panigrahi. Elastic caching. In SODA , pages 143--156, 2019

    2019

  12. [20]

    Caching with time windows and delays

    Anupam Gupta, Amit Kumar, and Debmalya Panigrahi. Caching with time windows and delays. SICOMP , 51(4):975--1017, 2022

    2022

  13. [21]

    S. Irani. Randomized weighted caching with two page weights. Algorithmica , 32(4):624--640, 2002

    2002

  14. [22]

    Page replacement with multi-size pages and applications to web caching

    Sandy Irani. Page replacement with multi-size pages and applications to web caching. In STOC , pages 701--710, 1997

    1997

  15. [23]

    Karlin, Steven J

    Anna R. Karlin, Steven J. Phillips, and Prabhakar Raghavan. Markov paging. SICOMP , 30(3):906--922, 2000

    2000

  16. [24]

    Papadimitriou

    Elias Koutsoupias and Christos H. Papadimitriou. Beyond competitive analysis. SICOMP , 30(1):300--317, 2000

    2000

  17. [25]

    Interleaved caching with access graphs

    Ravi Kumar, Manish Purohit, Zoya Svitkina, and Erik Vee. Interleaved caching with access graphs. In SODA , pages 1846--1858, 2020

    2020

  18. [26]

    Phillips, and Nick Reingold

    Carsten Lund, Steven J. Phillips, and Nick Reingold. Paging against a distribution and IP networking. JCSS , 58(1):222--232, 1999

    1999

  19. [27]

    Competitive caching with machine learned advice

    Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. In ICML , pages 3302--3311, 2018

    2018

  20. [28]

    Randomized Algorithms

    Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms . Cambridge U. Press, 1995

    1995

  21. [29]

    New and improved bounds for M arkov paging

    Chirag Pabbaraju and Ali Vakilian. New and improved bounds for M arkov paging. In ICALP , pages 123:1--123:20, 2025

    2025

  22. [30]

    On adequate performance measures for paging

    Konstantinos Panagiotou and Alexander Souza. On adequate performance measures for paging. In STOC , pages 487--496, 2006

    2006

  23. [31]

    Entropy-based bounds for online algorithms

    Gopal Pandurangan and Eli Upfal. Entropy-based bounds for online algorithms. TALG , 3(1):7:1--7:19, 2007

    2007

  24. [32]

    Beyond the Worst-Case Analysis of Algorithms

    Tim Roughgarden, editor. Beyond the Worst-Case Analysis of Algorithms . Cambridge U. Press, 2020

    2020

  25. [33]

    Sleator and Robert E

    Daniel D. Sleator and Robert E. Tarjan. Amortized efficiency of list update and paging rules. C. ACM , 28(2):202--208, 1985

    1985

  26. [34]

    Stochastic Calculus and Financial Applications

    J Michael Steele. Stochastic Calculus and Financial Applications. Vol I . Springer, 2001

    2001

  27. [35]

    Probabilistic computations: Toward a unified measure of complexity (extended abstract)

    Andrew Chi - Chih Yao. Probabilistic computations: Toward a unified measure of complexity (extended abstract). In FOCS , pages 222--227, 1977

    1977

  28. [36]

    Neal E. Young. On-line paging against adversarially biased random inputs. J. ALG , 37(1):218--235, 2000

    2000

  29. [37]

    Neal E. Young. Online paging and caching. In Encyclopedia of Algorithms , pages 1457--1461. Springer, 2016

    2016

Pith tools

Reviewed July 11, 2026 · model on record in the stance chip above.