Twilight: Adaptive Attention Sparsity with Hierarchical Top-p Pruning

Chaofan Lin, Jiaming Tang, Shuo Yang, Hanshuo Wang, Tian Tang, Boyu Tian, Ion Stoica, Song Han, Mingyu Gao

Abstract

Large Language Models (LLMs) face significant memory and latency bottlenecks due to the growing size of the Key-Value (KV) cache in long-context scenarios. While sparse attention methods mitigate this by selecting a subset of important tokens, existing approaches typically rely on a fixed-token budget (top-$k$), which fails to account for the dynamic nature of attention distributions across different heads and layers. We present Twilight, a framework that introduces adaptive budget capabilities through hierarchical top-$p$ pruning. By leveraging a 4-bit quantized importance estimation and a parallel-friendly threshold search, Twilight adaptively prunes up to 98% of tokens. Our evaluations demonstrate a 1.4× speedup over state-of-the-art sparse attention methods and up to 15.8× over full attention, maintaining high accuracy across diverse long-context benchmarks.

Introduction

As Large Language Models scale to support massive context windows exceeding one million tokens, the Key-Value (KV) cache has become a primary bottleneck for inference. The standard attention mechanism requires loading the entire KV cache from memory for every new token generated, a process that is heavily memory-bandwidth bound. This leads to high latency and increased operational costs for long-context applications like document summarization and complex reasoning.

To address this, researchers have turned to "sparse attention," which identifies and computes attention only for a subset of "important" tokens. However, most contemporary sparse attention methods utilize a fixed-token budget ($k$). This approach is inherently limited because attention distributions are highly dynamic and non-uniform across different layers, heads, and prompts.

The Problem: Fixed Budgets in a Dynamic World

The authors identify a fundamental flaw in fixed-budget (top-$k$) strategies: they cannot adapt to the varying density of attention.

  • Focused Attention: Some attention heads concentrate their weight on just a few "heavy hitter" tokens. In these cases, a fixed budget $k$ leads to over-selection, where the system performs unnecessary computations on tokens that contribute negligible weight.
  • Diffuse Attention: Other heads spread attention across a wide range of tokens. Here, a fixed budget leads to under-selection, causing significant accuracy loss because critical information is pruned away.
Figure 1: Comparison of fixed-budget top-k sparsity versus adaptive top-p sparsity.

Twilight addresses this by replacing the fixed budget with a threshold-based pruning strategy (top-$p$), similar to nucleus sampling used in LLM decoding. By keeping the minimum number of tokens required to reach a cumulative attention weight threshold (e.g., $p=0.9$), the system dynamically adjusts its workload to match the complexity of the attention distribution.

The Twilight Framework

Twilight introduces a hierarchical Select-then-Prune architecture designed to be both efficient and easy to integrate into existing serving stacks. The process consists of three main stages:

  1. Token Selector: Twilight treats existing sparse attention algorithms (such as Quest or H2O) as a coarse-grained "black box" selector. This step identifies a relatively large, conservative subset of potentially important tokens.
  2. Twilight Pruner: This is the core innovation. To minimize memory overhead, the pruner estimates the importance of the selected tokens using a 4-bit quantized K cache. It then applies top-$p$ pruning. To make this efficient on GPUs, the authors developed a parallel-friendly binary search to find the top-$p$ threshold without the need for expensive sorting.
  3. Sparse Attention Kernel: Finally, a high-precision attention calculation is performed using the refined, much smaller set of tokens. This stage utilizes custom Sparse GEMV (SpGEMV) kernels to maximize throughput.

Key Insights and Theoretical Foundations

The shift from top-$k$ to top-$p$ is not just an empirical heuristic; it is grounded in the realization that the problem of choosing an attention budget is identical to the problem of choosing a word generation budget during decoding. Furthermore, top-$p$ pruning provides a theoretical upper bound on the approximation error, offering a more robust mathematical guarantee for model performance than fixed-budget methods.

Empirical testing revealed that 4-bit quantization is the "sweet spot" for importance estimation. While 2-bit quantization proved too noisy for accurate top-$p$ thresholding, 8-bit quantization did not offer sufficient speedup to justify the memory bandwidth usage.

Experimental Results

Twilight was evaluated across a diverse range of benchmarks, including Longbench (summarization, QA), RULER (retrieval), and PG-19 (language modeling). The results highlight significant gains in both efficiency and accuracy.

Figure 2: Perplexity vs. Token Budget, showing how adaptive methods approach full-attention performance more efficiently than fixed-budget methods like Quest.
  • Performance: Twilight achieves up to a 15.8× speedup for the self-attention operator compared to FlashAttention-2. When integrated with existing sparse methods like Quest, it provides an additional 1.4× speedup.
  • Efficiency: In long-context scenarios, the framework adaptively prunes up to 98% of tokens without sacrificing accuracy. In real-world decoding, this translates to a 1.35× end-to-end latency reduction.
  • Accuracy: On Longbench, Twilight actually improved scores for some base algorithms by up to +5.7%. This is attributed to its ability to dynamically allocate more budget to difficult "diffuse" heads while saving resources on "focused" ones.

Conclusion

Twilight demonstrates that adaptive sparsity is a critical component for scaling LLM inference to massive context lengths. By moving beyond fixed budgets and leveraging hierarchical pruning with low-bit quantization, Twilight offers a path toward highly efficient, long-context AI without the accuracy trade-offs typical of previous sparse attention methods. Future work will look into even lighter-weight estimation methods and better compatibility with Group Query Attention (GQA) and newer architectures like Multi-head Latent Attention (MLA).

Summary updated

BibTeX
@inproceedings{lin2025twilight,
  author = {Chaofan Lin and Jiaming Tang and Shuo Yang and Hanshuo Wang and Tian Tang and Boyu Tian and Ion Stoica and Song Han and Mingyu Gao},
  title = {{Twilight: Adaptive Attention Sparsity with Hierarchical Top-p Pruning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=Ve693NkzcU},
}
Figure