acceptodds
Under review as a conference paper at ICLR 2027

ProbeRefine: Head-Adaptive Query Probing and Residual Refinement for Sparse Attention

Abstract

Large language models (LLMs) face substantial computational overhead during long-context prefilling due to the quadratic complexity of self-attention. Dynamic sparse attention alleviates this cost by selecting only a subset of tokens or blocks for computation, while proxy-based methods further reduce selection overhead by sharing block rankings across attention heads. However, head-specific budgets only determine how many blocks each head retains from a shared ranking, leaving limited flexibility in which blocks are selected when head preferences differ. In this paper, we introduce ProbeRefine, a training-free sparse attention method that preserves efficient shared proxy estimation while enabling head-specific block selection. ProbeRefine achieves this through two key designs: 1) Query-Guided Head-Specific Importance Estimation, which selects compact query probes for each head to estimate block importance and determine head-specific budgets; and 2) Gated Residual Block Replacement}, which revisits a bounded set of blocks beyond the shared cutoff and performs one-for-one replacement when a candidate receives sufficient head-specific importance and proxy support. Together, these designs allow different heads to refine their block selections without increasing the allocated block count or constructing full per-head attention maps. Experiments across Qwen2.5, Llama3.1, and Yi on RULER and InfiniteBench show that ProbeRefine consistently improves over ProxyAttn on both benchmarks and outperforms FlexPrefill across all three backbones on RULER while remaining competitive on InfiniteBench.

Primary area:
applications to computer vision, audio, language, and other modalities
Keywords:
Sparse Attention, Inter-Head Redundancy, Head-Adaptive Sparse Selection

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_hfiVOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

ProbeRefine is an improved version of ProxyAttn. The key difference is how it “probes” attention: it probes the attention matrix from the last query tokens.

Critical strengths

The method remains training-free and simple. Probing with outlier queries makes sense.

Critical weaknesses
  1. Novelty of the method is limited
  • The core sparsification algorithm is mostly from ProxyAttn. The only key difference is head probing, and I do not think this is significant enough to be published. I believe there should be more about probing.
  • There is also existing research addressing the nuances of sharing across heads versus accounting for differences between them, neither of which is cited here: specifically, “TokenSelect” (which examines soft voting across heads and head-specific attention patterns) and “SharePrefill” (which focuses on sharing patterns among heads).
  1. Limited evaluation
  • The cited papers and benchmark models are quite old, considering the speed of this kind of research. I strongly suggest updating the models to hybrid attention models, which are the mainstream of SoTA models, e.g., Qwen 3.8, DeepSeek 4.1 Flash, etc.
  1. Limited efficiency of implementation
  • ProbeRefine is even slower than the previous baseline, ProxyAttn.

And here is a critical mistake in the paper:

  • Table 6 should be titled Llama 3.1, but it is titled GLM. I am not sure which one is correct, but Tables 1 and 6 have exactly the same numbers while being claimed as different models, which makes no sense.
Questions for authors

Please check weakness section for answer my concerns.

4 comments
AuthorsOpenReview ↗

Response to Reviewer

Response to Reviewer — Part 1/3: Novelty and Related Work

We thank the reviewer for the careful assessment and helpful references. ProbeRefine builds on ProxyAttn but focuses on head-specific block correction after efficient cross-head sharing.


W1. Novelty and Relation to ProxyAttn

(1) Motivation. MInference [1] and FlexPrefill [2] sparsify sequence-axis interactions while considering head-dependent patterns or budgets. ProxyAttn [3] shares estimates across heads to reduce sparse-index selection cost. We retain this efficient coarse stage.

Yet head redundancy coexists with specialization [4,5]. ProxyAttn assigns per-head budgets, but each head takes a prefix of the shared ranking: budgets determine how many, not independently which, blocks are retained. We call this the shared-ranking bottleneck.

(2) Evidence and method distinction. Fig. 1(a) shows incomplete Proxy–Head and Head–Head Top-K overlap at 32K/64K. Fig. 1(b) shows W=16 covers 23.5%/12.6% of missed head-specific blocks; Fig. 1(c) shows that prefix expansion retains intervening blocks and increases budget.

DimensionProxyAttn [3]ProbeRefine
Initial selectionShared proxy rankingRetains the shared proxy ranking
Per-head budgetEstimated using queries from the last query blockEstimated using selected head-specific probes (outliers and, for longer contexts, representative queries)
Final selectionTop-K blocks from the shared ranking, with a head-specific budgetProbe-guided gated replacement beyond the shared cutoff; allocated block count preserved

Scale-aware probes estimate per-head importance for both budgets and candidate correction. Dual-gated one-for-one replacement revises block identities when justified by head-specific evidence. The contribution is a share-then-refine mechanism, not sharing alone.

(3) Experimental evidence. Tables 3 and 5 report controlled RULER probe ablations on Llama-3.1-8B-Instruct:

ContextProbe StrategyRULER
32KAvg-Q80.29
32KRandom-Q1690.07 ± 0.28
32KRepresentative-Q1690.39
32KOutlier-Q1692.07
64KOutlier-Q1687.26
64KOutlier-Q3286.30
64KBimodal-Q3284.62
128KOutlier-Q3278.61
128KBimodal-Q3279.09

Outlier-Q16 exceeds Random-Q16 by 2.00 at 32K. At 128K, Bimodal-Q32 (24 outlier + 8 representative) exceeds Outlier-Q32 by 0.48 at equal probe count; at 64K, Outlier-Q16 is best. Thus, probe selection and composition matter.

