mlsanityData to 14 Oct 2026

A Mathematical Theory of Top-k Sparse Attention via Total Variation Distance

arXiv 2512.07647 ↗First posted 8 Dec 2025cs.LG cs.AIcited by 4

Not on the map. Why?

Abstract (arXiv)

We develop a unified mathematical framework for certified Top-k attention truncation that quantifies approximation error at both the distribution and output levels. For a single attention distribution P and its Top-k truncation hat P, we show that the total-variation distance coincides with the discarded softmax tail mass and satisfies TV(P,hat P)=1-e-KL(hat PVert P), yielding sharp Top-k-specific bounds in place of generic inequalities. From this we derive non-asymptotic deterministic bounds -- from a single boundary gap through multi-gap and blockwise variants -- that control TV(P,hat P) using only the ordered logits. Using an exact head-tail decomposition, we prove that the output error factorizes as |Attn(q,K,V)-Attnk(q,K,V)|2=τ|μtail-μhead|2 with τ=TV(P,hat P), yielding a new head-tail diameter bound |Attn(q,K,V)-Attnk(q,K,V)|2≤τ,diamH,T and refinements linking the error to VarP(V). Under an i.i.d. Gaussian score model si~mathcal N(μ,σ2) we derive closed-form tail masses and an asymptotic rule for the minimal k_varepsilon ensuring TV(P,hat P)≤varepsilon, namely k_varepsilon/n≈Phic(σ+Phi-1(varepsilon)). Experiments on bert-base-uncased and synthetic logits confirm the predicted scaling of k_varepsilon/n and show that certified Top-k can reduce scored keys by 2-4× on average while meeting the prescribed total-variation budget.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 20 of its 28 references that are in the map. First posted on arXiv 8 Dec 2025.

Builds on

20 of 28 references.

References · 20

  1. 2017Attention Is All You Needcited by 60,361
  2. 2022FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awarenesscited by 3,673
  3. 2020Longformer: The Long-Document Transformercited by 3,413
  4. 2020Big Bird: Transformers for Longer Sequencescited by 1,684
  5. 2020Reformer: The Efficient Transformercited by 1,668
  6. 2020Rethinking Attention with Performerscited by 1,601
  7. 2019Generating Long Sequences with Sparse Transformerscited by 1,546
  8. 2025DeepSeek-V3.2: Pushing the Frontier of Open Large Language Modelscited by 815
  9. 2024Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inferencecited by 501
  10. 2020Efficient Content-Based Sparse Attention with Routing Transformerscited by 471
  11. 2021Nystr"omformer: A Nystr"om-Based Algorithm for Approximating Self-Attentioncited by 471
  12. 2025Native Sparse Attention: Hardware-Aligned and Natively Trainable Sparse Attentioncited by 407
8 more
  1. 2021Random Feature Attentioncited by 354
  2. 2024InfiniGen: Efficient Generative Inference of Large Language Models with Dynamic KV Cache Managementcited by 245
  3. 2025MoBA: Mixture of Block Attention for Long-Context LLMscited by 198
  4. 2024InfLLM: Training-Free Long-Context Extrapolation for LLMs with an Efficient Context Memorycited by 197
  5. 2024Loki: Low-rank Keys for Efficient Sparse Attentioncited by 89
  6. 2021Memory-efficient Transformers via Top-k Attentioncited by 60
  7. 2025HATA: Trainable and Hardware-Efficient Hash-Aware Top-k Attention for Scalable Large Model Inferencecited by 7
  8. 2025vAttention: Verified Sparse Attentioncited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 4.

4 papers.

  1. 2026Runtime-Certified Bounded-Error Quantized Attentioncited by 4
  2. 2026LOCKS: Page-Local Compact Key Summaries for Efficient Long-Context Decodingcited by 1
  3. 2026Trust the Mass: Forced Weights in KV-Cache Evictioncited by 1
  4. 2026CompKV: Compensation-Aware KV Selection for Long-Context LLM Inferencecited by 1