Certified Sparse Attention

Runtime verification of fidelity for sparse-attention LLM serving.

Sparse-attention KV-cache compression trades memory and bandwidth for a fidelity loss that behaves like a phase transition — silent on most requests, sharp on a few. This project detects that loss at serving time, without labels, from block scores the attention kernel already computes and discards, and bounds it with an anytime-valid statistical certificate.

#sparse-attention #llm-inference #llm-serving #kv-cache #long-context #confidence-sequences #pytorch #cuda

Overview

For a live request, the system produces a statement of the form:

≤ 2% of decode steps diverged from dense execution, at 95% confidence, at ~6% throughput cost.

No deployed serving system can currently make that statement. Three mechanisms make it possible:

1. Label-free detection — every selection-based sparse method scores KV blocks and keeps the top-k. The discarded scores are a free estimate of the omitted attention mass; a scalar summary of them predicts divergence from dense execution.
2. Sampled dense verification — occasionally re-run a decode step with dense attention over identical state, and feed the outcome into an anytime-valid confidence sequence — a bound legitimate at every step with no pre-committed sample size.
3. Elastic scheduling — probes are deferrable, so under load the system widens its confidence interval instead of degrading latency or fidelity.

Results

Four hypotheses were pre-registered with falsification thresholds before any result was seen. Verdicts and exact numbers: results/RESULTS.md.

Hypothesis	Question	Result
H1	Is divergence detectable label-free?	Confirmed to 7B on two architectures — AUC 0.71–0.81 (Qwen2.5, Mistral); kill line 0.65.
H2	Is a useful bound affordable?	Open — scale-free bound holds; short-trace ±5% falsified at a probe/step ratio ≈ 1 measured in an eager loop. Needs an in-kernel implementation.
H3	Can verification be elastic under load?	Supported (simulation) — elastic P99 latency 17.5 vs inline 44.0; the bound widens instead.
H4	Does divergence predict end-task error?	Confirmed to 7B on two architectures — Spearman ρ −0.58 to −0.93 on answerable requests; kill line |ρ| 0.5.

The fidelity cliff the work is premised on reproduces at 7B on both architectures: end-task accuracy falls monotonically as the KV budget tightens (0.85 → 0.63), and the label-free detector tracks it.

Contributions

• A label-free divergence detector from discarded block scores; the damage-aligned signals (dropped mass, cross-head eviction consensus) are separated from a logit-margin baseline that has the highest raw AUC but is shown to track uncertainty, not fidelity — a result that reproduces and strengthens across scale.
• An anytime-valid verifier (Hoeffding / empirical-Bernstein / betting confidence sequences, Horvitz–Thompson debiasing for adaptive sampling), with a coverage audit that rejects estimators unsafe under phase-transition drift.
• An elastic scheduling formulation in which contention degrades the guarantee, not the output.
• A cross-architecture evaluation at 7B on 2× H100, with a reproducible, tested implementation (CI · 88 tests) and a methodology that retains superseded runs and states its limits explicitly.

Built with Python, PyTorch, Hugging Face Transformers, NumPy/pandas/SciPy, and pytest; measured on NVIDIA H100.

Artifact	Description	Link
📄 PAPER	Preprint draft consolidating the confirmed results, with a submission plan	paper/PAPER.md
📊 RESULTS	Every result with its figure — all studies, ablations, gates, and the scaling story in one place	results/RESULTS.md
GATE 1 — cross-architecture	The headline result: premise + detector confirmed on Qwen2.5 and Mistral at 7B	results/GATE1_CROSS_ARCH.md
GATE 1	Rented-H100 measurements at 7B, and what they do not support	results/GATE1.md
GATE 1 — aggregation	The task redesign that made H4 measurable again, and the powered run that confirmed it	results/GATE1_AGGREGATION.md
REPORT	Pre-committed H1–H4 verdicts with numbers (smoke scale)	results/REPORT.md
TABLES	Auto-generated markdown tables (never hand-copied)	results/TABLES.md
METHODOLOGY	Threats to validity, written before interpreting results	results/METHODOLOGY.md
RFC	Serving-system integration design (vLLM path)	docs/RFC-runtime-fidelity-verification.md