In Table 4, swap improves probe-defined remote Top-2 recall by 4.64/2.95 pp at 32K/64K with nearly unchanged active ratios. Its isolated macro-average gains are modest (+0.24/0.00); we do not attribute all framework gains to swap. Relative to ProxyAttn, ProbeRefine gains 1.86/0.86/0.97 RULER points and 0.10/0.51/0.12 InfiniteBench points on Qwen2.5/Llama-3.1/Yi.


W1. Relation to Prior Work

We appreciate the suggestions of TokenSelect [6] and SharePrefill [7]. TokenSelect uses per-head importance and soft voting for token-level KV-cache selection; we address block-sparse prefill, correcting blocks after shared ranking. SharePrefill shares prefill sparse patterns among similar heads; our focus is the remaining within-group ranking disagreement and budget-preserving correction.

In the revised manuscript, we will cite both and expand Related Work with further recent studies on head sharing, heterogeneity, head-aware selection, and long-context attention, clarifying our contribution.


References

[1] Jiang H, Li Y, Zhang C, et al. MInference 1.0: Accelerating Pre-filling for Long-Context LLMs via Dynamic Sparse Attention[C]//NeurIPS. 2024.

[2] Lai X, Lu J, Luo Y, et al. FlexPrefill: A Context-Aware Sparse Attention Mechanism for Efficient Long-Sequence Inference[C]//ICLR. 2025.

[3] Wang Y, He H, Bao S, et al. ProxyAttn: Guided Sparse Attention via Representative Heads[C]//ICLR. 2026.

[4] Michel P, Levy O, Neubig G. Are Sixteen Heads Really Better than One?[C]//NeurIPS. 2019.

[5] Voita E, Talbot D, Moiseev F, et al. Analyzing Multi-Head Self-Attention: Specialized Heads Do the Heavy Lifting, the Rest Can Be Pruned[C]//ACL. 2019.

[6] Wu W, Pan Z, Fu K, et al. TokenSelect: Efficient Long-Context Inference and Length Extrapolation for LLMs via Dynamic Token-Level KV Cache Selection[C]//EMNLP. 2025.

[7] Peng D, Fu Z, Ye Z, et al. Accelerating Prefilling for Long-Context LLMs via Sparse Pattern Sharing[EB/OL]. arXiv:2505.19578, 2025.

Response to Reviewer — Part 2/3: Efficiency and GLM Correction

We thank the reviewer for carefully examining the implementation efficiency and identifying the GLM reporting inconsistency. We clarify the measured trade-offs and the corrections below.


W3. Implementation Efficiency

(1) Runtime limitations and their source. We agree that ProbeRefine is slower than ProxyAttn at some lengths and settings. We retain ProxyAttn's low-cost shared estimation, but head-specific probing, importance aggregation, budget selection, and residual refinement add work. Fig. 5 indicates that the main additional overhead lies in selection, rather than layout construction. Timings include selection, layout, and sparse execution.

Appendix E reports attention-pipeline speedups over a common FlashAttention reference:

LengthProxyAttnProbeRefine
32K1.4x1.7x
64K2.7x2.3x
128K3.6x2.5x

ProbeRefine is faster at 32K but slower at 64K/128K under these settings; at 128K, the speedup ratio 3.6/2.5 implies approximately 44% higher pipeline latency. At 4K–16K its additional selection work is not yet amortized (Fig. 4). We acknowledge these limitations.

(2) Quality at comparable latency. To evaluate whether the extra cost can improve task quality, we swept ProbeRefine, ProxyAttn and FlexPrefill at five coverage thresholds and two lengths (64K/128K): 30 operating points, each using 416 RULER examples. Latency was measured on NVIDIA A800 with fixed real QKV from four layers, not full-model inference. Additional fine-grained ProxyAttn thresholds were chosen by latency before evaluating quality. Gamma is the cumulative-importance coverage threshold.

LengthMethodGammaRULERLatencyActive ratio
64KProbeRefine0.95087.2688.74 ms0.3649
64KProxyAttn0.96084.1487.81 ms0.3483
128KProbeRefine0.95079.09290.94 ms0.3092
128KProxyAttn0.96578.85284.40 ms0.3374

The absolute latency mismatch divided by ProbeRefine latency is 1.05% at 64K and 2.25% at 128K, within our predefined 5% criterion. Relative to ProxyAttn's latency, ProbeRefine obtains +3.12 RULER points for +1.06% latency at 64K, and +0.24 points for +2.30% latency at 128K. We do not claim statistical significance for the smaller 128K gain. These points use different coverage settings from the original 44% comparison.

(3) Scope and optimization opportunities. These comparisons match runtime, not identical active-block budgets. ProbeRefine does not dominate every point: at 128K, ProxyAttn (gamma=0.90) scores 75.00 at 115.31 ms, while ProbeRefine (gamma=0.80) scores 74.28 at 119.87 ms.

In separate paired four-layer tests, swap alone adds only 1.14% (32K) and 0.68% (64K), so the overall gap cannot be attributed to replacement alone. Fig. 5 suggests concrete future optimization opportunities: fusing probe scoring with importance aggregation, reducing intermediate-memory traffic and budget-sorting overhead, and exploring GQA-aware K/V reuse where compatible with head-specific masks. These are future engineering directions, not measured speedups. We will clarify both current limitations and opportunities in the revision.


Critical Reporting Issue: GLM Table 6

We sincerely apologize for a transcription error in Appendix B, Table 6: the three Llama-3.1 rows from Table 1 were inadvertently copied into the GLM table. These duplicated entries are not independent GLM evidence. The corrected GLM-4-9B-Chat-1M RULER results are:

