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

Qizhi Wang

cs.DCMar 27, 2026

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

Authors: Qizhi Wang

Organizations: PingCAP, Data & AI-Innovation Lab Beijing, China

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.

Figures & tables

Figure 1: SCION architecture. A lightweight off-path selector chooses one expert from a small portfolio using a short-prefix workload fingerprint, while the request path remains a single active expert cache with standard hit/miss handling.

Trace	p50	p90	Mean	Cacheable	Unique
Alibaba-0	4.0KiB	420.0KiB	69.9KiB	1.000	0.439
Alibaba-1	4.0KiB	8.0KiB	6.2KiB	1.000	0.159
Alibaba-100	8.0KiB	28.0KiB	12.0KiB	1.000	0.935
Alibaba-103	12.0KiB	72.0KiB	29.5KiB	1.000	0.778
Alibaba-11	8.0KiB	32.0KiB	15.7KiB	1.000	0.680
Alibaba-12	8.0KiB	504.0KiB	89.4KiB	1.000	0.984

Table 1: Prefix trace diagnostics (size percentiles, cacheable and unique ratios). Sizes are in KiB/MiB; a few Twitter clusters include zero-size records in the public traces, which yields 0-sized percentiles and are flagged as degenerate for win-count statistics.

Trace	Cache	AUTO policy	AUTO OMR [CI]	Baseline	Baseline OMR [CI]
CloudPhysics-w02	1GiB	GDSF	0.438 [0.428,0.454]	SIEVE	0.976 [0.971,0.981]
Alibaba-103	256MiB	WTinyLFU-AV	0.768 [0.758,0.784]	GDSF	0.823 [0.814,0.835]
CloudPhysics-w02	128MiB	GDSF	0.979 [0.975,0.984]	WTinyLFU-AV	0.734 [0.714,0.758]

Table 2: Representative per-trace examples with OMR CIs (AUTO vs baseline).

Policy	Avg OMR (95% CI)	Avg BMR (95% CI)
AUTO	0.438240 [0.388795,0.490928]	0.528066 [0.469773,0.586067]
SIEVE	0.479133 [0.423313,0.532635]	0.541692 [0.484306,0.600559]
S3-FIFO	0.468178 [0.413922,0.521532]	0.566012 [0.511392,0.624286]
GDSF	0.432585 [0.381961,0.484499]	0.530435 [0.471803,0.588821]
DynamicAdaptiveClimb	0.470352 [0.415332,0.524424]	0.532683 [0.473753,0.592131]

Table 3: Average cacheable-only miss ratios over all evaluated workloads with 95% bootstrap CIs. Lower is better.

Family	$N$	AUTO	GDSF	S3-FIFO
Block	48	0.448 [0.378,0.514]	0.444 [0.372,0.518]	0.480 [0.410,0.551]
CloudPhysics	16	0.726 [0.643,0.799]	0.696 [0.633,0.758]	0.801 [0.733,0.869]
MSR	12	0.189 [0.110,0.281]	0.189 [0.110,0.277]	0.209 [0.134,0.291]
Meta-CDN	12	0.654 [0.585,0.714]	0.654 [0.585,0.717]	0.704 [0.640,0.766]
Meta-KV	4	0.151 [0.141,0.164]	0.141 [0.141,0.142]	0.151 [0.141,0.165]
Twitter	24	0.236 [0.137,0.330]	0.235 [0.153,0.325]	0.235 [0.148,0.333]

Table 4: Family-level cacheable-only OMR summary (95% CIs).

Figure 2: Family-level cacheable-only OMR with 95% CIs. The regime split is stable across families: CloudPhysics favors GDSF, Wiki favors AUTO, and FIFO-family policies trail on the large-object families.

Baseline	Improve%	Avg $\Delta$	Best $\Delta$	Worst $\Delta$
GDSF	13.3	0.0057	-0.2030	0.1402
S3-FIFO	65.8	-0.0299	-0.5426	0.0841

Table 5: Key aggregate gains vs strong baselines on cacheable-only OMR (delta = AUTO – baseline).

Policy	Avg OMR $\downarrow$	Avg BMR $\downarrow$	N
ARC	0.382226	0.448056	12
TwoQ	0.379894	0.472687	12
LIRS	0.422354	0.529858	4

