PaperlayerView exact revision on arXiv

Source-linked AI summary

KVFetch: Temporal Prefetching for the Missing Half of KV Cache Compression

Linfeng Dong

arXiv:2610.08811v1cs.LGcs.AI

TL;DR

Existing KV cache compressors use content relevance but lack sequential traversal, leaving verbatim copying vulnerable when successors are evicted. KVFetch adds a training-free temporal recall channel to score-based compressors. Under an iso-budget control, it improves RULER-16K results while remaining dormant on tasks without sequential access.

  • Problem

    Existing compressors provide content-based addressing but not sequential traversal, although verbatim copying requires retrieving successive positions from context.

    Source: §1 · p. 1

  • Method

    KVFetch adds a training-free temporal recall channel that stores evicted candidates in a quantized cold tier, detects copying with a monotone read pointer, and prefetches positional successors into fixed-size hot-tier slots.

    Source: §1 · p. 2

  • Results

    +8.4 on the RULER-16K 13-task average under an iso-budget control, with verbatim copying rising from 0.8 to 78.4 and no degradation on LongBench (+0.33).

    Source: §1 · p. 2

  • Takeaways & Limitations

    KVFetch recovers sequential-copy failures that content-addressing refinement cannot reach, while its channel remains dormant when sequential access is absent.

    Source: §5 · p. 9

    KVFetch does not repair multi-needle tasks when the host selects the wrong candidate rather than losing a copy midway.

    Source: §4.5 · p. 9

Abstract

from arXiv · show

As context windows scale to tens or hundreds of thousands of tokens, KV cache compression has become essential for efficient LLM inference. Existing methods fall into three families: score-based eviction, summary compensation, and offload-and-recall. Yet all three decide what to keep or recall by content relevance to the current query. We show this shared design is structurally incomplete. A cache supports two access modes: associative lookup by content and sequential traversal by position; current compressors implement only the first. The gap matters in practice: retrieval-augmented generation, code completion, and structured-data extraction all require the model to reproduce identifiers, field values, or code tokens verbatim from the context. Under compression, content-based eviction retains the head of such a sequence but discards its continuation, causing verbatim copying to break irreversibly midway, a failure we call sequential forgetting. This failure resists better scoring, larger budgets, summary compensation, and dynamic re-scoring; it is the dominant source of remaining quality loss under compression. We propose KVFetch, a training-free, drop-in framework that opens a temporal recall channel for any score-based compressor. It demotes evicted candidates to a quantized cold tier, detects active copying through a monotone read pointer, and prefetches positional successors into fixed-size hot-tier slots without increasing attention cost. On RULER-16K under an iso-budget control, KVFetch recovers verbatim copying from 0.8 to 78.4 and raises the 13-task average by +8.4, with gains concentrating on tasks that require sequential access. On LongBench, where no task requires sequential access, the channel remains dormant and imposes no cost.

1 INTRODUCTION

Existing KV cache compressors address entries by content relevance, but do not support sequential traversal, leaving verbatim copying vulnerable when a sequence’s successors are evicted. KVFetch adds temporal recall, improving RULER-16K results under an iso-budget control.

1 INTRODUCTION

  • Existing compressors use content relevance for associative lookup, but none provides sequential traversal, whose demand arises from the decoding trajectory.That demand is difficult for prefill-time scoring to anticipate.Source: §1 · p. 1
  • KVFetch adds a training-free temporal channel to score-based compressors, demoting literal spans to a quantized cold tier and prefetching positional successors into fixed-size hot-tier slots.A monotone read pointer detects active copying, while attention cost remains constant.Source: §1 · p. 2
  • +8.4 on the RULER-16K 13-task average under an iso-budget control; verbatim copying rises from 0.8 to 78.4.The evaluation also reports 9 of 13 tasks improving with no material regression, and no degradation on LongBench (+0.33).Source: §1 · p. 2
  • Sequential forgetting accounts for 86% of the strongest baseline’s residual gap to full KV, resisting score refinement, larger budgets, summary compensation, and dynamic re-scoring.At 40% retention, s3 rises only from 0.8 to 3.2; TOVA’s s3 is 0.0.Source: §1 · p. 2
  • The evaluation covers RULER and LongBench with budget and length scaling, iso-budget controls, and ablations of all three components.The reported ablations demonstrate that admission, triggering, and prefetching are each necessary.Source: §1 · p. 2

