Tactic: Adaptive Sparse Attention with Clustering and Distribution Fitting for Long-Context LLMs
Authors: Kan Zhu
Tian Tang
Qinyu Xu
Zhan Jin
Yile Gu
Zhichen Zeng
Rohan Kadekodi
Liangyu Zhao
Ang Li
Arvind Krishnamurthy
Baris Kasikci
Venue: ICLR 2026 Poster (2026)
Keywords: Sparse Attention
LLM
Serving
Primary area: generative models

Abstract: Long-context models are essential for many applications but face inefficiencies in loading large KV caches during decoding. Prior methods enforce fixed token budgets for sparse attention, assuming a set number of tokens can approximate full attention. However, these methods overlook variations in the importance of attention across heads, layers, and contexts.

To address these limitations, we propose Tactic, a sparsity-adaptive and calibration-free sparse attention mechanism that dynamically selects tokens based on their cumulative attention scores rather than a fixed token budget. By setting a target fraction of total attention scores, Tactic ensures that token selection naturally adapts to variations in attention sparsity. To efficiently approximate this selection, Tactic leverages clustering-based sorting and distribution fitting, allowing it to accurately estimate token importance with minimal computational overhead.

We show that Tactic outperforms existing sparse attention algorithms, achieving superior accuracy and up to 5.14x decode attention speedup. This improvement translates to an overall 1.51x end-to-end inference speedup, making Tactic a practical and effective solution for long-context LLM inference in accuracy-sensitive applications.

