Lifetime-Sorted KV Caches: Placing Tokens by When They Will Be Forgotten

When a language model generates text, it stores a key and value vector for every past token. This store is the KV cache, and it is what fills GPU memory during long reasoning. Recent methods learn to forget. Cache What Lasts (TRIM-KV) gives each token a learned retention rate at the moment it is written, and the token's importance then fades exponentially. The trouble is where forgotten tokens sit. Tokens that die early are scattered among tokens that live long, so eviction leaves holes inside memory pages. A page with even one live token cannot be returned to the pool. The system then needs custom kernels that fill holes in place, as in ThinKV and Zipage, or costly compaction.

This proposal borrows an old allocator trick: put objects that will die at the same time next to each other. Forgetting models already predict each token's death time when the token is created. So we can write each token into a page shared with tokens of similar predicted lifetime. Pages then empty all at once and can be freed whole, with no holes. Two ideas from human memory research shape the design. The first is that memory has two components: an all-or-nothing "recollection" process and a graded "familiarity" process. The second is that each item has its own decay rate. The cognitive framing is useful only if it holds up empirically, and the program is built to test that.

Core Claim

A write-time lifetime prediction, taken from a learned per-token forgetting curve, is enough to sort KV tokens into lifetime-homogeneous pages. Doing so turns token-level forgetting into page-level freeing. It should match the accuracy of token-level eviction while freeing far more whole pages per decoding step. It should also keep a small number of contiguous memory segments that ordinary attention kernels can read, in the spirit of vAttention.

The second, riskier claim is about the shape of the retention distribution. We predict it is a mixture: a threshold-like group of tokens with retention near 1, which are effectively never forgotten, plus a graded group that decays continuously. This is the computational analogue of the non-zero intercept that recollection adds to recognition curves in dual-process accounts. If the claim holds, the threshold group should be pinned in its own permanent, contiguous region, and only the graded group should be lifetime-binned. Single-process accounts in the REM tradition (Malmberg et al.) argue that such asymmetries can come from one continuous strength scale. Our ablation, which uses continuous bins with no pinned class, is exactly the single-process alternative, so the data will decide between them.

Research Program

The mechanism starts from TRIM-KV's per-head retention gate, which outputs $\beta_i \in [0,1]$ for token $i$. The token's importance at step $t$ is $\beta_i^{\,t-i}$. If the cache effectively evicts tokens whose importance falls below a level $\tau$, the predicted lifetime is

$$ L_i = \frac{\ln \tau}{\ln \beta_i}, $$

which follows directly from solving $\beta_i^{L_i} = \tau$. Here $\tau$ is not fixed in TRIM-KV, because eviction is by rank at capacity. We therefore estimate an effective $\tau$ per budget from calibration traces and track how well $L_i$ predicts the actual eviction step.

Each head keeps a small set of lifetime bins with geometrically spaced boundaries. Each bin is its own contiguous virtual segment backed by physical pages allocated on demand, using CUDA virtual-memory calls as vAttention does. A newly written token goes to the bin matching its predicted $L_i$. Tokens with $\beta_i$ above a fitted mixture threshold go to the pinned segment. We fit a two-component model to the $\beta$ distribution: a point-mass-like component near 1 and a continuous component. The fit is checked against held-out traces.

Attention is computed over the few segments separately and merged with the standard log-sum-exp combination used in split attention. This means unmodified FlashAttention-style kernels suffice. Positional information is already encoded in the keys, so reordering storage does not change the attention result.

Bins fill in arrival order, so each bin is also roughly ordered by predicted death time. A bin's oldest page is freed once its tokens pass their lifetime.

Mispredictions create "straggler" tokens that outlive their page-mates. The file raises a second source of error. Consolidation research suggests importance is not always monotone: items can become more important later (Dynamic and selective engrams; Bottlenecked Transformers). Stragglers are handled by migrating them to a longer-lived bin when a page falls below an occupancy floor. We report the migration traffic as a first-class cost. Measuring how much importance actually rises late in real traces is itself a finding. It tells us whether monotone forgetting curves, like the linear per-item decay of Newman et al. or TRIM-KV's exponential, are adequate for placement.

