Coverage-Verified Sparse Attention: Closed-Loop Quality Control for Long-Context LLM Decoding

Yan-Cheng Li, Chun-Yi LeearXiv 2026 · arXiv

TL;DR

Coverage-Verified Sparse Attention (CVSA) transforms sparse attention from an "open-loop" guessing game into a "closed-loop" verified process. By utilizing a free internal signal called coverage—the fraction of attention mass captured by selected tokens—CVSA identifies and corrects failing attention heads in real-time, achieving near-dense quality with up to a 6.21× speedup at 128K context.

What Problem Does This Paper Address?

As Large Language Models (LLMs) tackle increasingly long contexts, the primary bottleneck in decoding shifts from computation to memory bandwidth—specifically, the time spent loading the ever-growing Key-Value (KV) cache. Sparse attention methods attempt to solve this by reading only a small subset of the KV cache.

However, existing sparse methods are "open-loop." They use heuristics to select tokens, attend to them, and emit an output without ever checking if the selection was actually good. If a selection misses critical information, the resulting error compounds across every subsequent token generated. Furthermore, attention needs are not uniform; a global "budget" of tokens often overpays for easy attention heads while starving the few "fragile" heads that actually need more data to maintain accuracy.

Methods

The authors introduce Coverage-Verified Sparse Attention (CVSA), a training-free framework that adds a verification and recovery step to the standard decoding loop.

The "Coverage" Signal

The core innovation is the use of coverage ($c$), defined as the fraction of the total softmax mass that lands on the selected tokens. The authors prove two key theoretical properties:

  1. Exact Decomposition: The dense output is a convex combination of the sparse "draft" and the omitted "complement," with coverage acting as the mixing weight.
  2. Exact Error Identity: The error between the sparse draft and the dense output is exactly proportional to $(1 - c)$.

Crucially, this signal is "free"—the values needed to compute it (Log-Sum-Exp) are already numerical by-products of modern fused-attention kernels.

The CVSA Loop

CVSA operates in three phases (illustrated in Figure 3):

  1. Draft: An off-the-shelf selector picks a subset of KV pages and produces a sparse output.
  2. Verify: The system checks the coverage of each attention head against a threshold $\tau$ (e.g., 0.90).
  3. Correct: Only the minority of heads that fall below the threshold enter a recovery path, where they attend to an expanded set of tokens to fix the error.
The CVSA verify-then-correct loop

To maintain high throughput, CVSA uses Hybrid Scheduling, refreshing the selection and performing the coverage check only every $M$ steps (typically $M=4$), reusing the selection in between.

Datasets

The authors evaluated CVSA across three 7B model families (Llama-3.1, Mistral-v0.3, and Qwen2.5) and Llama-3.1-70B using:

  • LongBench: A comprehensive 16-task benchmark for long-context understanding.
  • RULER: A retrieval stress test covering context lengths from 4K to 128K tokens.
  • MATH-500: Used specifically to probe the limits of the method during long chain-of-thought reasoning.

Key Insights and Ideas

  • Failures are Concentrated, Not Uniform: As shown in Figure 2, most attention heads maintain very high coverage even with tight budgets. Failures happen in a small, "fragile" minority of heads. CVSA exploits this by only spending extra compute where it is actually needed.
  • Theoretical Grounding: Unlike previous methods that rely on probabilistic bounds, CVSA is built on an exact algebraic equality between coverage and output error. This allows for deterministic, per-head quality control.
  • Selector Agnostic: CVSA isn't a new way to select tokens; it's a way to verify any existing selector. It wraps around existing production stacks (like vLLM) without requiring model retraining or auxiliary "draft" models.
Empirical evidence that failures are concentrated in a few layers

Key Results

  • Near-Dense Quality: On LongBench, CVSA-c4 (the recommended configuration) comes within 1.13 points of dense attention at the 7B scale and statistically matches dense attention at the 70B scale.
  • Massive Speedups: CVSA achieves a median decode-step speedup of 6.21× at 128K context on Qwen2.5-7B.
  • Superior to Open-Loop Baselines: CVSA consistently outperforms popular sparse methods like H2O, SnapKV, and AdaKV. Even when those baselines are given double the token budget, they fail to close the quality gap to CVSA.
  • RULER Performance: CVSA loses only 0.8 points relative to dense attention on RULER, compared to a massive 8.7-point loss for the strongest open-loop baseline.

Limitations and Future Work

  • Proxy Drift: The implementation uses a page-level proxy for coverage rather than a token-level one. On certain architectures (like Qwen), this proxy can "over-accept," leading to small quality drops in late layers. The authors suggest token-aware calibration as a future fix.
  • Reasoning Length: The current $M=4$ scheduling is optimized for long prompts with short answers. For long chain-of-thought generation (where the "answer" itself is very long), the selection can drift, requiring a shorter reuse window ($M=1$ or $M=2$).
  • Static Scheduling: The scoring interval $M$ is currently a manual setting. The authors envision a future "self-tuning" framework where $M$ adapts dynamically based on observed coverage statistics.

Summary updated

Abstract

Sparse attention accelerates long-context decoding by reading a subset of the KV cache, but existing methods are open-loop: the kernel commits to its selection with no signal indicating whether enough attention mass was preserved and no recovery path when it was not. The needed signal already exists inside the kernel. The fraction of softmax mass on the selected tokens, which we call coverage, satisfies an exact algebraic equality with per-step output error and serves a dual role as the acceptance criterion and the interpolation weight for recovery. Coverage-Verified Sparse Attention (CVSA) turns coverage into a training-free, closed-loop verify-then-correct decode loop that accepts high-coverage drafts and recovers only the heads that fall short, with no sampling, no draft model, and no speculative-decoding infrastructure. Quality varies by only $0.14$ points across the threshold sweep; budget and scheduling ablations characterize the deployed operating point. On LongBench at 7B and 70B, CVSA comes within $1.13$ points of dense attention, statistically matching it at 70B, and it loses $0.8$ points on RULER; measured median decode-step speedup reaches $6.21\times$ at 128K context.
BibTeX
@misc{li2026coverage,
  author = {Yan-Cheng Li and Chun-Yi Lee},
  title = {{Coverage-Verified Sparse Attention: Closed-Loop Quality Control for Long-Context LLM Decoding}},
  year = {2026},
  eprint = {2611.10634},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.10634},
}
Figure