2 RELATED WORK

Related work is organized by addressing primitive: existing approaches decide what to retain or recall through content relevance. KVFetch adds temporal addressing to this landscape.

2 RELATED WORK

  • Score-based eviction retains top-scoring entries, with methods refining scoring, allocation, or update timing while still evaluating content relevance.The passage notes that mid-span literal successors remain low-scoring and are not preserved even at 40% retention.Source: §2 · p. 3
  • SnapKV preserves a fixed-size neighborhood around selected attention peaks, but its prefill-time window may not cover a multi-token literal’s full continuation.KVFetch instead detects ongoing copying during decoding and recalls successors on demand.Source: §2 · p. 3
  • Summary compensation methods approximate discarded tokens’ distributional effect on attention output, but not the bit-exact token identity needed for verbatim copying.Source: §2 · p. 3
  • Offload-and-recall methods retrieve entries by content similarity; page granularity can incidentally co-load successors, but does not systematically follow a copy trajectory.Quest’s page granularity raises s3 from 0.8 to 8.8, still below the full-KV ceiling of 99.2.Source: §2 · p. 3
  • Learned future-demand predictors target broad demand patterns, whereas KVFetch targets sequential continuation with a training-free signal; the approaches are complementary.Source: §2 · p. 3
  • KVFetch’s 4-bit cold-tier quantization is an implementation choice, not a quantization contribution.The related-work framing groups methods by the addressing primitive that determines what they can recover.Source: §2 · p. 3

3 METHOD: KVFETCH

KVFetch adds temporal addressing to score-based KV compression while preserving fixed hot-tier capacity. It admits low-predictability spans to a cold tier, detects sequential copying, and prefetches positional successors.

3.1 PRELIMINARIES AND NOTATION

  • After prefill, score-based compressors retain only the top-scoring positions, and the hot-tier membership then remains fixed during decoding.The retained count is top-⌊(1 − ρ)L⌋, where L is prompt length and ρ is the eviction rate.Source: §3.1 · p. 4

3.2 SEQUENTIAL FORGETTING

  • Sequential forgetting occurs when a compressed cache contains the beginning of a verbatim span but not its next position, causing copying to fail irreversibly.This abrupt failure resists better scoring, larger budgets, summary compensation, and dynamic re-scoring; affected tasks account for 86% of the aggregate per-task gap to full KV.Source: §3.2 · p. 4

3.3 OVERVIEW AND SYSTEM STATE

  • KVFetch adds temporal addressing alongside content addressing, updating hot and cold tiers, position mappings, and a read pointer using existing attention without extra forward passes.The cold tier is 4-bit and capped at 5% of prompt length; without sequential access, the added components remain idle and the system reduces to the baseline.Source: §3 · pp. 3–4, §3.3 · p. 4

3.4 ADMISSION: CONSTRUCTING THE COLD TIER

  • Low-frequency consecutive tokens are demoted into a position-indexed 4-bit cold tier capped at 5% of prompt length, with unused budget partly returned to hot slots.Candidate runs are extended at both ends for tokenizer-boundary tolerance; tasks without candidate spans receive no cold tier.Source: §3.4 · p. 4

3.5 TRIGGERING: DETECTING ACTIVE COPYING

  • During verbatim copying, attention peaks advance in original-position coordinates; a stall-tolerant pointer tracks this motion and copy mode activates after two advances within eight steps.The trigger is active on approximately 1% of decoding steps during copying and remains near zero otherwise.Source: §3.5 · pp. 4–5
  • The temporal channel depends on the host compressor preserving initial localization, so the pointer can form a trajectory that engages prefetching.Source: §3.5 · p. 5

3.6 PREFETCHING: RECALLING POSITIONAL SUCCESSORS

  • When triggered, KVFetch fetches positional successors into hot slots while swapping out unprotected prompt entries, preserving hot-slot count and making false-trigger replacements recoverable.Each trigger costs O(k) lookups independent of prompt length; newly swapped-in slots are protected for Tprot steps.Source: §3.6 · pp. 5–6, Figure 2 · p. 5
  • Positional successors are the default fetch criterion, while query–key similarity changes the four-task average by only 0.76, making the channel’s presence more consequential than its criterion.Source: §3.6 · p. 6