Table 6: Classic baselines on a small HR-Cache subset (cacheable-only averages; 20k-request prefixes for ARC/TwoQ, 5k for LIRS; N shows samples).

Policy	Avg OMR $\downarrow$	Avg BMR $\downarrow$	N
AUTO	0.513082	0.496279	40
AUTO ( $\alpha=0.2$ )	0.520135	0.465623	40
GDSF	0.510144	0.507296	40
LeCaR	0.504318	0.507363	32
Cacheus	0.526992	0.482302	40
LRB-BMR	0.529727	0.471793	40

Table 7: Learned baselines on the 10-trace subset (cacheable-only averages; 200k requests; 128/256/512/1024 MiB).

Policy	Avg OMR $\downarrow$	Avg BMR $\downarrow$
Belady	0.377158	0.445614
BeladySize	0.372115	0.447127

Table 8: Oracle lookahead bounds on a small subset (cacheable-only averages; 20k-request prefixes).

Policy	Avg OMR $\downarrow$	Avg BMR $\downarrow$
HR-Cache	0.504266	0.457858
AUTO ( $\alpha=0.2$ )	0.490309	0.452126
AUTO	0.483891	0.482311
SIEVE	0.508924	0.450670
S3-FIFO	0.502109	0.558957
GDSF	0.475218	0.487148

Table 9: Average cacheable-only miss ratios on the HR-Cache subset.

Objective	Subset	Acc	Avg regret	P95 regret	Worst regret	Low-conf%
cost:0.2	all	0.433	0.024102	0.113755	0.182123	42.5
cost:0.2	nonflat	0.327	0.029513	0.116286	0.182123	51.0
cost:0.5	all	0.508	0.020515	0.106438	0.189169	42.5
cost:0.5	nonflat	0.418	0.025121	0.109354	0.189169	51.0
cost:0.8	all	0.558	0.015684	0.096900	0.203912	16.7
cost:0.8	nonflat	0.500	0.019205	0.106430	0.203912	17.3

Table 10: Selector accuracy and regret (lower regret is better).

Fallback	OMR avg	OMR P95	$\alpha{=}0.2$ avg	$\alpha{=}0.2$ P95
GDSF	0.0241	0.1195	0.0295	0.1163
DynAdaptiveClimb	0.0325	0.1218	0.0476	0.1627
LHD	0.0248	0.1195	0.0441	0.1638
S3-FIFO	0.0300	0.1277	0.0396	0.1401
SIEVE	0.0321	0.1277	0.0529	0.1884

Table 11: Fallback sensitivity across objectives (non-flat samples; DynAdaptiveClimb = DynamicAdaptiveClimb).

Setting	Avg regret	Misclass rate
all	0.015819	0.367
drop log p50	0.016706	0.367
drop log p90	0.015819	0.367
drop log mean	0.015967	0.357
drop log tail ratio	0.016721	0.367
drop cacheable ratio	0.018268	0.367

Table 12: Drop-one-feature ablation (non-flat samples).

Setting	Avg regret	Oracle gap	Total gap
all	0.0158	0.0000	0.0158
drop GDSF	0.0152	0.0098	0.0249
drop DynamicAdaptiveClimb	0.0178	0.0000	0.0178
drop LHD	0.0150	0.0021	0.0171
drop WTinyLFU-AV	0.0086	0.0066	0.0152
drop S3-FIFO	0.0145	0.0000	0.0145

Table 13: Expert-set ablation (cacheable-only OMR).

Policy	$\alpha=0.2$	$\alpha=0.5$	$\alpha=0.8$
AUTO	0.510101	0.483153	0.456205
AUTO ( $\alpha=0.2$ )	0.505359	0.480854	0.456348
AUTO ( $\alpha=0.5$ )	0.506077	0.481263	0.456448
AUTO ( $\alpha=0.8$ )	0.507218	0.480113	0.453008
GDSF	0.510865	0.481510	0.452155
LHD	0.521778	0.489596	0.457415

Table 14: Avg. cost tradeoff for

\alpha

-weighted objective. Rows denote selector trained with

\alpha

; columns evaluate cost using

\alpha

Case	Count	Fraction
OMR improves, BMR_all worsens	28	0.233
OMR worsens, BMR_all improves	6	0.050
Both improve	52	0.433
Both worsen	34	0.283

Table 15: AUTO vs SIEVE: cacheable-only OMR vs all-request BMR tradeoffs.