Where the science stands. Findings began at smoke scale (0.5B–1.5B, 1–2K context) and were then re-run at 7B on 2× H100 at 16K context. The fidelity cliff the project is premised on is reproduced at 7B on two architectures — accuracy falls monotonically as the KV budget tightens (Mistral aggregation: 0.85 → 0.63, n=60) and a label-free signal predicts divergence at AUC 0.71–0.75. H1 (detectability) and H4 (proxy validity) hold through 7B; H2 (cost) remains open because the eager Transformers loop measures a probe/step ratio ≈ 1 regardless of hardware — settling it needs the in-tree vLLM path described in the RFC. Larger models are disk-limited, not compute-limited, on the rented image. Every limit here is stated, not hidden.

---

Table of contents

1. System architecture
2. Headline results (smoke scale)
3. Result catalog with tags
4. Figures
5. Repository layout
6. Quick start
7. Reproduce studies
8. Status and roadmap
9. Citation

---

System architecture

Three cooperating mechanisms turn an unverified sparse claim into a runtime certificate:

flowchart LR
  subgraph M1["Mechanism 1 — Label-free detection"]
    Q[Q / KV state] --> SEL[Block selection<br/>quest / mean / local]
    SEL --> SIG[Dropped mass · consensus<br/>entropy · margin]
    SIG --> DET[Logistic detector<br/>grouped CV]
  end

  subgraph M2["Mechanism 2 — Sampled dense verification"]
    DET -->|adaptive p_t| SMP[Probe sampler]
    SMP --> PRB[Dense probe on identical KV]
    PRB --> CS[Anytime-valid CS<br/>Hoeffding / EB / Betting]
    CS --> BND["Bound: μ ∈ [lo, hi]"]
  end

  subgraph M3["Mechanism 3 — Elastic work"]
    BND --> SCH[Scheduler]
    SCH -->|slack GPU| PRB
    SCH -->|under load| WIDE[Widen bound<br/>protect TPOT]
  end

Loading

Paired measurement harness (Study A substrate): dense and sparse attention share the same Q/KV; selection retains the full cache so the dense counterfactual is exact.

flowchart TB
  PROMPT[Prompt + decode token] --> CACHE[(Full KV cache)]
  CACHE --> DENSE[Dense attention]
  CACHE --> SPARSE[Selection-based sparse]
  DENSE --> DIV[Divergence labels<br/>greedy flip · logit KL]
  SPARSE --> SIG2[Label-free signals]
  DENSE --> OUT[Optional: return sparse output]
  SPARSE --> OUT
  DIV --> TRACE[steps.csv scalars only]
  SIG2 --> TRACE

Loading

Mechanism	Idea	Code
1. Label-free detection	Discarded block scores estimate omitted attention mass; cross-head eviction consensus catches globally erased content.	csa/sparse.py, csa/signals.py, csa/detector.py
2. Sampled dense verification	Dense probes on identical KV feed an anytime-valid confidence sequence; adaptive sampling uses Horvitz–Thompson weights.	csa/verify.py
3. Elastic verification work	Probes consume slack capacity; under load the bound widens instead of latency or silent fidelity loss.	csa/scheduler.py

---

Headline results (smoke scale)

Measured on NVIDIA T1000 8GB, models Qwen2.5-0.5B-Instruct and Qwen2.5-1.5B-Instruct, contexts 1K–2K. See REPORT.md for full caveats.

Hypothesis	Question	Verdict
H1	Divergence detectable label-free?	Confirmed through 7B on two architectures. Damage-aligned AUC 0.808 (0.5B) / 0.804 (1.5B) / 0.75 (Qwen 7B) / 0.71 (Mistral 7B), all above the 0.65 kill line, none underpowered. eviction consensus holds at 0.751 → 0.710 across a doubling of KV heads (Qwen→Mistral)
H2	Useful bound affordable?	Not falsified (scale-free); falsified on short traces at the measured r = 1.04. Betting CS fails under bursty drift (miss rate 0.825)
H3	Elastic under load?	Shape supported (simulation) — elastic TPOT ≈ baseline; inline latency collapses
H4	Divergence ↔ task wrongness?	Confirmed through 7B on two architectures. ρ −0.870 (0.5B) / −0.930 (1.5B) / −0.621 (Qwen 7B, n=60) / −0.576 (Mistral 7B, n=48), all past the |ρ| ≥ 0.5 bar. Qwen saturates the retrieval suite (0.979) while Mistral does not (0.875) — a model property, not a task defect