Method4K8K16K32K64K128KAvg.
FlexPrefill92.0791.1189.4291.5986.5483.1788.98
ProxyAttn93.2791.3589.9090.8786.5480.7788.78
ProbeRefine93.9991.5990.8791.5986.7881.9789.46

ProbeRefine has the highest six-length average (89.46), +0.68 over ProxyAttn, while FlexPrefill performs better at 128K (83.17 vs. 81.97). We will replace the duplicated entries and revise Appendix B to reflect these corrected findings.

Response to Reviewer — Part 3/3: Recent Hybrid-Attention Evaluation

We thank the reviewer for suggesting evaluation on recent hybrid-attention architectures. We added Qwen3.5-9B [8] results and an independent diagnostic of head-specific block refinement.


W2. Evaluation on a Recent Hybrid-Attention Model

(1) Model and adaptation. Qwen3.5-9B (2026) combines Gated DeltaNet and Gated Attention. We selected this 9B model to evaluate a recent hybrid architecture up to 128K within available resources. Its 32 text layers include 24 linear-attention and 8 full-attention layers. ProxyAttn [9], FlexPrefill [10], and ProbeRefine replace only the prefill computation of the 8 full-attention layers (zero-based indices: 3, 7, 11, 15, 19, 23, 27, 31). Linear-attention layers and decoding remain unchanged. Dense Attention denotes unmodified Qwen3.5-9B without sparse block selection.

(2) RULER results. All four methods were evaluated at six context lengths. Bold indicates the best results among the three sparse methods, including ties.

Method4K8K16K32K64K128KAvg.
Dense Attention93.4196.5696.4096.8795.8996.0595.86
ProxyAttn [9]93.3896.2796.1596.8796.1395.9895.80
FlexPrefill [10]92.4496.5195.6796.6396.4596.2295.65
ProbeRefine93.0296.5196.3296.8795.9295.8695.75

ProbeRefine averages 95.75, close to Dense Attention (95.86), ProxyAttn (95.80), and FlexPrefill (95.65), demonstrating competitive task quality on a recent hybrid backbone.

(3) Independent dense-reference diagnostic. To isolate residual replacement beyond shared ranking and probing, we conducted a paired 64K analysis on 12 RULER examples from four tasks. No Swap and Swap (W=16) shared dense-forward Q/K activations, proxy rankings, Q16 probes, and per-head budgets. Only gated one-for-one replacement differed. Ranking, selection, and swap operated on 128-token blocks; the resulting masks were mapped to 64-token execution blocks for the Triton kernel at head_dim=256, without re-selection. Per-row block counts remained equal before and after mapping.

Metric definition. Held-out Dense Top-2 Recall measures the fraction of the two highest-importance non-protected, causally visible 128-token key blocks, identified using dense causal attention on query positions excluded from probing, retained by the sparse layout. Dense Attention Mass Retained measures the original dense-softmax probability mass covered by selected blocks, accounting for both inserted and removed blocks.

DiagnosticNo SwapSwapGain (95% bootstrap CI)
Held-out Dense Top-2 Recall88.98%89.38%+0.405 pp [0.313, 0.498]
Dense Attention Mass Retained80.463%80.543%+0.080 pp [0.070, 0.089]
Executed 64-token Causal Block Ratio53.83%53.83%0

At the unchanged 53.83% execution-block ratio, Swap recovered 304 previously missed Top-2 hits and lost 105 initially retained hits, a net gain of 199. Both diagnostic metrics improved in 7 of 8 full-attention layers; the first showed a small decrease. The confidence intervals use task-stratified, sample-level bootstrap resampling. The execution-block ratio is distinct from the 128-token selection-block ratio and does not imply measured speedup.

(4) Implications. The paired diagnostic provides modest, independent evidence that probe-guided replacement improves head-specific block coverage at an unchanged block budget. Alongside full-model RULER results, it tests which blocks are retained as well as downstream task quality. We will add these results and the adaptation and diagnostic protocols to the revised manuscript.


References

[8] Qwen Team. Qwen3.5: Towards Native Multimodal Agents[EB/OL]. 2026.

[9] Wang Y, He H, Bao S, et al. ProxyAttn: Guided Sparse Attention via Representative Heads[C]//ICLR. 2026.

[10] Lai X, Lu J, Luo Y, et al. FlexPrefill: A Context-Aware Sparse Attention Mechanism for Efficient Long-Sequence Inference[C]//ICLR. 2025.

Dear Reviewer hfiV, We would appreciate your feedback on whether our rebuttal has adequately addressed your concerns. If any questions or concerns remain, we would be happy to provide further clarification and continue the discussion. Thank you for your time and consideration.

Reviewer_uNtfOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

ProbeRefine extends proxy-based sparse prefill with head-specific query probes and a bounded residual correction. Queries selected from the final query block estimate each head's block importance and budget. A shared proxy ranking supplies the initial block set, after which a gated one-for-one replacement can recover a head-preferred block beyond the cutoff.

Critical strengths
  1. The distinction between changing a head's budget and changing its block preferences is well motivated. A shared ranking cannot express arbitrary head-specific preferences simply by changing the cutoff. The bounded replacement is a simple way to address this limitation without increasing the allocated block count.

  2. The method has a practical GPU implementation using vectorized residual refinement and the FlexPrefill block-sparse backend, which provides empirical support for the hardware efficiency of the algorithm–implementation co-design on the evaluated GPU.