4 EXPERIMENTS

The experiments diagnose sequential forgetting as a major residual failure under compression and evaluate KVFetch across RULER, LongBench, and multiple model families. KVFetch improves sequential-copy performance under an iso-budget control, while ablations and scope tests identify when its temporal channel helps and what it costs.

4.1 SETUP

  • Experiments use RULER at 4K, 16K, and 32K plus 16 LongBench tasks, with 20% retention unless stated otherwise.KVFetch wraps OBCache+SnapKV; the iso-budget control allocates 22.9% storage versus 20.36% measured total for KVFetch.Source: §4.1 · p. 6

4.2 DIAGNOSING SEQUENTIAL FORGETTING

  • At 10%–40% retention, verbatim-copy scores remain low; sustained-copy length shows mid-copy breaks, while nine improving tasks account for 86.4% of the full-KV gap.On s3, full KV sustains 31.25 tokens on average, compared with 5.43 for H2O and 10.84 for OBCache+SnapKV.Source: §4.2 · p. 6

4.3 MAIN RESULTS: RULER-16K

  • On RULER-16K, KVFetch raises Qwen2.5-7B’s 13-task average from 56.45 to 64.88 (+8.43) and s3 from at most 8.8 for baselines to 78.4.The average improves on 9 of 13 tasks with no material regression; s3 gains also appear on Qwen3-4B and Llama-3.1-8B.Source: §4.3 · pp. 6–7, Table 1 · p. 7

4.4 COMPONENT ABLATION

  • Removing admission or prefetching returns s3 to the host’s 0.8; never-fetch does likewise, while always-fetch lowers s3 to 24.0 and average to 51.72.Always-fetch falls below the host average of 54.28; instantaneous-stride triggering lowers s3 from 78.4 to 30.4.Source: §4.4 · pp. 7–8

4.5 ROBUSTNESS AND SCOPE

  • Across 4K, 16K, and 32K RULER contexts, KVFetch exceeds the host, with s3 ranging from 73.6 to 80.8.On LongBench, no task family regresses materially (+0.33 overall), and trigger rates of 0.000–0.029 indicate the channel remains dormant.Source: §4.5 · p. 8, Figure 3 · p. 8
  • KVFetch repairs continuation but not localization: on Mistral-7B-Instruct, its gain is +1.66, while multi-needle tasks remain outside the mechanism’s scope.The Mistral host cannot localize targets; on multi-needle tasks the host selects an incorrect candidate rather than breaking a copy midway.Source: §4.5 · p. 9

4.6 EFFICIENCY

  • At 16K, decoding attention remains 1.000× the host; the 4-bit cold sidecar adds 3.25 MiB and latency rises 4.8%.Average per-step latency is 19.6 ms versus 18.7 ms for the host.Source: §4.6 · p. 9, Table 3 · p. 9

5 CONCLUSION

KVFetch adds temporal addressing to KV cache compression, complementing content-based addressing. Its reported results show gains on sequential-access tasks while imposing no cost on tasks without sequential access.

5 CONCLUSION

  • KVFetch improves the RULER-16K 13-task average by +8.4, lifts verbatim copying from 0.8 to 78.4, and imposes no cost on tasks without sequential access.The copying score reaches 97.6 on Qwen3-4B.Source: §5 · p. 9
  • Admission, triggering, and prefetching are each necessary, according to component ablations.Source: §5 · p. 9
  • The per-task hit-rate correlation is r = 0.924, supporting the framework’s identification of which tasks benefit and which do not.Source: §5 · p. 9
  • The authors argue that dual-channel addressing should become a standard design axis for KV memory systems.They describe their trigger and prefetch choices as one instantiation, with alternatives including learned triggers, variable prefetch distances, and offload-and-recall integration.Source: §5 · p. 9

REPRODUCIBILITY STATEMENT

The reproducibility statement identifies the benchmarks and models used and describes plans for sharing code and experiment materials. It also notes that baseline numbers are reproducible with KVPress.

REPRODUCIBILITY STATEMENT

ETHICS STATEMENT

The ethics statement limits the work to inference-time memory management and reports no changes to model weights, training data, or output distributions. The supplementary benchmark section describes expanded results across four dimensions.

