REVIEW 3 major objections 5 minor 29 references
Cache Management for Mixture-of-Experts LLMs -- extended version
T0 review · 3 major / 5 minor · reviewed 2026-08-05 · deepseek-v4-flash
Pith's one-line read Layer-aware cache rule beats LRU by 15% on MoE LLMs
desk verdict Layered paging is a clean new model for MoE expert caching, with reasonable lower bounds and a promising heuristic, but the real-trace evidence rests on an unvalidated preprocessing reorder that deserves scrutiny. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The paper's central object is the layered-paging model: pages are partitioned into ell layers of n experts each, a round is a block of ell requests with one request from each layer, and a cache of size k must serve an online request sequence. The algorithmic mechanism is LLRU, defined by two quantities for a cached page p at time t: the last-round index R(p,t), which is the number of rounds since p was last requested, and the relative layer distance D(p,t), which is how many future requests must occur before p's layer is visited again. On a miss, LLRU evicts the page with largest R, then largest D. The theoretical lower-bound machinery is a reduction from layered paging to the parallel coupo
What would settle it
Run the same LLRU and LRU policies on a real Mixtral or Llama-MoE inference engine using the engine's native per-token expert schedule (e.g., both experts of layer 1 before both experts of layer 2), and compare cache misses and latency. If LLRU no longer beats LRU-Dist under that order, the paper's central practical claim is refuted for deployed workloads.
Extended reading notes
Core claim
The central discovery is a new adversarial model and a matching algorithm. Layered paging generalizes standard paging by fixing ell layers and requiring every round to request one page from each layer. The paper proves two lower bounds: any deterministic algorithm has competitive ratio at least k - ell + 1, and LRU itself remains k-competitive, so the deterministic worst-case picture is essentially the same as classic paging, only slightly improved by the layer count. For randomized algorithms, using a parallel-coupon-collector bound, every randomized policy has competitive ratio at least max(H_n, log(ell)/(6n)); if the number of experts per layer or the number of layers is constant, this is
Load-bearing premise
The load-bearing assumption is that each round requests exactly one expert per layer in a fixed layer order; real MoE models activate several experts per layer, and the paper converts those traces by reordering requests, so the gains LLRU shows may depend on the converted order rather than on the order an actual inference engine encounters.
Editorial extensions
If this is right
- No deterministic layered-paging policy can be more than a factor of roughly k - ell + 1 from the optimal offline policy; LRU already attains k, so for worst-case analysis the layer structure only shaves ell - 1 off the classic bound.
- If the number of experts per layer or the number of layers is bounded, every randomized policy has an Omega(log k) competitive ratio; the paper leaves open whether any randomized algorithm actually reaches that bound.
- Splitting the cache into fixed per-layer partitions, as LRU-Dist and Opt-Dist do, is unbounded in the worst case and measurably worse on the tested traces, so shared caches should be preferred over static partitioning.
- LLRU translates layer structure directly into eviction priority and, on the tested MoE workloads, makes fewer faults than LRU, Marking, and partitioned variants, with a small gap to the offline optimum.
- The worst-case results show that the new model does not create a fundamentally easier online problem than ordinary paging, so improvements must come from exploiting structure beyond simple recency.
- The paper validates the model by comparing policies on traces from two MoE LLMs and on heavy-tailed synthetic requests: LLRU delivers the fewest faults among online policies on real traces and remains close to the offline optimum.
Reading between the lines
- The authors convert multi-expert-per-layer traces by grouping same-index experts across layers; an implementation that preserves the native per-token order (both experts of layer 1, then layer 2) might change which pages LLRU protects, so the reported gains should be re-checked on an end-to-end inference engine.
- The same two-dimensional eviction rule (round age first, layer distance second) could be applied to other structured cache streams, such as attention KV-caches or pipelined inference stages, though that extension is not in the paper.
- LLRU's protection of soon-to-be-requested layers suggests a testable design rule: when request streams move in fixed cyclic phases, eviction should rank by phase age before global recency.
- The randomized lower bound relies on a uniform random request distribution; non-uniform expert routing in real deployments may make the bound either conservative or insufficient, so the worst-case result is best read as a limit on fully general algorithms rather than on predictable workloads.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces ℓ-layered paging, a competitive-analysis model of expert-weight caching in MoE LLMs. In each round one page from each of ℓ layers is requested, generalizing standard paging. The authors prove lower bounds for deterministic and randomized algorithms (§3), including a lower bound of k−ℓ+1 for all deterministic algorithms and a randomized lower bound max(H_n, log(ℓ)/(6n)). They propose LLRU, an LRU variant that evicts pages with the largest last-round index and tie-breaking by relative layer distance (§4), and evaluate it on synthetic Zipf data and traces from Mixtral and Llama-MoE (§5). The experiments claim LLRU significantly outperforms LRU and LRU-Dist, with roughly 15% fewer faults on Llama traces and 4-5% on Mixtral traces.
Significance. If the proofs hold, the paper makes a useful theoretical contribution: it adapts the classical paging framework to the layered structure of MoE inference and demonstrates that layer-oblivious LRU can be k-competitive but not better, while randomized algorithms are subject to a logarithmic lower bound under constant n or ℓ. The model is clean, LLRU has no tunable hyperparameters, and the artifact is publicly available. The empirical setup, however, rests on a reordering of real traces that may not correspond to deployed inference order, and the main randomized lower-bound proof contains a load-bearing inequality error. With those fixed, the work would be a solid contribution to online caching and LLM systems.
major comments (3)
- [§3.2 (Theorem 4)] The proof's key step for OPT is invalid as written. After partitioning σ into minimal blocks containing k+1 distinct pages, the text states that 'Opt must suffer at least one cache miss per block' and then concludes E(Opt(σ)) ≤ |σ|/(ℓ E(T(n,ℓ))). The premise gives a lower bound on Opt, not the upper bound needed to lower-bound the ratio. A correct argument would need to show that a Belady-type offline algorithm incurs at most one miss per block (after an O(k) warm-up) and that blocks are independent enough for the expectation; neither is supplied. This inequality is load-bearing for the claimed randomized lower bound max(H_n, log(ℓ)/(6n)).
- [§3.1 (Theorem 2)] The proof sketch is incomplete. It assumes A begins each round with exactly one page missing from its k-slot cache; no argument handles the initial filling or ensures the adversary can maintain this invariant while respecting the layer-aligned round structure. The counting for Opt is also not justified: 'There are ℓ pages requested during round i, so at most k pages requested between rounds i and i+k−ℓ, included' is dimensionally off (that interval contains ℓ(k−ℓ+1) requests). The lower bound k−ℓ+1 therefore needs a complete proof; as it stands, the deterministic lower bound is not established.
- [§5.1/§5.2] The trace conversion changes the request order that LLRU sees. For a token with r experts per layer, real autoregressive inference requests layer 1's r experts, then layer 2's r experts, etc., whereas the paper converts each token into r rounds by grouping all first experts across layers, then all second experts. This is not the order a deployed cache would observe, and LLRU's eviction rule (Definition 2) is sensitive to last-round indices and layer distances, so the reported gains over LRU/LRU-Dist (Figs. 4-5, e.g., ~15% on Llama) may be an artifact of the transformation. Since no experiments are run on the original interleaving and no sensitivity analysis is reported, the practical claim 'LLRU significantly outperforms other policies' is not established for the real system.
minor comments (5)
- [§5.2] 'LLRU-Dist' is mentioned ('~7% less than LLRU-Dist') but never defined; likely LRU-Dist. Please correct.
- [Figure 4] The meaning of the vertical line labeled 'Cache size=num experts' is unclear; specify which experiment it marks.
- [Definition 2] R(p,t) uses integer division by ℓ; clarify whether it counts completed rounds before the current one and give the range of D(p,t).
- [§3.2 (Theorem 5 derivation)] The typeset fraction in the derivation after Theorem 5 is garbled ('2(1 + N/N−1)'); please re-check the algebra and formatting.
- [Conclusion] The conclusion mentions 'Large Language Systems' — should be 'Large Language Models'.
Circularity Check
No significant circularity: theoretical lower bounds are first-principles and LLRU evaluation, though depending on a simplifying trace transformation, is not a reduction of a prediction to fitted input.
full rationale
The paper's derivation chain is self-contained. The lower bounds in Section 3 are derived from first principles: deterministic bounds use explicit adversarial constructions (Theorems 1–3), and the randomized bound (Theorem 4) uses Yao's principle plus a parallel coupon-collector lower bound (Theorem 5) that the paper proves directly. No parameter is fitted to the data being predicted, and no 'prediction' is a relabeled fitted value. LLRU (Section 4) is a parameter-free deterministic policy; its experimental advantage is measured against real MoE traces and an optimal offline benchmark, not against a subset used to tune the algorithm. The only self-citations are the artifact pointer [25] and a related-work paper [6] used to justify Zipf-distributed synthetic workloads; neither is load-bearing, and neither smuggles in a uniqueness theorem or ansatz. The main validity caveat is the trace transformation in Section 5.1: real traces with 2–4 experts per layer are reordered into single-expert rounds, altering the interleaving that LLRU exploits. This is a legitimate external-validity concern, and the authors themselves acknowledge the single-expert simplification as a limitation in Section 6, but it is not circular. Nothing in the experiments is defined in terms of the transformation, and no equation reduces to an input by construction. The theoretical results and the algorithmic definition stand independently of the empirical comparison.
Assumptions & free parameters
free parameters (2)
- Zipf exponent a =
varied in Figure 6b; unspecified for Figures 4-5
- Zipf shift b =
not reported
assumptions (6)
- standard math Belady's rule (evict page requested furthest in the future) is optimal offline.
- standard math Yao's principle allows lower-bounding randomized competitive ratio by the best deterministic algorithm on a distribution.
- domain assumption The time until all nℓ pages are seen in an i.i.d. roundwise sequence equals the parallel coupon collector cover time T(n,ℓ).
- domain assumption MoE inference can be modeled as one expert per layer per round in fixed layer order.
- domain assumption Zipf-distributed request frequencies model real cache workloads.
- domain assumption All experts produce data of the same size (uniform page weights).
Cite this review
Pith. "Pith review of Cache Management for Mixture-of-Experts LLMs -- extended version." pith.science (2026). https://pith.science/paper/JUCIS72W
@misc{pith2026250902408,
author = {Pith},
title = {Pith review of: Cache Management for Mixture-of-Experts LLMs -- extended version},
year = {2026},
howpublished = {\url{https://pith.science/paper/JUCIS72W}},
note = {Machine review of arXiv:2509.02408}
}
read the original abstract
Large language models (LLMs) have demonstrated remarkable capabilities across a variety of tasks. One of the main challenges towards the successful deployment of LLMs is memory management, since they typically involve billions of parameters. To this end, architectures based on Mixture-of-Experts have been proposed, which aim to reduce the size of the parameters that are activated when producing a token. This raises the equally critical issue of efficiently managing the limited cache of the system, in that frequently used experts should be stored in the fast cache rather than in the slower secondary memory. In this work, we introduce and study a new paging problem that models expert management optimization. Our formulation captures both the layered architecture of LLMs and the requirement that experts are cached efficiently. We first present lower bounds on the competitive ratio of both deterministic and randomized algorithms, which show that under mild assumptions, LRU-like policies have good theoretical competitive performance. We then propose a layer-based extension of LRU that is tailored to the problem at hand. Extensive simulations on both synthetic datasets and actual traces of MoE usage show that our algorithm outperforms policies for the classic paging problem, such as the standard LRU.
Figures
Figures from the paper (3 more)
Reference graph
Works this paper leans on
-
[1]
In: Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)
Agrawal, K., Archaya, P., Lee, J., Srikant, R.: Green paging: Algorithms for energy- efficient caching. In: Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). pp. 169–178. ACM (2011)
work page 2011
-
[2]
In: ACM Symposium on Parallelism in Algo- rithms and Architectures (SPAA)
Agrawal, K., Bender, M.A., Das, R., Kuszmaul, W., Peserico, E., Scquizzato, M.: Green paging and parallel paging. In: ACM Symposium on Parallelism in Algo- rithms and Architectures (SPAA). pp. 493–495 (2020)
work page 2020
- [3]
-
[4]
Springer Science & Business Media (1993)
Blom, G., Holst, L., Sandell, D.: Problems and Snapshots from the World of Prob- ability. Springer Science & Business Media (1993)
work page 1993
-
[5]
Cam- bridge University Press, New York, NY, USA (1998)
Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cam- bridge University Press, New York, NY, USA (1998)
work page 1998
-
[6]
In: International Conference on Parallel Processing
Canon, L.C., Dugois, A., Marchal, L., Rivière, E.: Hector: A framework to design and evaluate scheduling strategies in persistent key-value stores. In: International Conference on Parallel Processing. pp. 535–545. ICPP ’23 (2023)
work page 2023
-
[7]
SIAM Journal on Computing20(5), 1052–1067 (1991)
Chrobak, M., Karlin, A.R., Phillips, C.A., Raghavan, P., Rosen, J.S.: New results on weighted paging. SIAM Journal on Computing20(5), 1052–1067 (1991)
work page 1991
-
[8]
The- oretical Computer Science324(2-3), 179–197 (2004)
Chrobak, M., Noga, J., Young, N.E.: Online hierarchical cooperative caching. The- oretical Computer Science324(2-3), 179–197 (2004)
work page 2004
Show all 29 references
-
[9]
In: International Conference on Machine Learning
Du, N., Huang, Y., Dai, A.M., Tong, S., Lepikhin, D., Xu, Y., Krikun, M., Zhou, Y., Yu, A.W., Firat, O., et al.: Glam: Efficient scaling of language models with mixture-of-experts. In: International Conference on Machine Learning. pp. 5547– 5569 (2022)
2022
-
[10]
Eliseev, A., Mazur, D.: Fast inference of mixture-of-experts language models with offloading (2023), https://arxiv.org/abs/2312.17238
2023 arXiv
-
[11]
Face, H.: Helpful instructions dataset, https://huggingface.co/datasets/ HuggingFaceH4/helpful-instructions
-
[12]
Ferrante, M., Tagliavini, A.: On the coupon-collector’s problem with several par- allel collections (2016),https://arxiv.org/abs/1609.04174
2016 arXiv
-
[13]
Journal of Algorithms12(4), 685–699 (1991) Cache Management for Mixture-of-Experts LLMs – extended version 17
Fiat, A., Karp, R.M., Luby, M., McGeoch, L.A., Sleator, D.D., Young, N.E.: Com- petitive paging algorithms. Journal of Algorithms12(4), 685–699 (1991) Cache Management for Mixture-of-Experts LLMs – extended version 17
1991
-
[14]
Journal of Machine Learning Research22(241), 1–124 (2021)
Hoefler, T., Alistarh, D., Ben-Nun, T., Dryden, N., Peste, A.: Sparsity in deep learning:Pruningandgrowthforefficientinferenceandtraininginneuralnetworks. Journal of Machine Learning Research22(241), 1–124 (2021)
2021
-
[15]
2401.04088
Jiang, A.Q., Sablayrolles, A., Roux, A., Mensch, A., Savary, B., Bamford, C., Chaplot, D.S., de las Casas, D., Hanna, E.B., Bressand, F., Lengyel, G., Bour, G., Lample, G., Lavaud, L.R., Saulnier, L., Lachaux, M.A., Stock, P., Subramanian, S., Yang, S., Antoniak, S., Scao, T.L...
-
[16]
In: Proceedings of the thirty-second annual ACM symposium on Theory of computing
Karlin, A.R., Kenyon, C., Randall, D.: Combining request scheduling with web caching. In: Proceedings of the thirty-second annual ACM symposium on Theory of computing. pp. 654–663. ACM (2000)
2000
-
[17]
In: Roughgarden, T
Karlin, A.R., Koutsoupias, E.: Beyond competitive analysis of online algorithms. In: Roughgarden, T. (ed.) Beyond the Worst-Case Analysis of Algorithms, pp. 373–416. Cambridge University Press (2020)
2020
-
[18]
In: 9th workshop on MEmory performance: DEaling with Applications, systems and architecture
Kotera, I., Egawa, R., Takizawa, H., Kobayashi, H.: Modeling of cache access be- havior based on Zipf’s law. In: 9th workshop on MEmory performance: DEaling with Applications, systems and architecture. pp. 9–15. MEDEA ’08 (2008)
2008
-
[19]
arXiv preprint arXiv:2412.19442 (2024)
Li, H., Li, Y., Tian, A., Tang, T., Xu, Z., Chen, X., Hu, N., Dong, W., Li, Q., Chen, L.: A survey on large language model acceleration based on kv cache management. arXiv preprint arXiv:2412.19442 (2024)
2024 arXiv
-
[20]
In: Dy, J.G., Krause, A
Lykouris, T., Vassilvitskii, S.: Competitive caching with machine learned advice. In: Dy, J.G., Krause, A. (eds.) International Conference on Machine Learning, (ICML). vol. 80, pp. 3302–3311 (2018)
2018
-
[21]
Journal of Algorithms11(2), 208–230 (Jun 1990)
Manasse, M.S., McGeoch, L.A., Sleator, D.D.: Competitive algorithms for server problems. Journal of Algorithms11(2), 208–230 (Jun 1990)
1990
-
[22]
Minaee, S., Mikolov, T., Nikzad, N., Chenaghlu, M., Socher, R., Amatriain, X., Gao, J.: Large language models: A survey (2024),https://arxiv.org/abs/2402. 06196
2024
-
[23]
Cambridge University Press (1995)
Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press (1995)
1995
-
[24]
Nagel, M., Fournarakis, M., Amjad, R.A., Bondarenko, Y., van Baalen, M., Blankevoort, T.: A white paper on neural network quantization (2021),https: //arxiv.org/abs/2106.08295
2021 arXiv
-
[25]
Simon, B., Marchal, L., Angelopoulos, S., Obrecht, A.: Artifact of the paper: Cache management for mixture-of-experts llms (Jun 2025).https://doi.org/10.5281/ zenodo.15576758, https://doi.org/10.5281/zenodo.15576758
2025 doi
-
[26]
Communications of the ACM28(2), 202–208 (1985)
Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Communications of the ACM28(2), 202–208 (1985)
1985
-
[27]
In: Neural Information Processing Systems conference (NeurIPS)
Vaswani,A.,Shazeer,N.,Parmar,N.,Uszkoreit,J.,Jones,L.,Gomez,A.N.,Kaiser, L., Polosukhin, I.: Attention is all you need. In: Neural Information Processing Systems conference (NeurIPS). pp. 5998–6008 (2017)
2017
-
[28]
Algorith- mica 11 (Jun 1994)
Young, N.E.: The K-Server Dual and Loose Competitiveness for Paging. Algorith- mica 11 (Jun 1994)
1994
-
[29]
Zhu, T., Qu, X., Dong, D., Ruan, J., Tong, J., He, C., Cheng, Y.: Llama-moe: Building mixture-of-experts from llama with continual pre-training (2024),https: //arxiv.org/abs/2406.16554
2024 arXiv
Reviewed August 5, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.