Critical weaknesses
  1. There is a concrete reporting inconsistency. Every entry in the three GLM rows of Appendix B, Table 6, including the averages, matches the corresponding Llama-3.1 rows of Table 1. This needs correction or explanation before the GLM experiment can support an additional generalization claim.

  2. The overall accuracy–efficiency trade-off needs stronger evaluation. The reported accuracy gains come with additional selection overhead, leaving the practical advantage over strong baselines such as ProxyAttn unclear. Comparisons across multiple budgets at matched accuracy or latency would better establish whether the proposed refinements offer a more favorable trade-off.

Questions for authors
  1. The ablation of residual exchange in Table 4 keeps active ratios nearly unchanged and improves diagnostic recall, but yields only a 0.24-point RULER gain at 32K and no gain at 64K. Could the authors clarify which tasks benefit from this component and whether those benefits justify its additional runtime cost?

  2. In Appendix E, the 128K speedups over dense FlashAttention are 3.6× for ProxyAttn and 2.5× for ProbeRefine, implying approximately 44% higher attention-pipeline latency for ProbeRefine. Could ProxyAttn match ProbeRefine's accuracy if allowed the same runtime, for example by retaining more blocks? Comparisons at matched latency and, separately, matched attention budgets would clarify whether ProbeRefine's selection strategy offers an advantage beyond additional computation.

  3. Please explain or correct the GLM table reporting issue.

4 comments
AuthorsOpenReview ↗

Response to Reviewer— Part 1/2

We thank the reviewer for identifying the GLM reporting inconsistency and requesting a more rigorous accuracy–efficiency evaluation. We re-examined the GLM results and conducted additional quality–latency and residual-exchange analyses.


W1. Duplicated GLM Results

(1) Cause and correction. Table 6 contained a transcription error: the Llama-3.1 results were inadvertently copied into the GLM rows during table preparation. We apologize for this mistake. The duplicated entries should not be considered independent GLM evidence. The corrected GLM-4-9B-Chat-1M results are:

Method4K8K16K32K64K128KAvg.
FlexPrefill92.0791.1189.4291.5986.5483.1788.98
ProxyAttn93.2791.3589.9090.8786.5480.7788.78
ProbeRefine93.9991.5990.8791.5986.7881.9789.46

(2) Interpretation. ProbeRefine achieves the highest six-length average (89.46), exceeding FlexPrefill and ProxyAttn by 0.48 and 0.68 points, respectively. It leads at 4K, 8K, 16K, and 64K, ties FlexPrefill at 32K, and trails FlexPrefill at 128K (81.97 vs. 83.17), while remaining above ProxyAttn (80.77).

(3) Cross-model evidence and revision. The main-paper RULER averages exceed ProxyAttn by 1.86 points on Qwen2.5-7B, 0.86 on Llama-3.1-8B, and 0.97 on Yi-9B; the corrected GLM result adds a 0.68-point advantage. These results provide additional cross-model evidence, without implying superiority at every length or on unseen architectures. We will correct Table 6 and all associated GLM claims in Appendix B.


W2. Accuracy–Efficiency Trade-off

(1) Motivation and experimental protocol. We agree that default operating points alone do not establish an advantageous quality–latency trade-off. Appendix E reports 128K speedups of 3.6× for ProxyAttn and 2.5× for ProbeRefine over the same dense reference, implying approximately 44% higher attention-pipeline latency for ProbeRefine at those settings.

To address this, we evaluated ProbeRefine, ProxyAttn, and FlexPrefill at five coverage thresholds across 64K and 128K (30 operating points) on Llama-3.1-8B-Instruct. Each point used 416 RULER examples. Latency was measured on NVIDIA A800 GPUs using fixed real QKV inputs from four layers under a consistent software setup. Measurements cover the attention pipeline, not end-to-end generation.

Dynamic sparse methods such as FlexPrefill (Lai et al., ICLR 2025) and ProxyAttn (Wang et al., ICLR 2026) adapt attention selection and budgets, motivating comparisons across multiple operating points.

(2) Additional latency-matched comparison. In a subsequent fine-grained ProxyAttn sweep, we selected γ=0.960/0.965 based on latency before measuring their quality. The selected pairs satisfy our predefined ≤5% relative latency criterion:

LengthMethodγRULERLatencyActive ratio
64KProbeRefine0.95087.2688.74 ms0.3649
64KProxyAttn0.96084.1487.81 ms0.3483
128KProbeRefine0.95079.09290.94 ms0.3092
128KProxyAttn0.96578.85284.40 ms0.3374

The matching criterion uses absolute latency difference normalized by ProbeRefine latency, yielding 1.06% at 64K and 2.25% at 128K. Relative to ProxyAttn latency, ProbeRefine incurs 1.07% and 2.30% additional latency, respectively.

(3) Findings. At 64K, ProbeRefine gains 3.12 RULER points with only 1.07% additional latency. At 128K, increasing ProxyAttn's computation narrows the gap to 0.24 points, with 2.30% additional latency for ProbeRefine. We do not claim statistical significance for this small difference.

The trade-off is not universally favorable: at 128K, ProxyAttn (γ=0.90) scores 75.00 at 115.31 ms, while ProbeRefine (γ=0.80) scores 74.28 at 119.87 ms.

(4) Comparison scope. These results establish performance at comparable latency, not strictly identical attention budgets. Average active ratios differ (64K: 0.3649 vs. 0.3483; 128K: 0.3092 vs. 0.3374). Therefore, the accuracy differences cannot be attributed solely to selection quality. We will report the complete quality–latency curves and clarify the length- and operating-point-dependent trade-off rather than claiming universal superiority.

AuthorsOpenReview ↗

Response to Reviewer — Part 2/2

Response to Reviewer — Part 2/2

Q1. Residual Exchange: Task Benefits and Cost

