Certified sparse attention speeds up long text processing with error guarantees
Certified Sparse Attention via Perturbed Retrieval
Machine LearningComputation and Language
Summary
Processing long pieces of text with attention models takes a lot of time because the model reads many parts of the text. This paper shows how to speed this up by carefully sampling parts to read while mathematically guaranteeing that the error stays low. The authors introduce a way to estimate attention using a probabilistic method that reads fewer parts but still gives reliable results with a confidence certificate. Their method works well on very long texts and performs better than existing approaches while running faster on CPUs.
What this means in practice
- •For large language model engineers: Implement efficient decoding of extremely long input sequences with guaranteed error bounds to reduce runtime and memory use.
- •For cpu-based ai infrastructure teams: Deploy faster long-text inference on CPUs by using certified sparse attention methods that outperform dense attention in speed and error tradeoffs.
Authors
Runguo Li
Abstract
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 every decoding step, each certificate fails with probability at most $δ$ during generation. At a suitable threshold, the estimator reads $O(\varepsilon^{-2}\log(1/δ))$ values regardless of the context length, and no adaptive method reads fewer, up to constants. A 4-bit scan with deterministic bounds, shared across a grouped-query-attention group, generates the candidates exactly but reads every key. On three LLMs and ten settings at 16K--128K tokens, no certificate is violated, and at equal keys read our 90th-percentile error is 4.6--7.9$\times$ lower than that of the best of 15 baseline families. At equal bytes, the best baselines have 0.6--1.6 times our 90th-percentile error and at least 4.9 times our largest. End to end, our method stays within one point of dense attention on tasks and within 0.1\% in PG-19 perplexity, and the strongest baselines at equal bytes score as well. On CPU, decoding steps at 32K--128K tokens run 1.1--1.4$\times$ faster than dense attention on the same 16-bit cache.