Methodological guards baked into analysis (csa/analysis.py):

1. Within-budget AUC (pooled AUC is inflated by budget).
2. H4 conditioned on dense-answerable requests.
3. Grouped cross-validation by request (no i.i.d. leakage).
4. Damage vs uncertainty: margin wins flip-AUC but fails damage correlation — dropped-mass / consensus are the fidelity signals.
5. KV-drift isolation: with drift removed entirely, dropped mass still separates diverged steps at 0.789 AUC (vs 0.817 with drift), so H1 reads the current step's omitted attention mass — though ~3 AUC points did come from drift, which is stated rather than rounded to zero.

Defects found by audit, stated rather than quietly fixed. Study A runs before results/study_a_*_v2/ had three faults that all suppressed or corrupted accuracy without ever crashing:

1. Unreproducible task seeds. Seeds came from hash((seed, fam, i, target_tokens)); hash() on a tuple containing a str is salted by PYTHONHASHSEED, which CPython randomizes per process, so those runs drew gold answers from a state that cannot be reconstructed — re-running the same commit does not reproduce them.
2. Substring answer matching. key scored correct inside monkey.
3. Two broken tasks. Coreference aliases were occupation-shaped ("the archivist"), making the profession question ambiguous; reasoning traces hit a 64-token cap before stating their total, so the family scored an intermediate count.

All are fixed — blake2b seeds, word-boundary and last-integer checks, non-agentive aliases, and a named LONG_DECODE_MIN_TOKENS budget — each with a regression test, including one that runs the generator under two values of PYTHONHASHSEED and asserts identical output.

H4 has been regenerated on both smoke-scale models and clears its bar on each — ρ = −0.870 (0.5B) and −0.930 (1.5B) on answerable requests, −0.821 and −0.936 within budget, strengthening with model scale rather than washing out. H1, H2, H3 and all six ablations never call Task.check and were never affected.

At 7B the picture is subtler and turned out to be model-specific: on Qwen2.5-7B the retrieval suite saturates (accuracy 1.000 at every budget), so H4 cannot be estimated there — but the same suite on Mistral-7B gives 0.875 accuracy, a real cliff, and ρ = −0.576. Qwen is simply unusually strong on synthetic retrieval; the tasks are sound. The aggregation suite (GATE1_AGGREGATION.md) produces ~3–7× the divergence and confirms H4 on both models at n=48–60, and the full architecture comparison is in GATE1_CROSS_ARCH.md.

Worth noting for anyone auditing similar work: old and new dense accuracy on the 0.5B are 0.438 and 0.458. The defects never produced a number that looked wrong, which is why they survived until an audit went looking. Details in METHODOLOGY.md.

---

Result catalog with tags

Each run directory includes *.meta.json (machine fingerprint) and online-aggregated CSVs only — never raw attention tensors.