(1) Role. Swap is a conditional refinement within ProbeRefine, not a standalone guarantee of accuracy gains. Probes identify candidates beyond the shared ranking; dual-gated one-for-one replacement changes which blocks a head retains at fixed budget. Head specialization [1] and cross-layer composition [2] suggest information utility may depend on other evidence, although we do not directly test block synergy.

(2) Diagnostic evidence. At the Table 4 settings (32K/64K, W=16), remote Top-2 recall improves:

LengthNo SwapSwapGain
32K58.56%63.20%+4.64 pp
64K60.88%63.83%+2.95 pp

Active ratios barely change (0.4196→0.4193; 0.3653→0.3649), preserving budget. The Top-2 reference is probe-derived, not dense-attention ground truth.

(3) Task effects. Swap improves CWE at 32K (65.62→68.75; +3.13 pp), raising the RULER macro-average from 91.83 to 92.07 (+0.24). At 64K, FWE rises 90.62→93.75 and CWE falls 31.25→28.12 (±3.13 pp), leaving the average at 87.26; other tasks are unchanged. Effects are task-dependent. Fig. 3 further shows that raising W from 16 to 32 improves recall but lowers 32K RULER from 92.07 to 91.59.

(4) Incremental cost. Four-layer pipeline measurements with other settings fixed show:

LengthNo SwapSwapAdded cost
32K33.150 ms33.528 ms0.378 ms (1.14%)
64K88.363 ms88.963 ms0.600 ms (0.68%)

These are attention-pipeline, not end-to-end, timings. Swap enables low-cost head-specific correction within the joint pipeline, though average gains here are modest.


Q2. Can ProxyAttn Match ProbeRefine at Comparable Runtime?

(1) Motivation and protocol. At the original 128K settings, speedups of 3.6× (ProxyAttn) and 2.5× (ProbeRefine) imply 44% higher pipeline latency for ProbeRefine. We therefore tested three methods at five thresholds over 64K/128K (30 operating points; 416 RULER examples each). Latency used four layers of fixed real QKV on A800. Fine-grained ProxyAttn thresholds were selected by latency before accuracy evaluation.

(2) Latency-matched results. Here γ is the cumulative-importance coverage threshold for block-budget allocation. ProxyAttn's γ was adjusted to approach ProbeRefine's runtime at γ=0.950:

LengthMethod (γ)RULERLatencyActive ratio
64KProbeRefine (.950)87.2688.74 ms0.3649
64KProxyAttn (.960)84.1487.81 ms0.3483
128KProbeRefine (.950)79.09290.94 ms0.3092
128KProxyAttn (.965)78.85284.40 ms0.3374

Both pairs meet our predefined ≤5% criterion: absolute latency difference divided by ProbeRefine latency is 1.05% (64K) and 2.25% (128K). Relative to ProxyAttn latency, ProbeRefine yields +3.12 RULER points for +1.06% latency at 64K; at 128K, the gain is only +0.24 points for +2.30% latency. We do not claim significance for the 128K difference. The 44% and ~1–2% comparisons use different coverage settings.

(3) Scope. At 128K, another point favors ProxyAttn (γ=.90: 75.00 at 115.31 ms) over ProbeRefine (γ=.80: 74.28 at 119.87 ms). Also, matched latency is not strict budget matching: active ratios differ, and at 128K ProbeRefine is slower despite selecting fewer connections, reflecting selection overhead. The Llama-3.1-8B/RULER trade-off is configuration-dependent, not universal or attributable solely to Swap.


Q3. GLM Reporting Issue

As explained in Part 1 (W1), Llama results were inadvertently copied into the GLM rows of Table 6. The corrected GLM RULER results are:

Method4K8K16K32K64K128KAvg.
FlexPrefill92.0791.1189.4291.5986.5483.1788.98
ProxyAttn93.2791.3589.9090.8786.5480.7788.78
ProbeRefine93.9991.5990.8791.5986.7881.9789.46

ProbeRefine has the highest reported average but trails FlexPrefill at 128K. We will replace the duplicated entries and correct Appendix B; we apologize for the error.


References

[1] Voita E, Talbot D, Moiseev F, et al. Analyzing Multi-Head Self-Attention: Specialized Heads Do the Heavy Lifting, the Rest Can Be Pruned[C]//Proceedings of ACL. 2019: 5797–5808. [2] Elhage N, Nanda N, Olsson C, et al. A Mathematical Framework for Transformer Circuits[R]. Transformer Circuits, 2021.

Dear Reviewer uNtf, We would appreciate your feedback on whether our rebuttal has adequately addressed your concerns. If any questions or concerns remain, we would be happy to provide further clarification and continue the discussion. Thank you for your time and consideration.

Thanks for your detailed response and additional experiments. Your rebuttal addresses some of my concerns. However, in terms of the accuracy–efficiency tradeoff, ProbeRefine’s advantage over ProxyAttn appears relatively incremental, especially when its engineering complexity is taken into account. I appreciate that you fixed the GLM issue. After consideration, I have decided to keep my current score.

Reviewer_cUD2OpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

ProbeRefine augments ProxyAttn's shared block ranking with head-specific query probes and a bounded residual replacement step. Probes selected from the final query block estimate head-specific key-block importance, which is used for budget allocation and local replacement of selected blocks. The proposed replacement uses head and proxy gates and preserves the block count during an exchange. Evaluation covers RULER and InfiniteBench across several language models, ablations of probing and replacement, and attention-pipeline latency measurements up to 128K context.

