PaperlayerView exact revision on arXiv

Source-linked AI summary

VestigeKV: The NoPE-MLA KV Cache Carries Its Own Sparse-Attention Signal in a Vestigial Branch

WenJie Fan

arXiv:2609.03949v2cs.LGcs.CL

TL;DR

Long-lived caches must be compressed before the queries that will read them exist, leaving observed-attention selection without the needed signal. VestigeKV derives a training-free, query-independent sparse pattern from a NoPE cache branch. The reported recall tier restores retrieval at high compression, while the deployment benefit is speed rather than memory reduction.

  • Problem

    Compression precedes future queries, so observed-attention statistics cannot identify which cached tokens those queries will need.

    Source: §2 · p. 2

  • Method

    VestigeKV uses a pretrained NoPE cache signal to form a training-free, query-independent sparse-attention pattern and partitions rows into an attended tier and archive.

    Source: §1 · p. 2, §3.2 · p. 4, §4.1 · p. 5

  • Results

    At 32×, the recall tier restores 0.89 → 1.00; at 128×, it restores 0.69 → 1.00.

    Source: §5 · p. 8

  • Takeaways & Limitations

    The scan reads ∼294 versus 1152 B/token, while both tiers remain GPU-resident, making the stated benefit speed rather than memory reduction.

    Source: §3.2 · p. 4, §4.3 · p. 7

    Measurements cover Kimi Linear 48B Base, the only released NoPE-MLA checkpoint; Kimi K3’s branch salience and long-context suites remain untested or future work.

    Source: §8 · p. 10

Abstract

from arXiv · show

A long-lived KV cache must be compressed before the queries that will read it exist. Selection by observed attention collapses there: on a NoPE-MLA model, H2O and SnapKV retrieve 0.00 and 0.33 of needles at 8x compression, because a token's importance has not yet been observed. VestigeKV instead derives a sparse attention pattern from a signal the cache already carries, occupying the sparse-attention literature's one unoccupied quadrant: training-free and query-independent. In NoPE-MLA the 64-dimensional decoupled branch is a vestige of RoPE that training repurposes into a salience channel; reading 11% of each row, it partitions the cache into an attended tier and a GPU-resident archive that no row ever leaves, reachable each step by a certified, query-adaptive trigger. Nothing is trained and cache rows are never quantized, so every quality effect attributes to selection and scheduling. On Kimi Linear 48B, retrieval holds at 1.00 under 8x and 0.96 under 32x from 8k to 65k context, with zero gap to full-row selection, and the recall tier holds 128x at 1.00 (8k). Both tiers stay on the GPU, so the win is speed, not memory: the per-step scan reads ~26% of the bytes dense attention would, and on a two-node sglang deployment the crossover sits at ~40k context, reaching 1.18x at 256k and 1.39x at 496k. The mechanism is exclusive to NoPE: the identical operator on a RoPE MLA collapses to 0.08, query-independent salience exists only without rotation, and query-universal exact merging is provably impossible under RoPE. All thresholds were frozen before their data; 20 archived verdicts and 8 closed routes accompany the paper.

1 INTRODUCTION: CAPABILITY, COST, AND REQUIRED CHANGES

VestigeKV derives a training-free, query-independent sparse-attention pattern from a signal already present in the NoPE cache. Its cache policy preserves rows across an attended tier and GPU-resident archive, with the benefit framed as speed rather than memory reduction.

1 INTRODUCTION: CAPABILITY, COST, AND REQUIRED CHANGES

  • For Kimi K3’s Gated-MLA, the machinery extends by proof, but whether its branch carries the salience signal is untested.The paper names the mathematics, engineering, and measurements as its three contributions, each addressing a NoPE benefit and RoPE obstruction.Source: §1 · pp. 1–2
  • At 32× compression, the attended tier retains retrieval at 0.96 from 8k–65k context; the recall tier reaches 1.00 at 128×.The signal read costs 11% of each row once per compression event; rows are partitioned between the attended tier and a GPU-resident archive.Source: §1 · p. 2
  • The per-step scan reads ∼294 bytes/token versus 1152 bytes/token for full attention, while both cache tiers remain GPU-resident.The paper describes the resulting benefit as speed, not memory savings.Source: §1 · p. 2
  • VestigeKV occupies the training-free, query-independent sparse-attention quadrant by deriving its pattern from the pretrained NoPE cache.The paper identifies this as the quadrant needed when compression precedes the queries that will read the cache.Source: §1 · p. 2