Directory	Tags	Description	Key result
results/study_a_0.5b/	#study-a #h1 #superseded #qwen-0.5b #t1000	0.5B paired sweep — SUPERSEDED by study_a_0.5b_v2/	Best LF AUC 0.85 (margin); damage-aligned 0.79. Accuracy figures withdrawn
results/study_a_1.5b/	#study-a #h1 #superseded #qwen-1.5b #t1000	1.5B full Study A — SUPERSEDED by study_a_1.5b_v2/	Damage-aligned AUC 0.84; combined CV 0.92. Accuracy figures withdrawn
results/study_a_0.5b_v2/	#study-a #h1 #h4 #qwen-0.5b #authoritative	Authoritative 0.5B sweep: reproducible seeds, fixed task suite	H4 ρ −0.870 answerable / −0.821 within budget; LF AUC 0.877; dense acc 0.458
results/study_a_1.5b_v2/	#study-a #h1 #h4 #qwen-1.5b #authoritative	Authoritative 1.5B sweep	H4 ρ −0.930 answerable / −0.936 within budget; LF AUC 0.847; dense acc 0.708
results/study_a/	#superseded	First Study A run (intermediate code)	Kept for provenance; see SUPERSEDED.md
results/study_b/	#study-b #h2 #confidence-sequences	Bound width vs probe cost; coverage audit under i.i.d. / bursty	Scale-free H2 not falsified; adaptive+Betting burst miss 0.97
results/study_c/	#study-c #h3 #scheduler #simulation	Elastic vs inline vs none under load	High-load P99 TPOT: elastic 17.5 vs inline 44 (none 19.5)
results/ablations/	#ablations #transfer #detector	Signals alone/combined; rate 0→100%; fixed vs adaptive; transfer	Cross-model transfer AUC 0.92 (0.5B→1.5B)
results/ablation6/	#ablation-6 #layer-budget #pyramid	Per-layer schedules at matched mean keep fraction	Detector CV AUC 0.87–0.93 within schedules; cross-schedule transfer ≥ 0.92
results/overhead/	#overhead #probe-cost #gather-path	Production sparse vs dense wall-clock on T1000	Speedup ≈ 1.0–1.12×; r ≈ 1.0–1.12 (MLP-bound host)
results/REPORT.md	#verdicts #phase-l	Written verdicts against pre-committed gates	H1/H4 supported; H2 scale-free OK; H3 sim-only
results/TABLES.md	#tables	make_tables.py output	Paste-ready numbers for papers

Hardware tag (all Phase L runs): #nvidia-t1000-8gb · driver 596.51 · CUDA 12.4 · Windows smoke host.

---

Figures

All plots are generated by the experiment drivers (never hand-drawn). Click through to the run directories for CSVs and fingerprints.

Study A — detection, cliff, calibration, traces

#h1 #roc #qwen-1.5b

ROC (1.5B, teacher-forced, budgets pooled) — label = greedy-token flip. Dropped-mass / consensus track the oracle; margin is high-AUC but low damage correlation.

#cliff #accuracy #flip-rate

Fidelity cliff — end-task accuracy and per-request flip fraction vs keep budget. Both panels move together at 7B (accuracy falls, divergence rises as the budget tightens), reproduced on Qwen2.5 and Mistral.

#calibration #dropped-mass

Detector calibration — estimated dropped mass (label-free) vs empirical flip rate.

#trace #oracle

Divergence trace — label-free vs oracle dropped mass over decode steps; crimson lines mark greedy-token flips.

Figures are from the authoritative study_a_0.5b_v2 run. The superseded runs' figures are retained in their directories for provenance but must not be quoted: their cliff accuracy panel is built on the withdrawn scoring.

0.5B ROC	0.5B cliff

Study B — bound width vs verification cost + coverage

#h2 #hoeffding #empirical-bernstein #betting-cs

Width vs cost — anytime-valid bound width against probe rate / throughput cost. Coverage gates which estimators may support a verdict.

Coverage audit — anytime miss rate by regime. Capital-process (betting) estimators fail under bursty drift; Hoeffding / EB remain valid.

Study C — elastic scheduling (discrete-event simulation)

#h3 #elastic #tpot #simulation

Elastic vs inline vs none — under load, elastic keeps TPOT near the no-verification baseline while the confidence bound widens; inline pays latency.

Ablations

#ablation-2 #verification-rate · #ablation-3 #adaptive-sampling

Verification rate 0→100% — recovers unverified sparse and full-dense endpoints	Fixed vs adaptive at equal probe cost — value of Mechanism 1 to Mechanism 2

#ablation-5 #transfer #cross-model

Detector transfer by task family	Detector transfer by keep budget

#ablation-6 #layer-schedule #pyramid

Per-layer budget schedules at matched mean keep fraction — fidelity differs by schedule; the label-free detector still transfers across allocators.

---

Repository layout

