Certified Sparse Attention via Perturbed Retrieval
Sparse attention speeds up long-context decoding by reading few keys of the KV cache, but existing methods do not control the error of a query, and on real KV caches their errors have heavy tails. We show that perturbing the score of every key with an independent Exp(1) variable turns threshold retrieval into sampling keys with probability proportional to their attention weights. Lowering the threshold along a geometric grid gives nested samples, a Horvitz--Thompson estimate of the output at every level, and confidence bounds that hold simultaneously over all levels, so each head stops at the first level whose certificate meets the target error $\varepsilon$. With fresh perturbations at e...
| Authors | Runguo Li |
|---|---|
| Primary category | cs.LG |
| Published | 18 October 2026 |
| Last updated at source | 18 October 2026 |
Popularity, last 4 days
0 now. Counts as reported by the source, snapshotted daily by Silytics.
Silytics shows public metadata from arXiv and links to the original. Information may be incomplete or out of date. Last refreshed 23 October 2026. Licenses and terms of the original apply to the work itself. Not financial, legal or professional advice.