Figure 3: Cacheable-only OMR (top) and BMR (bottom) vs cache size for representative traces (lower is better for both).

Objective	Acc $\uparrow$	Avg regret $\downarrow$	P95 regret $\downarrow$
OMR (subset)	0.592	0.019029	0.098285
Tail-5% OMR	0.625	0.011641	0.072579

Table 16: Selector performance when trained on a tail objective (non-flat samples).

Figure 4: Two compact visual summaries of secondary analyses. Top: AUTO trades a small mean-OMR increase for better BMR tails and slightly lower worst-case OMR than fixed GDSF. Bottom: AUTO-fast improves the fast-budget Pareto point over the best fixed fast policy.

Metric	Method	Mean regret	P90	CVaR90	Worst	N
OMR	AUTO	0.0197	0.0788	0.1265	0.2458	120
OMR	GDSF	0.0140	0.0351	0.1003	0.2615	120
BMR	AUTO	0.0336	0.0930	0.1508	0.2365	120
BMR	GDSF	0.0360	0.1170	0.1590	0.2365	120

Table 17: Risk-sensitive regret vs the best expert (cacheable-only).

Metric	Value
Trace-size pairs	98
Post-prefix windows	2282
Median regret	0.000415
P90 regret	0.091308
Frac $\leq 0.01$	0.637
Frac $\leq 0.02$	0.702

Table 18: Prefix-based selection stability (post-prefix windows; cacheable-only OMR).

Train -¿ Test	Acc	Avg regret	P95 regret	N
non-twitter -¿ twitter	0.750	0.000006	0.000023	24
twitter -¿ non-twitter	0.469	0.017631	0.078119	96
non-block -¿ block	0.521	0.020802	0.101020	48
block -¿ non-block	0.319	0.008301	0.041023	72
cloudphysics early -¿ cloudphysics late	0.375	0.025894	0.053132	8
cloudphysics late -¿ cloudphysics early	0.375	0.067903	0.147991	8

Table 19: Out-of-distribution generalization by dataset family (OMR objective).

Fingerprint	$N$	$\tau$ (bytes)	Miscls	Avg regret	Worst regret
logmean	1000	262144	0.742	0.036269	0.542588
mean	1000	262144	0.608	0.031072	0.542588
median	1000	262144	0.708	0.036070	0.542588
p90	1000	262144	0.475	0.025470	0.542588
trimmed	5000	262144	0.608	0.031072	0.542588