2 THE PROBLEM: THE CACHE IS COMPRESSED BEFORE ITS QUERIES EXIST

Cache compression must happen before the future queries that need its tokens exist, so importance based on observed attention is unavailable at decision time. The paper contrasts that information gap with NoPE’s query-independent signal, which is absent under RoPE.

2 THE PROBLEM: THE CACHE IS COMPRESSED BEFORE ITS QUERIES EXIST

  • At 8×, H2O retrieves 0.00 of needles on the NoPE-MLA testbed, and a half-budget recent window changes nothing.The paper attributes the failure to unavailable information about future queries, not to the budget.Source: §2 · p. 2
  • The compression decision precedes the query that will need a token, leaving observed-attention statistics blind to that future need.The passage illustrates this timing with a timeline in Appendix C, Figure 5.Source: §2 · p. 2
  • Under NoPE, a fixed bilinear form makes salience a property of the token; under RoPE, attention winners depend on query position.The paper says the RoPE-era approach selects on observed attention and inherits the pre-query collapse.Source: §2 · p. 2

3 THEORY: THE MATHEMATICS OF A POSITION-FREE CACHE

The theory identifies why NoPE permits query-independent selection, while exact merging cannot generally reduce the cache’s distinct rows. It also explains why rankings remain stationary over time and how a vestigial branch can supply a salience signal.

3 THEORY: THE MATHEMATICS OF A POSITION-FREE CACHE

  • Under NoPE, fixed bilinear scoring makes salience query-independent and attention depend on the cache-row multiset, while exact merging cannot reduce distinct rows.The proposition requires at least as many representative rows as there are distinct cache rows; measured NoPE merge classes were empty, so selection remains necessary.Source: §3 · pp. 2–3
  • A query-uniform certificate bounds score error for surrogate rows under the fixed NoPE form, and the guarantees extend to output-gated Gated-MLA.The extension does not cover query-row-coupled score gates, which break the fixed bilinear form; Kimi K3’s signal content remains unmeasured.Source: §3 · p. 3

3.1 EVICTION COMMUTES WITH TIME

  • Under NoPE, row-intrinsic rankings are time-stationary, so incremental global top-m eviction equals one-shot selection and blockwise compression matches one-shot at matched budgets.Under RoPE, pairwise row order can flip with time, requiring archived rows to be rescored at rebalance; constant-m schedules can still displace a needle through budget contention.Source: §3.1 · pp. 3–4

3.2 THE VESTIGE, AND THE NEW JOB TRAINING GAVE IT

  • NoPE frees the 64-dimensional branch from positional duty, and training repurposes it as a cache salience channel readable at 11% cost.Under RoPE, the same statistic scores 0.08 because those dimensions encode rotation frequencies rather than salience.Source: §3.2 · p. 4
  • At ρ=1/32 and r=64, the index budget yields ∼294 versus 1152 B/token, or 3.9×; the per-step adder is 68 µs.The admitted fraction is 0.4–0.8% on document decode and 0.5–2.6% on needle contexts; with full-precision indexing, the byte ratio is 2.1×.Source: §3.2 · p. 4

4 ENGINEERING

Engineering adds cache-membership policy around otherwise unchanged MLA operations: branch-slice ranking partitions rows, and a per-step recall scan can admit archived rows. On the production stack, the approach reduces attention cost but not memory footprint.

4.1 THE EVICTION POLICY

  • Every 4096-token block is transformed once; immutable σ rankings keep top-m rows plus sinks and the recent window, while other rows move bit-exactly to the GPU archive.The partition is rebalanced during decode as each new block closes; no row is deleted.Source: §4.1 · p. 5

4.2 THE RECALL TIER

  • The conformal threshold z uses hard calibration queries and exchangeability to guarantee target recovery; Gaussian-derived thresholds fail under selection effects, while the Cauchy–Schwarz bound fires on 99.5% of steps.The adopted threshold is based on empirically required inflations rather than a Gaussian assumption.Source: §4.2 · pp. 5–6
  • Each decode step scans archived rows and admits those that could compete with the kept tier, fetching exact copies into that query’s softmax.The trigger is query-adaptive rather than quota-based, and aims to fetch the minimal sufficient set when the target row was evicted.Source: §4.2 · p. 5, Figure 2 · p. 6

