Twilight: Adaptive Attention Sparsity with Hierarchical Top-Pruning

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

TL;DR

This paper introduces "Twilight," a novel framework that enhances existing sparse attention mechanisms in Large Language Models (LLMs) by dynamically adapting the number of tokens processed. By leveraging the principles of top-p sampling, Twilight achieves significant speedups (up to 15.4x for self-attention) with minimal accuracy loss, addressing a critical limitation of current fixed-budget sparse attention methods.

What Problem Does This Paper Address?

Long-context LLMs are revolutionizing NLP, enabling applications like document summarization and complex reasoning. However, their computational and memory demands, primarily from the attention mechanism and the growing Key-Value (KV) cache, are substantial. To mitigate this, attention sparsity techniques have been developed, which aim to compute attention on a subset of "critical" tokens. The main challenge with existing methods, often based on top-k selection, is their reliance on a fixed budget of tokens. This static approach is problematic in real-world scenarios where the optimal number of tokens to consider varies dynamically based on the input, the model's internal state, and the specific attention head. This can lead to either "over-selection" (processing more tokens than necessary, wasting computation) or "under-selection" (missing important tokens, degrading accuracy).

Methods

The core innovation of Twilight is the introduction of top-p sampling (also known as nucleus sampling) to the domain of sparse attention. Instead of selecting a fixed number of top-k tokens, Twilight selects tokens whose cumulative attention weights exceed a certain probability threshold p. This allows the number of selected tokens to adapt dynamically to the distribution of attention weights.

Twilight is implemented as a hierarchical, select-then-prune framework:

  1. Token Selector: This component acts as a black-box wrapper around existing sparse attention algorithms. It uses the base algorithm's logic but with a conservative, larger budget to ensure that most potentially important tokens are initially captured.
  2. Twilight Pruner: This is the novel part. It takes the tokens selected by the Token Selector and applies top-p sampling to further prune them down to a minimal set that meets the cumulative attention weight threshold p. This adaptive pruning is the key to efficiency and accuracy preservation.
  3. Sparse Attention Kernel: The final attention computation is performed only on the top-p pruned tokens.

To further optimize performance, Twilight also incorporates 4-bit quantization of the KV cache and efficient SpGEMV (Sparse General Matrix-Vector Multiplication) kernel implementations, leveraging techniques like FlashInfer.

Datasets

The paper evaluates Twilight on several benchmarks:

  • Long-context: Longbench (a collection of 12 diverse tasks), RULER (specialized tests for non-retrieval accuracy).
  • Medium-context: GSM8K (math reasoning), COQA (question answering), and PG-19 (perplexity).

Key Insights and Ideas

  • Top-p Sampling for Adaptive Budgeting: The paper's central insight is that top-p sampling, a successful technique in LLM text generation, can be effectively adapted to sparse attention. This allows for dynamic budget allocation, unlike the rigid top-k approach.
  • Dynamic Nature of Attention Weights: The authors highlight that attention weight distributions vary significantly across different prompts, queries, layers, and heads. This inherent dynamism is the root cause of the over/under-selection problem with fixed budgets.
  • Select-then-Prune Architecture: This hierarchical approach allows Twilight to leverage the strengths of existing sparse attention algorithms while enhancing them with adaptive pruning, making it a general framework.
  • 4-bit Quantization as a Sweet Spot: Empirically, the authors found that 4-bit quantization of the KV cache strikes a good balance between accuracy and efficiency for top-p attention, significantly reducing memory bandwidth.

Key Results

  • Accuracy: Twilight achieves nearly zero accuracy loss (<1%) on various benchmarks, even when pruning up to 98% of tokens. It also demonstrates performance improvements over baseline methods in some cases.
  • Efficiency:
    • Self-Attention Speedup: Twilight provides up to 15.4x speedup for the self-attention operator compared to full attention.
  • End-to-End Decoding Speedup: It achieves up to 3.9x speedup in end-to-end per-token latency during decoding.
  • Over Base Algorithms: Twilight offers an additional 1.4x speedup over existing sparse attention methods like Quest.
  • Generalizability: The framework is shown to be effective when applied to different base sparse attention algorithms (e.g., Quest, DS) and various LLM architectures (e.g., Longchat, LLaMA).

Limitations and Future Work

  • Estimation Overheads: While Twilight significantly reduces computation, the paper acknowledges non-negligible estimation overheads, particularly in scenarios with small batch sizes or when token loading costs are not dominant.
  • Group Query Attention (GQA) Integration: The head-wise dynamism of Twilight is inherently incompatible with GQA's group-wise structure. While a solution is proposed (union of tokens for a group), it leads to some inefficiencies.
  • Future Work: The authors suggest optimizing the estimation method for further latency and throughput improvements. They also propose exploring integration with other model architectures like multi-head latent attention (MLA).

Summary updated

Abstract

Leveraging attention sparsity to accelerate long-context large language models (LLMs) has been a hot research topic. However, current algorithms such as sparse attention or key-value (KV) cache compression tend to use a fixed budget, which presents a significant challenge during deployment because it fails to account for the dynamic nature of real-world scenarios, where the optimal balance between accuracy and efficiency can vary greatly. In this paper, we find that borrowing top-$p$ sampling (nucleus sampling) to sparse attention can surprisingly achieve adaptive budgeting. Based on this, we propose Twilight, a framework to bring adaptive sparsity to any existing sparse attention algorithm without sacrificing their accuracy. Empirical results show that Twilight can adaptively prune at most 98% of redundant tokens, leading to $15.4\times$ acceleration in self-attention operations and $3.9\times$ acceleration in end-to-end per token latency in long context LLM decoding.
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-Pruning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=Ve693NkzcU},
}
Figure