Table 20: Fingerprint sensitivity (best setting per fingerprint across

N

and

\tau

Prefix $N$	Best $\tau$	Avg regret $\downarrow$	P95 regret $\downarrow$
1K	256KiB	0.025470	0.029927
5K	256KiB	0.026814	0.031231
10K	256KiB	0.026814	0.031231
50K	256KiB	0.026814	0.031231
200K	256KiB	0.026814	0.031231
1M	256KiB	0.027014	0.031437

Table 21: Short-prefix p90 threshold sensitivity (best

\tau

per

N

Mode	Avg OMR $\downarrow$	Best OMR $\downarrow$	Worst OMR $\downarrow$
oracle_switch(cost=0.02)	0.566952	0.477694	0.647771
fixed_share(alpha=0.05)	0.569891	0.478663	0.652027
fixed:GDSF	0.570428	0.477694	0.654674
hedge	0.571376	0.478663	0.655083
threshold	0.571516	0.479902	0.654131
bandit	0.587959	0.494979	0.694912

Table 22: Online epochal selection on spliced traces (summary; cacheable-only OMR).

Trace	S3-FIFO	GDSF	SIEVE	ARC	SCION-P90
Hotspot (Zipf 1.1), large objects	0.472/0.470	0.389/0.388	0.508/0.507	0.492/0.490	0.389/0.388
Hotspot (Zipf 1.1), small objects	0.155/0.154	0.136/0.135	0.155/0.154	0.150/0.149	0.155/0.154
High churn (95Regime switch (hotspot-¿uniform)	0.668/0.475	0.527/0.393	0.740/0.507	0.683/0.525	0.527/0.393

Table 23: Synthetic stress tests (cacheable-only OMR/BMR at 256 MiB, 1M requests).

Selector	Policy	Avg OMR $\downarrow$	Avg BMR $\downarrow$
Best fixed (fast)	LHD	0.487550	0.417048
AUTO-fast	AUTO-fast	0.490259	0.404845
Oracle (fast)	oracle	0.484438	0.381937

Table 24: Overhead-aware selection under a fast-policy budget (cacheable-only averages).

Policy	Avg MQPS	Rel. to SIEVE
SIEVE	8.520	1.00x
AdaptiveClimb	8.512	1.00x
DynamicAdaptiveClimb	8.188	0.96x
S3-FIFO	5.708	0.67x
LHD	4.945	0.58x
GDSF	2.738	0.32x

Table 25: Per-policy throughput microbenchmark.

Trace	Policy	Cache	P50 ms	P95 ms	P99 ms	RPS	Hit	Origin GB
meta_reag.oracleGeneral.zst	SIEVE	256MiB	46.62	3023.18	8214.08	128.5	0.319	290.87
meta_reag.oracleGeneral.zst	GDSF	256MiB	41.96	3035.64	8774.38	128.8	0.365	298.09
meta_reag.oracleGeneral.zst	AUTO	256MiB	43.74	3162.16	8368.71	123.6	0.364	296.03
meta_reag.oracleGeneral.zst	S3-FIFO	256MiB	48.36	3038.00	7871.37	120.2	0.317	291.14
meta_rprn.oracleGeneral.zst	GDSF	256MiB	53.49	1358.30	4809.51	73.0	0.240	648.03
meta_rprn.oracleGeneral.zst	S3-FIFO	256MiB	46.94	1170.62	3870.59	71.7	0.206	647.41

Table 26: End-to-end prototype results (cache-daemon + origin).

Cache Replacement

See all 16 papers

LearnedCache: An eBPF-Integrated Perceptron-Based Eviction Policy for the Linux Page Cache
May 25, 2026Zejia QiCache Replacement
ObjectCache: Layerwise Object-Storage Retrieval for KV Cache Reuse
May 16, 2026Yu Zhu, Aditya Dhakal, Yunming Xiao +2LLM Inference Efficiency KV-Cache Offloading
ETH Zurich Switzerland · HPE Labs United States of America · The Chinese University of Hong Kong, Shenzhen China
CACHEFORGE: LLM-Guided End-to-End Generative Cache Replacement Policy for Performance and Hardware Efficiency
Oct 6, 2026Kaushal Mhapsekar, Bita Aslrousta, Brijesh Kumar Bhayana +5Large Language Model-Guided Optimization LLM-Based Program Synthesis
Department of Electrical and Computer Engineering North Carolina State University, Raleigh, NC, USA

May 25, 2026J/K move · Enter open · S save

LearnedCache: An eBPF-Integrated Perceptron-Based Eviction Policy for the Linux Page Cache

Zejia Qi

Cache Replacement

Open paper AskPDF arXiv

Linux is the foundation of the digital age, accounting for the majority of the cloud and mobile OS markets. Any device that runs Linux uses the Linux page cache, a central pillar in OS and application performance, serving to reduce extraneous disk access. Many page cache eviction policies have been developed but remain bound by the rigidity of heuristics. The rise of AI-driven tools in recent years, melded with the ever-increasing variety of workloads for Linux devices, sets the stage for machine-learning-driven cache eviction policies. Promising research has been done in this field, but only in the field of user-space applications such as CDNs. We develop LearnedCache, an eBPF-integrated single-layer perceptron-based cache eviction policy for the Linux page cache, trained on real kernel data from diverse workloads. We demonstrate median AUCs of nearly 80% over multiple linear models modeling page reuse time, then take a step further by embedding these models inside the Linux kernel for real-time performance evaluation. Through statistical testing over 50 paired trials against a baseline of FIFO for each workload, LearnedCache reveals that machine-learning-derived cache eviction policies are practical in the Linux kernel under representative empirical workloads and are able to surpass conventional FIFO by statistically significant margins of up to 10% in insertion rate, a frequency-adjusted derivation of cache hit rate, in specific workloads while incurring minimal overhead.

Abstract

Cache Replacement

Explore similar work

LearnedCache: An eBPF-Integrated Perceptron-Based Eviction Policy for the Linux Page Cache

ObjectCache: Layerwise Object-Storage Retrieval for KV Cache Reuse

CACHEFORGE: LLM-Guided End-to-End Generative Cache Replacement Policy for Performance and Hardware Efficiency