4.3 THE ATTENTION IMPLEMENTATION ON A PRODUCTION STACK

  • The production backend refuses non-NoPE-MLA caches, page sizes other than 1, and speculative decoding; its fused recall pipeline runs in the decode graph.It wraps the stock fused MLA-decode kernel and changes which rows it reads.Source: §4.3 · pp. 6–7
  • The attention-cost slope is about 0.26 of dense attention because every archived row is scanned each step; the recall guarantee therefore prevents savings from reaching zero.The scan reads archived rows at 260 B per row with the 16-bit index, and the fused pipeline adds 68 µs.Source: §4.3 · p. 7
  • ~40k is the crossover; speedup reaches 1.18× at 256k and 1.39× at 496k on the measured deployment.The measured long-context speedup depends on deployment; the two-GPU testbed's fixed costs suppress the ratio.Source: §4.3 · p. 7
  • Both tiers remain GPU-resident, so the benefit is speed rather than memory; at bs=1 and 64k+4k, attention is 7% of step time and throughput is near parity with dense attention.The advantage grows where attention accounts for more of the step, including with larger batch and context length.Source: §4.3 · p. 7

5 EXPERIMENTS AND RECOMMENDED CONFIGURATION

The experiments evaluate deployed quality and continuous-generation performance, then recommend a configuration derived from a single quality target. The serving path reproduces the harness’s selected rows and reports quality statistically indistinguishable from dense attention.

5 EXPERIMENTS AND RECOMMENDED CONFIGURATION

  • At bs=1, the continuous-decode crossover is ∼40k; VestigeKV reaches 1.18× at 256k and 1.39× at 496k.The protocol decodes continuously from 4k to 512k with decode-time block closes and the live archive active; throughput sweeps batch size at 64k prefill and 4k decode.Source: Figure 3 · p. 8, §5 · p. 8
  • The identical operator yields 0.89 NoPE vs. 0.08 RoPE at 32×, while teacher-forced ∆CE is ∼0.0006 bits/byte at 32× but misses a +15-nat needle-answer NLL degradation.The comparison motivates needle retrieval as the primary metric rather than continuation loss.Source: §5 · p. 8
  • At 8×, retrieval is lossless (1.00); at 128×, quality at fixed ratio improves from 0.69 at 8k to 0.83 at 32k.The recall tier restores retrieval from 0.89 to 1.00 at 32× and from 0.69 to 1.00 at 128×, admitting 0.5–2.6% extra rows per query.Source: §5 · p. 8

5.1 THE DEPLOYMENT PATH MEASURES THE SAME

  • On the serving path, 64-shot gsm8k is 0.830 vs. 0.821, MAUVE is 0.999 vs. 0.930, and teacher-forced ∆CE median is +0.0020 nats (Table 2).The fused kernels’ fired-and-fetched row sets are bit-identical to the harness’s on shared inputs, supporting transfer of its retrieval and language-modeling results.Source: §5.1 · p. 8

5.2 RECOMMENDED CONFIGURATION

  • At ρ=1/8 retrieval is lossless, and 1/32 is the default ratio and the only measured ratio flat in length.At 1/32, tier-2 recovery reaches 12/12 at an instrumental 256× in the deployment loop.Source: §5.2 · p. 9
  • At 1/32 with r=64, the GPU-resident archive permits uncapped fetches by default; topj=16 is an optional worst-case-latency bound.The trigger and entropy gate derive in closed form from the single recall target τ=0.90.Source: §5.2 · p. 9
  • The entire configuration self-calibrates from the compressed context because labels, thresholds, and sketch basis are functions of one fixed bilinear form.Under RoPE, calibration targets move with query position, so thresholds must track a distribution unavailable at compression time.Source: §5.2 · p. 9

6 MEASUREMENT INTEGRITY

Measurement integrity rests on adversarial gate checks, thresholds frozen before evaluation, and serving measurements collected with reproducibility checks.

6 MEASUREMENT INTEGRITY

  • Every gate was tested with a known-bad input and shown to refuse it before use.A per-decode-step attended-row-set assertion had zero violations on both arms, and every launch logged a content-level weight fingerprint.Source: §6 · p. 9
  • Every threshold was frozen and dated before its data were collected.Source: §6 · p. 9
  • All wall-clock measurements use sglang’s benchmark module on one source tree.The full protocol, including gates, Wilson intervals, row-set invariant, and serving methodology, is in Appendix E.Source: §6 · p. 9

7 RELATED WORK

VestigeKV’s sparse pattern comes from a query-independent signal already carried by NoPE caches, unlike fixed, trained, or observed-attention patterns. Its architecture resembles ArkVale, but its signal and certificate rely on the fixed NoPE bilinear form.

