PAGE: Partition-Aware Gated KV-Cache Eviction

arXiv:2609.22157v1 Announce Type: cross Abstract: KV-cache eviction methods decide which tokens to keep but not whether to evict at all, so a benchmark mean can hide a class of inputs on which compression drives accuracy from 99\% to 0\%. We reframe eviction as a per-input admission decision and show that inputs separate into a capacity-bound class, where eviction is catastrophic at every budget, and a dilution-prone class, where eviction is safe or beneficial. A single label-free scalar computed from prefill attention, the early-to-late drop in pairwise top-$k$ head agreement, predicts this class before any decoding. PAGE thresholds this drop: it applies any base evictor when the drop is large and retains the full cache otherwise, with no training and no accuracy labels. The drop orders inputs by eviction safety consistently across four architecture families, and a per-model unlabeled pilot of about 100 inputs recalibrates the threshold for a new family. Used as a safeguard, PAGE cuts the harm rate on the capacity-bound regime from 0.75 to 0.026, a 29 $\times$ reduction, across four evictors, four models, and two benchmarks, turning a 99\% to 0\% collapse into a flat 89\% without retraining the evictor. The gate is inert wherever eviction is already safe, and the capacity-bound class it protects is a small, identifiable minority of inputs, so the benefit is a targeted safety gain rather than an average one. PAGE is a per-input safeguard, not a compressor: realized compression is $1.8 - 3.4 \times$ (mean 2.9$\times$) against a nominal 16$\times$ budget and decays toward unity by batch 16 under static provisioning, and a trained evictor wins at matched memory.

Abstract:KV-cache eviction methods decide which tokens to keep but not whether to evict at all, so a benchmark mean can hide a class of inputs on which compression drives accuracy from 99\% to 0\%. We reframe eviction as a per-input admission decision and show that inputs separate into a capacity-bound class, where eviction is catastrophic at every budget, and a dilution-prone class, where eviction is safe or beneficial. A single label-free scalar computed from prefill attention, the early-to-late drop in pairwise top-$k$ head agreement, predicts this class before any decoding. PAGE thresholds this drop: it applies any base evictor when the drop is large and retains the full cache otherwise, with no training and no accuracy labels. The drop orders inputs by eviction safety consistently across four architecture families, and a per-model unlabeled pilot of about 100 inputs recalibrates the threshold for a new family. Used as a safeguard, PAGE cuts the harm rate on the capacity-bound regime from 0.75 to 0.026, a 29 $\times$ reduction, across four evictors, four models, and two benchmarks, turning a 99\% to 0\% collapse into a flat 89\% without retraining the evictor. The gate is inert wherever eviction is already safe, and the capacity-bound class it protects is a small, identifiable minority of inputs, so the benefit is a targeted safety gain rather than an average one. PAGE is a per-input safeguard, not a compressor: realized compression is $1.8 - 3.4 \times$ (mean 2.9$\times$) against a nominal 16$\times$ budget and decays toward unity by batch 16 under static provisioning, and a trained evictor wins at matched memory.

Machine Learning (cs.LG); Computation and Language (cs.CL); Cryptography and Security (cs.CR)

arXiv:2609.22157 [cs.LG]

(or arXiv:2609.22157v1 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2609.22157 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

aiqbench analysis

PAGE: Partition-Aware Gated KV-Cache Eviction

Related coverage