acceptodds
Withdrawn from ICLR 2027

ReScope: Sparse Prefill with Segment Observations and Query Updates

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Long-context language models incur substantial prefill costs as dense attention scales quadratically with input length. Sparse attention reduces this cost by selecting query–key interactions, but a few representative queries can miss important interactions when tasks and evidence are distributed throughout the input. Expanding observations, meanwhile, increases selection overhead. We propose ReScope, a training-free sparse prefill method that combines segment observations with temporary query updates. Segment observations cover different input regions, while a small tail window repeatedly reads the context and updates temporary query states to identify additional candidate interactions. Keys, values, and positions remain fixed during these updates. Final sparse attention uses the original queries, keys, and values and retains the full KV cache. On evaluation workloads constructed from real question-answering data and natural documents, including HotpotQA, NarrativeQA, and 128K scientific-paper question answering, ReScope improves F1 by 3.0–4.9 points over the respective sparse baselines. On a controlled retrieval benchmark with 128K-token inputs, optimized ReScope achieves 100% accuracy and a 2.45× complete-prefill speedup over dense attention.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Long-context language models, Sparse attention, Prefill acceleration, Training-free inference, Query refinement

Reviews

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

This paper proposes ReScope, a training-free sparse prefill method that combines segment-wise query observations with iterative refinement of temporary tail queries. The refined queries provide additional signals for identifying important attention candidates, while final sparse attention operates on the original QQ, KK, and VV. The method also introduces GPU-level optimizations for candidate selection and index construction.

Experiments on synthetic retrieval, HotpotQA, NarrativeQA, and constructed 128K QASPER workloads demonstrate improvements in sparse-attention quality, particularly for question-first layouts. The paper reports F1 improvements of 3.0--4.9 points over sparse controls on natural tasks and approximately 15--20% lower prefill latency at selected operating points.

Critical strengths

S1. Meaningful query refinement beyond expanded observations. ReScope addresses an important challenge in representative-query sparse attention, particularly when task-relevant information is distributed across long contexts. The combination of segment-wise observations and iterative temporary query updates offers a principled way to improve candidate selection without modifying the original attention tensors. The comparisons against expanded original-query sampling, candidate replacement, and value perturbation provide useful evidence that query refinement contributes additional selection information beyond simply increasing observation coverage.

S2. Practical design and careful experimental analysis. The method requires no additional training and retains the original QQ, KK, VV and full KV cache, making it compatible with existing model weights and attention implementations. The paper also pays attention to practical execution costs through GPU-level selection and index-construction optimizations. The inclusion of matched-support comparisons, paired statistical analyses, complete-prefill measurements, and results across different query layouts makes the empirical study informative.

Critical weaknesses

W1. Insufficient isolation of the efficiency gains attributable to query refinement. Although the optimized implementation reports promising latency improvements, the comparison in Table 15 uses selected optimized ReScope configurations against earlier baseline measurements. This makes it difficult to determine how much of the observed speedup comes from the refinement mechanism itself, as opposed to implementation optimizations or operating-point selection. Moreover, the original budget sweep in Tables 5--6 shows that ReScope does not consistently dominate simpler sparse alternatives in quality--latency trade-offs. A unified quality--latency comparison under comparable optimization settings would make the practical efficiency contribution more convincing.

W2. More evidence is needed to establish the consistency and magnitude of the refinement benefits. The natural-task results are encouraging, but the improvements vary across datasets, query layouts, models, and calibration settings. For example, the transfer results in Table 7 do not consistently favor ReScope over expanded original-query observations. Furthermore, some controlled comparisons in Appendix H report improvement thresholds rather than complete effect sizes and uncertainty estimates, making it difficult to assess the magnitude and consistency of the refinement contribution. More systematic analysis would help clarify when the additional refinement computation is most beneficial.

Questions for authors

Q1. Efficiency attribution. Could the authors provide a quality--latency Pareto comparison among ReScope, segment observations, expanded-query sampling, and FlexPrefill under comparable implementation optimizations? In particular, how much of the optimized ReScope speedup can be attributed to query refinement rather than shared kernel optimizations or budget selection?