7 RELATED WORK

  • VestigeKV inherits a query-independent pattern from the pretrained NoPE cache, occupying the training-free, query-independent quadrant of sparse attention.Fixed geometry ignores content; trained patterns require pre-training; score-based selection is training-free but query-dependent.Source: §7 · p. 9
  • Unlike ArkVale’s query-history page importance and lossy page digests, VestigeKV uses query-independent row-level bit-exact latents with a 16-bit index.ArkVale’s evict-summarize-recall architecture is the closest comparison and is inherited by VestigeKV.Source: §7 · p. 9
  • Under NoPE, a fixed bilinear form supports a query-uniform per-row Cauchy–Schwarz certificate and capture-time-stationary ranking; the query-universal exact-merge result is limited to NoPE+MLA.The cited work states that no tight query-uniform bound exists under RoPE and that Proposition 1 establishes the query-universal version only under NoPE+MLA.Source: §7 · pp. 9–10

8 LIMITATIONS

The evaluation and scope are bounded by the available NoPE-MLA checkpoint, model-specific eviction behavior, and untested long-context suites.

8 LIMITATIONS

  • Only Kimi Linear 48B Base is measured; K3’s Gated-MLA salience content remains untested.Gate-commutation covers the architecture, but not whether its signal content supports the method.Source: §8 · p. 10
  • Selector ordering replicates on a NoPE GQA hybrid, but eviction depth does not, and the depth mechanism remains open.Source: §8 · p. 10
  • Long-context suites remain future work, and per-step consultation is probabilistic at 0.9–1.0, with 1.00 end to end.Source: §8 · p. 10

9 OUTLOOK: TRAINING AGAINST THIS MATHEMATICS

The paper sketches three training-dependent extensions, each presented as a prospect rather than a result and conditional on scale.

9 OUTLOOK: TRAINING AGAINST THIS MATHEMATICS

  • A trained index channel could make sketch residuals small by construction, potentially reviving guaranteed-recall sparse attention.This is a prospect, not a claim about the current method.Source: §9 · p. 10
  • Training toward position-free latents on repeated spans could make Proposition 1’s collapse live, reducing cache size to O(distinct content).The passage makes this prospect conditional on training and scale.Source: §9 · p. 10
  • Eviction-aware fine-tuning has a uniquely stable target under NoPE, but remains a scale-dependent prospect.The passage cites Gelberg et al. (2026) for this direction.Source: §9 · p. 10

10 CONCLUSION

VestigeKV uses a NoPE branch as a salience signal to compress cache rows while preserving retrieval, whereas rotation removes that signal. The conclusion is supported by a proof, a digest comparison, and experiment results.

10 CONCLUSION

  • VestigeKV reads 11% of each row and compresses 8–32× with retrieval intact; a recall tier restores 128×, but the signal does not survive rotation.The cache branch is a trained record of token importance in NoPE-MLA.Source: §10 · p. 10

A PROOFS

  • Under RoPE, exact query-universal merging requires at least as many rows as there are distinct rows; under NoPE+MLA, positively proportional content vectors at the same position can form identical rows.The proof ties the difference to rotation making rows pairwise distinct, while NoPE+MLA admits a larger merge class.Source: A PROOFS · p. 11

B THE DIGEST OBSTRUCTION UNDER ROPE

  • RoPE makes the digest radius scale with fast-frequency key norms regardless of content coherence, while NoPE supplies an exact summand, per-token certificates, and prefetchable rankings.The table caption identifies the comparison as the measured effect of removing rotation under the same digest protocol.Source: B THE DIGEST OBSTRUCTION UNDER ROPE · p. 12, Table 1 · p. 12

C EXPERIMENT TABLES (HARNESS)

  • The deployed-path quality table uses 64-shot gsm8k prompts that engage compression, and its accuracy gaps are expressed in percentage points.The caption also specifies raw-score units for MAUVE and a relative reading only for the ∆CE row.Source: Table 2 · p. 13
  • The identical selector scores 0.08 on DSV2 under RoPE, while the caption identifies the branch as a trained salience channel.The caption distinguishes static weight-derived rows from behavioral rows using 512 queries and 32 heads.Source: Table 3 · p. 13
  • The recall tier restores retrieval lost to eviction, admitting only 0.5–2.6% extra rows per query; a larger sketch rank cuts trigger rate while recall rises.Table 5 describes end-to-end recovery at L=8192 over 24 trials.Source: Table 5 · p. 13
  • At 32×, the standard configuration is effectively lossless at ∼0.0006 bits/byte, while the recent-only floor scores +15 nats on the needle despite matching on CE.The table caption identifies these as held-out continuation-loss results and notes that CE alone cannot arbitrate retrieval.Source: Table 6 · p. 14

