QuoKA: Query-Oriented KV Selection for Efficient LLM Prefill
Authors: Dalton Jones
Junyoung Park
Matthew J Morse
Mingu Lee
Matthew Harper Langston
Christopher Lott
Venue: ICLR 2026 Poster (2026)
Keywords: Efficient LLM Inference
LLM Prefill Acceleration
Sparse Attention
KV Cache Subselection
Training-Free
Primary area: foundation or frontier models, including LLMs

Abstract: We present QuoKA: Query-oriented KV selection for efficient attention, a training-free and hardware agnostic sparse attention algorithm for accelerating transformer inference under chunked prefill. While many queries focus on a smaller group of keys in the attention operator, we observe that queries with low cosine similarity with respect to the mean query interact more strongly with more keys and have the greatest contribution to final attention logits. By prioritizing these low cosine similarity queries, the behavior of full attention during the prefill stage can be closely approximated. QuoKA leverages this observation, accelerating attention by (1) first retaining a small set of representative queries and (2) then subselecting the keys most aligned with those queries. Through experiments on Needle-In-A-Haystack, LongBench, RULER, and Math500, we show that, while realizing a 3× reduction in time-to-first-token, 5× speedup in attention on Nvidia GPUs and up to nearly a 7× speedup on Intel Xeon CPUs, QuoKA achieves near-baseline accuracy, utilizing 88% fewer key-value pairs per attention evaluation.

Published as a conference paper at ICLR 2026
QUOKA: QUERY-ORIENTED KV SELECTION FOR EF- FICIENT LLM PREFILL
Dalton Jones, Junyoung Park, Matthew Morse, Mingu Lee, Chris Lott, M. Harper Langston Qualcomm Al Research jone, junpark, mingul, clott, hlangsto) /qtioo ttt.luullloooooo com
ABSTRACT
We present QUOKA: Query-oriented KV selection for efficient Attention, a training-free and hardware agnostic sparse attention algorithm for accelerating transformer inference under chunked prefill. While many queries focus on smaller group of keys in the attention operator, we observe that queries with low cosine similarity with respect to the mean query interact more strongly with more keys and have the greatest contribution to final attention logits. By prioritizing these low co- sine similarity queries, the behavior of full attention during the prefill stage can be closely approximated. QUOKA A leverages this observation, accelerating attention by (1) first retaining small set of representative queries and (2) then subselecting the keys most aligned with those queries. Through experiments on Needle-In-Al A- Haystack, LongBench, RULER, and Math500, we show that, while realizing a 3x reduction in time-to- mome-to-firs-teee first-token, 5x speedup in attention on Nvidia GPUs and up nearly a 7 speedup on Intel Xeon CPUs. QuoKA achieves cese-baseline accuracy, utilizing 88% fewer key-value pairs per attention evaluation.
INTRODUCTION
major bottleneck large language model (LLM) inference is prefill latency, which can account for more than 70% of total runtime. This latency is especially significant CPUs, consumer grade GPUs, and edge accelerators, where resources are limited (Agrawal et al., 2024; Kamath et al., 2025; Xu et al., 2025a). To mitigate this, recent deployments increasingly adopt chunked prefill, which divides input into blocks to improve scheduling and utilization (Agrawal et al., 2023; Lai et al., 2025; Kwon al., 2023). Nevertheless, due quadratic complexity of the underlying attention, chunked prefill remains computationally expensive. Methods such as sparse attention seek to overcome this complexity by identifying and exploiting sparsity attention. Combining chunked prefill with sparse attention offers promising path to sub-quadratic complexity and substantial latency improvements resource constrained environments.
Sparse attention algorithms can be broadly categorized into two families: puttern-based and query- dependent approaches. Pattern-based approaches impose fixed sparsity patterns (e.g.. block, strided, or banded) on Q TT (Child et al., 2019; Dao et al., 2022; Xu et al., 2025b; Jiang et al., 2024; Gao et al., 2024; Zhang al., 2025), often achieving speedups through kernel-level optimizations; however, due to dynamic compute graph and KV cache memory bandwidth overhead under chunked prefill, their benefits are limited. Furthermore, reliance on custom kernels limits the portability of pattern-based approaches across heterogeneous hardware.
In contrast, query- dependeet approaches operate directly on the KV cache, adaptively subselecting the most relevant KVs for a given query (Ribar et al., 2024; Tang et al., 2024; Zhu et al., 2024; Yang et al., 2025b; Singhania et al., 2024). While remaining compatible with optimized kernels and offering strong portability benefits, this strategy reduces both attention complexity and memory traffic. However, existing query-dependent methods are primarily designed for generation, where KV's are selected for single query; such cases, is more straightforward determine which KVs are relevant for the given query. During prefill, when relevant KVs are selected for many queries at once, this can result significant performance degradations. Under chunked prefill, where important KVs are repeatedly subselected for multiple queries, these degradations become more pronounced.
"Qualcomm AI Research initiative of Qualcomm Technologies, Inc.

---

Published as a conference paper at ICLR 2026
Input Chunk
KV cache
Keys
Queries
3
3
5
5
QuaKA
QuoKA
QuoKA
CosSim Scoring
Query Selection
Attention
Attention
Attention
Gather
0
(a) Chunked Prefill with QUOKA
(b) KV selection with QUOKA
Figure I: Overview of chunked prefill with QUOKA: (a) A prompt of 6 tokens divided into three chunks of 2 tokens each. For each chunk, QUOKA subselects the KV cache and feeds the reduced cache into a dense attention kernel. (b) Subselection is performed by applying query subselection based cosine dissimilarity, followed by key subselection using query-key cosine similarity.
To address the drawbacks of existing approaches, we propose QuoKA: Query-oriented KV selection for efficient Attention, a training-free sparse attention method optimized for chunked prefill built upon the following observation: queries with lower cosine similarity to the mean query attend to the majority of keys.
QUOKA leverages this observation to retain small subset of representative queries and subselect KVs with which they strongly interact. While preserving accuracy, QuoKA accelerates attention during prefill and reduces the number of KVs through three steps: Query Subselection, which retains only the most informative queries; Cosine-Similane Scoring, which provides a stable, bounded proxy for query-key relevance; and Group-Aware Aggregation, which efficiently preserves compatibility with modern architectures such as grouped-query attention (GQA) (Ainslie et al., 2023). These steps can be seen in Figure 1, discussed in greater detail in Section 3. Unlike kernel-level sparsity, which depends on custom primitives, QUOKA relies on standard linear algebra operations, allowing for platform portability and straightforward deployment. Our contributions are summarized as follows:
QuoKA: a hundware-agnosiie and training- free query-oriented sparse attention method for chunked prefill, built standard linear algebra kernels.
Accuracy under sparsity: near- baseliee results on long-context benchmarks (Needle-in-at
Haystack, RULER, LongBench, Math500), outperforming existing sparse attention methods.
Latency reduction: up to 5x attention speedup and 3x lower time-to- to--ooot-tooker (TTFT) on enterprise-class GPUs, and 7x and 5-6x speedups on CPUs and consumer GPUs.
Generalization across architectures: validated on diverse decoder-only LLM families (Llama3, Qwen3, SmolLM, GPT-OSS) and on RoPE/NoPE and MoE-based LLMs.
Robustness to hyperparameters: accuracy degrades gradually with sparsity and remains stable across parameter choices, enabling deployment under varied constraints.
2 BACKGROUND
2.1 TRANSFORMERS AND ATTENTION
Since their introduction by Vaswani al. (2017), transformers have become the dominant sequence modeling paradigm. A transformer block consists of two main computational steps: the attention operator and a feed-forward network (FFN). this work, we focus on the attention primarily.
For an input sequence X [æ1,..., zr], the attention operator Attn ) is defined
Alln(X) Softmax (QKT / M) V =V,
where keys K = XWx, queries Q = XWQ, and values V = XWy are learned projections of the input tokens, with Wx. Wo, Wy E dddd With zeros below the diagonal and -oo elsewhere, the mask M enforces autoregressive causality.
2

---

