# Multipole Attention for Efficient Long Context Reasoning

arXiv: https://arxiv.org/abs/2506.13059 · HTML: https://mlsanity.com/paper/2506.13059/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 26 of its 38 references that are in the map.
- First posted on arXiv 16 Jun 2025.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 26 of 26)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Qwen2.5 Technical Report](https://mlsanity.com/paper/2412.15115/) (2024)
- [FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning](https://mlsanity.com/paper/2307.08691/) (2023)
- [Efficient Streaming Language Models with Attention Sinks](https://mlsanity.com/paper/2309.17453/) (2023)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [LongBench: A Bilingual, Multitask Benchmark for Long Context Understanding](https://mlsanity.com/paper/2308.14508/) (2023)
- [GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints](https://mlsanity.com/paper/2305.13245/) (2023)
- [Extending Context Window of Large Language Models via Positional Interpolation](https://mlsanity.com/paper/2306.15595/) (2023)
- [KIVI: A Tuning-Free Asymmetric 2bit Quantization for KV Cache](https://mlsanity.com/paper/2402.02750/) (2024)
- [YaRN: Efficient Context Window Extension of Large Language Models](https://mlsanity.com/paper/2309.00071/) (2023)
- [Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inference](https://mlsanity.com/paper/2406.10774/) (2024)
- [LongBench v2: Towards Deeper Understanding and Reasoning on Realistic Long-context Multitasks](https://mlsanity.com/paper/2412.15204/) (2024)
- [DuoAttention: Efficient Long-Context LLM Inference with Retrieval and Streaming Heads](https://mlsanity.com/paper/2410.10819/) (2024)
- [Llama-Nemotron: Efficient Reasoning Models](https://mlsanity.com/paper/2505.00949/) (2025)
- [Transformers are Multi-State RNNs](https://mlsanity.com/paper/2401.06104/) (2024)
- [RetrievalAttention: Accelerating Long-Context LLM Inference via Vector Retrieval](https://mlsanity.com/paper/2409.10516/) (2024)
- [Model Tells You Where to Merge: Adaptive KV Cache Merging for LLMs on Long-Context Tasks](https://mlsanity.com/paper/2407.08454/) (2024)
- [PQCache: Product Quantization-based KVCache for Long Context LLM Inference](https://mlsanity.com/paper/2407.12820/) (2024)
- [Squeezed Attention: Accelerating Long Context Length LLM Inference](https://mlsanity.com/paper/2411.09688/) (2024)
- [Tactic: Adaptive Sparse Attention with Clustering and Distribution Fitting for Long-Context LLMs](https://mlsanity.com/paper/2502.12216/) (2025)
- [GSM-Infinite: How Do Your LLMs Behave over Infinitely Increasing Context Length and Reasoning Complexity?](https://mlsanity.com/paper/2502.05252/) (2025)
- [Semantic Integrity Matters: Benchmarking and Preserving High-Density Reasoning in KV Cache Compression](https://mlsanity.com/paper/2502.01941/) (2025)
- [A2ATS: Retrieval-Based KV Cache Reduction via Windowed Rotary Position Embedding and Query-Aware Vector Quantization](https://mlsanity.com/paper/2502.12665/) (2025)
- [Fast Multipole Attention: A Scalable Multilevel Attention Mechanism for Text and Images](https://mlsanity.com/paper/2310.11960/) (2023)

## Built on by (most cited first, 14 of 14)

- [ThinKV: Thought-Adaptive KV Cache Compression for Efficient Reasoning Models](https://mlsanity.com/paper/2510.01290/) (2025)
- [Stochastic KV Routing: Enabling Adaptive Depth-Wise Cache Sharing](https://mlsanity.com/paper/2604.22782/) (2026)
- [Multipole Semantic Attention: A Fast Approximation of Softmax Attention for Pretraining](https://mlsanity.com/paper/2509.10406/) (2025)
- [S3-Attention:Attention-Aligned Endogenous Retrieval for Memory-Bounded Long-Context Inference](https://mlsanity.com/paper/2601.17702/) (2026)
- [MAC-Attention: a Match-Amend-Complete Scheme for Fast and Accurate Attention Computation](https://mlsanity.com/paper/2604.00235/) (2026)
- [Polestar: Drift-Aware Cache Calibration and Token Commitment for Efficient Inference of Diffusion LLMs](https://mlsanity.com/paper/2607.14107/) (2026)
- [LOCKS: Page-Local Compact Key Summaries for Efficient Long-Context Decoding](https://mlsanity.com/paper/2607.24555/) (2026)
- [LLM Inference in a Flash!](https://mlsanity.com/paper/2609.16161/) (2026)
- [CompKV: Compensation-Aware KV Selection for Long-Context LLM Inference](https://mlsanity.com/paper/2609.26300/) (2026)
- [KV-Kaizen: Learning Context-Adaptive Cache Compression Choices](https://mlsanity.com/paper/2609.37988/) (2026)
- [BeaconKV: Key-Value Cache Compression Guided by Beacon Queries for Efficient Large Reasoning Model Inference](https://mlsanity.com/paper/2609.04971/) (2026)
- [PQ-HSA: Reusing Product-Quantized Scores for Hybrid Sparse-Approximate Attention](https://mlsanity.com/paper/2609.33746/) (2026)
- [SANTA++: Sampling Attention through Representative Keys](https://mlsanity.com/paper/2609.35629/) (2026)
- [CommunityKV: Efficient Long-Context Decoding via Graph Partitioning](https://mlsanity.com/paper/2610.00418/) (2026)

## Abstract (arXiv)

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× speedup for attention in long-context reasoning applications. Our code is available at https://github.com/SqueezeAILab/MultipoleAttention.