D TIER-1 ABLATION DETAIL

The tier-1 ablations isolate selection from recall, while the appendices describe measurement checks, study boundaries, rate uncertainty, and a serving specification.

D TIER-1 ABLATION DETAIL

  • The tier-1 ablation turns recall off to isolate the selector, comparing branch-only and full-row selection at matched budget and testing needles when compression precedes the query.The passage cautions that these tables are not final quality results.Source: D TIER-1 ABLATION DETAIL · p. 14, Table 8 · p. 14, Table 9 · p. 15

H DEPLOYMENT SPECIFICATION

E MEASUREMENT INTEGRITY: FULL PROTOCOL

  • The serving row-set assertion checked every pipeline rank and layer during the benchmark campaign with zero violations, alongside known-bad-input checks and a recorded benchmarking protocol.The full campaign used the assertion on both ranks and arms across batch sizes.Source: E MEASUREMENT INTEGRITY: FULL PROTOCOL · p. 15

F SCOPE BOUNDARIES: FULL TABLE

  • Measurements cover Kimi Linear 48B Base only; post-training survival of the signal is untested, and standard long-context suites remain future work.The passage also distinguishes tested needle probes, held-out CE, QA, MAUVE, and serving latency scopes.Source: F SCOPE BOUNDARIES: FULL TABLE · p. 16

G INTERVAL ESTIMATES FOR THE PRIMARY RATES

I THE DIVIDEND INSIDE PRIOR ALGORITHMS

NoPE makes several existing cache-management ideas more principled by removing position-dependent score rotation: their statistics, rankings, and certificates can remain valid across time. The paper derives separate dividends for attention-based selection, page pruning, projection, merging, and cross-request reuse, while noting where the frozen checkpoint limits practical use.

I THE DIVIDEND INSIDE PRIOR ALGORITHMS

  • NoPE makes cache-score statistics time-invariant and rankings stationary, so past-query heavy-hitter estimates transfer to future queries without a shelf life.Under RoPE, future-query rotations make the estimate age-dependent and its shelf life depends on the frequency bands.Source: I THE DIVIDEND INSIDE PRIOR ALGORITHMS · p. 17
  • SnapKV votes have an unbounded validity horizon under NoPE, while under RoPE the horizon equals the generation length.The vote-to-generation score difference vanishes under NoPE and oscillates by frequency band under RoPE; SnapKV is described by Li et al. (2024).Source: I THE DIVIDEND INSIDE PRIOR ALGORITHMS · p. 18
  • For a fixed sink row, NoPE keeps its score invariant to sequence length, while RoPE's difference term drifts with distance in the lowest frequency bands.This gives the sink mechanism of Xiao et al. (2024) exact stability under NoPE.Source: I THE DIVIDEND INSIDE PRIOR ALGORITHMS · p. 18
  • Quest page-bound pruning is admissible under NoPE, but prunes under 0.2% of pages on this checkpoint with 256-dimensional index boxes at page size 64.The method is described by Tang et al. (2024); a sublinear hierarchical recall index is a theoretical opening, not a built or measured system.Source: I THE DIVIDEND INSIDE PRIOR ALGORITHMS · p. 18
  • NoPE gives orthogonal projection a query-uniform score-error objective, but the frozen Kimi Linear checkpoint's rank-512 read-out leaves this dividend for future training.The projection method is MatryoshkaKV (Lin et al., 2025); under RoPE its objective depends on position unless the projector nearly commutes with the rotation family.Source: I THE DIVIDEND INSIDE PRIOR ALGORITHMS · p. 18
  • KeepKV's exact merge certificate is available only under NoPE-MLA, yet the tolerant merge class is empty on real corpora at 5% tolerance.Identical rows can merge with an ln m bias, and RMSNorm homogeneity enlarges the merge class; under RoPE the class is empty. KeepKV is described by Tian et al. (2025).Source: I THE DIVIDEND INSIDE PRIOR ALGORITHMS · p. 18
  • NoPE-MLA rows can be reused at any position in any context by zero-copy, whereas RoPE reuse requires re-rotating each moved row.The exchangeability lemma underlies the cross-request cache-reuse systems Irminsul and Kamera (Ma et al., 2026b;a).Source: I THE DIVIDEND INSIDE PRIOR ALGORITHMS · p. 18
Loading 2609.03949v2…