Critical strengths
  1. The method addresses a concrete limitation of shared proxy rankings with a restrained intervention. Shared rankings can miss head-specific dependencies. Using a small set of probes and a limited exchange step is a plausible way to recover some of this information without independently constructing a dense ranking for every head. This makes the approach a meaningful extension of an existing sparse-prefill method.
  2. The main-table experiments show consistent average quality improvements over ProxyAttn. RULER averages improve by 1.86, 0.86, and 0.97 points on Qwen, Llama, and Yi, respectively. The paper also provides probing and replacement ablations and reports the selection overhead rather than only sparse-kernel execution time. These results establish that the approach can improve quality, even though the cost of that improvement needs stronger justification.
Critical weaknesses
  1. The robustness of the length-dependent configuration is insufficiently established. ProbeRefine uses different configurations on either side of 64K: the probes change from 16 outliers to 24 outliers plus 8 representatives, and Table 8 also changes proxy grouping and minimum budgets for Llama and Yi. Appendix A states that the allocation rule was selected once and then fixed; nevertheless, this is a fixed length-dependent schedule, rather than one configuration shown to work across lengths. Table 5 provides useful support for the probe choices at 64K and 128K, but the preferred composition differs between these two lengths. This leaves uncertainty about how much the gains depend on the selected length regimes and whether the schedule transfers reliably to other lengths and workloads. A comparison using a single configuration across lengths would help establish the contribution of the schedule, and transfer to an unseen length such as 32K or 256K without further adjustment remains unvalidated. Since probes affect both head-specific budgets and residual replacement, this robustness matters to the practical applicability of the method.
  2. The quality gains are not convincingly established at a comparable execution cost. At 128K, the reported speedups relative to the same dense reference are 2.5× for ProbeRefine and 3.6× for ProxyAttn, implying approximately 44% higher attention-pipeline latency for ProbeRefine. Meanwhile, InfiniteBench average gains over ProxyAttn are only 0.10–0.51 points. It remains unclear whether allowing ProxyAttn a larger block budget at the same latency would recover the quality difference. A quality–latency comparison on the same hardware, varying each method's budget or coverage threshold, would directly address this concern. The residual swap itself improves the 32K task score by 0.24 points and leaves the 64K score unchanged in Table 4. Its recall diagnostic uses remote Top-2 blocks identified by Outlier-Q16, rather than an independent dense-attention reference across query positions. These results do not yet show that the added probing, budget allocation, and refinement offer a compelling quality–latency advantage.
  3. Additional reporting and configuration issues: Table 6's GLM results reproduce all 21 displayed values in the corresponding Llama rows of Table 1 for FlexPrefill, ProxyAttn, and ProbeRefine. Please correct the table or explain the match before treating it as independent cross-model evidence. Separately, Appendix D/Table 7 state that the confidence gate is disabled, without clearly mapping this setting to the two gates in Eq. (7) or reporting their thresholds. These issues require clarification, but the main concerns above concern probe generalization and the quality–latency trade-off. The duplicated values establish a reporting problem, not its cause.
Questions for authors
  1. GQA execution and K/V reuse: During the final token-level sparse attention computation, are multiple query heads sharing the same KV head processed jointly to reuse K/V tiles, or scheduled independently? If processed jointly, how are their different selected block sets handled: does each head retain its own mask, or is a common block set used?
  2. Clarification of the Figure 1 diagnostic: How is (K) chosen for the Top-K overlap in Figure 1(a)? Is it fixed or determined by the adaptive per-head budget, and can it vary across heads, query blocks, or context lengths? Please give the exact overlap definition and explain how the head-specific reference selections are constructed. These details are needed to interpret the reported degree of shared-ranking disagreement.
  3. Table 6's GLM results reproduce all 21 displayed values in the corresponding Llama rows of Table 1 for FlexPrefill, ProxyAttn, and ProbeRefine. Please correct the table or explain the match before treating it as independent cross-model evidence.
3 comments
AuthorsOpenReview ↗

Response to Reviewer

Response to Reviewer — Part 1/2

We thank the reviewer for the constructive feedback. We conducted additional cross-length, latency-matched, and residual-exchange analyses.


W1. Robustness of Length-Dependent Configuration

(1) Additional evaluation. ProbeRefine uses a predetermined length-dependent schedule. We compared four variants on Llama-3.1-8B-Instruct across six RULER lengths (4K–128K): Fixed-Short/Long use the respective settings at every length; Probe Schedule varies probe allocation only; Full Schedule also varies grouping and minimum budget. All 24 combinations were evaluated on 416 examples each, with no missing results.

Configuration4K8K16K32K64K128K
Fixed-Short95.1993.9994.2392.0787.2678.85
Fixed-Long95.4394.2394.4786.7885.1079.09
Probe Schedule95.1993.9994.2392.0787.2678.61
Full Schedule95.1993.9994.2392.0787.2679.09

(2) Findings. Neither fixed setting dominates. Fixed-Long improves by 0.24 points at 4K–16K but loses 5.29 and 2.16 points at 32K and 64K versus Fixed-Short. Full Schedule matches Fixed-Short through 64K and reaches 79.09 at 128K, versus 78.85 for Fixed-Short. At 128K, Probe Schedule alone scores 78.61; its 0.48-point gap to Full Schedule reflects joint grouping/minimum-budget effects, not probe composition alone.

(3) Scope. The schedule represents an empirical robustness trade-off, not a universal optimum. Since 32K was evaluated, it is not unseen-length evidence; 256K and other genuinely unseen lengths remain unvalidated.


W2. Quality–Latency Trade-off and Residual Exchange

