Multipole Attention for Efficient Long Context Reasoning

• URL: http://arxiv.org/abs/2506.13059v1
• Date: Mon, 16 Jun 2025 03:00:40 GMT
• Title: Multipole Attention for Efficient Long Context Reasoning
• Authors: Coleman Hooper, Sebastian Zhao, Luca Manolache, Sehoon Kim, Michael W. Mahoney, Yakun Sophia Shao, Kurt Keutzer, Amir Gholami,
• Abstract summary: Large Reasoning Models (LRMs) have shown promising accuracy improvements on complex problem-solving tasks.<n>LRMs need to generate long chain-of-thought reasoning in order to think before answering.<n>We introduce Multipole Attention, which accelerates autoregressive reasoning by only computing exact attention for the most important tokens.
• Score: 64.94673641704289
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Large Reasoning Models (LRMs) have shown promising accuracy improvements on complex problem-solving tasks. While these models have attained high accuracy by leveraging additional computation at test time, they need to generate long chain-of-thought reasoning in order to think before answering, which requires generating thousands of tokens. While sparse attention methods can help reduce the KV cache pressure induced by this long autoregressive reasoning, these methods can introduce errors which disrupt the reasoning process. Additionally, prior methods often pre-process the input to make it easier to identify the important prompt tokens when computing attention during generation, and this pre-processing is challenging to perform online for newly generated reasoning tokens. Our work addresses these challenges by introducing Multipole Attention, which accelerates autoregressive reasoning by only computing exact attention for the most important tokens, while maintaining approximate representations for the remaining tokens. Our method first performs clustering to group together semantically similar key vectors, and then uses the cluster centroids both to identify important key vectors and to approximate the remaining key vectors in order to retain high accuracy. We design a fast cluster update process to quickly re-cluster the input and previously generated tokens, thereby allowing for accelerating attention to the previous output tokens. We evaluate our method using emerging LRMs such as Qwen-8B, demonstrating that our approach can maintain accuracy on complex reasoning tasks even with aggressive attention sparsity settings. We also provide kernel implementations to demonstrate the practical efficiency gains from our method, achieving up to 4.5$\times$ speedup for attention in long-context reasoning applications. Our code is available at https://github.com/SqueezeAILab/MultipoleAttention.

Related papers

• TokenSqueeze: Performance-Preserving Compression for Reasoning LLMs [57.217593337454026]
  TokenSqueeze is a novel Long2Short method that condenses reasoning paths while preserving performance and relying exclusively on self-generated data.<n>We show that TokenSqueeze reduces token usage while maintaining accuracy on the MATH500 benchmark.
  arXiv  Detail & Related papers  (2025-11-17T10:38:56Z)
• DELTA: Dynamic Layer-Aware Token Attention for Efficient Long-Context Reasoning [6.468843780300177]
  We present textbfDELTA, a training-free sparse attention mechanism that achieves computational efficiency without sacrificing model accuracy.<n>Our results show that selective reuse of intermediate attention maps offers a robust path toward efficient long-context reasoning.
  arXiv  Detail & Related papers  (2025-10-10T21:37:49Z)
• Less Is More: Training-Free Sparse Attention with Global Locality for Efficient Reasoning [12.808478519221577]
  We introduce LessIsMore, a training-free sparse attention mechanism for reasoning tasks.<n>LessIsMore aggregates token selections from local attention heads with recent contextual information.<n>It achieves a $1.13times$ end-to-end speed-up compared to existing sparse attention methods.
  arXiv  Detail & Related papers  (2025-08-09T21:10:33Z)
• ConciseHint: Boosting Efficient Reasoning via Continuous Concise Hints during Generation [53.149817480019834]
  Recent advancements in large reasoning models (LRMs) have achieved notable performance enhancements on complex reasoning tasks by scaling up the generation length by Chain-of-Thought (CoT)<n>We propose a framework dubbed ConciseHint, which continuously encourages the reasoning model to speak concisely by injecting the textual hint during the token generation of the reasoning process.<n>Experiments on the state-of-the-art LRMs, including DeepSeek-R1 and Qwen-3 series, demonstrate that our method can effectively produce concise reasoning processes while maintaining performance well.
  arXiv  Detail & Related papers  (2025-06-23T16:20:44Z)