Published as a conference paper at ICLR 2026
Algorithm 1 KV cache sub-selection using QUOKA
Require: queries Q. keys K, values V, prefill chunk size BCp, selective attention budget BSA, max queries No. number KV heads nkv,, number of attention heads nQ Query Sub-selection
1: if Ber > NQ then
2:
MQ mean( (2, dim-2)
3:
Sq f CosSim Q, Mo)
4:
Q < gather(topk] (-s NQ)
Sq
5: end if
Efficient Cosine Similarity via Pre-aggregation > (b, ng. No. (6, ngv. T.d)
6: Q + Q/norm (imm=-)
7: K + K/norm(Ht K, dim=-1)
8: Q mean @.zeshape(b, nkv. nkv .N, d), dim=2)
> 16, NQ.
9: S QKT
nK, No. T) D nkv. T)
10: $ + max(S, dim=2)
11: I + topk($, BSA)
K V gat gather(V,
2.2 ATTENTION LATENCY: PREFILL VS GENERATION
Autoregressive text generation in transformer LLMs be divided into two stages: prefill and generation, both with distinct latency characteristics. During the prefill stage, the entire input prompt processed initialize the KV cache, requiring O(T²) operations from dot products between T queries and T' keys in addition to the FFN computation for each token. As a result for long prompts, attention dominates prefill latency. Optimized kernels such as FlashAttention (Dao et al., 2022: Dao, 2023; Shah et al., 2024) improve memory locality and utilization, but they do not reduce the quadratic complexity; asymptotic speedups can be achieved by reducing the effective number of KVs attended to by each query. In the generation stage, single new query attends to the T cached KVs.. For short generation lengths, performance is memory-bound by the large transfer cost of FFN weights. However for longer outputs, the KV cache dominates the memory footprint and bandwidth. Reducing the number of stored KVs both speeds up the attention computation and reduces data transfer, making KV reduction essential for accelerating generation-hest -havvo tasks (e.g.. reasoning or code generation).
2.3 CHUNKED PREFILL
Given the causality in Equation (1), chunked prefill (Agrawal et al., 2023; Holmes et al., 2024) partitions the input sequence X into non-overlapping chunks of size Bep and process the chunks sequentially: X X Ng = [T/ BBBcl,, where X; [ [Treris...... x Bar(++1)-11 denotes the i-th chunk. For chunk let Ket and Vza denote the concatenation of keys and values from all preceding chunks. Then:
(X,) = Softmax (Q: Ka/T M.) (V: Val.
where |-| denotes concatenation along the sequence dimension and M, enforces causality within X; and against future tokens. Chunked prefill is particularly important for inference on edge devices such as mobile hardware or consumer GPUs where bandwidth and memory capacity are constrained. It also improves cloud inference throughput by enabling interleaved prefill and decode requests, increasing GPU utilization (Holmes al., 2024; Agrawal al., 2025).
2.4 ATTENTION SPARSITY AND SPARSE ATTENTION
High sparsity in the attention matrix A has been widely observed in LLMs (Zhang al., 2024; Xiao et al., 2024; Oren et al., 2024; Zhu et al., 2024; Park et al., 2025). This sparsity allows for a reduction in attention cost by selecting the most relevant KVs for incoming queries into an active cache (K, V) such that:
I -= T= K), Bsa), == (K),, V= gather(V,T),
(3)
3

---

Published as a conference paper at ICLR 2026
2D Visualization of and
Sy and log(maxlA))
Attention
10
0.770
PC of PEPPMCO KO)
10
20
10
30
-5
40
10
50
-10
Bay
Query
60
Quary High
-15
20
40
60
-10
-5
0
10
Key
1 PC PCMOO KK)
(a) Attention score A
(b) PCA viz. of Q and K
(c) Scatter plot Sq v.s. max
Figure 2: Empirical observations from Llama 3.2-3B- I-Istuctut,, layer 0 head 11. (a) Attention map
A. (b) PCA visualization of Q and K, showing that queries with higher Sg lie closer to the keys. (c) Correlation between Sg and max (A)), (A), indicating stronger key interactions for higher Sy queries.
where / satisfies
minimize |ootmax (QKT///+ V - Softmax (QRT/VVL M) F/|. f(Q.K)
(4)
where f is usually constrained be more efficient than the attention computation itself.
Prior work (Zhao et al., 2019; Ribar et al., 2024; Tang et al., 2024; Singhania et al., 2024; Yang et al., 2024b) generally focused on the generation phase, where the scoring function operates on single query Q. Extending these methods to the multiple-query setting with by averaging over queries significantly degrades performance (see Table 3), highlighting the need for better ways to aggregate information from multiple queries. While recent work Zhang et al. (2025); Gao et al. (2024); Zhu et al. (2024); Jiang et al. (2024); Lai et al. (2025) attempt to address this, these methods typically depend on custom CUDA kernels on NVIDIA GPUs. This limits compatibility with hardware-tuned kernels like FlashAttention and hinders broader deployment outside of data centers.
3 QUOKA METHOD
As discussed in Section 2, existing sparse attention methods face limitations prefill efficiency and portability. QuoKA addresses this by reducing the active KV cache during the chunked prefill process. Specifically, the input sequence is divided into chunks X1, XN each chunk X,, QUOKA A selects only the most relevant KVs before computing attention shown in Figure 1. This is achieved in three stages, as detailed Algorithm 1.
XN -1g------- and for
Query subselection: retain only the most informative queries to reduce redundancy.
2. Cosine-Similarity Scoring: compute cosine similarity between queries and keys estimate their relevance.
Score Aggregation: combine scores across queries and key-value groups to select the final KV.
The reduced KV for X, is then fed into dense attention kernel such FlashAttention. By applying this repeatedly, QUOKA reduces prefill cost from O(T²) to a sub-quadratic complexity.
3.1 QUERY SUBSELECTION
Prior work (Park et al., 2025) examined the distinctive geometric characteristic of keys in LLM. Inspired by this insight, focus the geometry of queries. We observe that queries with lower cosine similarity to the mean query tend to align broadly with most keys, while near-mean queries concentrate small shared group of keys (Figure 2a). Thus, utilizing all queries yields redundant information and increases complexity.
To mitigate this, QuoKA retains only those queries that consistently exert significant influence keys. These queries can be identified using their angular distance from the average query vector Mo. Formally, we rank each query q by -CosSim( (M, q) and retain the top Nq. This preserves
4

---

Published as a conference paper at ICLR 2026
the queries most responsible for large key-query dot products while normalizing per query. allowing us to efficiently approximate the post-sofumax attention matrix A. This can be formalized through the following theorem:
Theorem 1. Consider tokens a fixed query go and key k. and let the average of set of queries be denoted MQ. Suppose CosSim( (k; qo) Bg > 0 and CosSim( k) 04 Then
CosSim( Mossim(M@:11 4²) S + 0g - 0.50 0.5
(5)
The proof is provided in Appendix D. Intuitively, if a query g attends strongly to k. then Bg will be large while Ox will be small, resulting in large subselection score
S CosSSi(MMo q*)-
Hence our subselection retains queries that contribute most the attention distribution, in line with both empirical observations and the underlying geometry of keys and queries in modern LLMs. To further validate our design choice, we analyze the geometry of queries and keys. As shown in Figure 2b, most queries are separated from the key cluster in a 2D PCA projection, while queries with higher S, tend to lie closer to the keys. Complementing this, Figure 2c demonstrates that higher Sg is correlated with larger max; (A) outside of the sink token, indicating that such queries exert stronger influence on individual keys. Together, these observations suggest that Sy identifies queries that are both geometrically aligned with keys and dominant in attention.
3.2 SCORING VIA COSINE SIMILARITY
Given the reduced set of queries, the next step is to evaluate their interactions with keys. Existing methods often use dot products QK but these are scele-dependent and unstable under aggregation. Instead, QUOKA A computes
S CosSim(Q,.a
which normalizes vectors to unit length and provides a bounded, geometry- proxy for softmax attention weights. Recent work (Mongaras et al., 2025; Park et al., 2025) also supports the of cosine similarity as a lightweight normalization that approximates softmax behavior. Empirically, ablations the RULER benchmark in Table 9 show that cosine similarity improves subselection quality by more than 10% compared to the dot product.
3.3 AGGREGATION ACROSS QUERIES AND KV GROUPS
30-
Query
Head
Aggregation of scores required along two axes: across queries and across grouped-query attention (GQA) heads. For the query axis, averaging can obscure rare but important query-key interactions, so QUOKA instead takes the maximum, which preserves such outliers. This is supported by the heavy-tailed distribution in Figure 3 and by gains the RULER benchmark (Table 10). For the GQA axis, we simply average scores across KV groups. Unlike queries, head-level importance is correlated (Bhojanapalli et al., 2021), making the mean accurate and stable. Notably, if normalize K and Q prior computing the score, we can achieve the same average by pre-aggregation: averaging normalized queries actoss KV groups due to the linearity of the mean and the outer product QK" Pre-aggregation also lowers computation and memory cost by a factor of the number of KV groups (which large in most modern models), enabling compatibility with modern architectures and enhancing efficiency.
15
8.0
0.1
0.2
0.3
0.4
0.5
0.6
Maximum Abs Deviation from Mean
Figure 3: score max deviation from mean along query and head dimension.
Distribution of attention
3.4 CHUNKED PREFILL WITH QUOKA
The three components described above-query query subselection, scoring, and aggregation integrated into the overall chunked prefill process. For each incoming block X,, QUOKA subselects the active KV tokens using the procedure in Algorithm 1. The resulting subset of keys and values is then passed to the attention computation for that chunk. By reducing the KV budget at each chunk, QUOKA shrinks both compute and memory transfer costs. This enables significant prefill acceleration while maintaining accuracy across long-context benchmarks and is summarized in Algorithm 2.
5

---

Published as a conference paper at ICLR 2026
(a) QUOKA
(b) SampleAttention
(c) Full
Figure 4: Accuracy across document length and needle depth for NIAH with BSa 2048 and
BeP = 128. Results for additional sparse attention methods shown in Figure 7.
RESULTS
In this section, we empirically demonstrate the effectiveness of QUoKA. We begin with detailed description of the evaluation setup and sparse attention baselines, then present our results.
Sparse Attention Baselines: We compared a group of sparse attention algorithms on of models across a variety of selective budgets. The competing algorithms include SAMPLEATTENTION (Zhu al.. 2024) which uniformly samples queries to compute S. LESSISMORE (Yang et al., 2025b) which computes S only at specified layers, SPARQ (Ribar et al., 2024) which subselects along channel dimension before computing S, and [.OII (Singhania et al., 2024) which down-projects keys and queries before computing S. Unless otherwise specified, QUOKA A and SAMPLEATTENTION subselect 16 queries at a time while SPARQ and LOKI down project keys and queries to 64 dimensions.
Models and Evaluation Setup: To evaluate the efficacy of QUOKA across diverse model structures, we adopted QUOKA A and baseline methods across a variety of model families, including simple attention-only models, MoE-based FFN variants, and NoPE adaptations. The models considered include Llama 2223BBIInstrue (Dubey et al., 2024), Qwen 2.5-3B-Instrun (Yang et al., 2024a), Smollm3 (Bakouch et al., 2025), Qwen3-4B, Qwen3-30B-A3B (Yang et al., 2025a), and GPT- OSS-20B (Agarwal et al., 2025). Additionally, we simulated a resource constrained scenario by utilizing chunked prefill with a block size Bep 128. Unless otherwise specified, experiments were performed utilizing an Nvidia A100 GPU.
We show that QuoKA successfully preserves downstream accuracy on intensive tasks such as mathematical reasoning, and provides both attention module-level and end-to-end speedup. Results are summarized below:
Evaluation Summary:
benchmarks involving long input prompts. extends naturally to generation imnerationinntnsvve
Needle-In-a-Naystackk QUOKA significantly outperforms competing selective attention methods on the needle-in-an -aaaa-li--- (NIAH) benchmark (Section 4.1).
RULER. QUOKA significantly outperforms competing methods the RULER benchmark Hsieh et al. (2024), achieving consistently better performance across all prompt lengths and models (Section 4.2).
LongBench. QuOKA exceeds the performance of competing baselines the LongBench suite Bai et al. (2024), demonstrating substantially less performance degradation with decreasing selective budgets. Across all models and budgets, chunked prefill with QUOKA outperforms other methods by at least 10-20% (Section 4.3).
Math500. Although our primary focus is prefill, QUOKA is also directly applicable to generation. On the Math500 benchmark, QUOKA outperforms a sparse attention method specialized for generation and in some cases surpasses accuracy of dense attention (Section 4.4).
Ablation. In sweeping over combinations of BeP, BSa, and Nę that govern the efficiency-accuracy trade-off in QUOK.A A, we observe that accuracy decreases only gradually as sparsity increases. This indicates that QUOKA A can be tuned for diverse hardware environments while maintaining high efficiency. (Section 4.5)
ter-tttoffiitttttt (TTFT) across increasing prompt lengths for end-to-end inference, along with standalone attention module latency. QuoKA achieves 5x module-level speedup on 30k tokens and a 3x TTFT improvement on 50k tokens relative to the base model with full attention, while scaling more efficiently than competing sparse methods (Section 4.6).
Latency. We measured

---

Published as a conference paper at ICLR 2026
Table 1: RULER evaluation results across increasing lengths with BSA 1, 024. Highest per column in bold (Higher is better). Attention sparsification applied on full attention layers.
Ltorsp-J J.2 Justract
Clec Jestract
Qren-I-48
GPT
Length
16k
30%
6K
16k
16k
37k
4K
16k
16k
3IK
Snapkyy
29.15
13.70
12.44
6.21
19.25
12.40
9:85
5.13
27.29
17.15
10.94
10.07
43.72
35.95
24.21
12.23
55,18
31.45
24,52
16,63
Keyloir
$3.34
31.10
24.20
14.87
34.09
20.68
15.79
10.32
37.20
27.35
20.04
12.07
62.85
$1.60
41.64
30.31
69.58
28.75
15,86
9.65
LesaiMorr
36.65
20.21
79.67
50.17
38.27
20:11
78.07
59.87
56,02
15.20
SumpleAm
78.25
61.14
48.31
31.73
77.17
60.88
$6.64
96.17
$7.84
72.46
59.57
40.72
85,72
66.44
59.10
45.95
76.20
70.35
$3.91
30.42
QUOKA
X6.71
88.19
71.90
37.01
87.88
74.27
66.82
59.37
98.73
91.07
$8.57
74883
89.90
79.94
72.09
61.37
78.92
79.19
73,40
57.79
We provide additional runtime and memory complexity analysis for QUOKA A and the baselines in Appendix C.
4.1 NEEDLE IN HAYSTACK
NIAH is synthetic benchmark designed to evaluate how well large language models retrieve specific information from long contexts (Kamradt, 2023; Liu et al., 2024). single needle sentence containing key fact is inserted into a large body of irrelevant text (i.c., haystack), and the model is asked a question that can only be answered by finding that needle. We test Llama3.2-3BB 2-3Bn..---s- with selective budget BSA 2048 and sequence lengths up to 30K. Figure 4 shows that most selective attention methods incur significant degradation during chunked prefill. However, QUOKA retains the ability to retrieve important information across various input sequence lengths.
4.2 RULER BENCHMARK
RULER (Hsieh et al., 2024) is synthetic test for evaluating long-context capabilities of LLMs using NIAH and QA tasks. It addresses shortcomings of NIAH by extending beyond basic retrieval to include multiple needles and new categories such multi-hop tracing and aggregation, which require reasoning across dispersed information rather than locating a single token.
We ran experiments to evaluate QuoKA against sparse attention methods and the full attention base- line. Table reports results with BSA 1024, show- ing 10-20% higher scores than baselines. We also simulated BSa growing with the KV cache main- tain a constant compression ratio: during chunked prefill and token generation, BSa is set 25% of full cache length. Table 2 shows that accuracy loss remains very limited even at long sequences.
Table 2: RULER eval of QuoKA with BSa set 25% of the KV cache length
Prompt I Length
Model
Budget
4096
8192
16384
32768
1.ama.32.38
87.50
81.33
78.98
76.31
25%
86.94
79.72
76.02
74. 14
Full
89.56
81.99
76.09
71.69
Qwen2.5-3B
25%
86.07
79.78
74.25
68.84
Qwen3-48
93.32
91.68
91.18
88.55
25%
92.50
91.35
90.63
87.87
4.3 LONGBENCH
Qwen3-30B
91.87
A3B Instruct
25%
93.25
92.77
91.90
91.08
LongBench (Bai al., 2024) is multi-task bench- mark designed to evaluate the ability of LLMs han- dling long sequences. It includes real-world tasks with inputs such as books, technical reports, and multi-document collections. The benchmark features substantial input lengths average 12K tokens and maximum exceeding 60K tokens measured with the Llama tokenizer, making it rigorous test for models that aim process extended inputs effectively,
91.12
83.46
80.11
75.18
Smollm3
25%
89.60
81.45
78.72
73.55
GPT-OSS-20B
79.35
79.78
75.47
25%
77,40
80.66
77.17
73.45
Table 3 reports the normalized accuracy of sparse attention methods across various models and values of BSA. Each cell shows relative scores compared to the dense baseline (where 1.0 indicates no accuracy drop). Across models, we observe that QUOKA maintains minimal accuracy degradation even with a small budget (e.g., BSA = 1, 1.024). Moreover, QUOKA consistently outperforms competing methods across both models and budget settings.
4.4 MATH 500 BENCHMARK
Although our primary focus is prefill optimization, QuoKA also directly applicable to the gen- eration phase, where the model computes attention for a single query and query subselection is
7

---

Published as a conference paper at ICLR 2026
Table 3: LongBench results (Higher better). For each model, the three columns correspond to
selective budgets BSa E (512, 1024, 2048).
Llama3.2-38 2-B-Intruutt
Oween.553BB-nsttee
Qwen334B
Smolim3
Budget
512
1024
2048
512
1024
2048
512
1024
2048
512
1024
2048
LessIsMore
0.703
0.788
0.850
0.461
0.556
0.659
0.665
0.773
0.868
0.765
0.842
0.918
SparQ
0.721
0.802
0.842
0.636
0.726
0.808
0.686
0.782
0.872
0.725
0.805
0.922
Loki
0.686
0.757
0.842
0,589
0.671
0.787
0.622
0.782
0.872
0.384
0.801
0.622
SampleAttn
0.738
0.800
0.901
0.660
0.756
0.828
0.755
0.875
0,947
0.856
0.929
0.966
QUOKA
0.945
0.972
0.986
0.869
0.945
0.977
0.966
0.992
0.995
0.998
1.03
1.028
applicd. To demonstrate its efficacy in this setting, we evaluated QUOKA on a cenneration-intense reasoning task, applying chunked prefill whenever applicable and using sparse attention for the computation. As shown in Table 8, QUoKA A outperforms a sparse attention method specifically designed for generation, and in some cases even surpasses the accuracy of dense attention.
4.5 ABLATION STUDY
To examine the Sfficiency-accuraan trade-off of QUOKA, we performed ablations over the key BSA. BcP and Nr parameters Tables 3, 5 and for both LongBench and Ruler varying BSa demonstrate that across models and benchmarks, accuracy decreases very gradually as sparsity increases while latency and memory usage improve substantially. We achieve less than a 3% drop in performance with less than 12% of the original tokens used for attention. As shown in Table 11, QUOKA A maintains stable performance under varying BeP. In Table 12 we observe that even with a small setting of Ng 1 To Bep, accuracy drops by only ~3% compared to full attention. This robustness allows practitioners to tune QUOKA for diverse hardware constraints with minimal quality loss.
4.6 ATTENTION LATENCY AND TTFT
To evaluate the efficiency of QUOKA, A, we measured latency in two settings: standalone attention mod- ules and -frett--rfttt (TTFT) on the Qwen3-4B model. All experiments use the HuggingFace implementation with bfloat/ 1 6 precision and FlashAttention for the dense bascline. Each data point is averaged over 100 trials, and hyperparameters follow original publications. To compare QUOKA measured performance across increasing input sequence
with existing sparse attention methods, lengths. All reported times are expressed as speedups relative to the full attention module, and the end-to-end case, the base Qwen3-48 4B model with chunked prefill (Bęp 128). Figures 5a and 5b show QUOKA A scales substantially better than the dense baseline and consistently outperforms or matches the strongest sparse attention competitors speedups on consumer-gres -grade hardware: Figures 5c and 5d show 5-6x gains at long context lengths on both an Intel Xeon W-2125 CPU and Nvidia RTX 2080 GPU, and in decoding (Figure 6).
Nvidia A 1000 QUOK A also achieves significant
5 RELATED WORK
As discussed in Section 2, the computational bottleneck in prefill stems from the quadratic growth of attention with the size of the KV cache. Under chunked prefill, this cost can be mitigated by subselecting the KV pairs used in the attention. In this context, we review three related lines of work.
Query-dependent sparse attention methods select subset of cached keys for each query using lightweight proxies for attention scores (Singhania et al., 2024; Tang et al., 2024; Yang et al., 2024b; Ribar et al., 2024). While effective for single-query decode, naively averaging such proxies across multiple queries prefill chunk often degrades accuracy because these methods are tuned for generation-time settings. SampleAttention (Zhu et al., 2024) targets prefill but treats multiple queries homogeneously. Since queries can exhibit distinct geometry with respective to keys, such a geometry- aware query and key subselection is desirable. QUOKA first selects representative queries via cosine dissimilarity and then selects keys via cosine similarity, enabling higher sparsity at comparable accuracy.
Dynamic query- -eeeddee sparse attention:
8

---

Published as a conference paper at ICLR 2026
Reialive Speeciup (eb Depse)
Sample Attn
Spart)
Relatzve Spoedup (ve
Spart
Marel QUIOA
LewelsMors
2.0
QUOKA
1.5
5,000
10,000
20,000
25,000
10,000
20,000
30,000
40,000
50,000
60,000
Sequence Length (loeens)
Sequence Length (lokens)
(a) Attention latency on NVIDIA A100 GPU
(h) TTFT NVIDIA A A100 GPU
Relative Speedap (vs, Dense)
Sample
Sample
Laki
Loki
Spart)
Spart)
LasslsMore DUOKA
LausBaMMrw QUDKA
Relative Speedap
2-
5,000
10,000
15,000
20,000
25,000
5,000
10,000
15,000
20,000
25,000
Sequence Length (takens)
Sequence Longth (tokens)
(c) Attention latency Intel Xeon W-2125 CPU
(d) Attention latency on NVIDIA RTX 2080 GPU
Figure 5: Relative speedup of attention and TTFT compared to dense attention baseline using
BcP 128 different hardware.
KV cache eviction: KV cache eviction removes low-salience KV pairs to reduce memory footprint based on pre-defined patterns, attention scores, or cosine similarity of the keys (Xiao al., 2024; Zhang et al., 2024; Li et al., 2024; Oren et al., 2024; Park et al., 2025). Like query-dependent sparsification, most eviction policies are designed for single-query generation; few works aggregate importance across multiple queries (Li et al., 2024; Kim et al., 2024), but typically treat queries homogeneously and remain generation-centric. Eviction complementary our approach and could be integrated with QUOKA in chunked prefill; we leave this to future work.
Kernel-level sparse attention: Another line work accelerates prefill through kernel-level sparse attention, typically relying on predefined patterns such as block, band, or strided sparsity (Child et al., 2019; Dao et al., 2022; Xu et al., 2025b; Jiang et al., 2024; Lai et al., 2025). While effective with spe- cialized CUDA implementations. these methods require hardware-specife kernel optimizations and often incur additional overhead. In particular, under chunked prefill the repeated kernel invocations and memory transfers substantially reduce their efficiency. By contrast, QUOKA is fully compatible with standard dense kernels and avoids such hardware and runtime dependencies.
CONCLUSION
We introduced QUOKA, a training-free and hardware-agnostic sparse attention mechanism that reduces LLM inference latency. Leveraging the geometry of queries and keys. QuoKA identifies and retains the most influential queries to score and subselect the KV cache for attention without sacrificing accuracy. Across LongBench and RULER, QUOKA achieves near-dense performance with fraction of the budget while outperforming competing sparse attention methods. On Math500 QUOKA further demonstrates versatility by surpassing seneration-speciie methods and even dense attention in some cases. In addition, QUOKA provides substantial efficiency gains, including up to 5x standalone attention speedup and 3x TTFT reduction across different devices, suggesting that selective attention is promising direction for TTFT and TPS optimization. An avenue for future improvement is to make the computation QKT more efficient, for example by exploiting query/key channel sparsity or learned low oiw-dinesiional projections.

---

Published as a conference paper at ICLR 2026
7 ETHICS STATEMENT
This work presents QUOKA, A, hardware-agnostic sparse attention algorithm designed to accelerate transformer inference. Our research does not involve human subjects, sensitive personal data, or datasets that raise privacy or security concerns. All datasets used -Needleln----Hayttee RULER, and Math500) are publicly available and widely used the research community. To our knowledge, QuOKA does not introduce methodologies or applications that pose foreseeable risks of misuse or harm. We have no conflicts of interest or sponsorship to declare. We believe this work adheres to the code of ethics and does not raise any ethical concerns.
LongBench,
REPRODUCIBILITY STATEMENT
We have taken care to ensure that QuoKA is readily reproducible. The main paper includes a detailed description of the algorithm, including its design principles, KV scoring/subsclection strategy, and implementation using standard linear algebra routines. We provide comprehensive experimental setups, including datasets used, evaluation metrics, and hardware specifications. All hyperparameters documented in the main text and appendix. While we have not included
and test configurations source code, the simplicity of QUOK A's training-free design makes it straightforward to implement using widely available libraries.
REFERENCES
Sandhini Agarwal, Lama Ahmad, Jason Ai. Sam Altman, Andy Applebaum, Edwin Arbus, Rahul Arora, Yu Bai, Bowen Baker, Haiming Bao, et al. gpt-oss-120b & gpt-oss-20b model card. arXiv preprint arSiv:2508. 10925, 2025.
Amey Agrawal, Ashish Panwar, Jayashree Mohan, Nipun Kwatra, Bhargav S Gulavani, and Ra- machandran Ramjee. Sarathi: Efficient I1m inference by piggybacking decodes with chunked prefills. arXiv preprint arXiv:2308. 16369, 2023.
Amey Agrawal, Nitin Kedia, Ashish Panwar, Jayashree Mohan, Nipun Kwatra, Bhargav Gulavani, Alexey Tumanov, and Ramachandran Ramjee. Taming (Throughput-Latennn tradeoff in (LLM) inference with (Sarathi-Serve). In 18th USENIX Symposium on Operating Systems Design and Implementation (OSDI 24), pp. 117-134, 2024.
Arney Agrawal, Nitin Kedia, Ashish Panwar, Jayashree Mohan, Nipun Kwatra, Bhargav S Gulavani, Alexey Tumanov, and Ramachandran Ramjee. Efficient IIm inference via chunked prefills. ACM SIGOPS Operating Systems Review, 59(2):9-16, 2025.
Joshua Ainslie, James Lee- Thorp, Michiel de Jong, Yury Zemlyanskiy, Federico Lebrón, and Sumit Sanghai. Gqa: Training generalized multi-query transformer models from multi-head checkpoints. arXiv preprint arXhv:2305.13245. 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 1: Long Papers), pp. 3119-3137, 3137, Bangkok, Thailand, August 2024. Association for Computational Linguistics. doi: 10. 1..11865/11222.aaa-aaa 172. URL https: httpss///aaaaaatahaaaae
org/ a01-224..ll...e long 172.
Elie Bakouch, Carlos Miguel Patino, and Anton Lozhkov. Smoll smol, multilingual, long-context reasoner - huggingface.co Huggingface Blog Post, 2025.
Srinadh Bhojanapalli. Ayan Chakrabarti, Andreas Veit, Michal Lukasik, Himanshu Jain, Frederick Liu, Wen Chang, and Sanjiv Kumar. Leveraging redundancy in attention with reuse transformers. arXiv preprint arXiv:21 10.06821, 2021.
Rewon Child, Scott Gray, Alee Radford, and llya Sutskever. Generating long sequences with sparse transformers. arXiv preprint arXiv: /904, 10509, 2019.
10

---

Published as a conference paper at ICLR 2026
Tri Dao. Flashattention-2: Faster attention with better parallelism and work partitioning. arXiv preprint arXiv:2307.08691, 2023.
Tri Dao, Dan Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. Flashattention: Fast and memory- efficient exact attention with io-awareness. Advances in neural information processing systems, 35: 16344-16359, 2022.
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, al. The llama 3 herd of models. arXiv preprint arXiv:2407.2178. 2024.
Yizhao Gao, Zhichen Zeng, Dayou Du, Shijie Cao, Peiyuan Zhou, Jiaxing Qi, Junjie Lai, Hayden Kwok-Hay So, Ting Cao, Fan Yang, et al. Seerattention: Learning intrinsic sparse attention in your llms. arXiv preprint arXiv:2410. 13276, 2024.
Connor Holmes, Masahiro Tanaka, Michael Wyatt, Ammar Ahmad Awan, Jeff Rasley, Samyam Rajbhandari, Reza Yazdani Aminabadi, Heyang Qin, Arash Bakhtiari, Lev Kurilenko, al. Deepspeed-fastgen:: High-throughput text generation for Ilms via mii and deepspeed-inffrrece. arXiv preprint arXiv:2401.0886 006671,...1..... 2024.
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? arXiv preprint arXiv.2444.06654 2024.
Huiqiang Jiang, Yucheng Li, Chengruidong Zhang, Qianhui Wu, Xufang Luo, Surin Ahn, Zhenhua Han, Amir H Abdi, Dongsheng Li, Chin Lin, et al. Minference 1.0: Accelerating pre-filling for long-contex, Ilms via dynamic sparse attention. Advances in Neural Information Processing Systems, 37:52481-5255 2024.
Aditya K Kamath, Ramya Prabhu, Jayashree Mohan, Simon Peter, Ramachandran Ramjee, and Ashish Panwar. Pod-attention: Unlocking full prefill-deoode overlap for faster Ilm inference. In Proceedings of the 30th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2, pp. 897-912, 2025.
G. Kamradt. Needle in a haystack pressure testing llms. GitHub repository, 2023. URL https: //github. cwm/ g amaradt LLMTest www.rresst_eeelleeennaaatttttss
Minsoo Kim, Kyuhong Shim, Jungwook Choi, and Simyung Chang. Infinipot: Infinite context processing on memory-constrained lims. arXiv preprint arXiv:2410.015188 2024.
Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica. Efficient memory management for large language model serving with pagedattention. In Proceedings of the 29th Symposium on Operating Systems
Principles, pp. 611-626, 2023.
Xunhao Lai, Jianqiao Lu, Yao Luo. Yiyuan Ma, and Xun Zhou. Flexprefill: A context-aware sparse attention mechanism for efficient long-sequence inference, In The Thirteenth International Conference Learning Representations, 2025. URL https::/ /ttp://://////eeeee/// net forum? id=OfjIlbelrf.
Yuhong Li, Yingbing Huang, Bowen Yang, Bharat Venkitesh, Acyr Locatelli, Hanchen Ye, Tianle Cai, Patrick Lewis, and Deming Chen. Snapkv: Lim knows what you are looking for before generation. arXiv preprint ar arXiv:2404, 2122224444.445 14469, 2024.
Nelson Liu, Kevin Lin, John Hewitt, Ashwin Paranjape, Michele Bevilacqua, Fabio Petroni, and Percy Liang. Lost in the middle: How language models long contexts. Transactions of the Association for Computational Linguistics, 12:157-173, 20244
Gabriel Mongaras, Trevor Dohm, and Eric Larson. Cottention: Linear transformers with cosine attention. In Intelligent Computing-Proceedie of the Computing Conference, pp. 485-500. Springer, 2025.
Matanel Oren, Michael Hassid, Yossi Adi, and Roy Schwartz. Transformers are multi-state mns. arXiv preprint 4rXiv:2401.06 006044 2024.
11

---

Published as a conference paper at ICLR 2026
Junyoung Park, Dalton Jones, Matthew Morse, Raghavv Goel, Mingu Lee, and Chris Lott. Keydiff: Key similarity- -bssed kv cache eviction for long-context Ilm inference in resource-constraing environments. arXiv preprint
2025.
Luka Ribar, Ivan Chelombiev, Luke Mudlass-Galleyy Charlie Blake, Carlo Luschi, and Douglas Orr. Sparq attention: Bandwidth-efficien Ilm inference. In International Conference on Machine Learning, pp. 42558-42555 PMLR, 2024.
Jay Shah, Ganesh Bikshandi, Ying Zhang, Vijay Thakkar, Pradeep Ramani, and Tri Dao. Flashattention-3: Fast and accurate attention with asynchrony and low-precision. Advances in Neural Information Processing Systems, 17766688-686855 2024.
Prajwal Singhania, Siddharth Singh, Shwai Hc, Soheil Feizi, and Abhinav Bhatele. Loki: Low- rank keys for efficient sparse attention. Advances in Neural Information Processing Systems, 37: 16692-16723, 2024.
Jiaming Tang, Yilong Zhao, Kan Zhu, Guangxuan Xiao, Baris Kasikci, and Song Han. Quest: Query-aware sparsity for efficient long-context Ilm inference. arXiv preprint arXiv:2406.10774, 2024.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. Efficient streaming language models with attention sinks. In The Twelfth International Conference on Learning Representations, 2024.
Daliang Xu, Hao Zhang, Liming Yang, Ruiqi Liu, Gang Huang. Mengwei Xu, and Xuanzhe Liu. Fast on-device I1m inference with npus. In Proceedings of the 30th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 1, pp. 445-462, 2025a.
Ruyi Xu, Guangxuan Xiao, Haofeng Huang, Junxian Guo, and Song Han. Xattention: Block sparse attention with antidiagonal scoring. arXiv preprint arXiv:2503. 16428, 2025b.
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, 2024a. URL https: /wtwxvaivvv//.////////...//..av. org/ als/ 2407.1066
An Yang, Anfeng Li, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Gao, Chengen Huang, Chenxu Lv, et al. Qwen3 technical report. arXiv preprint ar arXiv:2505.00 099388 2025a.
Lijie Yang, Zhihao Zhang, Zhuofu Chen, Zikun Li, and Zhihao Jia. Tidaldecode: Fast and accurate Ilm decoding with position persistent sparse attention. arXiv preprint arXiv:2410.05076, 2024b.
Lijie Yang. Zhihao Zhang, Arti Jain, Shijie Cao, Baihong Yuan, Yiwei Chen, Zhihao Jia, and Ravi Netravali. Less is more: Training-free sparse attention with global locality for efficient reasoning. arXiv preprint arXiv:2508.07/1 2025b. URL https: // arxiv. org/ / abs////////// 2508 07101.
Jintao Zhang, Chendong Xiang, Haofeng Huang, Jia Wei, Haocheng Xi, Jun Zhu, and Jianfei Chen. Spargeattn: Accurate sparse attention accelerating any model inference. arXiv preprint arXiv:2502. 18137, 2025.
12

---

Published as a conference paper at ICLR 2026
Zhenyu Zhang, Ying Sheng, Tianyi Zhou, Tianlong Chen, Lianmin Zheng, Ruisi Cai, Zhao Song, Yuandong Tian, Christopher Ré, Clark Barrett, et al. H2o: Heavy-hitter oracle for efficient generative inference of large language models. Advances in Neural Information Processing Systems, 36, 2024.
Guangxiang Zhao, Junyang Lin, Zhiyuan Zhang, Xuancheng Ren, Qi Su, and Xu Sun. Explicit sparse transformer: Concentrated attention through explicit selection. arXiv preprint arXiv:1912.11637, 2019.
Qianchao Zhu, Jiangfei Duan, Chang Chen, Siran Liu, Xiuhong Li, Guanyu Feng, Xin Lv, Huanqi Cao, Xiao Chuanfu, Xingcheng Zhang, et al. Sampleattention: Near-lossless acceleration long context Ilm inference with adaptive structured sparse attention. arXiv preprint 24X1v22406.15486, 2024.
13

---

Published as a conference paper at ICLR 2026
QUOKA Supplementary Material
A CHUNKED PREFILL WITH QUOKA
We provide the full algorithm of QUOKA A used in chunked prefill. Algorithm 2 summarizes the optimized prefill processes with QUOKA under chunked prefill.
Algorithm 2 Chunked Prefill with QUOKA
Require: Input sequence X Xo, XI...., XB-1) chunk size L, KV budget BSA
1: Initialize output list y +- []
2: for each chunk X; do
3: Compute queries Qi, keys Kú, values V; from X;
4: (K,V) < QUOKA(Q;, Ket, Vei, BSA)
Subselect KV cache
5: Y; + ATTENTION(Q;, [R] K.), V V.))
6: Append Y, to
7: Ke411 Ki), Ve++1 [V]
Update KV cache
8: end for
9: return Y Concat())
B ADDITIONAL TIMING RESULTS
Delaiive Speedup (vs. Denee)
Relative Speedap Ovr. Denge)
Sample
Spart
2.00
LaeslaMiew
1.75
QUOKA
1.50
1.25
15,000
20,000
10,000
20,000
30,000
40,000
50,000
60.000
Sequence Length (tokens)
Sequencc Length (tokens)
Attention latency (decnde) NVIDIA A100
End-to-Fnd latency (decode) NVIDIA A 100
Figure 6: Speedup versus full attention of an increasing number of decoding steps for a standalone attention module and end to end model (Qwen3-4B). Timings were measured on an Nvidia A100 GPU across 100 trials.
C RUNTIME AND MEMORY COMPLEXITY
We compute the runtime and memory complexity for QUOKA A and competing sparse attention methods in Table For prefill chunk size Bep, KV cache length T, number of V heads nkv. number of heads nQ, hidden dimension d and number of subselected queries No. QUOKA has O(Brr + (No (1 + dngy))7) runtime complexity and ([(nkyNQT) memory complexity. Note that both terms require πgy rather no where nQ ykV, resulting in significant compute and memory savings. For SampleAttention, given the same parameters we obtain O ((dnq + no ngv + T runtime complexity and ((ngNo7) memory complexity. Note that since this method
14

---

Published as a conference paper at ICLR 2026
computes attention logits before aggregation, no appears in both terms. For Loki and SparQ, let di < d be the lower dimension used to downproject the channels of Q and K. With this SparQ has runtime complexity O(BerIdino) and memory complexity O(noBrrI] whereas Loki has runtime complexity ((dma + d( Bcp + T)) due to the matrix multiplications and memory complexity (ng 7. Note that Loki additionally has memory overhead of (ddino) to store the downprojection matrices in each layer. Finally, since LessIsMore is not applied uniformly across layers, where L is the number of layers, we amortize complexity to obtain runtime complexity of Odng Ber L) and memory complexity of (ng BerT/ LL). Note that, asymptotically our method more efficient than other methods due to the fact that ngv < nq. justifying our are-aggregation design.
Table 4; Runtime and memory complexity of sparse attention methods.
Runtime Complexity
Memory Complexity
QUOKA
O (BcP + (No(1 (1 + dT)
NoT)
SampleAttention
O + +nq/ IKVV + NKT)
((naNoT)
SparQ Loki
OBCpIIddng
OnnoBerT)
O (ding (Bep'' + d(Ber + +))) O CdnTBeTT/I.
Onqg)rr)
LessIsMore
O(ngBeIT L))
D MATHEMATICAL PROOFS
We provide the statement of Theorem 1 for completeness below along with the accompanying proof. Note that due to the unique geometry of LLM attention heads, this theorem implies that if go is angularly distant from Mq. it will have higher attention scores with most keys. Specifically, as CosSim Mq; k)) + 1, the cosine similarity CosSim(Mq;99) is bounded above by monotonically decreasing function converging to -1.
Theorem 1. Consider tokens a fixed query go and key k, and let the average of set of queries be denoted MQ. Suppose CosSim lk, qo) = Bx > O and CosSim MQ. k) as < 0. Then
CosSim(Mo q¹) S 1 + 3x - 0.5a 0.5
(A.1)
Proof. First compute the cosine similarity of MQ with g": CosSim( Mo, = 1T q" Ma can expand Mo in an orthonormal basis containing k/[[A|],
We
where MQ
||Mell //1b/||||++
+ Σ aari) and a; CosSim(Mq, Let B CosSim(q ri) and note
n-1
n-1
since 7; are orthonormal we have that oz +
Σ af and that 82
+
Σ
8
Then
T
(IMO
[[Mollank//
/
Mallaars
g- T MQ
11 |||
Mell
119 |||
-0 +
0.9 rj
l19*1
n-1
=0 +
a
<
|o,|1.8.
15

---

Published as a conference paper at ICLR 2026
(a) QUOKA
(b) SampleAttention
(c) Full
(d) Loki
(c) SparQ
(f) LessIsMore
Figure 7: Accuracy across document length and needle depth for NIAH using additional sparse attention methods with BSa 2048 and Bep = 128.
Using Young's inequality:
S
Σ
0f + 33
2 t=1
(1
1
1 32
+ 0
0g
2
2
2
E ADDITIONAL NEEDLE IN A HAYSTACK EXPERIMENTS
In Figure 7 we show the results of the Needle In Haystack experiment utilizing variety of selective attention methods. We used the 1amman.--3B-Instteee with selective budget BSA- 2048. The figure clearly shows the degradation incurred using most selective attention techniques with chunked prefill, while QUOKA is competitive even with full attention. This indicates that information is retained and recalled significantly more effectively using QUOKA under chunked prefill.
model and chunked prefill with Ber 128
F ADDITIONAL RULER RESULTS
provide additional results QUOKA on RULER benchmark, varying prompt length and selective attention budget BSA- As shown in Table 5, QuoKA achieves near-dense accuracy with 1/8- - 1/4 of the full KV cache. This suggests that a significant speed up can be obtained for long context tasks with relative little performance drop.
G EXTENDED LONGBENCH RESULTS
In Tables 6 and present the performance individual tasks of different models using different sparse attention methods across different selective attention budgets BSA- In particular, Table 6 shows detailed task scores for different sparse attention methods across array of models in which QUoKA consistently outperforms by a gap of 10 40%. Table show a more detailed ablation studying the effects of varying BSa on LongBench tasks using only QUOKA. We selective budget of 1024 achieves less than 5% error overall, which is remarkable considering this is less than 1/10 of the average task length for the considered LongBench tasks.
that general,
16

---

Published as a conference paper at ICLR 2026
Table QuOKA RULER results across prompt lengths and BSA {1024, 2048, 4096).
Prompt Length
Model
Budget
4096
8192
16384
32768
Full
87.50
81.33
76.98
74.31
4096
87.51
80.60
75.69
69.95
Llama-3.2-2
2048
87.33
80.20
73.79
63.67
1024
86.71
80.19
70.90
$7.01
Full
89.45
90.24
90.53
86.65
4096
89.45
89.03
87.46
81.33
Llama-3.1-33
2048
89
88.82
86,21
78.86
1024
89.24
89.51
83.25
70.04
Full
89.57
81,99
76.09
71.69
Qwen-2.5-3B
4096
89.53
81.53
74.83
68.43
2048
89.56
79.41
71.13
63.82
1024
87.85
74.27
66.82
59.37
Full
93.32
91.68
91.18
88.54
Qwen-3-4B
4096
93.32
91.83
91.06
2048
93.13
91.80
88.87
85,23
1024
93.73
91.07
88.57
74.83
Full
91.21
83.46
80.11 11
75.18
4096
91.21
83,70
79.66
71.83
Smollm3
2048
83.06
78.26
67.65
1024
89.97
79.94
72.69
61.37
H
MATH 500 RESULTS
The MATH-500 benchmark is a test designed to challenge the mathematical reasoning capabilities of LLMs. It comprises 500 problems sourced from high-level math competitions like the AMC and AIME, spanning domains such algebra, geometry, number theory, precalculus, combinatorics, and probability. Unlike simpler datasets, MATH-500 emphasizes multi-step problem solving and abstract reasoning, requiring models to produce precise, sep-by-step solutions. It has become key benchmark for comparing LLMs' mathematical proficiency and due to long reasoning traces, good way to the effectiveness of selective attention models during generation. While the majority of focus on QUOKA A has been on its effectiveness with chunked prefill, also performs remarkably well during decode as well. This is seen in Table 8 which QuoKA performs well or better than other competing methods, with much smaller reasoning traces generally resulting in significantly shorter reasoning times. This suggests that more information is collated during reasoning with QUOKA A than competing methods.
I
ABLATIONS
Table Scoring Ablation
Table 10: Aggregation Ablation
Ruler Test Length
Ruler Test Length
Scoring
Aggr.
4096
8192
16384
32768
4096
8192
16384
32768
Dot Prod. 83.76
68.22
57.97
46.24
Mean
84.28
69.14
58.81
45.53
Cos. Sim
88.56
73.78
65.57
52.48
Max
88.56
73.78
65.57
52.48
In this section report the results of several ablation studies. In Table 9 we explore the effects of using cosine similarity instead of dot products to estimate the attention scores prior to aggregation in QUOKA. Specifically, we apply our method varying both scoring methods in the Llama3.2-3B Instruct model on the RULER benchmark, where is clear that the cosine similarity provides more normalized, better aggreated scores for selective attention. In Table 10 we demonstrate the differences between aggregation across the query dimension the approximated attention scores using both the max and the mean. Again, the Ilama3. 2-3B-Instrue model and RULER benchmark used, and
17

---

Published as a conference paper at ICLR 2026
Table 6: LongBench results comparing performance of different selective attention mechanisms across different budgets.
Namuatce QA
Queper
2W1ERR0A
Musque
GorRoper
TRICC
SANSRE
FR-mn
Tic
RI--7
Any-
10279
16976
14934
01:83
01864
13342
03693
0.982
3.874
3360
QUOKA
1785
0.972
2048
00713
0051
1/029
188
10352
0.863
0.354
0.56
1.91
1.000
1706
0.583
0.399
1901
0556
0U995
512
D:259
16677
0.381
11545
0.230
0.817
0.387
1022
0.587
1983
0.53
0.12
0.662
0,886
0.735
Senplokanvion
1004
01914
0.17
0.18
0.56
0.834
0.922
0.33
0.902
1019
0.348
0093
0.91
0.234
0991
0916
01.
D199
0/66
01288
0.50
0.39
0.731
0.831
01925
023
1998
0.001
0.96
0381
01703
244
00004
0921
10705
0.577
087
0.549
0.835
0.81
10905
0.546
1080
0.99
0.354
1803
1100
0.25
513
06629
006
06689
11:00
03330
01339
01580
19955
102-
0991
06289
0.60
01731
SpaQ
1004
0.35
030
6679
0.564
0.335
0.595
0.336
0.517
1022
0.35
0085
0.05
0.234
0571
0501
0.922
512
0.53
0/63
0638
0.90
0.375
0.311
0.811
0.913
1739
0.846
0006
0.93
0.00
0.01
0.211
0,985
2048
D007
0397
0.35
14577
0.837
0.554
0.947
0.594
1/915
0.844
1973
0398
0.334
0.62
0377
0L942
21.4
15.52
$1.35
233
26.44
17.64
21.5
23.27
$3.57
43:35
31.51
23:128
513
0.28
0.553
10077
0.534
01:11
0.53
0.945
0.933
1.0
0.999
1991
537
0.751
0.744
1180
0.59
Q
2HH
D904
6962
1.333
0.985
0.975
131
1992
0.622
11000
1111
0.977
1804
0:226
0.0
0007
3.33
0.578
0.23
0.333
0.956
1.77
0.7
0997
0.95%
0.353
0.003
1016
0.765
2H4
03553
0.53
1063
06819
276
0.387
0.342
1/14
1,706
0.897
1069
0.973
0.563
0.966
1105
0.825
513
0196
0.77
0.342
0.304
0.53
0.76
01967
0.576
0:36
0.633
0.357
0336
6.766
0.96
TiddDoodd
1154
0,233
01397
0.425
0.282
3.6
0.26
0.007
0199
0.661
0563
0.594
Spar
1024
0422
0,66
0.35
0.385
0.529
0.365
0.322
0.965
1.75
0.555
0296
0.554
0.399
0.011
1846
0.225
2H6
0/01
0.60
10039
06622
01535
0.582
01945
1/301
1475
0.80
109-7
0.95
01011
0.6
1164
513
0.34
0.96
D612
0.30
0.337
0.333
0.857
0.823
1.90
0.18
0/05
0.76
0.93
0360
0.91
0.50
1104
1U773
11289
1381
1609)
0.71
0.5%
11.45
0.537
1,300
0.822
0.32
18:66
31.55
13.11
15:42
19.58
10:32
36.18
33.3
36.76
75.0
54.36
11.94
58146
67.10
63.1
43.300
512
0.335
0.623
0.993
QuoRA
1004
0005
0065
1007
1.113
1.022
1.009
0.311
0.97
0991
0.547
1.53
0.98
1,000
1,01
0196
10
D721
0379
019%6
01%
0.31
0.19
0198
01888
1005
5.55
0.557
1105
5956
0.5%
7016
0/207
6962
0967
1.90
1.00
0.553
0.441
0.455
0.91
0.054
1.05
0.955
0.55
1.01
69%
0.465
2.12
Tiddboode
1004
0.761
0.78
1096
01542
0.8.2
0.535
0.333
10
0067
0.335
1006
0183
0.344
0516
0561
0.542
3/2
0.39
0.51
0.36
0.555
0.711
0.335
0.855
0.581
1,9%
0.188
0,596
0375
0.999
0991
0.25
0.255
2H4
0654
0965
1947
1.903
01875
0.737
0.987
0.942
0696
0.548
1696
0.666
0.76
1.60
6951
1L923
513
0.195
0.07%
01:43
01311
0.385
0.530
0.315
0.557
Loke
1044
0.519
0.85
0.701
0.833
0.337
0.787
0
0091
0.195
0.57
0185
01.30
0.64
0503
(.911
0.915
0.331
3848
53-46
56.55
31.83
21.31
18.36
43.65
$4.14
54.00
QUAKA
1004
0004
01985
0.363
0.912
0.965
1.52
0.583
1/04
(1390
0.581
3,012
0.912
284
0326
0996
1/04
1.85
01877
0.995
0.999
0.985
1,0%5
0.599
1001
3.00
1.006
1148
1104
0.945
513
D1575
0.63
0.30
0.35
0.637
0.535
0.855
0.67
1.05
0.831
D1963
0.95
01907
0.955
0.511
0.765
Samploksaskk
1104
0066
0.99
0.52
0.911
0.536
0071
1106
0,975
0422
1104
D/603
0.309
01328
0.654
0.855
0.87
0696
0.871
1997
0.66
01351
0565
0.51
13373
0457
0.8
1051
09913
07281
0.59
01355
0.99
1.00
0.595
1066
0.63
0.911
0.66
116G
512
0.299
0.55
0/06
0.541
0.303
0.48
0.36
0.82
1.390
0.383
0.06
0.94
0333
0576
6.250
0.585
Spart)
1104
0.316
0299
1034
11722
00322
0.577
01345
0.997
1182
0.895
1982
0363
0.664
0373
0.762
03356
Take
0486
0.91
0.561
0.601
0.76
0171
01374
7868
0.58
0.60
0.066
0.17
0.85
0.8
1.0%
0.97
1006
0.67
09/6
0.60
0.908
0.8
0324
0.611
the higher scores indicated that the max captures important outlying key query interactions better than the mean.
In order to determine if QuoKA can be reliably used with different prefill chunk sizes, we use LongBench to test the Qwen3-4B model with both QUoKA and sample attention across different Bep. The results are presented in Table in which the number of queries selected No is 25% of BcP and the selctive budget BSA- = 1024. In this case we see no performance degradation when varying the prefill chunk size suggesting QuoKA is robust to changes in this parameter.
To explore the effects of varying the number of subselected queries during chunked prefill, we compared the performance of the Qwen3-4B model on the LongBench task using both QUOKA and SampleAttention. During prefill, the number of queries subselected varied between 4 and 128. These results are presented in Table 12 in which it is clear that very little performance is lost even with a small number of queries used to approximate attention scores for KV subselection. This performance, particularly compared to the closest competitor Sample seems to justify our query subselection method.
18

---

Published as a conference paper at ICLR 2026
Table 7: LongRench results (Higher is better). Each model utilizes chunked prefill with B = 128 with different selective budgets. Raw scores reported for base models and relative errors (percent of performance compared to baseline) presented for QUOKA.
Mathod
Seaget
Nurntii QA
Quope:
HoperQA
2WAIMQA
Maspp
KidiNens
19822
SAMSaa
Pl--s
Ang.
11:331
160.90
1.007
QUOKA
1001
512
11.84
0.863
0.644
0.96
1.001
B3801
0.365
10943
0.96-
1.000
(186)
1480
3163
0.855
1.034
1.294
4056
1.003
0.588
01302
00977
1.800
07990
1,000
1.00
1,000
0,933
22.01
42.49
43.00
30096
43.39
28-07
33-42
24.35
24.35
75.
93.17
42.04
98.1
36.35
56.35
45.31
19A
13373
0.34
00311
03577
3.99
0.283
1.5M
QLOKA
312
0.544
0.6
0379
0U778
3.584
0.765
0032
0.354
1.042
0073
3.0
3.000
0.386
1,24
1.003
0343
2015
(1975
8.883
1179
1.30
6993
B3663
04488
3.6
1
108
1706
0.967
0.868
1,366
0.86
0-486
4056
1.324
1.003
0.59
0.993
1.0
1.002
0/94
01415
0.933
0.55
0081
3.955
QUOKA
1024
01835
0.593
0327
0U796
0,54
0356
0.59
01354
0.955
0023
C377
1/22
0.501
0.50
0.6
03443
4056
07377
0.995
1/2
2.044
0/33
2.44
35552
31.55
25.3
25.44
17.64
32.55
21.5
23.29
675
85.37
43:85
43.5
51.57
07.55
29.128
156
0.354
0.91
0.88
065
3.95
0.13
OKOKA
0.00
0311
01933
0289
3.7
0,80
2015
0.334
0.60
1.30
01983
0313
1075
0194
0.755
1-2
1070
6.973
3.900
0.85
1.00
1.04
6477
4006
01343
1.6
0.955
0.533
0795
1.803
0093
2.544
0.53
QUOKA
1024
513
0.225
850
0.999
0366
00377
0.544
0.916
5000
1002
01351
0.98
1.021
10877
1
1103
1:31
1.5
1,077
1.34
0.556
LUSSS
4006
(1935
1335
132
3.58
0/955
25,02
43.35
33.46
35.35
43.31
31.22
$2.45
26.51
25.25
755
11.26
43
56.5
66.14
2100
5005
256
0.799
0.804
6217
0.50
0728
2.547
0.341
0,337
0.321
0.563
QCOKA
515
01814
0.564
0.35
0.39
1954
0196
0.94
1.00
0935
1006
1.05
0.76%
0.355
1.00
0.96
2048
0.33
0.592
1004
1.055
0.911
0996
0199
0.988
1.008
0.93
1011
1023
1.006
1.005
1.591
0.95
4006
6.11
1.000
1.309
0.991
00944
1.002
1187
3.900
1.005
1.301
01311
3.560
QUOKA
1024
512
1.241
1.000
0963
0.775
1.62
D3865
1821
0.240
1.01
00555
0.55
3
3360
0.80
1,222
0.834
0.555
4056
(1582
03885
0.567
1.04
1.311
EN1E3-918-668-222 2207
31.35
42.19
558
63.0
33.54
33.23
31.00
21.79
23.35
16.22
$2.42
46.43
100.
76.35
07.05
34.15
256
11555
1.548
1011
0.575
1399)
1.0
01.72)
0.59)
QUOKA
$12
0.333
1.022
0.35
0.988
0357
0966
1000
0.736
0.93
0971
1000
1000
1.5
1,007
0.39
0.75
2045
0.92
1.001
0.38
1/355
0.514
1012
1,09
1.02
0.58
0097
1915
1012
1.5
0.396
1.500
1/011
4056
1011
1.555
1,022
0.95
0/99
0937
QUOKA
1004
11.55
0.85
1487
1.305
1.99
0001
0.77
0.81
0981
0947
1.3
3.74
3963
1.03
1.00
0.980
1.01
4056
0.991
1.02
1.236
1446
100G
1016
0.97
0.95
1.0
0.555
3.560
0.999
0.995
1,155
19

---

Published as a conference paper at ICLR 2026
Table 8: Math 500 results across different selective budgets utilizing QUOKA. Reasoning generation
length limited to 8192 tokens.
Flex Match
Exact Match
Avg. Cien. Length
GPT-OSS-220
0.893
0.694
2558.262
SparQ
256
0.848
0.648
2436.86
Loki
128
0,055
0,711
0.714
2181.49
2276.0
Mess
3591.4
256
0.85
0.681
2830.49
QUOKA
128
0,911
0.707
2199.
Owen3-4p
0.82
0.701
1179.78
SparQ
0.615
2044,9002
256
0.777
0.658
1518.82
Loki
128
0.785
0.668
0,702
1345.88
1143.51
LesslsMore
256
128
0.729
0.814
0.695
0.621
2674.25
1618.00
QUoKA
0.708
0.703
Smollmm3
0.659
0.522
629.01
SparQ
128
0.647
0.514
715.18
256
0.665
0,532
634.34
Loki
128
0.615
0.494
621.02
618.47
LossIsMore
128
0.623
0.495
642,26
256
0.657
0.527
$98.907
QUOKA
256
0.661
0.527
614.73
Table 11: LongBench results for the Qwen3-4B model utilizing QUOKA across Ber {128, 256, 512} with BSA = 1024 (Higher is better). Set N₂ to 25% of Ber. Relative scores compared to the dense model are reported.
Ber
128
256
512
QUoKA
0.978
0.977
Sample Attention
0.876
0.871
0.872
Table 12: LongBench results for the Qwen3-4B model utilizing QUOKA across NQ (4, 8, 16, 32, 64, 128) with BSA 1024 and Ber = 128 (Higher is better). Relative scores compared the dense model are reported.
NQ
4
8
16
32
64
128
QUOKA
0.935
0.957
0.965
0.978
0.988
0.995
Sample Attention
0.854
0.862
0.88
0.878
0.885
0.884
20


Reviews:
[{"review_id": "IL1r83bJgo", "reviewer": "Reviewer_gbPS", "summary": "The paper proposes a novel sparse attention method for improving the efficiency of transformer models during the prefill stage with chunked prefill. The idea is to select a subset of important queries by divergence to the mean query and only compute attention for those important queries and important key-value pairs. The method is evaluated on SOTA open-source LLMs against other sparse attention baselines and shows better efficiency and performance frontier.", "questions": "Thank you for your submission. I like the paper overall and think the method is well motivated. I particulary enjoy the insight experiments in Figure 2 and 3, which make the motivation very clear. However, some claims and descriptions in the paper are poorly explained and a bit vague to me. I would appreciate it if the authors can clarify the following questions:\n- What is the relationship with chunked prefill? The proposed method seems to be highly dependent on chunked prefill, but the relationship is not very clear to me. I can understand that some previous sparse attention methods can be inefficient under prefill with multiple queries due to aggregated sparsity. But why is chunked prefill specifically needed for the proposed method? Is it possible to use the proposed method without chunked prefill?\n- \"however, due to dynamic compute graph and KV cache memory bandwidth overhead under chunked prefill, their benefits are limited.\" Can you please elaborate more on this point? Why dynamic compute graph and KV cache memory bandwidth overhead limit the benefits?\n- \"During prefill, when relevant KVs are selected for many queries at once, this can result in significant performance degradations. Under chunked prefill, where important KVs are repeatedly subselected for multiple queries, these degradations become more pronounced.\" These two sentences are particulary confusing to me. Why chunked prefill makes the performance degradation more pronounced?\n- The gather operator in algorithm 1 has inconsistent notations (at line 4 and line 12).\n- “As discussed in Section 2, existing sparse attention methods face limitations in prefill efficiency and portability.” What do you mean by portability here?\n- I don't fully understand the query selection process. Many of the previous sparse attention methods also reduce among the KV dimension, so the attention socres are approximated with partial KV, however, we still get the full attention scores for all queries. In this paper, it seems that you only select a subset of queries, does this means some of the queries are pruned? Does this means it is somehow similar to the previous work on token pruning?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The proposed method is well-motivated with insight experiments\n- The pseudo-code is extremely helpful in understanding the method\n- The experiment is solid", "weaknesses": "- Some explanations of the claims are confusing", "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": "TyCuna1DpX", "reviewer": "Reviewer_gdtt", "summary": "The authors propose a better chunked prefill technique which only uses a small subset of KV cache for each chunked prefill. The algorithm goes like this -- choose a subset of queries to select KV cache, compute scores for these queries and aggregate across heads and queries, choose topk scoring KV for chunked prefill. They show that their method outperforms a bunch of baselines at same sparsity.", "questions": "1. Can we have plots for cosine similarities (K, q) for chosen queries and all the queries.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "Strengths\n1. Great experimental breadth and strong performance compared to baselines. The experiments cover multiple benchmarks and baselines. \n2. Easy to understand algorithm.", "weaknesses": "1. The approach is not very principled. While it is true that queries with high similarity with K will have low similarity with Mean(Q) due to OOD nature of query and key distributions (this is what theorem says), the converse is not true (this is what you want for efficiency) . It is especially not true in high dimensions -- where it is highly likely that queries with low similarity with Mean(Q) would also have low similarity with K. \n\nSo this being a critical component of algorithm is unsettling. I would assume that most queriers chosen are actually even worse than Mean(Q) w.r.t similarity with K.  Can we have distribution plots of cosine similarities of chosen queries vs. all the queries. \n\nHaving said that their experimental section strongly supports their method.\n\n2. some latest baselines are missing -- duoattention, xattention, spargeattention, might be good to add discussion / results for these.", "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": "dTCGbCfmSz", "reviewer": "Reviewer_nDFH", "summary": "Due to the quadratic nature of attention, long-context prefill remains a major challenge for large language models (LLMs). However, each query only needs to attend to a subset of key–value (KV) pairs to achieve reasonable performance. Existing sparse attention methods either rely on fixed attention patterns or are optimized primarily for the generation phase.  \nThis paper presents **QUOKA**, which identifies representative queries from each chunk based on the smallest cosine similarity to the mean query vector, then uses these representative queries to locate important KV pairs. The model finally performs full query–subset KV attention. QUOKA achieves strong performance on long-context benchmarks and is efficient to implement.", "questions": "Thanks for submitting to ICLR 2026. This paper introduces an interesting idea of filtering query vectors using cosine similarity, inspired by DiffKV’s approach to KV cache filtering. However, I still have some concerns about the motivation and the efficiency claims.  \n\n## 1. Intuition behind the “critical” query vectors\nThe intuition for using “critical” query vectors is not fully convincing. It is true that such queries are closer to the key vector space and may attend to a wider range of keys or exhibit higher variance in attention scores. However, since the softmax operation is applied independently to each query, the proposed approach only ensures that these selected queries have smaller attention errors. It does not necessarily guarantee that other queries in the same group will also exhibit small errors. Intuitively, it is unclear why these tokens should be more important for overall generation accuracy.  \n\n## 2. Limited benefit in the generation phase\nIt is unclear how this method can lead to meaningful speedups during the generation phase. QUOKA estimates the similarity between each query and all keys, but since generation involves only one query vector, this step effectively performs half of the full attention computation. Even after selecting top-k keys and multiplying by the corresponding values, the overall computational reduction—and thus the speedup—appears minimal.  \n\n## 3. Hardware inefficiency due to small chunks\nIn the evaluation, the block size is set to 128. However, this configuration is inefficient on modern hardware, as each GEMM or attention operation on such small blocks yields low arithmetic intensity and thus lower TFLOPs. This effect is particularly noticeable on H100 and B200. In your latency test, do you also use block size 128 for the full attention baseline? A fairer comparison would allow full attention to use larger block sizes (e.g., 1024 or 2048), which are more hardware-efficient.  \n\n## 4. Constraints on KV selection\nAre there any constraints imposed on the selected KV pairs? If the selected KVs are discontinuous, how is self-attention computed efficiently using existing kernels? Discontinuous memory access patterns can severely hinder performance unless carefully optimized.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The evaluation is comprehensive and the reported results are impressive.  \n- The proposed method is clearly described, and the paper is easy to follow.", "weaknesses": "- Hardware efficiency may degrade due to the small chunk size and discontinuous KV selection.", "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": "pHTbkvPR0P", "reviewer": "Reviewer_JhZf", "summary": "The authors present QUOKA, a training-free sparse attention algorithm for efficient LLM prefill. The method prioritizes queries with low cosine similarity to the mean to subselect keys. This achieves a 3-7x speedup and an 88% reduction in key-value pairs, while maintaining near-baseline accuracy.", "questions": "- Could you provide a more direct comparison or discussion against a \"central representativeness\" approach, such as selecting K-Means query centroids? This would help to empirically situate the performance of your proposed heuristic.\n- The assumptions in Theorem 1 are central to the method's motivation. How consistently do these geometric conditions hold empirically across different models and layers? Supporting statistics or visualizations would be valuable.\n- For the Math500 experiments where query subselection is not applied, could you please clarify the exact mechanism of QUOKA? Specifically, how are keys selected for the single active query during the generation phase?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "-  The paper introduces a heuristic for query selection based on the hypothesis that queries with greater angular distance from the mean are more informative. This provides a geometric perspective on the multi-query attention problem that is distinct from conventional approaches focused on representativeness.\n- The algorithm is designed to be training-free and hardware-agnostic by avoiding the use of custom kernels. This design allows for its potential integration into various inference systems without requiring model retraining or fine-tuning.\n- The paper's experiments report reductions in Time-to-First-Token and attention latency across multiple hardware platforms. The results also show that these efficiency improvements are achieved while task accuracy is maintained close to that of the dense attention baseline.", "weaknesses": "- The paper does not include a comparison to alternative query selection strategies, such as selecting representative queries via clustering (e.g., K-Means centroids). Without this comparison, it is difficult to fully assess the performance of the proposed \"outlier query\" heuristic relative to more established methods for summarization.\n- The evaluation of the method's applicability to generation tasks appears less developed. Since the core query subselection component is bypassed in the single-query decoding scenario, a comparison against baselines specifically designed for decoding-phase KV management would be necessary to fully substantiate the method's competitiveness in this setting.\n- The potential impact of quantization on the method's performance is not discussed. The algorithm's reliance on precise geometric relationships (via cosine similarity) means its robustness in low-bit precision environments, which are common on its target hardware, remains an important but unevaluated factor.", "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)