Published as a conference paper at ICLR 2026
TACTIC: ADAPTIVE SPARSE ATTENTION WITH CLUS- TERING AND DISTRIBUTION FITTING FOR LONG- CONTEXT LLMS
Kan Zhu- Tian Tangh.2 Qinyu X Zhan Jin Yile Gu Zhichen Zeng'
Rohan Kadekodi' Liangyu Zhao? Ang Li Arvind Krishnamurthy! Baris Kasikci
University of Washington TTingguu University
SPeking University
ABSTRACT
Long-context models are essential for many applications but face inefficiencies in loading large KV caches during decoding. Prior methods enforce fixed token budgets for sparse attention, assuming a pre-chosen number of tokens can approxi- mate full attention. However, these methods overlook variations in the sparsity of attention across heads, layers, and contexts.
To address these limitations, we propose Tactic, an adaptive and calibration -free sparse attention mechanism that dynamically selects tokens based on their cumula- tive attention scores rather than fixed token budget. By setting a target fraction of total attention scores, Tactic ensures that token selection naturally adapts to variations in attention sparsity. To efficiently approximate this selection, Tactic leverages clustering- sorting and distribution fitting, allowing it to accurately estimate token importance with minimal computational overhead.
We show that Tactic achieves superior accuracy and up to 7.29x x decode attention speedup, contributing overall 1.58x end-to-end inference speedup, making it a practical and effective solution for long-context LLM inference in accuracy- sensitive applications.
INTRODUCTION
Large language models (LLMs) power wide range of applications, from conversational assistants to document analysis systems and search engines. The demand for multi-turn interactions and long-document processing has driven expansion of context length, growing from thousands as many as one million tokens (Liu et al. 2024b).
However, supporting long contexts LLM inference presents significant challenges, primarily due to the growing memory footprint of the Key-Value (KV) cache (Tang et al., 2024 Zhao et al. 2025 2024). The memory requirements of the KV cache scale proportionally with the context length; therefore, it can quickly become a bottleneck despite optimizations such as Grouped- Query Attention (GQA) (Ainslie al.) (023). Furthermore, the need to repeatedly load the KV cache for every generated token becomes a bottleneck. For instance, loading the large KV cache can account for over 50% of the total latency during reto-segeesivve decoding, significantly impeding the efficiency of
large-scale serving systems. TTagg al. 2024 Zhu et al. 2025)
To mitigate the high cost of V--acche loading, recent methods approximate full attention by selecting subset of stored Key and Value vectors, corresponding
subset of tokens, within fixed token budget (Liu et al. 2024a Tang et al., 2024 Zhang et al. 2023 Xiao et al. 2023). These approaches
exploit the natural sparsity of attention, where only small fraction of tokens significantly influence the output. By leveraging this sparsity, they aim to reduce the overhead loading the KV-cache without notably sacrificing model accuracy.
Alas, existing fixed budget-based methods have several shortcomings. Some methods employ a global fixed token budget (Tang al. 2024 Xiao et al. 2023 Zhang et al. (023). not accounting for
Work done University of Washington.

---

Published as a conference paper at ICLR 2026
Fixed Taken Budget (Budget
Output
Tactic
Target:
Output
Context
Step
Context
Step
Context 2
Step
Lower
Higher Attention Score
Full Attention Score
Attention Score
Figure I: Comparison between ixed-budget-base methods and Tactic. Fixed-budget-basee methods may select excessive tokens or have a large difference from full attention score. In contrast, Tactic dynamically selects tokens to efficiently approximate full attention based on cumulative attention score, considering variation of sparsity across different query tokens and contexts.
variations in attention sparsity across attention heads and layers. In practice, some attention heads focus significantly
tokens than others, and the level of sparsity fluctuates across layers. More adaptive methods (Cai et al. 2024 Feng et al. 2024; Ge et al. 2024) attempt to distribute token budgets more effectively using calibration data predefined rules, but they remain constrained by static allocation and cannot adapt to the sparsity variations across query tokens and contexts, often leading to suboptimal approximations in different cases.
To address the limitations of fixed-budge-bbased methods, we propose Tactic, an adaptive and calibration-free post-training sparse attention mechanism that improves both the accuracy and effi- ciency of long-context LLM inference. Fig. shows a comparison between existing fixed budget- based methods and Tactic. Instead of enforcing fixed budget, Tactic dynamically selects tokens starting from ones with the highest attention score (i.e., the softmax output of the Query-Key product) ensure that their cumulative attention scores reach target fraction of the full attention score.
Tactic offers key advantages. First, it provides flexibility- -Tactic selects fewer tokens in high-sparsity cases and more in low-sparsity cases without requiring calibration. Second, since V vectors have similar norms as we show in Fig. 4 reaching fixed cumulative attention score offers bounded difference between sparse and full attention (see Sec. 2.3 and Proof
However, efficiently selecting tokens to reach certain threshold P of cumulative attention score is challenging. To minimize the number of tokens selected (i.e., loads from memory), Tactic ideally needs to select tokens following descending order of attention score until the cumulative attention score surpasses P. Additionally, unlike fixed budget-basee methods that simply stop at a fixed token count, Tactic must track cumulative attention score in real time to determine the stop point, making the selection process more complex.
To approximate optimal token selection, Tactic introduces two key techniques: clustering and distri- bution fitting. First, to efficiently sort tokens, Tactic groups similar tokens to reduce computational overhead. However, we observe that positional proximity, which is used for grouping tokens by prior work (Tang et al. (2024), does not necessarily guarantee similarity in Key vectors, which limits the grouping quality and the attention score estimation. Since attention operates on Query-Key interactions rather than token positions, Tactic groups tokens using K-means clustering based on Key-vector similarity (i.e., vector distance) the prefill phase. During decoding, Tactic approximates the sorted clusters of tokens based on the similarity between the current Query vector and cluster centroids. After approximating token sorting, Tactic estimates the attention score for each token by leveraging the observation that attention scores follow smooth distribution. Using distribution fitting, Tactic effectively keeps track of attained cumulative attention score to determine the end of token selection.
By loading only the cluster centroids along with a small sampled subset of tokens (~ 2.5% of the KV cache size in practice), Tactic efficiently selects the most critical tokens that reach the target cumulative attention score. To balance efficiency and accuracy, Tactic performs full attention on newly generated tokens and updates the clustering every fixed number of decoding steps (e.g.. 2048).
2

---

Published as a conference paper at ICLR 2026
1.00
1.00
0.30
Hoad 10
Head 0
0.50
Iyer
byer 10
0.50
Quzry
Surry
Read
0.25
20
Query
byer 30
Query
0.00
0.00
10000
20000
30000
10000
20300
30000
10000
20000
30000
(a)
(b)
(c)
Figure 2: Variation in sparsity across attention heads (a), model layers (b), and query tokens (c). In (c), Query represents the query vector of i-th decoded token. Sorted token indices (by attention score) on the x-axis and the cumulative density of attention score on the y-axis.
Our experiments show that Tactic achieves superior and consistent accuracy compared to existing algorithms, including Quest (Tang et al. 2024), MagicPig (Chen et al. 2024), PyramidKV (Cai et 2024), and V (Feng et al. 2024). offering more effective solution for long-context LLM inference accuracy-sensitivy applications. Tactic achieves up to 7.29x decode attention speedup, which leads to 1.58x end-to-end speedup.
summary, we contribute the following:
A detailed analysis dynamic nature of attention sparsity across heads, layers, queries, and contexts.
Tactic, sparsity-adapliss adaptive attention algorithm that uses clustering and distribution fitting to dynamically determine the token budget for achieving cumulative attention score targets.
A comprehensive evaluation of Tactic, demonstrating Tactic consistently achieves high accuracy and significant speedup.
ANALYSIS
2.1 INTRINSIC SPARSITY IN SELF-ATTENTION MECHANISMS
the decode phase, for one request, assuming there are n previous tokens, attention formula can be written
gk.
exp(
5;11,
Vi
(I)
9k
exp
Our empirical results, evaluated Llama 3.1 8B model using the PG19 dataset (Rac al. 2019).
show that ||v/|| are remarkably consistent, while in s;, the exponential term exp( gk amplifies the differences in the attention scores, leading sparse distribution (Zhang al. 2023
non non-linc
Xiao et al. 2023). This indicates that a small subset of tokens can exert a significant influence on the model's output, motivating the possibility of only loading subset of tokens approximate the attention output and incur lower memory loading overhead.
2.2 FIXED TOKEN BUDGET APPROACHES LEAD TO ACCURACY VARIATIONS
Several methods have been proposed to choose small set of tokens / minimizing the distance e e(I) between full and approximate attention. Some of the work, including Quest (Tang et al. 2024). uniformly chooses tokens across attention heads and layers. These result in large variance of c(1 as shown in Fig. This variance stems from the intrinsic sparsity difference across heads and layers. As illustrated in Fig. 2a attention heads exhibit distinct sparsity patterns. Some heads display more uniform distribution of 8; (retrieval heads, e.g., head 10), whereas others are dominated by a few high-man mainituannieeeeeee values (streaming heads, e.g., head 20). When fixed number of tokens [/] is selected per head, it leads to inefficiencies allocating excessive tokens to streaming heads while introducing significant estimation errors in retrieval heads. Similarly, Fig. 2b highligss variation in

---

Published as a conference paper at ICLR 2026
(1) 10 p(I) Ener 8:1i1|
Exer sell Eier si0; pij Excrsesl|
0.3
Ratio
p(T)) Dier 8:t; Eitt &tull
p(rl] Dier vill Eigs silloall
10 Norm of Value Vector
(T)) 1)p(7) max[|u:ll + (1-p(T) max||
2(1 (TT) max|||=]].E
Figure 4: Distribution of [[V] across layers, heads, and decoding steps. Values concentrate in a narrow range.
Proof Derivation of the error bound.
sparsity across layers, where layer O requires significantly more tokens to reach the same cumulative attention score, making inefficient to select a fixed number of tokens from different layers.
Motivated by the diversity of sparsity patterns across heads and layers, some works, including AdaKV (Feng et al.) 2024) and PyramidKV (Cai al. 2024). fix the total budget |r] but use calibration data or assumptions to statically assign different budgets to different layers and heads. However, as we show in Fig. 2c] the sparsity of particular heads varies significantly depending on query token. For example, in the model output "The Answer is ...", the token "Answer" attends to far fewer tokens compared to "is". This is because "Answer" relies primarily on local information to generate "is", whereas "is" requires broader context produce the subsequent answer. Thus, relying on static partitioning of a fixed token budget also falls short of maintaining a consistent low attention distance < (T). While MagiePig (Chen al. 2024) uses dynamic selection, it does not provide accuracy guarantee on e()).
2.3 CUMULATIVE ATTENTION SCORE: A MORE ROBUST TARGET FOR SPARSE ATTENTION
The key drawback of existing work is the reliance on fixed total token budget, making it hard to adapt to sparsity variations. Instead, we propose directly using the cumulative attention score of tokens in to guide token selection.
Distance of Attemion Dusbut
Specifically, we define p(!) the cumulative atten- tion score of tokens in L, which is
Eier exp(
gk.
p(I)=
Va
(2)
E exp(
gk
iET
Va
1000
2000
3000
4000
5000
5000
7000
Index
Attention Computation
These cumulative attention score targets offer two key advantages over fixed token budgets. First, they in- herently adapt to sparsity variations without requiring assumptions or calibration data. Less sparse heads, layers, query tokens, and contexts naturally require more tokens to reach cumulative attention score than sparser ones.
Figure Distance of attention output full attention of Quest and our proposed solution of selecting tokens until reaching cumulative attention score threshold P. measured with Ilama3.1-8 -88--IItruttt model.
Second, targeting cumulative attention score provides theoretical guarantee on attention distance. Specifically, the attention distance is bounded by e(T) < 2(1 p())) max, || Proof [rovides the full derivation. Since value vectors have similar norms across tokens (Fig. 4 setting a threshold P (typically close to 1.0) for p(I) establishes tight upper bound on e(I). Identifying the minimal index set I that satisfies p(T)= > reduces the variance of the attention approximation error, as shown in
Fig. 3
2.4 CHALLENGES OF ATTAINING CUMULATIVE ATTENTION SCORES
While effective, identifying the minimal subset of tokens that achieve a target cumulative attention score during the inference is challenging task. The optimal way is to select tokens following
4

---

Published as a conference paper at ICLR 2026
Table WCSS of clustering and consecutive grouping, evaluated on Llama-3.1-8B, with data from LongBench (Bai et al. 2024).
Sequence Length
WCSS (cluster)
WCSS (consecutive)
8192
173.42
195.06
16384
75.29
93.29
32768
75.39
93.25
65536
78.07
93.83
descending order of attention score until the cumulative attention score surpasses the target value. Therefore, like prior approaches, Tactic must rank tokens by attention score to minimize the number of tokens needed to reach the desired cumulative attention score. However, unlike previous methods, Tactic also requires the exact attention score values for each token track the cumulative sum of selected tokens in real-time. This process involves two key components: (1) computing the sum of attention intermediate values, exp(gk" /vd), for the selected token set I, and (2) computing the total sum of exp(gkT /vd) for normalization. Both components need to be effectively approximated without actually calculating the attention score for all tokens. We discuss how Tactic achieves efficient subset identification in the following section.
METHODOLOGY
3.1 ALGORITHM OVERVIEW
Fig- provides an overview of Tactic's workflow. During prefill, Tactic performs K-means clustering on key vectors to group similar tokens. During decode, Tactic ranks tokens based the dot product between cluster centroids and the current query vector. Tactic then models the distribution attention score with fitted curve and determines the tokens to meet the desired cumulative attention score threshold. After token selection, Tactic handles the Group Query Attention (GQA) and then performs the attention using FlashInfer (Ye al. 2025).
3.2 PREFILL STAGE: GROUPING TOKENS VIA CLUSTERING
Similar to prior works, Tactic groups tokens to reduce computational overhead for identifying critical tokens. However, existing methods rely positional order, assuming consecutive tokens share similar attention patterns (Tang et al.) (224)). However, Tab. [ shows that clustering achieves lower WCSS than consecutive grouping, which means consecutive grouping is suboptimal. Moreover, modern attention kernels efficiently handle non-contiguous KV-cache access, making positional grouping unnecessary. Therefore, Tactic applies K-means clustering to group tokens based Key- vector similarity during the prefill as a one time cost. Based on the sensitivity analysis in Sec. /ec. on pyper-parameters, Tactic empirically chooses the average cluster size be 16 to balance accuracy and efficiency and randomly samples initial cluster centroids
3.3 DECODE STAGE: PARTIAL SORT TOKENS USING CLUSTER CENTROIDS
Once the tokens organized into clusters, Tactic identifies critical clusters for given query vector Q in the decode phase. The criticality of each cluster is determined by the dot product between Q and each cluster c This process produces sequence of clusters sorted by the criticality, which can then be unwrapped to obtain a partially sorted token list.
3.4 DECODE STAGE: ESTIMATING ATTENTION SCORE VIA DISTRIBUTION FITTING
Exec || 2 is the mean vector of C. 2 Note that neither multiple initializations nor K-Means ++ initialization drastically improves the clustering quality, and in fact leads to high-performance overhead, as stated in Sec. C.2
'WCSS
Compared distance, dot product directly relates the attention score, which accurate.
5

---

Published as a conference paper at ICLR 2026
Stage1: Clustering
Stage2A: Querying
Stage2B: Fitting
Keys
Custer Centroids
Inner Product
Sort
Sorted Centroids
Retrieved Tokens
Exp Inner
Product
Est. Score
Selection
Keez
CI
C3
K1
Attention
C2
K5
C3
P
K4
Dasribation
Cum
Attn
Dot Product
K7
Score
Query
Det Product
Query
Prefill Phase
Decode Phase
The overall workflow of Tactic. Tactic operates in three stages to achieve low overhead adaptive sparse attention. Stage applied right after prefill phase, Stage 2A and 2B happens during the decode phase.
Figure 5:
Due the non- non-linearity of Softmax, cluster cen- troids do not accurately reflect the average at- tention score of individual tokens. Thus, Tactic requires more precise approach estimating per-token attention score. We observe that after partial sorting, the attention score distribution follows a consistent pattern across heads, layers, and contexts. For example, shown in Fig. [6 the attention score is high for a few tokens and then smoothly decreases, forming long-tai anigtail dis- tribution suggesting that function fitting can be used estimate attention score. Tactic models the distribution of the exponential values of the dot products (exp( QK" )) for each token using va
20 1c
Attention Scores
5000
10000 15000
20000 25000 30000
Index
Figure 6: The distribution of attention scores af- ter cluster-based sorting for one request in PG19 dataset using Llama3. 1-8---Itt-ttt model. De- spite some variations, the overall trend closely aligns with the function
a lightweight function = + h, where x is the position index in the sorted list of tokens. To estimate parameters and b, we select two segments of the tokens in the middle of the curve (e.g., 10% and 60% of all the tokens), and calculate the average of tokens within each segment (as labeled in Fig. (6) However, initial tokens (1-2% of the total tokens) are often outliers and cannot accurately described by the curve. Moreover, these tokens feature high attention score, and thus a bad estimation would cause high deviations of estimated cumulative attention score, which affects accuracy Tactic. Therefore, Tactic directly calculates the exponential values of the dot products for these tokens. The complete algorithm is provided in Sec. A
Clustering and distribution fitting operate as coupled, self-correcting feedback loop that enhances robustness. the initial token clustering is suboptimal, the resulting attention distribution decays more slowly (i.e., exhibits flatter curve). Tactic's distribution-fite fitting procedure detects this flattening and automatically increases the token budget. Moreover, even if the curve-fitting step selects an imperfect cutoff, Tactic's grouping and sorting mechanism continues prioritize the most critical tokens. Because selection proceeds in priority order, estimation errors mainly shift the cutoff within the low-value tail, leaving high-value tokens largely unaffected.
3.5 DECODE STAGE: GQA-AWARD SPARSE ATTENTION
Modern models use Grouped Query Attention (GQA) to reduce the KV cache size (Dubey et al. 2024), where multiple query heads share KV head. However, existing methods select tokens

---

Published as a conference paper at ICLR 2026
1.0
Thresholds
Threshold
0.0030
Acceptancs Rate
0.8
divergence
0.0020
0.6
0.0015
0.4
0.0010
MagicPig SmapkY/yramidk Quest
Ada-SnapKV
Pyramiaky
Quest
Figure KL-Divergence against full attention of Tactic and other baseline methods on the PG19 dataset. Tactic maintains the most accurate out- put in two configurations.
Figure 8: Acceptance of draft tokens at 80% and 90% thresholds on the PG19 dataset. Tactic shows more than 95% of acceptance rate, sur- passing other baselines.
on per-head basis, and each query head reads KV cache independently. Tactic instead takes the union of selected tokens across all grouped query heads and loads it only once. To ensure workload balancing, Tactic divides each request into subrequests. Each subrequest processes KV head and its corresponding Query head, with sequence length determined by the tokens selected for each KV head, allowing the request-level workload balance in modern libraries Ye et al. 2025) to effectively handle head-level imbalance efficiently.
4 EXPERIMENTS
4.1 SETTING
We evaluate Tactic for both accuracy and efficiency. We mainly two models: Llama-3.1- 8B-Instruct (Grattafiori et al. 2024), a widely used model with Grouped-Query Attention; and (Chen Wu and Yin Song and Eden Duthie 2024). an extended version with a 512k token context window. To assess cross- generalization.
BrgaBeam--Mistal-255 of Mistral-7B-IIstruuctte we additionally evaluate on Qwen2-7B (Yang al. 2024 and Llama- 1000--70-B- Instruutt (Grattafiori et al. 2024) (see Sec. B.I.
For accuracy evaluations, we use the PG19 language modeling dataset (Rae 2019), LongBench dataset (Bai et al. 2024), including HotpotQA (Yang et al. (2018) TriviaQA (Joshi et al. 2017).
MultifieldQA (Bai et al.| (024)) NarrativeQA (Kočiský et al. 2018). Qasper (Dasigi et al.
2022 al.2 the RULER benchmark (Hsich
and
Musique (Bii et al. (024). Additionally, we conduct experiments
ctt al., 2024), using 50 examples for each task. We compare Tactic with the most popular fixed token budget KV cache algorithms, Quest (Tang al. 2024), PyramidKV (Cai et al. 2024), and
Ada-SnapKV (Feng et al. 2024). Also, we compare Tactic with MagicPig (Chen et al. 2024) RULER benchmarks.
For fair comparison, we first rum Tactic to map each target cumulative attention score ratio to a token budget, and then evaluate all baselines under the matched budget. Parameter-wise set the page size in Quest and the cluster size in our method to 16. Both Ada-SnapKV and PyramidK V follow the configuration settings outlined in (Feng al. (024), including an observation window size of 32 and max pooling kernel size of We follow the configuration of MagicPig in the original paper RULER evaluation.
For efficiency evaluations, we perform the evaluation on Nvidia Ada 6000 GPUs with CUDA 12.4 compared with full attention using Flashinfer Yee et al. 2025).
4.2
ACCURACY EVALUATION
4.2.1
OUTPUT ACCURACY
We assess the KL- KL-divergence of the model output probability distribution of Tactic relative to the full attention on the PG19 test set (Rae et al. 2019). under Top-K K sampling. We include all texts in PG19 with the number of tokens larger than 32k. In the prefill stage, truncate the input to 32k tokens
7

---

Published as a conference paper at ICLR 2026
Table Performance comparison on RULER for
and Mega-Beam- Beam-Mistral
5 512k models.
Alama-3.1-88-mme
Mega-Beam Beaa---ittta---12222
Methods
Config
16K
32K
64K
96K
Avg.
Methods
Config
16K
32K
64K
96K
Avg.
Full
91.3
86.0
85.2
85.0
86.8
Full
90.9
88.4
82.7
83.1
86.3
Tactic
15%
90.9
85.5
83.4
78.9
84.7
Tactic
75%
88.0
88.8
81.7
82.5
85.2
PyramidKV
75%
61.8
67.4
63.1
PyramidKy
75%
80.2
79.0
75.2
71.0
77.1
Ada-Su
75%
58.0
62.2
59.2
58.7
59.2
Ada-SnapKV
75%
50.6
78.1
75.4
73.6
76.8
Quest
75%
70.0
71.5
69.7
65.7
69.2
Quest
75%
80.7
79.0
71.1
70.5
75.1
MagiePig
75%
78.6
76.8
74.0
MagicPig
75%
86.5
S1.0
69.4
81.6
Tactic
90%
90.3
84.9
82.8
80.5
84.6
Tactic
90%
90.3
88.0
81.0
82.6
85.4
PyramidKV
90%
73.1
76.2
74.2
08.6
73.0
PyramidKV
90%
84.3
82.7
76.2
86.2
82.4
Ada-SnapKV
72.7
73.0
Ada-SnapKV
90%
76.2
87.1
82.4
Quest
90%
85.8
81.9
79.8
70.5
79.5
Quest
90%
81.1
81.3
73.5
79.7
78.9
MagicPig
90%
79.8
76.9
71.3
70.7
74.7
MagicPig
90%
90.2
87.1
82.3
82.3
85.4
and then feed it into the model. In the decode stage, we use full attention as the reference. We first generate a token sequence with full attention, and then feed the generated tokens one-by-one into each sparse-attention variant. At each decode step, we collect the output logits and compare them against the corresponding full-attention logits compute the distributional difference, We collect 32 decode steps in total. As shown in Fig. 7 Tactic achieves the most aligned output compared to all baselines.
4.2.2 ACCEPTANCE RATE IN SPECULATIVE DECODING
To further demonstrate the practical indication of smaller KL-divergence, we evaluate the token acceptance rate under greedy sampling when using Tactic as draft model for speculative decoding using the PG19 test set. Specifically, we select all documents in PG19 containing more than 32K tokens and decode up 96 tokens per document, varying the number of draft tokens (i.e., different values of y). During the experiments, we record the verification results, capturing the number of tokens accepted by the target model at each verification step. After computing the average number of accepted tokens for each y, we fit curve to the resulting data points to estimate the acceptance rate, following the formulation Equation
Q 2+1
E( E(#accepted tokens)
which is adapted from (Leviathan et al. 2023). Here a is the acceptance rate to be estimated. The results are presented in Fig. Tactic achieves more than 90% of acceptance rate, significantly surpassing all baselines.
4.2.3 ACCURACY FOR LONG-CONTEXT TASKS
LongBench. We evaluate Tactic on six LongBench tasks, as illustrated in Sec. 4.1 For each dataset, we first evaluate Tactic by setting the cumulative attention score threshold as 70% and 90%. The average number of tokens selected each threshold serves the token budget for evaluating baselines. As shown in Sec. B.2 Tactic beats all other baselines across tasks. At threshold of 90%, Tactic achieves performance close to full attention. We further validate cross-model and cross-task generalization Qwen2-7B, Llama-3.1 Instruct, and coding benchmarks in Sec. B. where Tactic consistently surpasses all baselines across different architectures, scales, and task domains.
We evaluate Tactic and baselines all tasks in RULER (Hsich et al.) 2024 with context length ranging from 16K to 96K. As shown in the Tab. 2 Tactic consistently exceeds all baselines in each configuration in terms of average accuracy. Furthermore, at higher thresholds, Tactic achieves similar accuracy to full attention, significantly higher than other methods. Also, we provide the efficiency comparison in the RULER test in Sec. D.I
RULER.
We provide a detailed table of the average number of tokens selected by Tactic across various thresholds, datasets, and models in Sec. B.3 which is set token budgets for baselines.
8

---

Published as a conference paper at ICLR 2026
Table 3: Evaluation of number of tokens selected and ratio of cumulative attention score achieved for 1lmma-31-88- 1-18--Insttuce model.
Average Achieved Score
Success Rate
Threshold
Optimal
Cluster Optimal
Tactic
50%
71
166
185
66%
92%
60%
122
271
294
72%
89%
70%
212
451
490
78%
86%
80%
394
802
890
84%
84%
90%
895
1723
1975
91%
86%
4.2.4 ACCURACY OF CLUSTERING & DISTRIBUTION FITTING
We evaluate our method the PG19 dataset, focusing on how consistent Tactic achieve the target cumulative attention score and how many tokens it selects. We vary target cumulative attention score thresholds and compare the number of selected tokens produced by our method against two oracles. The global optimal ranks individual tokens by attention score in descending order and selects the smallest prefix whose cumulative attention score meets the target. The clustering optimal operates on clusters: it sorts clusters by their aggregate attention score contribution and selects clusters in that order until the target is reached. addition, we report the realized average cumulative attention score and the success rate, defined as the fraction of cases where the selected tokens achieve least the target attention score. Tab. iiddicates that Tactic achieves the target threshold cumulative attention score with high success rates. Also, the values of Cluster Optimal and Tactic are close, indicating that the distribution fitting presents an accurate estimation of the number of tokens.
4.2.5 SENSITIVITY STUDY
We analyze the sensitivity of Tactic to its key design choices. First, we compare the inverse fitting function (y a /rr + b) against linear, exponential, quadratic, and constant alternatives on Long- Bench (Sec. C.1. All non-constant functions achieve comparable accuracy, but the inverse function consistently selects the fewest tokens, making it the most efficient choice. Additionally, we examine clustering hyperparameters in Sec. the default configuration (cluster size 16, 10 iterations, single initialization) achieves near-optimal Silhouette scores while minimizing overhead.Finall we evaluate K-means initialization stability across 8 random seeds in Sec. C.3) where Tactic exhibits strong robustness.
4.2.6 COMPONENT ABLATION
To isolate the contributions of clustering and cumulative attention score based selection, we introduce two ablated variants on LongBench (I.ama-3. 1-8--33.-8BB-nstrucct (1) Tactic-topK, which retains K- clustering but uniformly distributes the token budget, and (2) Position-cluster, which replaces K-means similarity-based clustering with sequential token grouping. As shown in Sec. Sec. Tactic- topK suffers notable accuracy degradation, while Position-cluster achieves comparable accuracy but requires significantly more tokens.
4.3 EFFICIENCY EVALUATION
We begin by analyzing the latency breakdown of Tactic, focusing on token clustering during the prefill phase and attention computation for critical tokens during decoding (Sec. 4.3.1) Next, we evaluate Tactic's end-to-end performance and its speed-up relative to full attention (Sec. 4.3.3
4.3.1 LATENCY BREAKDOWN
Latency clustering during prefill. We measure the time taken for clustering for different sequence lengths in Fig. 9 We observe that, as the sequence length increases, the clustering time increases quadratically and is dominated by the distance calculation. However, long sequences also significantly increase the prefill time. Overall, the clustering time stays below 7% of the prefill time across all sequence lengths up to 256K. Because both clustering and prefill scale quadratically with sequence length, this ratio remains stable context grows. For batched inference, clustering be applied

---

Published as a conference paper at ICLR 2026
Oustering
150
Sequan 32K
Sequan 64K
Sequan 128K
Quary
30
20
100
Temre (mmo
hikinn
16
Jreen
Alt
CASe
15:1
32K
64K
120K
258K
P-0.7
P-0.9
Full
P-0.7
P-0.9
Full
P-0.7
P-0.9
Full
Figure 9: Comparison of Cluster- ing and Prefill time across sequence lengths.
Figure 10: Latency breakdown of Tactic in the decode stage for different sequence lengths and thresholds.
Winer
Tine (md)
Winh
14
JG44
to Ent
1.2
1,0
P-
0.9
P= 0.7
P
P.7.7
P-
0.7.7
0.9
0.7
P 0.9
P- 0.9
Figure 11: Ablation study on taking union for the GQA model. Taking union significantly reduces the attention time.
Figure 12: End-to-end speedup of Tactic com- pared to the full attention.
independently per sequence, so both costs scale linearly with batch size, preserving the same overhead ratio.
Latency of attention during decode. In the decode stage, Tactic identifies and performs attention on critical tokens. We break down this process into four parts: Cluster sorting, where the clusters are ranked based on the dot product of centroids and queries, 2) Distribution fitting, where Tactic samples small portion of tokens and derives the attention score identify the token budget for each attention head, 3) performing attention for the selected tokens. Fig. I0 shows the latency of this breakdown for different sequence lengths.
The latency of sparse attention during decode is reduced significantly, while the overheads sorting and distribution fitting remain low across various sequence lengths. Overall, Tactic achieves up to 7.29x speedup compared to the full attention.
4.3.2 ABLATION STUDY FOR QUERY HEAD UNION
evaluate the benefits of taking the union of grouped query heads versus computing attention for each query head individually. As shown in Fig. [1 across different context lengths and ratio P. taking unions can achieve up to 1.65x attention speedup, due to the reduced memory loading.
4.3.3 END-TO-END PERFORMANCE
We compute the end-ta-end performance of Tactic with different output tokens, sequence lengths, and ratios in Fig. 1 considering the prefill stages and the clustering overhead. Overall, Tactic achieves speedup of up to 1.58x compared to full attention.
CONCLUSION
We presented Tactic, aparsity-adaptive attention mechanism for efficient long-context LLM inference. Unlike fixed token budget methods, Tactic dynamically selects tokens based on cumulative attention scores, adapting to variations attention sparsity. By leveraging clustering based sorting and distribution fitting, Tactic accurately estimates token importance with low overhead. Our results showed that Tactic outperforms existing sparse attention methods, achieving higher accuracy and significant inference speedups, making it practical solution for long-context L.MMs.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Joshua Ainslie, James I Lee-Thorp Michiel de Jong, Yury Zemlyanskiy, Federico Lebrón, and Sumit Sanghai. Gqa: Training generalized multi-query transformer models from multi-head checkpoints, 2023.
Yushi Bai, Xin Lv, Jiajie Zhang, Hongchang Lyu, Jiankai Tang, Zhidian Huang, Zhengxiao Du, Xiao Liu, Aohan Zeng, Lei Hou, Yuxiao Dong, Jie Tang, and Juanzi Li. LongBench: A bilin- gual, multitask benchmark for long context understanding. In Lun-Wei Ku, Andre Martins, and Vivek Srikumar (eds.), Proceedings of the 62nd Annual Meeting of the Association for Com- putational Linguistics (Volume I: Long Papers), pp. 3119-3137, Bangkok, Thailand, August 2024. Association for Computational Linguistics. doi: 10. 10.18653/1//204.ccclu 172. URL longllon..1111
Zefan Cai, Yichi Zhang, Bofei Gao, Yuliang Liu, Tianyu Liu, Keming Lu, Wayne Xiong, Yue Dong, Baobao Chang, Junjie Hu, and Wen Xiao. Pyramidkv: Dynamic kv cache compression based on
pyramidal information funneling, 2024. URL URL https: http://axxivv.ooo
/tt.////./2222222 02069
Zhuoming Chen, Ranajoy Sadhukhan, Zihao Yc, Yang Zhou, Jianyu Zhang, Niklas Nolte, Yuandong Tian, Matthijs Douze, Leon Bottou, Zhihao Jia, and Beidi Chen. Magicpig: Lsh sampling for efficient Iim generation, 2024. http/tttp..//arr.....rr//aa///.p 16179
Chen Wu and Yin Song and Eden Duthie. wwwp://wwwwg.agoggooaaaaeaaaaaaa http://hhhh...c..oooo/p/prp/apaa
2024. URL -11-51kk
Pradeep Dasigi, Kyle Lo, Iz Beltagy, Arman Cohan, Noah A. Smith, and Matt Gardner. A dataset of information-sseking questions and answers anchored in research papers. In Kristina Toutanova, Anna Rumshisky, Luke Zettlemoyer, Dilek Hakkani -ur. Iz Beltagy, Steven Bethard. Ryan Cot- terell, Tanmoy Chakraborty, and Yichao Zhou (eds.). Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Lan- guage Technologies, pp. 4599-4610, Online, June 2021. Association for Computational Linguis- tics. doi: 10. 00.188533v1/2022
URL httpas///cc.arbhooocy..////////
naacl ma mmain.3. 365
seacl-maing
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang. Angela Fan, et al. The Ilama 3 herd of models. arXiv preprint arXiv:2407.21783 2024.
Yuan Feng, Junlin Lv, Yukun Cao, Xike Xie, and S. Kevin Zhou. Ada-kv: Optimizing kv cache eviction by adaptive budget allocation for efficient Ilm inference, 2024. htttps//////ar
org/abs/ 2407 11550
Suyu Ge, Yunan Zhang, Liyuan Liu, Minjia Zhang, Jiawei Han, and Jianfeng Gao. Model tells you what to discard: Adaptive kv cache compression for 1lms, 2024. URL htt/:ttts///axxi..rrggg/
abs/2310. 01801
Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan, Amy Yang, Angela Fan, Anirudh Goyal, Anthony Hartshom, Aobo Yang, Archi Mitra, Archie Sravankumar, Artem Korenev, Arthur Hinsvark, Arun Rao, Aston Zhang, Aurelien Rodriguez. Austen Gregerson, Ava Spataru, Baptiste Roziere, Bethany Biron, Binh Tang, Bobbie Chern, Charlotte Caucheteux, Chaya Nayak, Chloe Bi, Chris Marra, et al. The llama 3 herd of models, 2024. URL. https
7/a 1/arxiv. org. abs/ /20/////47.mmm 021.//247222222 217383
Cheng-Ping Hsieh, Simeng Sun, Samuel Kriman, Shantanu Acharya, Dima Rekesh, Fei Jia, Yang Zhang, and Boris Ginsburg. Ruler: What's the real context size of your long-context language models?, 2024. https: wttp:/iwwwrr/bb//e/aeao/ooese/
06654
Mandar Joshi, Eunsol Choi, Daniel Weld, and Luke Zettlemoyer. TriviaQA: A large scale distantly su- pervised challenge dataset for reading comprehension. In Regina Barzilay and Min- Yen Kan (eds.), Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1601-1611, Vancouver, Canada, July 2017. Association for Computational Linguistics. doi: 20.18653/1//11-11
URL TRLlhttts:://///tt //ap: /tttpaa://cclantooooo.g..

---

Published as a conference paper at ICLR 2026
Tomáš Kočiský. Jonathan Schwarz, Phil Blunsom, Chris Dyer, Karl Moritz Hermann, Gábor Melis, and Edward Grefenstette. The NarrativeQA reading comprehension challenge. Transactions of the Association for Computational Linguistics, 6:317-328, 2018. doi: 10.1162/tacl a_00023. URL
httpss acl antho
-1023
Yaniv Leviathan, Matan Kalman, and Yossi Matias. Fast inference from transformers via speculative decoding. 2023. URL
Guangda Liu, Chengwei Li, Jieru Zhao, Chenqi Zhang, and Minyi Guo. Clusterkv: Manipulating Ilm kv cache in semantic space for recallable compression, 2024a. URL https://arxl org/
abs/2412. 03213
Xiaoran Liu, Hang Yan, Shuo Zhang, Chenxin An, Xipeng Qiu, and Dahua Lin. Scaling laws of rope-based extrapolation, 2024b. URL
2310. /ttp///.0b/331005002333333
Jack W. Rae, Anna Potapenko, Siddhant M. Jayakumar, and Timothy P. Lillicrap. Compressive transformers for long-range sequence modelling, 2019. URL https:://ar.vvorr///a 1911.05500
Peter J. Rousseeuw. Silhouettes: A graphical aid to the interpretation and validation of cluster
analysis. Journal of Computational and Applied Mathematics, 20:53-65, 1987. ISSN 0377-0427. doi: http://ccieeeeaarrrcceeee//////2
URL https: sci http://www.ccccccceeeeeeeeee
com/
Jiaming Tang. Yilong Zhao, Kan Zhu, Guangxuan Xiao, Baris Kasikci, and Song Han. Quest:
Query-aware sparsity for efficient long-context Ilm inference, 2024. URL https: Utthhttss://ara //aa:iv///xvvv/
brg/abs/2405. 10774
Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. Efficient streaming language models with attention sinks. arXiv, 2023.
An Yang, Baosong Yang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Zhou, Chengpeng Li, Chengyuan Li, Dayiheng Liu, Fei Huang, Guanting Dong, Haoran Wei, Huan Lin, Jialong Tang, Jialin Wang, Jian Yang, Jianhong Tu, Jianwei Zhang, Jianxin Ma, Jianxin Yang, Jin Xu, Jingren Zhou, Jinze Bai, Jinzheng He, Junyang Lin, Kai Dang, Keming Lu, Keqin Chen, Kexin Yang. Mei Li, Mingfeng Xue, Na Ni, Pei Zhang, Peng Wang, Ru Peng. Rui Men, Ruize Gao, Runji Lin, Shijie Wang, Shuai Bai, Sinan Tan, Tianhang Zhu, Tianhao Li, Tianyu Liu, Wenbin Ge, Xiaodong Deng, Xiaohuan Zhou, Xingzhang Ren, Xinyu Zhang, Xipin Wei, Xuancheng Ren, Xuejing Liu, Yang Fan, Yang Yao, Yichang Zhang, Yu Wan, Yunfei Chu. Yuqiong Liu, Zeyu Cui, Zhenru Zhang, Zhifang Guo, and Zhihao Fan. Qwen2 technical report, 2024. URL
2407. 10671
Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William Cohen, Ruslan Salakhutdinov, and Christopher D. Manning. HotpotQA: dataset for diverse, explainable multi-hop question answer- ing. In Ellen Riloff, David Chiang, Julia Hockenmaier, and Jun ichi Tsujii (eds.), Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 2369-2380, Brussels, Belgium, October-Novemllee 2018. Association for Computational Linguistics. doi: 10.18653/v 1/D//5////DD1----. 1-299 URL hutt::://acaanthoooy..ooo
1259
Zihao Ye, Lequn Chen, Ruihang Lai, Wuwei Lin, Yineng Zhang. Stephanie Wang, Tianqi Chen, Baris Kasikci, Vinod Grover, Arvind Krishnamurthy, and Luis Ceze. Flashinfer: Efficient and customizable attention engine for IIm inference serving. arXiv preprint arXiv:2501.01005, 2025. URL https:://axxiii org. abs. 01005
Zhenyu Zhang, Ying Sheng, Tianyi Zhou, Tianlong Chen, Lianmin Zheng, Ruisi Cai, Zhao Song, Yuandong Tian, Christopher Ré, Clark Barrett, Zhangyang Wang, and Beidi Chen. H20: Heavy- hitter oracle for efficient generative inference of large language models, 2023.
Yilong Zhao, Chien- Yu Lin, Kan Zhu, Zihao Ye, Lequn Chen, Size Zheng, Luis Ceze, Arvind Krishnamurthy, Tianqi Chen, and Baris Kasikci. Atom: Low-bit quantization for efficient and accurate Ilm serving, 2024. WRR.tttss: / http://///.arri.ooor/////////11/
12

---

Published as a conference paper at ICLR 2026
Yilong Zhao, Jiaming Tang, Kan Zhu, Zihao Ye, Chi-Chih Chang, Chaofan Lin, Jongseok Park, Guangxuan Xiao, Mohamed S. Abdelfattah, Mingyu Gao, Baris Kasikci. Song Han, and lon Stoica. Accelerating large-scale reasoning model inference with sparse self-speculative decoding, 2025.
URL /tt./http.:///rxxv.rr///////// 2t1.a/////112. 01278
Kan Zhu, Yufei Gao, Yilong Zhao, Liangyu Zhao, Gefei Zuo, Yile Gu, Dedong Xie, Zihao Ye, Keisuke Kamahori, Chien- Yu Lin, et al. Nanoflow: Towards optimal large language model serving throughput. In 19th USENIX Symposium on Operating Systems Design and Implementation (OSDI 25), pp. 749-765, 2025.
13

---

Published as a conference paper at ICLR 2026
A ALGORITHM OF DISTRIBUTION FITTING
The algorithm for distribution fitting is illustrated in Alg.
Algorithm Estimating Token Budget Distribution Fitting
1: Input: Key sequence unpacking from sorted clusters {k1, hg..... kn ). query Q. weight percent- age threshold P. initial token count N, centers of two sampling window p1 and p2, sampling window size w, head dimension
2: Output: Token budget K
3:
4: Compute in and μ22 the means of exp(k; Q/vd) within fixed windows around pl and p2. namely,
Mj Limp - exp(k: Q/va) 1,2
(4)
w
Solve for parameters a and in y = a/x + using (pI, mi) and (fz, u22..
5:
6: Initialize array Sy, i E [nx] to store the fitted attention scores for all tokens
7: for == to do
8: i N, = exp(x; Q/vd)
9: Else, = =/i
10: end for
Compute the minimal K such that the cumulative sum Σ P Σ 8
12:
return K
B ADDITIONAL BENCHMARK RESULTS
B. CROSS-MODEL AND PROSS-TASK GENERALIZATION
To assess generalization across model architectures, scales, and task types, we evaluate Tactic on two additional models: Qwen2-7B (Yang et 2024) and Llama-3.1-70B-Inntte
(Grattafiori et al. 2024) using LongBench tasks. We additionally evaluate on coding benchmarks (RepoBench-P and LCC) from LongBench test cross-task generalization beyond question answering. As shown in Tab. 4 Tab. 5 and Tab. 66) Tactic consistently achieves near-full near-full-attenioon accuracy and outperforms all baselines across difterent models, scales, and task domains.
Table 4: LongBench results Qwen2-7B. Tactic achieves near-full-ateenionn accuracy and consis- tently outperforms baselines.
Method
Config
NarrativeQA
HotpotQA
Qasper
MultifieldQA
TriviaQA
Musique
Avg
Full
Full
24.47
36.99
45.88
47.61
85.54
20.68
43.53
Tactie
70
26.31
37.20
44.23
46.25
82.24
20.76
42.82
PyramidKV
20.13
35.51
25 50
39.37
82.82
20.76
37.35
Ada-SnapKV
21.91
34.86
27.58
40.83
85.81
19.23
38.37
Quest
8.83
11.65
9.36
10.32
24.73
3.52
11.40
Tactic
90
25.71
37.26
44.08
46.19
84,26
20.79
43.05
PyramidKV
22.31
36.81
31.18
41.97
84.87
19.10
39.37
Ada-SnapKV
21.84
35.72
34.51
44.26
21.01
40.58
Quest
9.97
18.46
15.10
13.64
31.78
7.02
15.99
14

---

Published as a conference paper at ICLR 2026
Table 5: LongBench results on Llama-3.4700--nstruuct Tactic generalizes well larger model
scales.
Method
Config
HotpotQA
Qasper
MultificldQA
TriviaQA
Musique
Avg
Full
Full
64.69
49.79
54.58
87.71
44.67
60.29
Tactic
70
64.71
49.64
54.28
92.16
44.51
61.06
PyramidKV
70
63.39
38.01
44.69
93.65
43.00
56.55
Ada-SnapKV
70
63.02
35.52
50.39
93.75
42.28
56.99
Quest
70
45.91
20.12
27.84
68,40
33.37
39.13
Tactic
90
64.88
49.98
54.75
89.71
44.25
60.71
PyramidKV
90
64.08
42.14
51.25
92.98
43.96
58.88
Ada-SnapKV
64.98
44.92
52.38
92.98
45.18
60.09
Quest
90
54.60
42.23
46.84
78.53
39.49
52.34
Table 6: LongBench coding benchmark results on Llama-3, better accuracy than full attention.
Tactic achieves near or
Method
Config
RepoBench-P
LCC
Avg
Full
Full
52.82
49.28
51.05
Tactic
70
52.73
56.46
54.59
PyramidKV
70
51.93
49.94
50.94
Ada-SnapKV
70
50.80
49.45
50.12
Quest
44.75
37.57
41.16
Tactic
52.51
50.73
51.62
PyramidKV
49.90
51.03
50.47
Ada-SnapKV
90
51.30
50,32
50.81
Quest
90
53.71
52.80
53.25
B.2 LONGBENCH ACCURACY EVALUATION
The LongBench evaluation results are presented Tab. provide evaluation script Longbench.
MagicPig not included since they don't
Methods
Config Full
HotpotQA
TriviaQA
MultiFildQAA
Qasper
Narrative(AA
Musique
Llama-3.1 1-8B-bnstruct
54.99
55.05
46.52
27.12
32.16
Tactic
70%
51.20
90.38
52.98
43.30
30.39
28.57
PyramidKV
70%
52.59
89.57
43.26
27.50
21.44
25.34
AdaKV
70%
49.32
89.57
43.45
29.99
25.23
23.54
Quest
70%
45.43
77.42
49,96
38.09
24.77
24.78
Tactic
90%
53.57
90.61
54.35
44.20
29.59
30.71
PyramidKV
90%
53.77
90.31
48.15
36.40
26.97
28.52
AdaKV
90%
54.05
90.46
49.15
37.55
27.86
29.19
Quest
90%
49.37
80.38
52.42
42.41
26.64
MegaBeam- BeeraBaa--Misra--Se Mistral-512k
Full
48.89
88.24
52,14
33.13
26.08
26.38
Tactic
70%
49.15
87.89
$0.50
32.37
25.66
25.85
PyramidKV
70%
21.23
AdaKV
70%
42.23
85.65
38.44
22.23
21.89
21.68
Quest
70%
48.90
88.13
50.58
30.78
23.88
24.65
Tactic
90%
49.59
89.16
49.85
33,93
26.31
25.93
PyramidKV
90%
44.05
86.64
24.22
21.13
23.32
AdaKV
90%
44,80
86.80
42.80
22.51
22.46
24.86
Quest
90%
51.69
88.49
51.81
32.46
24.63
25.89
Table 7: Experiment Results on LongBench
B.3 NUMBER OF TOKENS SELECTED BY TACTIC IN BENCHMARKS
We provide the average number of tokens selected by Tactic in benchmark evaluations Tab. Tab. and Tab. 10
15

---

Published as a conference paper at ICLR 2026
Table
Average number of tokens selected by Tactic for different cumulative attention scores.
P
HotpotQA
TriviaQA
MultiFieldOA
Qasper
NarrativeQA
Musique
Llama-3.1-M 1oima-3.1-8B-Maa Insttrenstt
70%
959 2298
761
774
629
1918
1229
90%
1813
1559
1276
4254
2754
BrggaBeam-Mistrake
7B-572k
70%
2126
1733
1399
1191
3017
2598
90%
3641
3048
2031
1546
5616
4384
Table 9: Average number of tokens selected by Tactic for Llama-3.1-88 1.1---Insttrct across context lengths and cumulative attention scores.
Task
16K
32K
64K
96K
75 %
90 %
75%
90 %
75 %
90%
75 %
90%
NIAH Single
166
813
363
1567
2404
1790
3319
NIAH Single
271
1289
534
2196
711
3209
2030
3940
NIAH_Single
NIAH_ Single 3
171
1015
369
1820
507
3031
1068
3952
NIAH Mulltiky
224
1052
449
1832
654
2792
978
4438
NIAH Multikey
399
1612
706
2533
981
3902
1405
S527
NIAH Multikey
340
1428
567
2404
3990
1068
5062
NIAH Multivalue
246
1769
478
2679
4458
1025
8147
NIAH Multiquery
253
1524
465
2648
681
4830
915
6011
FWE
282
1572
515
2693
778
4376
963
6202
CWE
443
1939
570
3036
655
4707
780
6731
QA
329
1250
704
2565
852
3830
3417
5055
QA
547
1484
1092
2263
1662
3455
2120
4276
VT
118
731
253
1413
269
2028
404
3068
AVG
291
1344
543
2281
746
3616
1382
5056
AVG/Token
1.78%
8.21%
1.66%
6.96%
1.14%
5.52%
1.41%
5.14%
Table 10: Average number of tokens selected by Tactic for MegiBBea--Misrra--BB55112 across context lengths and cumulative attention scores.
Task
16K
32K
64K
96K
75%
90%
75%
90%
75%
90%
75%
90 %
NIAH. MinglSingle|
1410
1176
2521
2354
4715
4512
7042
7271
NIAH Single
1418
1665
2704
3364
5113
6732
7668
10472
MAHHSingle
3005
2032
5312
3800
10235
7327
15492
11900
NIAI Multikey
1486
1661
2872
3415
5332
5983
778.
8767
NIAH Multikey
1480
1639
2826
3031
5288
5956
8240
9279
NIAH Multikey
28400
2039
5990
4306
11438
7741
11292
NIAIL MAHLMultivalue
2225
5070
4006
7463
11853
NIAH Multiquery
3088
2165
5234
4075
9931
7551
14420
11164
FWE
2706
1809
5537
3685
10837
7157
16558
10818
CWE
4240
2526
7404
4869
13189
8802
1 18329
13215
QA
1003
1502
2772
3132
5828
5685
6007
9150
QA 2
724
1718
2124
3017
4853
6520
8598
8598
2227
1409
4132
2619
8667
4719
14318
8671
AVG
2193
1813
4192
3513
8124
6627
12129
10126
AVG/Token
13.38%
11.06%
12.79%
10.72%
12.40%
10.11%
12.34%
10.30%
C ABLATION AND SENSITIVITY STUDIES
C.I DISTRIBUTION FITTING ALGORITHM
We compare five curve fitting algorithms for estimating the attention score distribution: inverse
(g a/x + b), linear (y + b), exponential (y "e" quadratic (y ax² + bar c). and
16

---

Published as a conference paper at ICLR 2026
constant (uniform budget). Tab. reports accuracy and average number of tokens selected six LongBench tasks. All non-constant curves model the monotonically decreasing trend of attention scores and achieve comparable accuracy. Among them, the inverse function consistently selects the fewest tokens while maintaining high accuracy, making the most efficient choice.
Table Ablation study on distribution fitting algorithms. We report accuracy and average number of tokens selected (Tok) on LongBench tasks at cumulative attention score thresholds of 70% and 90%.
Alge
HotpotQA
MultifielQQA
Musique
NarrativeQA
Qasper
TriviaQA
Invers
$6.89
719
52.81
459
29.87
878
29:34
1417
48.74
59:46
399
Lineur
70
55.90
764
52.96
-99
29.67
941
29.28
1465
45.28
377
$8.71
620
Exp
70
$6.89
761
$3.49
496
30.09
928
29.35
1501
45.15
369
99.16
621
Quadratic
96.17
776
$2.98
508
29.85
953
29.85
1518
48.55
379
99.76
636
27.81
Invers
57.17
1707
$1.19
1251
29.57
2056
29.11
3460
18.69
90.30
1356
Linear
90
56.67
1812
33.52
1335
29.54
2203
30.38
5740
44,80
1051
90.50
1397
Exp
90
56.67
1769
$4.26
1293
29.46
2142
29.43
3003
45.25
100.3
90.50
1381
Quadratic
90
56.67
1884
53.74
1387
29.54
2287
50.18
5863
44.5
1099
90.40
1463
Coust
C.2 SENSITIVITY ANALYSIS OF CLUSTERING
As stated in Sec. 3.2 clustering is controlled by three parameters: the number of iterations, the cluster size, and the initialization count (n init). In this section we provide the effects of different value of the three parameters. We use Silhouette Score (Rousseeuw 1987) to evaluate the performance of clustering, which commonly used metric in machine learning field.
Tab. 12 presents the impact of key hyperparameters on clustering quality across different sequence lengths. Increasing the number of iterations number of initializations brings little improvement on the performance of clustering but proportional overhead, Tactic chooses 10 iterations and one time initialization maintain high performance with minimal overhead. Also, smaller cluster size yields better clustering performance but longer clustering time, Tactic chooses 16 to balance the performance and efficiency. Notably, the effect of these hyperparameters is largely independent of sequence length.
Hyperparameter
Value 8192
16384
32768
65536
init
0.091
0.113
0.145
0.166
0.095
0.117
0.150
0.170
0,095
0.117
0.149
0.170
0.095
0.118
0.149
0.170
max iter
0.091
0.111
0.145
0.166
10
0.091
0.113
0.144
0.165
20
0.095
0.117
0.150
0.171
30
0.095
0.117
0.150
0.171
40
0.095
0.117
0.150
0.171
50
0.095
0.117
0.150
0.171
cluster_size
0.096
0.118
0.155
0.173
16
0.095
0.116
0.149
0.170
32
0.088
0.110
0.143
0.164
64
0.082
0.104
0.131
0.155
128
0.070
0.096
0.119
0.143
Table 12: Silhouette scores for K-Means clustering across different sequence lengths, evaluated against hyperparameters init, max iter, and cluster size.
C.3
RANDOM SEED STABILITY
To verify the robustness of Tactic's clustering- -ased approach, we evaluate on LongBench (Llama-3., 8B-Instruct, threshold 90%) using eight random seeds (100, 200, .... 800) for K-means initialization.
17

---

Published as a conference paper at ICLR 2026
As shown in Tab. 13 Tactic exhibits strong stability across runs, with a standard deviation of approximately 0.2 per task and only 0.05 on the overall average. This confirms that the large number of clusters and data points per dataset effectively mitigates the randomness of K-means initialization.
Table 13: LongBench accuracy across random seeds (threshold 90%). Tactic exhibits strong stability with std x 0.2.
Seed
HotpotQA
MultifieldQA
Musique
NarrativeQA
Qasper
TriviaQA
Avg
100
56,52
54.15
28.90
29.35
44.70
50.74
200
57.17
54.14
29.13
29.35
44.47
90.80
50.84
300
57.17
54.11
29.13
29.27
44.76
90.30
50.79
400
57.17
54.24
28.67
29.23
44.80
90.80
50.82
500
56.92
53.81
29.13
29.41
45.02
90.80
50.85
600
57.17
53.77
29.13
29.61
44.77
90.80
50.88
700
56.92
54.26
29.13
29.85
44.56
90.80
50.92
800
57.02
53.77
29.13
29.36
44.65
90.80
50.79
Std
0.21
0.20
0.16
0.19
0.16
0.17
0.05
C.4
COMPONENT ABLATION
To isolate the contributions of clustering and cumulative attention score- base-baeddee selection in Tactic, we compare the full system against two ablated variants on LongBench 1-8--..tt------ttece at cumulative attention score thresholds of 70% and 90%:
Tactic (full):
K-means clustering groups tokens by key-vector similarity; clusters ranked by attention score and the token budget is adaptively determined via distribution fitting.
Tactic-topK: Retains K-means clustering but uniformly distributes the token budget (as determined by Tactic) across all layers and heads, ignoring the adaptive scoring mechanism.
Position-cluster: Replaces K-means similarity- clustering with sequential token grouping (consecutive windows), while keeping the distribution fitting pipeline unchanged.
As shown in Tab. 14 Tactic-topK fails allocate tokens effectively eritical layers and heads, leading to notable accuracy degradation (e.g.. HotpotQA drops from 57.39 to 43.38 at 70% threshold). Position-cluster yields lower-quality clusters, requiring more tokens achieve the same cumulative attention score target (e.g., 33% more tokens on average at 70%). However, since the cumulative score target fixed, Position-clusee ultimately achieves similar accuracy but at higher memory loading cost. These results confirm that both high-qualiy, clustering and score-based token selection are essential for Tactic's performance-effict weweeceeeffccccyyyyy tradeoff.
Table 14: Component ablation on LongBench (I.lama-3, ---t----ttt We report accuracy (Acc) and average number of tokens selected (Tok) at cumulative attention score thresholds of 70% and 90%.
HolpotQQA
Musique
NarrativeQA
Qusper
TriviaQA
Tactic
70
$7.39
719
$2.71
458
29.87
29.27
1413
45.22
89.46
Tacke-topk
70
43.38
719
47.55
458
16.47
877
29.82
1415
30.00
334
50.40
596
Position cluster
70
55.62
508
52.29
589
28.76
1102
30.90
2053
45.05
444
89.71
752
1704
2072
3429
44.68
90.50
1356
Tacfic-opp
44.60
Rositinn-claster
90
2308
1936
D ADDITIONAL EFFICIENCY RESULTS
D. SPEEDUP OF TACTIC IN RULER EVALUATION
To ensure fair comparison of efficiency between Tactic and baseline methods in Sec. 4.2.3 adjust the number of selected tokens to match the RULER scores. The token count required to achieve this accuracy, along with the attention speedup over baseline methods, is shown in Tab. 15
18

---

Published as a conference paper at ICLR 2026
Table 15: Attention speedup over baselines in RULER evaluation.
Method
SeqLen
# Tokens Chosen
Tactic
32K
543 (1x)
Quest
32K
5430 (10x)
Pyramid
32K
8145 (15x)
Ada
32K
8688 (16x)
Tactic
64K
746 (1x)
Quest
64K
9698 (13x)
Pyramid
64K
16412 (22x)
Ada
64K
14920 (20x)
Tactic
128K
1381 (Ix)
Quest
128K
20715 (15x)
Pyramid
128K
34525 (25x)
Ada
128K
33144 (24x)
E COMPUTER INFORMATION OF EXPERIMENTS
For Longbench and RULER evaluation (Tab. 7 and Tab. 2). we use a Nvidia H100 DGX server, Longhench evaluation takes around 8 hours and RULER evaluation takes 12 hours, two models (Llama-3.1-88) 1-88BInnstrct and MegaBcam- 1afcammMiittaa-755 7B551kKK. Other accuracy evaluations like KL- divergence can be done within 30 minutes single H100. For Efficiency evaluation, use Nvidia Ada 6000 GPUs with CUDA 12.4.
F POTENTIAL SOCIAL IMPACTS
This paper motivated by recent advances in the field of long-conters language models. Sparse attention methods has the potential to be used to serve more requests and thus benefit more users.
19


Reviews:
[{"review_id": "dTnLA2tBNn", "reviewer": "Reviewer_zjbE", "summary": "This paper aims to address critical inefficiencies in long-context LLM inference by proposing a calibration-free sparse attention mechanism that dynamically selects tokens based on cumulative attention scores to meet a target fraction, rather than relying on a fixed token count.", "questions": "1. Any ablation study on distribution fitting? Compare \\(y=\\frac{a}{x}+b\\) with power-law and analyze the fitting error impact on results.\n2. The selector will cause any latency overhead; some papers have mentioned this [1]. Can you add some analysis?\n\n[1] HShare: Fast LLM Decoding by Hierarchical Key-Value Sharing.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The paper is well structured and easy to follow.\n2. This paper addresses a real, practical problem, and this area is promising.\n3. The evaluation is comprehensive.", "weaknesses": "1. Vague practical cost tradeoffs: Clustering overhead is <6% of prefill time, but no breakdown of how this scales with ultra-long sequences (>128K) or batch inference—critical for real-world high-throughput serving.\n2. The idea is similar to several other papers, such as Twilight: Adaptive Attention Sparsity with Hierarchical Top-p Pruning.\n3. Typo: line 43, reference", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7h30YEfjH6", "reviewer": "Reviewer_Bx4T", "summary": "The paper presents a novel adaptive sparse attention mechanism designed for efficient inference in long-context language models (LLMs). \n\nUnlike existing fixed-budget methods, Tactic dynamically selects tokens based on cumulative attention scores, allowing it to adapt to variations in attention sparsity. This flexibility enhances the model's efficiency in processing long sequences.\nTactic employs clustering-based sorting and distribution fitting techniques to accurately estimate the importance of tokens while minimizing computational overhead. This approach improves the model's ability to handle large amounts of data effectively.\nThe experimental results demonstrate that Tactic achieves up to 7.29 times speedup in decoding attention and 1.58 times overall inference speedup compared to traditional methods, all while maintaining high accuracy.\nThe framework is designed to be practical for long-context LLMs, making it a valuable contribution to the field of natural language processing, particularly for applications requiring efficient handling of extensive textual data.\nIn summary, Tactic represents a significant advancement in adaptive attention mechanisms, providing both efficiency and accuracy for long-context language models.", "questions": "1. Could you provide more detailed insights into the clustering methodology used in Tactic? Specifically, how do you determine the optimal number of clusters, and what criteria do you use to evaluate the effectiveness of the clustering?\n\n2. How well does Tactic generalize to other language models beyond Llama-3.1-8B-Instruct and MegaBeam-Mistral-7B-512k? Are there any limitations observed when applying Tactic to different architectures or tasks?\n\n3. What is the impact of different hyperparameter settings on the performance of Tactic? For instance, how does varying the average cluster size or the number of iterations in K-means affect the results?\n\n4. Could you elaborate on the real-time performance metrics used to evaluate Tactic? How do you measure the efficiency gains during actual inference as opposed to theoretical evaluations?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Tactic employs a dynamic approach to token selection based on cumulative attention scores rather than a fixed budget. This adaptability allows the model to efficiently handle variations in attention sparsity across different contexts, leading to improved performance in long-context language models  \n2. The experimental results demonstrate that Tactic achieves up to 7.29 times speedup in decoding attention and 1.58 times overall inference speedup compared to traditional methods. This efficiency is crucial for practical applications of long-context language models, making Tactic a valuable contribution to the field  \n3. Despite the focus on efficiency, Tactic maintains high accuracy levels. The method's design ensures that the attention distance error is minimized, providing a theoretical guarantee on the accuracy of the attention approximation  \n4. Tactic utilizes clustering-based sorting and distribution fitting techniques to estimate token importance effectively. This innovative approach reduces computational overhead while ensuring that critical tokens are selected based on their relevance to the current query, enhancing the overall performance of the model", "weaknesses": "1. The adaptive nature of Tactic, which involves dynamic token selection based on cumulative attention scores, may introduce additional complexity in implementation compared to simpler fixed-budget methods. This complexity could pose challenges for practical deployment in certain environments.\n2. Tactic relies heavily on accurately estimating attention scores for effective token selection. Any inaccuracies in this estimation could lead to suboptimal performance, potentially affecting the overall effectiveness of the model\n3. While Tactic uses clustering to improve efficiency, the initial clustering step may introduce computational overhead, especially for large datasets or models. This could negate some of the efficiency gains achieved during the decoding phase \n4. The performance improvements demonstrated in the paper are based on specific models (e.g., Llama-3.1-8B-Instruct). There may be concerns regarding how well Tactic generalizes to other architectures or tasks, which could limit its applicability in diverse scenarios", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tzT7gBou8e", "reviewer": "Reviewer_tuQx", "summary": "Paper points out that using a fixed number of tokens for attention is inefficient because different inputs require appropriate or different amounts of focus. To solve this, TACTIC adjusts the number of tokens dynamically—it keeps only as many tokens as needed to capture most of the important information in the attention layer. It does this by grouping similar tokens with K-means clustering during setup and by modeling how attention changes during generation. This method makes the model run much faster (7× faster in attention calculations) while keeping accuracy almost the same.", "questions": "1. Since the paper focuses on a few model families, is the adaptive token selection strategy architecture-agnostic, as it would support broader applicability?\n\n2. Can the authors provide results across multiple random seeds or include confidence intervals to confirm reproducibility and eliminate the possibility that observed improvements are dataset or run-specific?\n\n3. Has there been consideration to compare against the very latest “heavy hitter / speculative decode / KV eviction + reuse” on real hardware latency, not just attention microbenchmarks?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "It is a smart and adaptive approach to improving efficiency in large language models. Instead of using a fixed number of tokens for attention, which can waste computation on unimportant parts it dynamically selects only the most relevant tokens using clustering and distribution fitting. This makes the smaller model(8~9B)  much faster while keeping accuracy almost unchanged, and it’s done without extra training or calibration, making it easy to apply to existing models.", "weaknesses": "This method mainly focuses on the decode phase, so, it doesn’t speed up the initial setup (prefill) as much. Additionally, although the results are strong, the paper doesn’t thoroughly examine how the method performs on large models(e.g., 70B and above) or various types of tasks, and it lacks detailed statistical analysis across multiple runs to confirm consistency.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VykZCsdH2K", "reviewer": "Reviewer_gwJo", "summary": "This paper introduces Tactic, an adaptive and calibration-free sparse attention mechanism for long-context LLMs. Unlike prior methods that use a fixed token budget, Tactic dynamically selects tokens by targeting a fraction of the total attention scores, allowing it to naturally adapt to sparsity variations across heads and layers. To achieve this efficiently, it leverages clustering-based sorting and distribution fitting. The method reports significant improvements, including up to a 7.29× speedup in decode attention and a 1.58× end-to-end inference speedup while maintaining accuracy.", "questions": "1.  Could you provide an ablation study that isolates the contributions of the clustering-based sorting, the distribution fitting components and the cumulative attention score based selection to the overall performance?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.  The core idea of targeting a fraction of attention scores instead of a fixed budget is elegantly designed to address the limitations of fixed-budget methods in handling variable attention sparsity.\n2.  The method is calibration-free, which significantly lowers the barrier for practical adoption and simplifies its integration into existing inference pipelines.\n3.  The combination of clustering and distribution fitting appears to be a computationally efficient approach to enable the adaptive selection mechanism.\n4.  The reported performance gains are substantial, suggesting that Tactic is a promising solution for accelerating long-context LLM inference.", "weaknesses": "1.  The method has two main components, clustering and cumulative attention score based selection. It's not clear how the two components work together to achieve the accuracy gains. An ablation study is needed to isolate the contributions of the two components.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)