• Think Clearly: Improving Reasoning via Redundant Token Pruning [57.01254508252785]
  We show that deliberately removing redundancy in the reasoning process significantly improves performance.<n>We demonstrate that our method significantly improves overall accuracy across reasoning-intensive benchmarks without any training.
  arXiv  Detail & Related papers  (2025-06-17T06:04:01Z)
• Curse of High Dimensionality Issue in Transformer for Long-context Modeling [31.257769500741006]
  We propose textitDynamic Group Attention (DGA) to reduce redundancy by aggregating less important tokens during attention computation.<n>Our results show that our DGA significantly reduces computational costs while maintaining competitive performance.
  arXiv  Detail & Related papers  (2025-05-28T08:34:46Z)
• Fast Quiet-STaR: Thinking Without Thought Tokens [51.79231070632772]
  Fast Quiet STaR is a more efficient reasoning framework that preserves the benefits of token-level reasoning while reducing computational cost.<n>Our method introduces a curriculum learning based training strategy that gradually reduces the number of thought tokens.<n>Experiments on four benchmark datasets with Mistral 7B and Qwen2.5 7B demonstrate that Fast Quiet-STaR consistently outperforms Quiet-STaR in terms of average accuracy.
  arXiv  Detail & Related papers  (2025-05-23T11:14:12Z)
• Language Model Uncertainty Quantification with Attention Chain [9.093726246465117]
  Large language models' (LLM) predictive uncertainty is crucial for judging the reliability of its answers.<n>We propose UQAC, an efficient method that narrows the reasoning space to a tractable size for marginalization.<n>We validate UQAC on multiple reasoning benchmarks with advanced open-source LLMs.
  arXiv  Detail & Related papers  (2025-03-24T21:43:47Z)
• Tactic: Adaptive Sparse Attention with Clustering and Distribution Fitting for Long-Context LLMs [10.52833484759311]
  We propose Tactic, a sparsity-adaptive and calibration-free sparse attention mechanism.<n>It dynamically selects tokens based on their cumulative attention scores rather than a fixed token budget.<n>We show that Tactic outperforms existing sparse attention algorithms, achieving superior accuracy and up to 7.29x decode attention speedup.
  arXiv  Detail & Related papers  (2025-02-17T08:39:43Z)
• AttentionPredictor: Temporal Pattern Matters for Efficient LLM Inference [51.1972443343829]
  We propose AttentionPredictor, which is the first learning-based critical token identification approach.<n> AttentionPredictor accurately predicts the attention score while consuming negligible memory.<n>We also propose a cross-token critical cache prefetching framework that hides the token time overhead to accelerate the decoding stage.
  arXiv  Detail & Related papers  (2025-02-06T13:41:46Z)
• Token Assorted: Mixing Latent and Text Tokens for Improved Language Model Reasoning [44.84219266082269]
  Large Language Models (LLMs) excel at reasoning and planning when trained on chainof-thought (CoT) data.<n>We propose a hybrid representation of the reasoning process, where we partially abstract away the initial reasoning steps using latent discrete tokens.
  arXiv  Detail & Related papers  (2025-02-05T15:33:00Z)
• Squeezed Attention: Accelerating Long Context Length LLM Inference [61.787865959140994]
  We propose Squeezed Attention to accelerate applications where a large portion of the input context is fixed.<n>During inference, we compare query tokens from the user input with the centroids to predict which keys from the fixed context are semantically relevant.<n>We also present a hierarchical version of our algorithm which can reduce the complexity of attention from linear to logarithmic with respect to the fixed context length.
  arXiv  Detail & Related papers  (2024-11-14T18:54:19Z)
• RefreshKV: Updating Small KV Cache During Long-form Generation [54.00118604124301]
  We propose a new inference method, RefreshKV, that flexibly alternates between full context attention and attention over a subset of input tokens during generation.<n>Applying our method to off-the-shelf LLMs achieves comparable speedup to eviction-based methods while improving performance for various long-form generation tasks.
  arXiv  Detail & Related papers  (2024-11-08T18:57:07Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.