(1) Latency-matched comparison. At the original 128K operating points, ProxyAttn/ProbeRefine speedups over dense attention were 3.6×/2.5×, implying 44% higher attention-pipeline latency for ProbeRefine. We then evaluated three methods at five thresholds and two lengths (64K/128K): 30 points, 416 RULER examples each. Timing used four layers of fixed real QKV on NVIDIA A800, not end-to-end generation. Additional fine-grained ProxyAttn thresholds were selected by latency before measuring accuracy. Here γ is the cumulative-importance coverage threshold for block-budget allocation.

LengthMethodγRULERLatencyActive Ratio
64KProbeRefine.95087.2688.74 ms0.3649
64KProxyAttn.96084.1487.81 ms0.3483
128KProbeRefine.95079.09290.94 ms0.3092
128KProxyAttn.96578.85284.40 ms0.3374

Using displayed latencies, the absolute latency difference divided by ProbeRefine latency is 1.05% (64K) and 2.25% (128K), within our predefined 5% criterion. Relative to ProxyAttn latency, ProbeRefine gains 3.12 RULER points for 1.06% extra latency at 64K and 0.24 points for 2.30% extra latency at 128K; we do not claim significance for the latter. The original 44% and these 1–2% gaps reflect different operating points, not inconsistent measurements. At another 128K point, ProxyAttn (γ=.90) scores 75.00 at 115.31 ms, versus ProbeRefine (γ=.80) at 74.28 at 119.87 ms. These are latency-, not strictly budget-matched, comparisons: active ratios differ, so selection quality alone cannot explain the differences.

(2) Role and task-level effects of Swap. Swap works with head-specific probing and shared ranking to provide conditional, one-for-one correction beyond the proxy cutoff. At the Table 4 lengths (32K/64K; W=16), its effects depend on the task. At 32K, CWE rises 65.62→68.75 (+3.13 pp), raising the RULER average 91.83→92.07 (+0.24). At 64K, FWE rises 90.62→93.75 (+3.13 pp) but CWE falls 31.25→28.12 (−3.13 pp), leaving the average at 87.26; other tasks are unchanged. We do not claim consistent macro-average gains.

Remote Top-2 diagnostic recall nonetheless rises from 58.56% to 63.20% (+4.64 pp) at 32K and 60.88% to 63.83% (+2.95 pp) at 64K, with near-unchanged active ratios (0.4196→0.4193; 0.3653→0.3649). These reference blocks come from Outlier-Q16 probes, not independent dense attention; recovered evidence need not translate into proportional accuracy gains, as its utility may depend on the task and other selected context.

(3) Incremental cost and scope. Paired four-layer attention-pipeline timings, with other settings fixed, show:

LengthNo SwapSwapAdded cost
32K33.150 ms33.528 ms0.378 ms (1.14%)
64K88.363 ms88.963 ms0.600 ms (0.68%)

Swap thus offers a low-cost opportunity for head-specific block correction, while its isolated gains remain task-dependent. These are pipeline microbenchmarks, not end-to-end timings; average active ratios do not prove per-head/per-query budget equivalence.

AuthorsOpenReview ↗

Response to Reviewer

Response to Reviewer — Part 2/2

W3. GLM Reporting Error and Gate Configuration

(1) Correcting Table 6. We apologize for a transcription error: Llama-3.1 results were inadvertently copied into the GLM rows. The corrected GLM-4-9B-Chat-1M RULER results are:

Method4K8K16K32K64K128KAvg.
FlexPrefill92.0791.1189.4291.5986.5483.1788.98
ProxyAttn93.2791.3589.9090.8786.5480.7788.78
ProbeRefine93.9991.5990.8791.5986.7881.9789.46

ProbeRefine achieves the highest reported six-length average (89.46), outperforming FlexPrefill and ProxyAttn by 0.48 and 0.68 points, respectively. However, it does not lead at every length: at 128K, FlexPrefill scores 83.17 versus 81.97. We will correct all 21 duplicated entries and revise the GLM discussion without treating the original duplicated rows as independent cross-model evidence.

(2) Gate configuration. The optional probe-allocation confidence gate is disabled in our formal experiments. This is distinct from the two residual-refinement acceptance gates in Eq. (7), which remain enabled, with a head-gain ratio threshold of 1.5 and a shared-score retention threshold of 0.9. These are the actual experimental configurations rather than the standalone selector defaults. We will explicitly distinguish these gates and document their settings.


Q1. GQA Execution and K/V Reuse

(1) Kernel scheduling. The Triton attention kernel schedules computation by query head and query block. For each query head, it uses the GQA mapping to locate the corresponding KV head and reads that query head's independently selected block indices and attention mask.

(2) K/V sharing. Multiple query heads sharing the same KV head are not explicitly fused to jointly process or reuse KV tiles. Each query head retains its own selected block indices and executes sparse attention according to its individual mask.

(3) Implementation scope. Incidental cache-level reuse may occur through hardware caching, but our implementation does not explicitly optimize cross-query-head KV-tile reuse. We will clarify this distinction in the revised manuscript.


Q2. Figure 1: Top-K Overlap

(1) Choice of K. The nominal K is determined by the head-specific block budget for a given input and layer, rather than independently reassigned for each query block. However, the effective cutoff K_eff may vary across query blocks because of causal visibility, exclusion of protected blocks (e.g., sink and current blocks), and the number of eligible blocks available in the compared rankings. For Head–Head overlap, we use a common K_eff additionally bounded by the smaller feasible head budget, ensuring equal-sized sets.

(2) Exact overlap definition. For two rankings A and B, we define their Top-K overlap as:

Overlap(A,B)=∣SAKeff∩SBKeff∣Keff\mathrm{Overlap}(A,B)=\frac{|S_A^{K_{\mathrm{eff}}}\cap S_B^{K_{\mathrm{eff}}}|}{K_{\mathrm{eff}}}

