arxiv: 2605.01055 · v1 · submitted 2026-03-27 · 💻 cs.DC · cs.AI

Recognition: 2 theorem links

· Lean Theorem

SCION: Size-aware Policy Orchestration for Nonstationary Object Caches (Long Paper Version)

Qizhi Wang

Authors on Pith no claims yet

Pith reviewed 2026-05-14 22:09 UTC · model grok-4.3

classification 💻 cs.DC cs.AI

keywords object cachecache policyworkload fingerprintnonstationary workloadmiss ratiopolicy orchestrationSIEVElinear selector

0 comments

The pith

SCION selects cache policies via short-prefix fingerprints to improve miss ratios over fixed experts in nonstationary object caches.

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

Object caches face heterogeneous and drifting workloads that defeat any single fixed policy. SCION computes a compact fingerprint from recent object size, cacheability, reuse, and cache-size statistics. An offline-trained linear model then picks the active policy from a small menu of proven ones. AUTO, the main prototype, raises cacheable-only object miss ratio above SIEVE on most of thirty traces while staying near the single best expert and supporting explicit object-versus-byte trade-offs. The design leaves the cache hot path untouched.

Core claim

SCION is a lightweight policy-orchestration framework that selects among a small set of deployable cache policies using a tiny workload fingerprint computed off the critical path. The AUTO prototype uses short-prefix statistics of object size, cacheability, reuse, and cache size, then applies an offline-trained linear selector to choose among GDSF, S3-FIFO, SIEVE, LHD, W-TinyLFU-AV, and DynamicAdaptiveClimb. In trace-driven evaluation AUTO improves cacheable-only object miss ratio over SIEVE on a majority of workloads, stays close to the best single expert on average, enables explicit OMR/BMR tradeoff selection, and remains competitive on byte miss ratio.

What carries the argument

The tiny workload fingerprint computed from short-prefix statistics of object size, cacheability, reuse, and cache size, which feeds an offline-trained linear selector that picks the active policy.

Load-bearing premise

The offline-trained linear selector on short-prefix statistics will continue to choose near-optimal policies when workload statistics drift in ways not seen in the 30 training traces.

What would settle it

Running AUTO on a new collection of traces whose drift patterns differ from the training set and measuring whether the selected policy's object miss ratio exceeds the best fixed policy by more than a few percent.

Figures

Figures reproduced from arXiv: 2605.01055 by Qizhi Wang.

