Coverage-Verified Sparse Attention: Closed-Loop Quality Control for Long-Context LLM Decoding
Organizations: National Taiwan University
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 points across the threshold sweep; budget and scheduling ablations characterize the deployed operating point. On LongBench at 7B and 70B, CVSA comes within points of dense attention, statistically matching it at 70B, and it loses points on RULER; measured median decode-step speedup reaches at 128K context.
Figures & tables
| Configuration ( effective read) | Llama | Mistral | Qwen | Avg | Gap |
| Dense | — | ||||
| Uniform Fixed-12%, no gate | |||||
| Offline per-(layer, head) budget, no gate | |||||
| CVSA -c4 (coverage gate) |
Appendix figures & tables32 assets
Supplementary material from the paper’s appendix.
Appendix
| Model | Cells | Proxy accept | Token accept | False accept | False reject | Agreement |
|---|---|---|---|---|---|---|
| Llama-3.1-8B | 3840 | 0.0% | 0.0% | 0.0% | 0.0% | 100.0% |
| Mistral-7B-v0.3 | 3840 | 0.0% | 0.0% | 0.0% | 0.0% | 100.0% |
| Qwen2.5-7B | 3360 | 12.3% | 4.3% | 9.4% | 1.4% | 89.2% |
| Production probe ( , 5% base) | Llama-3.1-8B | Mistral-7B-v0.3 | Qwen2.5-7B |
|---|---|---|---|
| False accepts (% of proxy accepts) | |||
| FA output-error median (absolute) | |||
| Catastrophic FA ( ) | |||
| False rejects (% of proxy rejects) |
| Model | Dense mean | CVSA -c4 mean | 95% CI( CVSA ) | 95% CI( ) |
|---|---|---|---|---|
| 3-model avg ( ) | 41.83 | 40.70 | — | — |
| Llama-3.1-8B ( ) | 43.13 | 42.34 | [40.83, 43.87] | [ , ] |
| Mistral-7B-v0.3 ( ) | 42.63 | 41.71 | [40.25, 43.23] | [ , ] |
| Qwen2.5-7B ( ) | 40.15 | 38.38 | [36.91, 39.87] | [ , ] |
| Model | CVSA -c4 SnapKV | CVSA -c4 AdaKV |
|---|---|---|
| Llama-3.1-8B | [+ , + ] | [ , + ] |
| Mistral-7B-v0.3 | [+ , + ] | [+ , + ] |
| Qwen2.5-7B | [+ , + ] | [+ , + ] |
| Model | Paged dense | KVPress dense | KVPress paged |
|---|---|---|---|
| Llama-3.1-8B | 42.57 | 42.70 | +0.13 |
| Mistral-7B-v0.3 | 42.73 | 41.03 | |
| Qwen2.5-7B | 40.18 | 39.27 |
| Method (all paged-decode) | Llama | Mistral | Qwen | Avg | Gap |
|---|---|---|---|---|---|
| Dense | — | ||||
| CVSA -c4 (5% base) | |||||
| AdaKV (10%) | |||||
| Quest (10%) | |||||
| H2O (10%) | |||||
| SnapKV (10%) |
| Task | Dense | CVSA | Mean | Llama | Mistral | Qwen |
|---|---|---|---|---|---|---|
| Qasper | 41.47 | 36.99 | ||||
| LCC | 37.08 | 34.04 | ||||
| SAMSum | 42.87 | 39.90 | ||||
| RepoBench-P | 38.33 | 36.21 | ||||
| NarrativeQA | 27.17 | 25.44 | ||||
| MultiNews | 11.29 | 10.31 |
| Configuration | Llama | Mistral | Qwen | 3-model avg | vs. dense |
|---|---|---|---|---|---|
| Dense | — | ||||
| CVSA -c1 | |||||
| CVSA -c2 | |||||
| CVSA -c4 (default) | |||||
| CVSA -c8 |
| Configuration | Llama | Mistral | Qwen | Avg | vs. dense |
|---|---|---|---|---|---|
| Dense | — | ||||
| Fixed-5% (no verification) | |||||
| CVSA -c4 + AR20, no dL0 | |||||
| CVSA -c4 + AR20 + dL0 |
| Recovery policy | Llama | Mistral | Qwen | Avg | vs. dense |
|---|---|---|---|---|---|
| Dense | — | ||||
| CVSA -c4 + Exact + dL0 | |||||
| CVSA -c4 + AR20 + dL0 |
| Configuration | Llama | Mistral | Qwen | Avg |
|---|---|---|---|---|
| CVSA -c4 (reference) | 41.87 | 41.71 | 38.54 | 40.70 |
| Uniform 9%, refresh 4, dL0 | 42.39 | 42.06 | 39.13 | 41.19 |
| Uniform 10%, refresh 4, dL0 | 42.39 | 41.92 | 39.17 | 41.16 |
| Offline budget, refresh 4, dL0 | 42.58 | 41.78 | 38.72 | 41.03 |
| Task | Paged dense | CVSA -c2 | CVSA -c4 | KVPress AdaKV | KVPress SnapKV |
|---|---|---|---|---|---|
| hotpotqa | |||||
| triviaqa | |||||
| qasper | |||||
| multifieldqa_en | |||||
| trec | |||||
| lcc |
| Model | Layers | Q/KV heads | Head dim | Hidden | MLP inter. |
|---|---|---|---|---|---|
| Llama-3.1-8B | 32 | 32 / 8 | 128 | 4096 | 14336 |
| Mistral-7B-v0.3 | 32 | 32 / 8 | 128 | 4096 | 14336 |
| Qwen2.5-7B | 28 | 28 / 4 | 128 | 3584 | 18944 |
| Model | (%) | Predicted (Eq. 8 ) | Measured | |
|---|---|---|---|---|
| Llama-3.1-8B | 1 | |||
| 8 | ||||
| 32 | ||||
| Mistral-7B-v0.3 | 1 | |||
| 8 | ||||
| 32 |
| B=1 (single-stream) | B=8 (batched) | |||||
|---|---|---|---|---|---|---|
| Model | 32K | 65K | 128K | 32K | 65K | 128K |
| Llama-3.1-8B | — | — | ||||
| Mistral-7B-v0.3 | — | — | ||||
| Qwen2.5-7B | ||||||
| Attention-path kernel | ms / decode step | Share |
|---|---|---|
| Coverage check (verifier) | ||
| Page scoring | ||
| Conditional recovery | ||
| Sparse draft attention |
| Method | Eff. budget | 3-model avg | vs. dense | vs. Quest |
|---|---|---|---|---|
| Dense | — | — | ||
| CVSA -c8 (ours) | ||||
| SnapKV (KVPress) | ||||
| AdaKV (KVPress) | ||||
| H2O (paged) | ||||
| Quest (paged) | — |
| Configuration (read% / quality) | Llama | Mistral | Qwen | 3-model |
|---|---|---|---|---|
| Pre-hoc top- (alone) | 14.42 / 35.12 | 13.55 / 32.79 | 10.21 / 27.16 | 12.73 / 31.69 |
| Pre-hoc top- + coverage gate | 16.88 / 38.94 | 16.94 / 36.21 | 13.64 / 30.93 | 15.82 / 35.36 |
| CVSA -c4 (verified top- ) | 11.67 / 41.87 | 11.74 / 41.71 | 11.66 / 38.54 | 11.69 / 40.70 |
| Selector (gate and recovery unchanged) | Without gate | With gate | Change |
|---|---|---|---|
| Quest-style min/max indexer | |||
| Pre-hoc top- (adaptive budget) | |||
| AdaKV-style cross-head allocation | — |
| Method | Quality | KV read | Pages touched | |
|---|---|---|---|---|
| Dense | — | |||
| CVSA -c4 | ||||
| Tactic (reproduced) | ||||
| + coverage gate |
| Task | Coverage | Read | Task | Coverage | Read |
|---|---|---|---|---|---|
| narrativeqa | passage_retrieval_en | ||||
| musique | triviaqa | ||||
| qmsum | trec | ||||
| repobench-p | multifieldqa_en | ||||
| hotpotqa | 2wikimqa | ||||
| passage_count | lcc |
| Quality (3-model) | Effective read | Per-head accept | Re-score rate | |
|---|---|---|---|---|
| 0.80 | 40.82 | 10.3% | 49.6% | 79.4% |
| 0.85 | 40.72 | 10.8% | 44.7% | 83.9% |
| 0.90 (deployed) | 40.70 | 11.7% | 37.8% | 89.5% |
| 0.95 | 40.84 | 12.6% | 27.1% | 95.4% |
| 0.97 | 40.83 | 13.0% | 19.1% | 98.1% |
| Configuration | Quality | Effective read | Total read incl. scoring |
|---|---|---|---|
| Dense | 42.57 | 100% | 1.00 |
| CVSA -c4 (exact selector + norm.) | 41.87 | 11.67% | 0.24 |
| Quest selector, exact norm. | 40.01 | 12.36% | 0.25 |
| Quest selector, sketch norm. (lightweight) | 40.07 | 12.95% | 0.15 |
| Method | 4K–32K | All measured contexts |
|---|---|---|
| CVSA -c4 | (72) | (108) |
| CVSA -c8 | (72) | (108) |
| SnapKV | (72) | (90) |
| H2O | (72) | (90) |
| AdaKV | (72) | (90) |
| Fixed-10% | (72) | (108) |
| Task | Context | Dense | CVSA -c4 | CVSA -c8 | SnapKV | H2O | AdaKV | Fixed-10% |
|---|---|---|---|---|---|---|---|---|
| S-NIAH | 4K | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 |
| 8K | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | |
| 16K | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | |
| 32K | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | |
| 64K | 100.0 | 100.0 | 100.0 | – | – | – | 100.0 | |
| 128K | 100.0 | 100.0 | 100.0 | – | – | – | 100.0 |
| Task | Context | Dense | CVSA -c4 | CVSA -c8 | SnapKV | H2O | AdaKV | Fixed-10% |
|---|---|---|---|---|---|---|---|---|
| S-NIAH | 4K | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 |
| 8K | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | |
| 16K | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | |
| 32K | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | |
| 64K | 100.0 | 100.0 | 100.0 | – | – | – | 100.0 | |
| 128K | 100.0 | 100.0 | 100.0 | – | – | – | 100.0 |
| Task | Context | Dense | CVSA -c4 | CVSA -c8 | SnapKV | H2O | AdaKV | Fixed-10% |
|---|---|---|---|---|---|---|---|---|
| S-NIAH | 4K | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 |
| 8K | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | |
| 16K | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | |
| 32K | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | |
| 64K | 100.0 | 100.0 | 100.0 | – | – | – | 100.0 | |
| 128K | 20.0 | 20.0 | 20.0 | – | – | – | 20.0 |
LLM Inference Acceleration
LLM inference acceleration develops algorithms and systems that reduce language-model latency, memory use, and serving cost while preserving output quality.
See all 1,228 papers