ProxyAttn: Guided Sparse Attention via Representative Heads

Yixuan Wang, Huang He, Siqi Bao, Haifeng Wang, Qingfu Zhu, Wanxiang Che · 2025

Read ProxyAttn: Guided Sparse Attention via Representative Heads by Yixuan Wang, Huang He, Siqi Bao, Haifeng Wang, Qingfu Zhu, Wanxiang Che (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-24745.txt.

Introduction

Yixuan Wang and co-authors propose ProxyAttn, a sparse attention method that uses representative heads to guide which blocks to compute. Their 2025 paper deals with the quadratic cost of attention, which limits large language models on long texts.

Dynamic methods estimate block importance to enable sparse attention, but coarse estimates degrade quality at high sparsity. Attention heads often behave alike, so the method pools a few representative heads and uses their scores to approximate all heads. A block-aware dynamic budget method accounts for heads differing in sparsity. The approach needs no training. Combined, the two ideas aim at precise block selection and faster long-text pre-filling.

Catalog record

CREATORYixuan Wang, Huang He, Siqi Bao, Haifeng Wang, Qingfu Zhu, Wanxiang Che
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE39 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-24745

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

ProxyAttn: Guided Sparse Attention via Representative Heads Yixuan Wang, Huang He, Siqi Bao, Haifeng Wang, Qingfu Zhu, Wanxiang Che Abstract The quadratic complexity of attention mechanisms limits the efficiency of Large Language Models (LLMs) on long-text tasks. Recently, methods that dynamically estimate block importance have enabled efficient block sparse attention, leading to significant acceleration in long-text pre-filling of LLMs. However, their coarse-grained estimation inevitably leads to performance degradation at high sparsity rates. In this work, we propose ProxyAttn , a training-free sparse attention algorithm that achieves more precise block estimation by compressing the dimension of attention heads. Based on our observation of the similarity among multiple attention heads, we use the scores of pooled representative heads to approximate the scores for all heads. To account for the varying sparsity among heads, we also propose a block-aware dynamic budget estimation method. By combining the scores from representative proxy heads with multi-head dynamic budgets, we achieve a more fine-grained block importance evaluation at low computational cost. Experiments on a variety of mainstream models and extensive benchmarks confirm the underlying similarity among attention heads. Leveraging a fine-grained estimation, the proposed method achieves substantial gains in performance and efficiency compared to existing methods. More precisely, ProxyAttn can achieve up to 10.3x attention acceleration and 2.4x prefilling acceleration without significant performance loss. Our code is available at https://github.com/wyxstriker/ProxyAttn . 1 Introduction Large Language Models (LLMs) have shown outstanding performance in long context tasks ( Liu et al. 2025a ; Liu et al. 2025b ) and are widely applied in fields such as code generation ( Jimenez et al. 2023 ; Hui et al. 2024 ) and mathematical reasoning ( Chen et al. 2025 ; Guo et al. 2025 ) . However, transformer-based LLMs face efficiency limitations when processing long texts with millions of tokens. The quadratic complexity of the attention mechanism poses a significant challenge to the inference of models. Recently, numerous studies ( Brauwers & Frasincar 2021 ; Zhang et al. 2025 ) have worked on refining the attention module to increase the training and inference efficiency. In particular, sparse attention methods mitigate the latency issues of the attention mechanism by skipping certain computations. By leveraging the inherent sparsity ( Liu et al. 2022 ; Deng et al. 2024 ) of attention score distributions, these methods can reduce computational costs while preserving model performance. Some static methods ( Beltagy et al. 2020 ; Zaheer et al. 2020 ) use heuristic fixed templates to achieve sparse computation, making it difficult to maintain model performance with diverse attention patterns ( Likhosherstov et al. 2021 ) . To achieve a more accurate estimation, many efforts have focused on exploring various low-cost method to assess the importance of tokens, which in turn enables the dynamic sparse patterns. The performance of hardware-friendly sparse attention, which is typically handled at the block level ( Guo et al. 2024 ) , is heavily dependent on the efficiency and accuracy of its importance estimation. MInference ( Jiang et al. 2024 ) leverages multiple pre-defined templates and an online computed index to guide the construction of block sparse patterns. Furthermore, FlexPrefill ( Lai et al. 2025 ) proposes an input-aware approach that dynamically determines the sparse patterns and sparsity rates. While existing methods have proven effective in long-context scenarios, their performance at high sparsity rates is still limited by their coarse-grained importance estimation . To evaluate the importance of each block, these methods typically compress along the sequence dimension to approximate their attention scores. This coarse-grained compression can cause a few high-scoring positions to be overlooked, which in turn impacts the final performance. A token-level dot-product calculation would solve this issue but is not feasible, as its time complexity scales identically to full attention. In this paper, we achieve a fine-grained and efficient trade-off in block importance estimation by exploring compression of the attention head dimension. We begin by analyzing the performance of multi-head attention on long sequences, where we observed two primary characteristics of how the heads behave: (1) The overall attention trends of different heads are consistent. (2) The primary differences between heads lie in their sparsity. Based on these findings, we propose ProxyAttn , a training-free sparse attention algorithm that approximates attention scores using a few representative heads. Specifically, we leverage the similarity among attention heads to approximate the full attention scores using the complete scores from a few pooled heads. By incorporating max pooling, our proposed method enables more accurate block importance estimation while ensuring efficiency. Furthermore, given the significant differences in head sparsity, we propose an online block-aware budget estimation method. By integrating the unified importance score with head-level budget, we can achieve diverse sparse attention patterns across different heads. Figure 1: Performance and speedup results of different sparse attention methods on RULER. In order to evaluate our proposed method, we conduct a series of extensive experiments. We use widely-adopted LLMs that are specifically designed for long-context tasks like Llama3.1-8B-Instruct ( Grattafiori et al. 2024 ) and Qwen2.5-7B-Instruct-1M ( Yang et al. 2025 ) , along with a variety of mainstream benchmarks such as RULER ( Hsieh et al. 2024 ) , InfiniteBench ( Zhang et al. 2024 ) , and LongBench-v2 ( Bai et al. 2024a ; Bai et al. 2024b ) . Experimental results show that ProxyAttn significantly outperforms other methods on both synthetic and real-world datasets. As illustrated in Figure 1 , the proposed ProxyAttn achieves a Pareto front for performance and efficiency compared to other coarse-grained estimation methods. Our contributions can be summarized as follows: • We introduce ProxyAttn, a training-free sparse attention estimation method. It leverages the attention scores from a small number of proxy heads to efficiently estimate the scores for all heads, achieving more accurate importance measures. • Considering the diverse sparsity among heads, we propose a block-aware budget allocation method. Coupled with the unified importance score, our method can provide different head sparsity budgets online, which in turn yields diverse sparse attention masks. • Extensive experiments demonstrate that the proposed ProxyAttn outperforms other coarse-grained sparse attention methods across various model architectures and benchmarks. Our approach yields a maximum 10.3x speedup for attention computation without significant performance loss. 2 Observation 2.1 Motivation Recent work ( Jiang et al. 2024 ; Lai et al. 2025 ; Gao et al. 2024 ) on the importance of different attention blocks typically employs heuristic “vertical and slash” patterns or pooling methods along the sequence dimension for approximation. These methods either rely on specific heuristic template assumptions or opt for a coarse-grained estimation, rendering the importance measures of blocks inaccurate ( Xu et al. 2025 ) . Given the inherent sparsity of attention distributions, such coarse-grained pooling can easily overlook a few high-scoring positions. A viable approach for both accuracy and efficiency in token-level dot-product computations is to compress along the head num dimension instead of the sequence dimension. This allows a few key heads to serve as proxies for estimating the importance of all heads. However, the feasibility of this approach hinges on the assumption that attention heads exhibit a certain degree of consistency in their scores. To validate this hypothesis, we conduct some observational studies on the behaviors of multiple heads in a long-context

Read the complete text