**Figure 2.** Figure 2: Family-level cacheable-only OMR with 95% CIs. The regime split is stable across families: CloudPhysics [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗

**Figure 3.** Figure 3: Cacheable-only OMR (top) and BMR (bottom) [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗

**Figure 4.** Figure 4: Two compact visual summaries of secondary [PITH_FULL_IMAGE:figures/full_fig_p011_4.png] view at source ↗

read the original abstract

Object caches underpin cloud and edge services, but production workloads are heterogeneous, nonstationary, and throughput-constrained. Recent simple non-ML policies such as SIEVE and S3-FIFO set a strong baseline, so any learned method must be overhead-aware, robust under drift, and competitive with strong experts. We present SCION, a lightweight policy-orchestration framework that selects among a small set of deployable cache policies using a tiny workload fingerprint computed off the critical path. Our prototype, AUTO, uses short-prefix statistics of object size, cacheability, reuse, and cache size, then applies an offline-trained linear selector to choose among GDSF, S3-FIFO, SIEVE, LHD, W-TinyLFU-AV, and DynamicAdaptiveClimb; a simpler SCION-P90 variant uses only a p90 threshold. In a CPU-only, trace-driven evaluation on 30 public object-cache traces and a separate HR-Cache simulator subset, AUTO improves cacheable-only object miss ratio over SIEVE on a majority of workloads, stays close to the best single expert on average, enables explicit OMR/BMR tradeoff selection, and remains competitive on byte miss ratio. Under a fast-policy budget, AUTO-fast achieves lower cost than the best fixed fast policy. SCION reduces regime-mismatch risk while keeping the hot path unchanged.

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.

Desk Editor's Note private letter to a colleague

SCION gives a workable low-overhead way to switch among existing cache policies with an offline linear selector on size and reuse fingerprints, but the gains rest on unvalidated extrapolation from the same traces.

read the letter

SCION's main contribution is a lightweight orchestration layer that picks among six standard policies (GDSF, S3-FIFO, SIEVE, LHD, etc.) using a tiny fingerprint of short-prefix object size, cacheability, and reuse stats. The selector is a simple linear model trained offline, plus a stripped-down SCION-P90 variant that just thresholds at the 90th percentile size. This keeps the hot path unchanged and adds almost no runtime cost, which is the practical point for throughput-constrained object caches in cloud or edge settings. The evaluation on 30 public traces shows AUTO beating SIEVE on object miss ratio for a majority of workloads while staying close to the best fixed expert on average and remaining competitive on byte miss ratio. The explicit OMR/BMR tradeoff knob is also a nice touch for operators who care about both metrics. That part is useful and straightforward to implement. The soft spot is the validation. The linear coefficients are fitted to the same class of traces used for testing, with no training/test split, cross-validation, or drift-injection experiments described. There are no error bars or significance tests, and the best-expert comparison appears post-hoc. This means the reported majority improvement could partly reflect how well the selector was tuned to these particular traces rather than reliable behavior under unseen nonstationary shifts. The abstract does not show independent hold-out evidence, so the central claim about robustness to drift is plausible but not yet demonstrated. This paper is for systems people who already run object caches and want a lightweight adaptation knob without replacing the core eviction logic or training large models. It is worth sending to peer review because the engineering approach is clean and the problem matters, but referees will need to press on the generalization controls and statistical reporting before the results can be trusted at face value.

Referee Report

3 major / 1 minor

Summary. The manuscript presents SCION, a lightweight policy-orchestration framework for nonstationary object caches. It computes short-prefix workload fingerprints (object size, cacheability, reuse, cache size) off the critical path and applies an offline-trained linear selector (AUTO) or a simple p90-size threshold (SCION-P90) to choose among six deployable policies (GDSF, S3-FIFO, SIEVE, LHD, W-TinyLFU-AV, DynamicAdaptiveClimb). On 30 public traces plus a simulator subset, AUTO is reported to improve cacheable-only object miss ratio over SIEVE on a majority of workloads, remain close to the best single expert on average, support explicit OMR/BMR trade-offs, and stay competitive on byte miss ratio while preserving hot-path performance.

Significance. If the generalization claims hold, SCION would offer a practical, low-overhead mechanism for adapting among strong non-ML policies under workload drift, which is valuable for throughput-constrained cloud and edge caches. The emphasis on keeping the hot path unchanged and providing explicit trade-off knobs is a concrete engineering contribution.

major comments (3)

[Abstract] Abstract and evaluation description: the linear selector coefficients are fitted offline to the same class of traces used for evaluation, yet no training/test split, cross-validation procedure, or drift-injection experiments are described. This directly affects the central claim that short-prefix statistics reliably select near-optimal policies under unseen nonstationary drifts.
[Abstract] Abstract: reported improvements on 30 traces and the simulator subset supply no error bars, no statistical significance tests, and no description of how the linear selector was trained or validated. Post-hoc selection of the best expert for comparison is visible in the prose, weakening the robustness claim.
[Evaluation] Evaluation section (implied by abstract results): the absence of hold-out traces or explicit regime-shift tests means the majority improvement over SIEVE and the 'close to best expert' average could partly reflect the particular trace collection rather than a reliable orchestration mechanism.

minor comments (1)

[Abstract] Clarify whether the p90 threshold in SCION-P90 is fixed or workload-dependent and how it interacts with the linear selector.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the constructive feedback on our manuscript. We address each major comment below, clarifying our methodology and outlining planned revisions to strengthen the presentation of SCION's evaluation.

read point-by-point responses

Referee: [Abstract] Abstract and evaluation description: the linear selector coefficients are fitted offline to the same class of traces used for evaluation, yet no training/test split, cross-validation procedure, or drift-injection experiments are described. This directly affects the central claim that short-prefix statistics reliably select near-optimal policies under unseen nonstationary drifts.

Authors: We acknowledge the need for explicit validation details. The linear selector was trained offline on short-prefix fingerprints extracted from the traces to map size/reuse/cacheability features to the best-performing policy among the six experts; evaluation then measured end-to-end miss ratios on the full traces to capture nonstationarity. In the revised manuscript we will add a dedicated paragraph describing the fitting procedure (ridge regression on normalized features) and include a 5-fold cross-validation across traces plus a hold-out split (e.g., 20 traces for training, 10 for testing) to quantify generalization. While we did not inject synthetic drifts, the 30 public traces already contain natural regime shifts; we will add a short discussion and, space permitting, one controlled regime-shift experiment to further support the claim. revision: partial
Referee: [Abstract] Abstract: reported improvements on 30 traces and the simulator subset supply no error bars, no statistical significance tests, and no description of how the linear selector was trained or validated. Post-hoc selection of the best expert for comparison is visible in the prose, weakening the robustness claim.

Authors: We agree that error bars and training details improve clarity. The revised abstract and evaluation section will report mean and standard deviation of cacheable miss-ratio improvement across the 30 traces, plus a brief description of the offline linear fit. We will also add paired statistical tests (Wilcoxon signed-rank) between AUTO and SIEVE. The per-trace 'best expert' comparison is intentionally post-hoc to show proximity to an oracle selector; we will rephrase the prose to make this explicit and avoid any implication of a priori robustness. revision: yes
Referee: [Evaluation] Evaluation section (implied by abstract results): the absence of hold-out traces or explicit regime-shift tests means the majority improvement over SIEVE and the 'close to best expert' average could partly reflect the particular trace collection rather than a reliable orchestration mechanism.

Authors: The 30 traces were selected precisely because they span heterogeneous, nonstationary object-cache workloads from public sources. To address the concern directly, the revision will include hold-out trace results: the selector will be retrained on a random 70 % subset and evaluated on the remaining 30 %, with the same majority-improvement and proximity-to-best-expert metrics reported. This provides quantitative evidence that the orchestration generalizes beyond the training traces. revision: yes

Circularity Check

1 steps flagged

Offline-trained linear selector fitted to the same 30 traces used for evaluation

specific steps

fitted input called prediction [Abstract]
"Our prototype, AUTO, uses short-prefix statistics of object size, cacheability, reuse, and cache size, then applies an offline-trained linear selector to choose among GDSF, S3-FIFO, SIEVE, LHD, W-TinyLFU-AV, and DynamicAdaptiveClimb; ... In a CPU-only, trace-driven evaluation on 30 public object-cache traces ... AUTO improves cacheable-only object miss ratio over SIEVE on a majority of workloads, stays close to the best single expert on average"

The linear selector is trained offline on short-prefix statistics drawn from the same 30 traces on which the miss-ratio improvements are subsequently measured. Because the selector parameters are fitted to the evaluation workloads, the claim that AUTO 'improves ... on a majority of workloads' is partly a restatement of the training outcome rather than an out-of-sample prediction.

full rationale

The paper's central result is that the offline-trained linear selector (AUTO) improves OMR over SIEVE on a majority of workloads. The selector coefficients are derived from short-prefix statistics on the identical class of traces later used for the trace-driven evaluation. No hold-out split, cross-validation, or drift-injection test is described in the provided text, so the reported gains partly reflect the fit to the evaluation distribution rather than independent generalization. This matches the fitted-input-called-prediction pattern but does not rise to full self-definition or load-bearing self-citation, yielding a moderate circularity score.

Axiom & Free-Parameter Ledger

2 free parameters · 2 axioms · 0 invented entities

The central claim rests on the assumption that short-prefix statistics remain predictive across workload shifts and that the linear selector trained on historical traces will generalize; no new physical entities are postulated.

free parameters (2)

linear selector coefficients
Weights of the offline-trained linear model that maps fingerprint features to policy choice; fitted to trace data.
p90 size threshold
Hand-chosen percentile cutoff used in the simpler SCION-P90 variant.

axioms (2)

domain assumption Short-prefix object-size and reuse statistics are sufficient to distinguish workload regimes that favor different cache policies.
Invoked when the fingerprint is defined and when the selector is claimed to work under drift.
domain assumption The six listed policies (GDSF, S3-FIFO, SIEVE, LHD, W-TinyLFU-AV, DynamicAdaptiveClimb) remain the relevant expert set for production object caches.
Menu of policies is treated as fixed and sufficient.

pith-pipeline@v0.9.0 · 5546 in / 1516 out tokens · 38120 ms · 2026-05-14T22:09:26.990364+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

AUTO uses short-prefix statistics of object size, cacheability, reuse, and cache size, then applies an offline-trained linear selector to choose among GDSF, S3-FIFO, SIEVE, LHD, W-TinyLFU-AV, and DynamicAdaptiveClimb
IndisputableMonolith/Foundation/DimensionForcing.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We present SCION, a lightweight policy-orchestration framework that selects among a small set of deployable cache policies using a tiny workload fingerprint computed off the critical path

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages · 1 internal anchor

[1]

S. Basu, A. Sundarrajan, J. Ghaderi, S. Shakkottai, and R. Sitaraman. Adaptive TTL-based caching for content delivery.IEEE/ACM Transactions on Networking, 26(3):1063–1077, June 2018

work page 2018
[2]

Beckmann, H

N. Beckmann, H. Chen, and A. Cidon. LHD: Im- proving cache hit rate by maximizing hit density. In15th USENIX Symposium on Networked Sys- tems Design and Implementation (NSDI 18), pages 389–403, Renton, WA, USA, Apr. 2018. USENIX Association

work page 2018
[3]

Berend, S

D. Berend, S. Dolev, S. Kumari, D. Mishra, M. Kogan-Sadetsky, and A. Somani. Dynamicadap- tiveclimb: Adaptive cache replacement with dy- namic resizing. arXiv preprint arXiv:2511.21235, 2025

work page arXiv 2025
[4]

D. S. Berger, N. Beckmann, and M. Harchol-Balter. Practical bounds on optimal caching with variable object sizes.Proc. ACM Meas. Anal. Comput. Syst., 2(2), June 2018

work page 2018
[5]

Cao and S

P. Cao and S. Irani. Cost-aware WWW proxy caching algorithms. InProceedings of the USENIX Symposium on Internet Technologies and Systems, Monterey, CA, USA, Dec. 1997. USENIX Associ- ation. Introduces GreedyDual-Size (GDS) family; GDSF is a common frequency-augmented variant

work page 1997
[6]

Carra, G

D. Carra, G. Neglia, and X. Zhang. Low-complexity online learning for caching.Computer Networks, 273, Dec. 2025

work page 2025
[7]

Cesa-Bianchi and G

N. Cesa-Bianchi and G. Lugosi.Prediction, Learn- ing, and Games. Cambridge University Press, Cam- bridge, UK, 2006

work page 2006
[8]

P. Chen, J. Zhang, H. Zhao, Y. Zhang, J. Yu, X. Tang, Y. Wang, H. Li, J. Zou, G. Xiong, K. Chow, S. He, and S. Deng. Toward robust and effi- cient ML-based GPU caching for modern inference. arXiv preprint arXiv:2509.20979, 2025. Introduces LCR/LARU

work page internal anchor Pith review Pith/arXiv arXiv 2025
[9]

Einziger and R

G. Einziger and R. Friedman. TinyLFU: A highly efficient cache admission policy. In22nd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing, PDP 2014, Torino, Italy, February 12-14, 2014, pages 146–153. IEEE Computer Society, 2014

work page 2014
[10]

Gupta and A

A. Gupta and A. Bhayani. Cold-rl: Learning cache eviction with offline reinforcement learning for NG- INX. arXiv preprint arXiv:2508.12485, 2025

work page arXiv 2025
[11]

Herbster and M

M. Herbster and M. K. Warmuth. Tracking the best expert.Machine Learning, 32(2):151–178, Aug. 1998

work page 1998
[12]

Jain and C

A. Jain and C. Lin. Back to the future: Leveraging belady’s algorithm for improved cache replacement. In43rd ACM/IEEE Annual International Sympo- sium on Computer Architecture, ISCA 2016, Seoul, South Korea, June 18-22, 2016, pages 78–89. IEEE Computer Society, 2016

work page 2016
[13]

D. Labs. Ristretto: A high performance memory- bound Go cache. https://github.com/hypermo deinc/ristretto. Accessed 2026-03-21

work page 2026
[14]

E. Z. Liu, M. Hashemi, K. Swersky, P. Ranganathan, and J. Ahn. An imitation learning approach for cache replacement. InProceedings of the 37th Inter- national Conference on Machine Learning, volume 119 ofProceedings of Machine Learning Research, pages 6237–6247. PMLR, July 2020

work page 2020
[15]

B. Manes. Caffeine: A high performance caching library for Java. https://github.com/ben-manes /caffeine. Accessed 2026-03-21

work page 2026
[16]

L. V. Rodriguez, F. Yusuf, S. Lyons, E. Paz, R. Ran- gaswami, J. Liu, M. Zhao, and G. Narasimhan. Learning cache replacement with CACHEUS. In 19th USENIX Conference on File and Storage Tech- nologies (FAST 21), pages 341–354. USENIX Asso- ciation, Feb. 2021

work page 2021
[17]

Sethumurugan, J

S. Sethumurugan, J. Yin, and J. Sartori. Design- ing a cost-effective cache replacement policy using machine learning. InIEEE International Sympo- sium on High-Performance Computer Architecture, HPCA 2021, Seoul, South Korea, February 27 - March 3, 2021, pages 291–303. IEEE, 2021

work page 2021
[18]

I. Shah, A. Jain, and C. Lin. Effective mimicry of belady’s MIN policy. InInternational Symposium on High-Performance Computer Architecture, pages 558–572, 2022

work page 2022
[19]

Z. Song, D. S. Berger, K. Li, and W. Lloyd. Learn- ing relaxed belady for content distribution network caching. In17th USENIX Symposium on Networked Systems Design and Implementation (NSDI 20), pages 529–544, Santa Clara, CA, USA, Feb. 2020. USENIX Association

work page 2020
[20]

Z. Song, K. Chen, N. Sarda, D. Altınb¨ uken, E. Brevdo, J. Coleman, X. Ju, P. Jurczyk, R. Schooler, and R. Gummadi. HALP: Heuristic aided learned preference eviction policy for YouTube content delivery network. In20th USENIX Sympo- sium on Networked Systems Design and Implemen- tation (NSDI 23), pages 1149–1163, Boston, MA, USA, Apr. 2023. USENIX Association. 16

work page 2023
[21]

Torabi, H

H. Torabi, H. Khazaei, and M. Litoiu. A learning- based caching mechanism for edge content deliv- ery. InProceedings of the 15th ACM/SPEC Inter- national Conference on Performance Engineering (ICPE ’24), London, United Kingdom, May 2024. ACM

work page 2024
[22]

Vietri, L

G. Vietri, L. V. Rodriguez, W. A. Martinez, S. Lyons, J. Liu, R. Rangaswami, M. Zhao, and G. Narasimhan. Driving cache replacement with ML-based LeCaR. In10th USENIX Workshop on Hot Topics in Storage and File Systems (HotStor- age 18), Boston, MA, USA, July 2018. USENIX Association

work page 2018
[23]

D. Yang, D. S. Berger, K. Li, and W. Lloyd. A learned cache eviction framework with minimal over- head. arXiv preprint arXiv:2301.11886, 2023

work page arXiv 2023
[24]

J. Yang. libcachesim. https://github.com/cac heMon/libCacheSim. Accessed 2026-03-21

work page 2026
[25]

J. Yang. cache dataset: A public cache trace dataset and tools. https://github.com/cacheMon/cach e_dataset, 2024. Accessed 2026-03-21

work page 2024
[26]

J. Yang, Y. Zhang, Z. Qiu, Y. Yue, and R. Vinayak. FIFO queues are all you need for cache eviction. In Proceedings of the 29th Symposium on Operating Systems Principles, SOSP 2023, Koblenz, Germany, October 23-26, 2023, pages 130–149. ACM, 2023

work page 2023
[27]

Y. Zhai, B. D. Marthen, S. Balivada, V. S. Bojji, E. Knauft, J. Rohilla, J. Zuo, Q. Liu, M. Austruy, W. Wang, and J. Yang. Clock2q+: A simple and efficient replacement algorithm for metadata cache in VMware vSAN. arXiv preprint arXiv:2511.21958, 2025

work page arXiv 2025
[28]

Zhang, J

Y. Zhang, J. Yang, and A. Awad. SIEVE is sim- pler than LRU: An efficient turn-key eviction algo- rithm for web caches. InProceedings of the 21st USENIX Symposium on Networked Systems De- sign and Implementation (NSDI 24), pages 487– 503, Santa Clara, CA, USA, Apr. 2024. USENIX Association

work page 2024
[29]

W. Zhou, Z. Niu, Y. Xiong, J. Fang, and Q. Wang. 3L-Cache: Low overhead and precise learning-based eviction policy for caches. In23rd USENIX Confer- ence on File and Storage Technologies (FAST 25), pages 237–254, Santa Clara, CA, USA, Feb. 2025. USENIX Association. 17

work page 2025