ETHICS STATEMENT

  • The work addresses inference-time memory management and does not modify model weights, training data, or output distributions.The authors identify no specific ethical risks beyond those inherent to the underlying language models.Source: ETHICS STATEMENT · p. 10

A SUPPLEMENTARY BENCHMARK RESULTS

A.1 QWEN2.5-7B PER-TASK RESULTS

The supplementary section gives per-task and cross-setting benchmark details, then adds mechanism diagnostics including sustained-copy-length measurements. These materials specify table scope and selected outcomes, while several tables provide breakdowns without numerical results in the supplied passages.

A.1 QWEN2.5-7B PER-TASK RESULTS

  • Table 4 gives Qwen2.5-7B’s full 13-task breakdown, listing the 20% host, per-task full-KV reference, and KVFetch.The full-KV scores support the gap decomposition in §4.2.Source: §A.1 · p. 13, Table 4 · p. 13

A.2 QWEN3-4B PER-TASK RESULTS

  • The Qwen3-4B cross-model run reports a +7.22 gain using the 22.9% aggregate control (61.86), and Table 5 compares per-task changes against the 20% host.Source: §A.2 · p. 13, Table 5 · p. 14

A.3 RETENTION SWEEP

A.4 CROSS-LENGTH FULL BASELINE TABLE

  • Table 9 expands Figure 3 by adding score-based baselines omitted from the main text for space.Source: §A.4 · p. 13

A.5 PLUG-AND-PLAY VALIDATION ACROSS HOSTS

  • The plug-and-play validation wraps KVFetch around different host scorers; TOVA, with baseline s3 of 0.0, cannot bootstrap the trigger and stays near the host.Source: §A.5 · p. 13, Table 10 · p. 15

A.6 LONGBENCH TASK-FAMILY AND PER-TASK RESULTS

B MECHANISM DIAGNOSTICS AND ABLATION DETAILS

B.1 SUSTAINED-COPY LENGTH

  • On niah single 3, KVFetch reaches 28.86 tokens in sustained-copy length, versus 5.43 for H2O, 10.84 for OBCache+SnapKV, and 11.82 for OBCache+AdaKV; full KV reaches 31.25.Sustained-copy length measures the longest matching token prefix and is averaged over samples.Source: §B.1 · p. 16

B.2 VISUALIZING THE ABLATION RESULTS

The ablations examine trigger and recall-selection choices, relate cold-tier hit rate to gains, and compare fetch criteria. LongBench remains in a low-hit, near-zero-gain regime.

B.2 VISUALIZING THE ABLATION RESULTS

  • Figure 4 shows trigger-mechanism and recall-selection ablations on Qwen2.5-7B at 20% hot retention, with each panel internally consistent but the panels not directly comparable.Panel (a) uses the default unigram admission signal; panel (b) uses the literal-predicate signal to match Table 13.Source: Figure 4 · p. 17, §B.2 · p. 17

B.3 HIT-RATE–GAIN CORRELATION

  • LongBench trigger rates of 0.000–0.029 and cold-tier recall hit rates of 0.042–0.130 both fall in the zero-gain band.Figure 5 separates these low-hit LongBench tasks in a dedicated zoom rather than compressing them into the RULER plot.Source: §B.3 · p. 17, Figure 5 · p. 17
  • r = 0.924 is the Pearson correlation between task-level cold-tier hit rate and gain across 13 RULER-16K tasks; after removing niah single 3, Spearman’s ρ is 0.818.An independent earlier run yielded Pearson r = 0.940 and post-removal Spearman ρ = 0.846; LongBench’s 0.042–0.130 hit-rate band coincides with +0.33 average gain and no material regression.Source: §B.3 · p. 17, Figure 5 · p. 17

B.4 FETCH CRITERION

  • 0.76 points separate query–key similarity from positional successors on the four-task average (92.96 vs. 93.52); random successors score 12.8 on s3.Query–key similarity improves s3 by +9.6, from 80.0 to 89.6; positional successors are the default because they need only an O(k) position lookup and no extra dot products.Source: §B.4 · p. 18, Table 13 · p. 18

C HYPERPARAMETER SENSITIVITY

The sensitivity sweeps vary quantization, prefetch distance, and admission threshold under a configuration-matched signal. The section also distinguishes continuation loss from failures to locate a target.