Here, KeffK_{\mathrm{eff}} denotes the effective cutoff, and SAKeffS_A^{K_{\mathrm{eff}}} and SBKeffS_B^{K_{\mathrm{eff}}} represent the sets of the top-KeffK_{\mathrm{eff}} eligible blocks selected from rankings A and B, respectively.

  • Proxy–Head: A and B represent the shared proxy ranking and the corresponding head-specific reference ranking.
  • Head–Head: A and B represent the reference rankings of two heads within the same proxy group, evaluated using the same effective cutoff.

(3) Reference construction. The head-specific reference ranking is constructed by aggregating the mean attention mass over all token queries within the sampled query block, rather than using only the selected query probes. This provides a reference for measuring disagreement between shared proxy rankings and head-specific block preferences.

We will clarify the nominal versus effective K distinction, provide the exact overlap definition, and describe the reference construction in the revised manuscript.


Q3. Duplicated GLM Results

As explained in W3, the duplicated GLM entries resulted from a transcription error during table preparation, rather than identical experimental outcomes across models. We will replace the incorrect entries with the corrected GLM results reported above (ProbeRefine average: 89.46) and revise the corresponding discussion. We apologize for this reporting error.

Dear Reviewer cUD2, We would appreciate your feedback on whether our rebuttal has adequately addressed your concerns. If any questions or concerns remain, we would be happy to provide further clarification and continue the discussion. Thank you for your time and consideration.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Review and Discussion

Dear Area Chair and Reviewers,

Thank you for your time and constructive feedback. We sincerely appreciate the careful assessments by reviewers hfiV, cUD2, and uNtf. During the discussion, we conducted additional evaluations, corrected a reporting error, and clarified the method and its limitations. We summarize the main responses and revisions below.

I. Review and Discussion\color{#A52A2A}{\text{I. Review and Discussion}}

The key concerns centered on (1) novelty beyond ProxyAttn and related work, (2) length-dependent probing and generalization, (3) the independent benefit and cost of residual exchange, and (4) quality–latency trade-offs, reporting accuracy, and reproducibility.

II. Additional Evidence and Responses\color{#A52A2A}{\text{II. Additional Evidence and Responses}}

1. Novelty and probe allocation [hfiV-W1; cUD2-W1]. ProxyAttn varies per-head budgets within a shared ranking; ProbeRefine additionally uses head-specific query evidence to revise which blocks are selected via gated, budget-preserving replacement. We added eight relevant studies, including TokenSelect and SharePrefill. We also clarified our fixed, task-independent probe schedule: Outlier-Q16 up to 64K and Bimodal-Q32 (24 outlier + 8 representative queries) beyond 64K. Ablations support this empirical design: Outlier-Q16 scores 92.07 at 32K and 87.26 at 64K; at 128K, Bimodal-Q32 exceeds Outlier-Q32 by 0.48 points at the same probe count. We do not claim this schedule is theoretically optimal.

2. Residual exchange [uNtf-Q1; hfiV-W1]. Swap raises probe-defined remote Top-2 recall by 4.64/2.95 percentage points at 32K/64K, while its isolated RULER gains are +0.24/0.00. The effects on individual tasks vary. Its additional attention-pipeline cost is 0.378 ms (1.14%)/0.600 ms (0.68%). We distinguish this diagnostic benefit from the gains of the complete framework.

3. Quality–latency trade-offs [cUD2-W2; uNtf-Q2; hfiV-W3]. We evaluated 30 operating points at 64K/128K (416 RULER examples per point), choosing ProxyAttn's finer thresholds based on latency before testing quality. At comparable runtime, ProbeRefine gains 3.12 points for 1.06% extra latency at 64K and 0.24 points for 2.30% extra latency at 128K. The latter gain is small; we do not claim statistical significance or universal superiority. Measurements cover selection, layout construction, and sparse execution with model-derived Q/K/V from four layers on an A800, not full-model inference; active-block budgets are not identical.

4. Recent hybrid model and independent evidence [hfiV-W1,W2]. On Qwen3.5-9B, we sparsify only its eight full-attention prefill layers. The six-length RULER average is 95.75, versus 95.80 (ProxyAttn), 95.65 (FlexPrefill), and 95.86 (original hybrid model): competitive, not uniformly superior. A separate held-out dense-attention diagnostic shows Swap improving Top-2 recall by 0.405 pp and retained attention mass by 0.080 pp, while the 64-token executed-block ratio remains 53.83%. We explain the 128-token selection to 64-token execution mapping.

5. GLM correction and implementation [cUD2; uNtf; hfiV]. We corrected a transcription error that duplicated Llama-3.1 values in the GLM table. The corrected RULER averages are 89.46 (ProbeRefine), 88.98 (FlexPrefill), and 88.78 (ProxyAttn); FlexPrefill remains better at 128K. We apologize for this error. We also clarified that the optional probe-allocation confidence gate is disabled, while both residual-refinement gates are enabled (thresholds 1.5 and 0.9).

III. Revised Manuscript\color{#A52A2A}{\text{III. Revised Manuscript}}

The revised Introduction and Related Work clarify positioning; Method and Appendix D specify probe and gate settings; Appendices A–B strengthen the ablation discussion and correct GLM; and Appendices E–F include the runtime protocol and new experiments. We also updated Conclusion and Limitations to reflect the observed trade-offs.

We have uploaded a revised version of the manuscript addressing the reviewers' comments. Please refer to the updated PDF, where we have revised the relevant sections accordingly. We would greatly appreciate it if you could review the revised version and let us know if any concerns remain.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.