Baselines

The naive reference point is full-cache decoding under vLLM with PagedAttention (Efficient Memory Management for LLM Serving with PagedAttention). It sets the accuracy ceiling and the memory floor. A second naive baseline is a sliding window with the same budget. It must be beaten on accuracy.

The strongest accuracy competitor is TRIM-KV itself, using its native token-level eviction. The file reports a 198.4% relative accuracy gain over SnapKV on AIME24 at an identical low budget, and 58.9% Pass@1 over SeerAttn-R. No absolute AIME24 accuracy for TRIM-KV was found on Lacuna, so we rerun it. Our method uses the same gates and the same budget, so any accuracy difference isolates placement and straggler handling. Beating TRIM-KV means accuracy within noise of it while freeing substantially more whole pages. It also means higher sustained batch concurrency at equal memory.

The strongest systems competitors are ThinKV and Zipage. ThinKV reports less than a 4% accuracy drop at 75x less memory on R1-Llama-8B and up to 5.8x throughput. Zipage reports over 2.1x decoding throughput over vLLM at around 95% of full-cache accuracy on AIME 24, AMC 23, and GSM8K. Both handle holes by reusing slots inside pages. All systems run on the same GPU type, backbone, prompts, sampling seeds, and memory budget, with each method's published hyperparameters and an equal small tuning sweep. Beating them means matching accuracy and exceeding throughput at equal memory, without a custom paged kernel. If we only match them, the result still stands as a simpler design, and we will say so.

The key ablations isolate each ingredient. The first uses random bin assignment with identical machinery. The second uses continuous lifetime bins with no pinned class, which is the single-process version. The third uses page-level eviction with TRIM-KV scores averaged per page but no sorted placement.

Why not just…?

Why not just average TRIM-KV scores per page and evict the weakest pages? This is the most serious threat. It needs no new allocator. However, in unsorted pages the per-page average mixes long- and short-lived tokens. Evicting a page therefore either drops live, high-retention tokens or never frees the page. We run exactly this as an ablation at matched budgets. If it matches our accuracy and page-freeing rate, the sorted-placement idea is unnecessary and we will report that.

Why not just reuse holes in place, as ThinKV's kernel and Zipage's Compressed PagedAttention do? Slot reuse keeps memory usage dense within a request. But partially live pages stay owned by that request and cannot be given to other requests, and the approach needs a dedicated paged kernel. The comparison above measures whether whole-page freeing actually raises concurrency across requests. If slot reuse achieves the same concurrency, our advantage shrinks to kernel simplicity.

Why not just use smaller pages, as vAttention does with 64KB pages? Smaller pages reduce internal waste but do not stop mixed lifetimes from pinning pages. They also increase translation overhead. We sweep page size for both our method and TRIM-KV to see whether small pages alone close the gap.

Why not drop the dual-process split and use only continuous bins? This may well be enough. The no-pinned-class ablation answers it directly. The mixture fit on $\beta$ tells us whether a distinct threshold component exists at all.

Proposed Experiments

We run on R1-Llama-8B, following ThinKV's setting, plus a second backbone for which we train TRIM-KV gates using its distillation-plus-capacity recipe. Reasoning benchmarks are AIME24, MATH-500, GSM8K, and LiveCodeBench. For multi-session memory we use LongMemEval_S (LongMemEval), where long-context models reportedly drop 30% to 60% relative to the oracle setting.

Metrics fall into three groups. For task quality we report accuracy or Pass@1. For memory behaviour we report page occupancy over time, whole pages freed per thousand steps, and straggler migration bytes. For serving we report maximum concurrent requests and tokens per second at a fixed memory size.

The decisive checks are these. First, $L_i$ must rank-correlate with actual eviction time, or placement cannot work. Second, the $\beta$ distribution must support a two-component fit that beats a single continuous component on held-out likelihood. Third, the sorted design must beat per-page-averaged TRIM-KV on pages freed at equal accuracy. Fourth, straggler migration must stay a small fraction of KV write bandwidth, even on LongMemEval, where late importance increases should be most common.