C HYPERPARAMETER SENSITIVITY

  • 4-bit quantization scores 80.8 on s3 versus 79.2 for 8-bit, while 2-bit scores 24.0.The figure caption likewise reports that 4-bit matches 8-bit and 2-bit collapses.Source: C HYPERPARAMETER SENSITIVITY · p. 18, Figure 7 · p. 18
  • On s3, prefetch distance k = 32 scores 93.6 versus 80.0 at the default k = 8; admission thresholds 4, 6, and 8 score 83.2, 80.0, and 80.0.The sweeps use the literal-predicate signal; their relative ordering is unchanged under the default unigram signal.Source: C HYPERPARAMETER SENSITIVITY · p. 18, Figure 6 · p. 18

D FAILURE CASES AND APPLICABILITY

  • KVFetch targets spans that are located but lose their continuation; failure to locate the target after compression limits its applicability.The paper distinguishes continuation loss from localization failure as separate failure modes.Source: D FAILURE CASES AND APPLICABILITY · p. 18
  • The three candidate-signal instantiations perform comparably on their covered tasks; unigram frequency is the default because it needs no format priors.Table 14 compares the signal variants with all other configuration fields held identical.Source: C HYPERPARAMETER SENSITIVITY · p. 18, Table 14 · p. 19

D.1 FAILURE-SAMPLE GALLERY

The gallery distinguishes continuation failures from localization failures, while the implementation identifies literal runs, ranks cold-tier entries, and recalls successors through bounded swaps. Its pointer and swapping behavior is organized per layer and KV head.

D.1 FAILURE-SAMPLE GALLERY

  • Figure 1 is illustrative, not a recorded failure sample; it depicts a correctly located span whose copying stops when successor KV entries are unavailable.This is the diagnostic category targeted by KVFetch.Source: §D.1 · p. 19

D.2 MISTRAL FULL-KV PROBE AND TRIGGER-RATE TELEMETRY

  • For Mistral-7B-Instruct, the 13-task compressed-host average is 26.39 and KVFetch reaches 28.05; a 10% full-KV probe scores 100.0 on niah single 2 versus 0.8 for the compressed host.The trigger rate is 0.0018, versus 0.068 on Qwen2.5 copy tasks; KVFetch repairs continuation but does not globally re-localize targets lost through compression.Source: §D.2 · p. 19

E.1 CANDIDATE IDENTIFICATION AND COLD-TIER ORDERING

  • The literal predicate identifies consecutive runs of hex-like tokens of at least Mrun tokens; cold-tier ranking extends candidate runs by δ, excludes hot positions, and retains the top-ncold positions.The candidate set also includes positions around high-scoring hot-tier anchors, with the specified scoring parameters in the prose.Source: §E.1 · p. 19

E.2 4-BIT AFFINE QUANTIZATION

  • Cold-tier keys and values use per-channel affine quantization; two 4-bit values pack into one byte and are dequantized before a cold entry returns to the hot tier.The stored integer is clipped to the range 0–15.Source: §E.2 · p. 19

E.3 VICTIM SCORING AND THE PROTECTION PERIOD

  • Victim scoring uses an attention EMA with β = 0.9, while recalled slots receive 12 protected decoding steps.The EMA is used only for victim scoring; peak extraction uses current-step attention.Source: §E.3 · p. 20

E.4 HYPERPARAMETERS

  • Defaults include prefetch distance k = 8, trigger window W = 8, advance threshold 2, maximum stride 4, and protection period 12; the pointer-band constraint dominates back-tolerance.The default configuration also sets a cold-tier budget cap of 0.05 and EMA decay β = 0.9.Source: §E.4 · p. 20

E.5 COMPLETE PSEUDOCODE

  • Each decoding step updates the read pointer and copy signal, then swaps up to k eligible cold successors for low-score, unprotected hot slots, keeping hot-tier size unchanged.Peak extraction computes arg max(QK⊤) for one confident KV head and requires no additional full forward pass.Source: §E.5 · p. 20

E.6 PER-LAYER AND PER-HEAD SEMANTICS

  • Each layer maintains one pointer per sample, observes its highest-confidence KV head after GQA aggregation, and executes prefetching and swaps independently per KV head.A trigger in one layer does not force other layers into copy mode.Source: §E.6 · p. 21
Loading 2610.08811v1…