csa/                  # Core library
  sparse.py           # Block selection, gather path, schedules
  signals.py          # Label-free + oracle signals
  detector.py         # Combined logistic detector, grouped CV
  verify.py           # Confidence sequences + HT sampling
  scheduler.py        # Elastic verification simulator
  paired.py           # HF AttentionInterface harness
  analysis.py         # Shared Study A analysis (do not fork)
  tasks.py            # Synthetic long-context tasks
  recording.py        # Machine fingerprint + CSV discipline

experiments/          # Study / ablation drivers
tests/                # 60 unit tests (pytest)
results/              # Fingerprinted runs, figures, REPORT
docs/                 # Serving RFC draft

Recording discipline: online-aggregated per-step scalars only — never raw attention tensors. Every run ships a machine fingerprint (GPU, driver, power limit, PCIe, library versions).

---

Quick start

python -m pip install -e ".[dev]"
python -m pytest tests -q
python experiments/smoke_check.py

Requirements: Python ≥ 3.10, PyTorch ≥ 2.2 with CUDA (CPU works for unit tests; sweeps need a GPU). Use python -m pip so installs land in the same interpreter that runs the code.

---

Reproduce studies

Study	Command	Outputs
A (H1/H4)	python experiments/study_a_smoke.py --model Qwen/Qwen2.5-1.5B-Instruct --out results/study_a_1.5b_v2	steps.csv, requests.csv, figures, summary.json
A analysis	python experiments/analyze_study_a.py results/study_a_0.5b_v2 results/study_a_1.5b_v2	Rewrites summary.json + figures
B (H2)	python experiments/study_b_estimators.py	Width–cost curves, coverage audit
C (H3)	python experiments/study_c_scheduler.py	Elastic vs inline load sweep
Ablations 1–5	python experiments/ablations.py	Signal isolation, rate sweep, transfer
Ablation 6	python experiments/ablation6_layer_budget.py	Layer-schedule composition
Overhead	python experiments/overhead_bench.py	Probe/sparse cost ratio r
Tables	python experiments/make_tables.py --out results/TABLES.md	Paste-ready markdown tables

Sparse methods: quest_topk, mean_topk, local_sink. Layer schedules: uniform, pyramid, inv_pyramid (budget-matched by construction).

Tasks: multi-entity tracking, multi-hop chains, coreference, multi-step reasoning, longform — chosen for known sparse-attention failure modes (not NIAH-only).

---

Status and roadmap

Phase	Scope	Status
L — local smoke	0.5B + 1.5B @ 1–2K on T1000; Studies A/B/C + ablations	Done — see REPORT.md
R1 — Gate 1	7B @ 16K–32K on 2× H100; scale transfer	H1/H4 confirmed at n=60 (GATE1_AGGREGATION.md). Remaining: larger models (disk-blocked at 24 GB), a second architecture, and published baselines
R2 — Gate 2	Production probe-rate overhead on characterized host	Pending
R3 — Gate 3	Elastic probes inside vLLM	Pending
F — final	Full matrix, paper, upstream RFC → PR	Pending

Smoke-scale hardware is not the regime where sparse attention pays (KV-bandwidth-bound 8B+ at long context). Threats to validity are enumerated in METHODOLOGY.md before results were interpreted.

---

Skills and stack

PyTorch · Hugging Face Transformers · selection-based sparse attention (Quest-style block scoring) · anytime-valid confidence sequences (Hoeffding, empirical-Bernstein, betting martingales) · Horvitz–Thompson inverse-propensity weighting · grouped cross-validation · discrete-event GPU scheduling · experimental methodology for LLM systems research.

---

Citation

If you use this code or the paired dense/sparse traces, please cite the repository and link the run fingerprint from the relevant *.meta.json.

@software{certified_sparse_attention,
  title        = {Certified Sparse Attention: Runtime-Verified Fidelity for Sparse-Attention LLM Serving},
  author       = {Archana Chetan},
  year         = {2026},
  url          = {https://github.com/ArchanaChetan07/sparse-attention},
  note         = {Smoke-scale results on Qwen2.5-0.5B/1.5B; see results/REPORT.md}
}

---

License and contact

See the repository for license terms. Issues and discussion welcome via GitHub. Upstream serving integration design: docs/RFC-runtime-fidelity-verification.md.