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

Georgios Tzachristas, Lei Deng, Ioannis Tzachristas, Gong Zhang, Renhai ChenarXiv 2025 · DOI · arXiv

Abstract

The quadratic complexity of the attention mechanism remains a primary bottleneck for scaling Transformers to long context windows. Top-k sparse attention is a common heuristic to mitigate this, yet it lacks rigorous error guarantees. This paper introduces a unified mathematical framework for "certified" Top-k sparse attention. By establishing an exact identity between Total Variation (TV) distance and KL divergence for truncated softmax distributions, we provide a foundation for rigorous error bounds. We introduce two adaptive algorithms, $\Delta_k$-Search and MC-Search, which dynamically select the number of keys to maintain a user-defined accuracy level. Empirical evaluations on BERT and synthetic datasets demonstrate that our approach can reduce computation by 2–4× on average, and up to 120× on specific heads, while providing formal safety guarantees.

1. Introduction

As context windows in modern Transformer models expand to hundreds of thousands of tokens, the $O(n^2)$ complexity of the attention mechanism becomes a critical bottleneck. Top-k sparse attention—retaining only the $k$ largest attention scores—is a popular strategy to improve efficiency. However, choosing $k$ has traditionally been a heuristic process. A fixed $k$ may be too small, leading to significant information loss, or too large, wasting computational resources. This work addresses the lack of formal error quantification in Top-k truncation, providing a "mathematical safety net" for sparse attention.

2. Theoretical Framework

The core of our approach lies in analyzing Top-k truncation through probability and geometry. We define the notation used throughout our derivations in Table 1.

Table 1: Summary of notation and symbols used in the mathematical framework.

A key contribution is the proof of a "sharp" identity relating the Total Variation (TV) distance between the full softmax distribution $P$ and its Top-k truncated version $\hat{P}$ to the KL divergence:

$$TV(P, \hat{P}) = 1 - e^{-KL(\hat{P} \parallel P)}$$

This identity is more precise than standard bounds like Pinsker’s inequality. Crucially, we show that the TV distance is exactly equal to the "tail mass"—the sum of the discarded probabilities.

Furthermore, we demonstrate that the error in the final attention output depends not only on the attention weights but also on the geometry of the Value matrix ($V$). Through a "head-tail decomposition," we prove that if value vectors are clustered (low diameter), the mechanism is more robust to aggressive truncation.

3. Certified Selection Algorithms

We propose two practical algorithms to dynamically determine the optimal $k$ for a given error budget $\epsilon$:

  • $\Delta_k$-Search: This algorithm utilizes the "boundary score gap" $\Delta_k = s_k - s_{k+1}$ to certify the error.
  • MC-Search: A more adaptive "mass-based" approach that terminates the scoring process once it can be proven that the discarded tail mass is below $\epsilon$.

4. Experimental Evaluation

We validated our framework using bert-base-uncased on WikiText-2 and synthetic Gaussian logits for long-context scaling (up to $n=16,384$).

4.1 Efficiency and Precision

Our certified algorithms achieved an average 2–4× reduction in scored keys on BERT. On specific "peaked" heads, speedups reached 14× to 120×. Under a Gaussian model, our theory predicted the required $k$ with 0.1% accuracy for standard logit variances.

4.2 Scaling and Safety

Unlike fixed-$k$ methods where error spikes with sequence length, our adaptive methods maintained a constant, guaranteed error level across all context lengths. This confirms that to maintain a constant error $\epsilon$, the number of keys $k$ must scale linearly with the sequence length $n$, a design rule derived from our Gaussian probabilistic model.

5. Discussion and Limitations

While providing a rigorous foundation, our current analysis assumes independent and identically distributed (i.i.d.) Gaussian attention scores. Real-world distributions often exhibit correlations and heavier tails. Future work will explore extending this framework to multi-query regimes and training models to inherently possess larger score gaps to facilitate even more aggressive sparsification.

Summary updated

BibTeX
@misc{tzachristas2025mathematical,
  author = {Georgios Tzachristas and Lei Deng and Ioannis Tzachristas and Gong Zhang and Renhai Chen},
  title = {{A Mathematical Theory of Top-k Sparse Attention via Total Variation Distance}},
  year = {2025},
  eprint = {2512.07647},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2512.07647},
}
Figure