VestigeKV: Query-Independent Sparse Attention with Certified Recall for NoPE-MLA Caches

A long-lived KV cache must be compressed before the queries that will read it exist. Methods ranking by observed attention are built for the opposite order and are not compared against here: with no query, the statistic they rank by is undefined rather than weak. VestigeKV decides before any query exists and makes the decision non-destructive. Reading 11% of each row, a statistic the cache already carries, it partitions the cache into an attended tier and a GPU-resident archive no row ever leaves, reachable each step by a certified, query-adaptive trigger. The certificate is what carries the result: swapping the first tier's statistic for a stride, a norm, a recency window or a random draw leaves every cell of the retrieval table unchanged, so the recovery is the archive's and not the selector's, and we report that rather than claim the selector. Nothing is trained and nothing is stored below 16 bits. On Kimi Linear 48B the two tiers recover every needle trial at 32x and 128x (1.00, 1.00) and 32/32 on the served path at 128k; delete tier 2 and the algorithm is incomplete. Both tiers stay on the GPU and the cache grows 1.14x, so the win is bandwidth, not memory: the per-step scan reads  26% of the bytes dense attention would, and on a two-GPU sglang deployment the crossover sits at  24k context, reaching 1.45x at 512k. Two conditions bound the claim, and both are measured. It holds under NoPE, where the score is position-free so a ranking taken at prefill is permanent: with rotation the only variable it inflates the winner set a fixed cone can select by 1.1-2.1x (Prop. 1), and exact merging is provably impossible there. And it holds on natural text, where the selector's overlap with an oracle sits at 3.3x the random floor against 1.6x on a synthetic haystack; the overflow fallback owns that minority regime. All thresholds were frozen before their data; 20 archived verdicts and 8 closed routes accompany the paper.