Q2. Refinement contribution. Could the authors provide the full numerical results underlying the controlled comparisons in Appendix H, including effect sizes, confidence intervals, and experimental settings? It would be helpful to understand how consistently the refinement mechanism improves selection quality at matched support or selector cost.

Q3. Robustness and operating conditions. What factors explain the variations in ReScope's relative performance across natural tasks, models, and calibration settings, particularly the cases in Table 7 where expanded original-query observations perform comparably or better? Are there identifiable characteristics of the input distribution, attention patterns, or support budget that predict when refinement is most useful? Additionally, could the authors clarify the experimental configuration differences responsible for the quality changes between original and optimized ReScope in Table 2?

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

This paper proposes ReScope, a training-free sparse prefill method that combines segment observations with temporary query updates to improve attention selection in long-context LLMs. It observes original queries across different input positions and iteratively updates a small tail window to identify additional attention candidates, while performing final sparse attention with the original Q, K, and V.

Critical strengths
  1. The paper identifies an important limitation of representative-query selection under different question placements. Combining segment observations with temporary query updates provides a reasonable approach to improving attention coverage.
  2. ReScope demonstrates quality improvements on controlled retrieval and natural question-answering tasks, along with potential complete-prefill speedups. The evaluation also considers matched attention support and selection overhead, providing useful evidence of the method's effectiveness.
Critical weaknesses
  1. FlexPrefill is the only complete external method used in the main comparisons, while Segments and Expanded Queries are component-level controls. Direct quality-efficiency comparisons with complete methods such as MInference, SampleAttention, and XAttention are needed to establish ReScope's advantages over existing approaches.

  2. The main optimized results focus on Qwen2.5-14B, with limited validation across other model architectures and scales.

  3. Although matched-support and matched-cost controls are provided, Table 16 mainly summarizes improvements through inequalities without detailed effect sizes or confidence intervals. Figure 2 also shows that segment observations increase approximation error in some layers, which deserves further investigation.

Questions for authors

Could the authors further analyze the impact of non-prefix-causal selection and clarify the method's applicability to incremental prefilling and prefix-cache reuse?

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

This paper proposes ReScope, a training-free sparse prefill method that combines segment-based query observations with iterative query refinement. The method samples representative queries from different context segments and updates a small set of temporary tail queries through repeated context attention to identify additional sparse attention patterns.

Critical strengths

The idea of iteratively updating temporary queries to improve sparse pattern selection is interesting. It provides an alternative to simply increasing the number of observation queries and can identify important interactions missed by the original queries.

Critical weaknesses

1. Insufficient comparisons with representative sparse prefill methods. The paper motivates its approach primarily through the limitations of Vertical-Slash sparse attention patterns, yet it does not provide a direct comparison with the complete MInference method, which is a fundamental and widely used baseline for sparse prefilling.

2. Incomplete and non-standard benchmark evaluation. The experimental evaluation is insufficient to establish the general effectiveness of the proposed method. The official LongBench benchmark contains 21 tasks, but the paper evaluates only HotpotQA and NarrativeQA, using just 40 samples per task instead of the official 200. The primary controlled retrieval experiments use a custom synthetic benchmark with only 80 documents containing name–number facts. This resembles a simplified Needle-in-a-Haystack task but does not follow standard RULER protocols. In particular, the paper does not evaluate the standard 13 RULER tasks, which are important for assessing long-context retrieval capabilities.

Questions for authors

1. Baseline comparisons. Why is the complete MInference method not included, given that ReScope directly builds upon VS sparse attention?

2. Benchmark completeness. Why are only two LongBench tasks evaluated, with 40 samples per task? Can the authors provide results on the full 21-task LongBench benchmark and the standard 13-task RULER benchmark to demonstrate broader generalization?

3. Experimental protocol and support budgets. In Table 3, question-first and question-last settings use different VS support targets (3% and 6%). Can the authors provide comparisons with identical budgets across both question placements to better isolate the impact of query position?

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

Related papers

Discussion (0)

Sign in to comment.