acceptodds
Under review as a conference paper at ICLR 2027

SudokuRAG: Efficient RAG Prefilling via Coordinated Intra- and Inter-Document Attention Sparsity

Abstract

Retrieval-augmented generation (RAG) can incur substantial prefill overhead when multiple retrieved documents are incorporated into the model input. Existing approaches accelerate RAG prefilling through parallel encoding, but often require additional training or incur accuracy degradation. We observe that intra-doc attention patterns can be profiled offline and reused across prompts, whereas inter-doc selection must adapt to the current context. Building on this insight, we introduce SudokuRAG, a training-free design that coordinates offline intra-doc masks and online inter-doc pruning within the tiled attention loop, using current prefix and intra-doc softmax statistics as guidance. Empirical results show that SudokuRAG achieves prefill-attention speedups over dense attention at approximately 50% sparsity while largely preserving task accuracy.

Primary area:
generative models
Keywords:
sparse attention, retrieval-augmented generation, large language models, algorithm-hardware codesign

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_kfZvOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

SudokuRAG addresses the prefill-attention overhead of long RAG inputs by combining reusable offline intra-doc masks with adaptive online inter-doc pruning. It first profiles each document independently and caches document-local block masks. During online prefill, it visits Prefix → Intra-doc → Inter-doc, using the accumulated prefix/intra-doc softmax statistics to guide inter-doc QK and PV skipping. The authors integrate this design into a FlashAttention-3 kernel, evaluate task accuracy on two 8B models, and report 1.34–1.64× online prefill-attention speedups on H100 at approximately 50% sparsity.

Critical strengths

The design is well motivated and solid. Documents are available in advance, whereas their composition and order are determined at request time. Separating reusable intra-doc selection from context-dependent inter-doc selection is therefore a reasonable direction.

The implementation considers execution costs through block-sparse masks, shared K/V loads, command compaction, and pipelined execution. All regions share the same online-softmax state, giving the method a clear computational interpretation.

The accuracy evaluation covers two models and multiple benchmark groups. In Table 2, the average ChatRAG F1 differences from full attention are below 0.04 percentage points for both models. SudokuRAG also generally outperforms the evaluated sparse baselines on the group-average LOFT and LaRA scores. The paper reports both accuracy regressions and the overhead of the zero-sparsity control.

Critical weaknesses
  1. Practical benefits remain unclear: Table 3 reports 1.34–1.64× prefill-attention speedups without full-model prefill latency or TTFT measurements. It is also unclear whether all online selection and mask-processing costs are included, while offline profiling costs and the document reuse needed to amortize them remain unquantified.

  2. The method relies on offline document profiling, but its applicability to dynamic or frequently updated corpora remains unclear. The paper does not discuss how new or updated documents are handled, or whether profiling costs can be amortized in these settings.

Questions for authors
  1. What is the complete configuration used in Table 2, particularly λPV\lambda_{\mathrm{PV}}? How to select this parameter? Could you provide some insight about this? What achieved sparsity, attention latency, and full-model prefill latency does this same configuration produce on the inputs used in Table 3?
  2. Is this method only useful in fixed corpus setting?
1 comment

Thank you for your constructive review and for noting the clarity of our single-softmax formulation, our GPU execution optimizations, and our balanced reporting of zero-sparsity overheads. Below, we address your concerns and questions directly.

W1. Full-model prefill / TTFT, online overheads, and offline profiling amortization

Please see Global Comment 2 and Global Comment 4:

  • Full-model prefill / TTFT & online overheads (Global Comment 2): All online selection, compaction, packing, and mask-mapping costs are included. On LOFT NQ 128K, SudokuRAG reduces full-model prefill wall time from 8.34 s (standalone FA-3) to 6.68 s (1.25×) at 50% sparsity (54.0% accuracy) and 5.00 s (1.67×) at 75% sparsity (53.7% accuracy), outperforming both FlexPrefill and SIFT.
  • Offline profiling & reuse amortization (Global Comment 4): Standalone profiling takes 0.77 s–10.53 s (0.15–2.67 MiB on disk) for 4K–16K-token documents and amortizes in ~4–60 document retrievals.

W2 & Q2. Is this method only useful in fixed corpus setting?

No, SudokuRAG works directly on dynamic corpora without blocking online inference. Our method profiles documents offline at the document level. In a dynamic corpus, when new documents are added, we only need to run intra-doc offline profiling on those new documents and store their masks; existing masks remain valid. If an existing document is edited or appended to, the affected document/chunks are re-profiled, so stale masks are never reused. Online inference is therefore not blocked.

Q1. Complete Table 2 configuration, lambda_PV selection insight, and performance on Table 3's inputs.

  • Configuration & selection insight (Global Comment 1 & 2): Table 2 uses B=64B = 64, α=0.001\alpha = 0.001, τ=0.6\tau = 0.6, lambda_QK = 0.8, and lambda_PV = 1e-4 at 128K (layers 0–1 and decode dense). lambda_PV is scaled inversely with context length (~c / N) so cumulative omitted post-QK weights stay negligible across long contexts, while sweeping lambda_PV on a log scale (1e-5 to 1e-1) smoothly controls 25%–75% sparsity.
  • Performance on Table 3's NQ inputs (Global Comment 2): At this ~50% sparsity operating point, SudokuRAG achieves 10.62 ms (1.24× vs. FA-3), 39.53 ms (1.38×), and 157.41 ms (1.45× vs. FA-3 / 1.60× vs. cuDNN) online attention latency at 32K, 64K, and 128K, and 6.68 s (1.25× full-prefill TTFT speedup) on 128K LOFT NQ while preserving 54.0% accuracy (5.00 s / 1.67× at 75% sparsity with 53.7% accuracy).
Reviewer_HmpNOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes SudokuRA, a training-free method for accelerating RAG prefill by combining reusable offline intra-document masks with online inter-document pruning. It processes prefix and intra-document attention first, using their softmax statistics to guide QK/PV skipping in a FlashAttention-3-based kernel. Experiments on two 8B models across ChatRAG, LOFT, and LaRA show generally preserved task quality, with reported online prefill-attention speedups of 1.34–1.64× on H100 at approximately 50% sparsity.

Critical strengths
  1. The paper identifies a meaningful distinction between reusable intra-document attention patterns and context-dependent inter-document interactions. The attention analysis provides useful evidence for this design, and the proposed execution order offers a practical way to exploit RAG structure.

  2. The method is training-free, keeps inter-doc attention available, and is implemented as a fused FA-3 kernel with real measured speedups on H100. The accuracy table shows it avoids the severe degradation of document isolation and of the reproduced SIFT baseline, especially on LOFT retrieval and LaRA at 128K.

Critical weaknesses
  1. The quality–efficiency advantage is not sufficiently established. Accuracy is compared against sparse baselines, but latency is compared only against dense attention, leaving the comparative quality–cost trade-off unclear. Moreover, the connection between the accuracy configuration and timing sweep is insufficiently specified: λPV\lambda_{\mathrm{PV}}, sparsity-target settings, and separate QK/PV skip rates are not reported.
  2. The benefit of the proposed coordination is not isolated. The main distinction from prior components is the prefix/intra-document-first traversal and state-dependent inter-document pruning. However, no controlled ablation isolates these choices, leaving unclear whether the coordination improves quality or efficiency over the same components without it.
Questions for authors
  1. Could the authors report paired task-quality and online attention-latency results for SudokuRAG, SIFT, and one suitable general sparse baseline on existing long-context tasks? A matched-quality comparison or a quality–latency curve would clarify the trade-off. Please specify whether timing includes Q/K means, reliability checks, mask mapping, and command compaction. Full-prefill or TTFT measurements, if available, would further clarify practical benefits.

  2. How much improvement comes specifically from the prefix/intra-document-first traversal and the state-dependent QK threshold? Please compare against otherwise identical variants using ordinary page order or an independently calibrated, state-independent threshold, reporting task quality, QK/PV skip rates, and latency.

  3. What value of λPV\lambda_{\mathrm{PV}} was used, and which parameters were varied to obtain the sparsity targets in Table 3? Does the 50% timing point use the same configuration as the accuracy evaluation, including the first two dense layers? Please also clarify SIFT’s implementation, settings, and realized sparsity to help interpret its substantial degradation on some tasks.

  4. What are the offline profiling time and mask-storage requirements for representative document lengths? Given the measured online savings, approximately how many document reuses are needed to amortize profiling? This would help identify the workloads in which offline mask reuse is practically beneficial.

1 comment

Thank you for your detailed review and for highlighting our distinction between reusable intra-document patterns and context-dependent inter-document interactions in a fused FA-3 kernel. Below, we address your concerns and questions point by point.

W1 & Q1. Paired quality–latency trade-off against sparse baselines, online overhead scope, and full-prefill / TTFT

Please see Global Comment 2:

  • Paired quality–latency & TTFT vs. FlexPrefill and SIFT: On LOFT NQ 128K, SudokuRAG outperforms both FlexPrefill and SIFT across 50%, 75%, and 90% sparsity in both task accuracy and latency. At 75% sparsity, SudokuRAG achieves 53.7% subspan_em, 88.72 ms (2.57×) attention latency, and 5.00 s (1.67×) full-prefill TTFT, beating FlexPrefill (52.0%, 156.94 ms [1.45×], 6.56 s [1.27×]) and SIFT (26.8%, 113.67 ms [2.01×], 5.65 s [1.48×]); at 90% sparsity, SudokuRAG still retains 51.2% accuracy at 4.11 s (2.03×) TTFT vs. FlexPrefill (50.3% / 5.50 s) and SIFT (10.4% / 4.28 s).
  • Timing scope: Online attention latencies include Q/K block means, coherence checks, scoring, selection, command compaction, and QKV packing; full-prefill TTFT additionally includes host mask mapping, all 32 layers' projections/MLPs, KV-cache writes, dense layers 0–1, and first-token argmax.

W2 & Q2. Separate QK/PV skip rates and isolating Prefix -> Intra-doc -> Inter-doc coordination

Please see Global Comment 3 and Global Comment 5:

  • Global Comment 3 reports separate QK (68.53%) and PV (71.96%) sparsity on LOFT NQ 128K and isolates each mechanism: disabling pre-QK skipping removes the speedup (1.43× -> 0.93×), disabling post-QK PV skipping reduces speedup (1.43× -> 1.28×), and replacing Prefix -> Intra-doc -> Inter-doc with ordinary causal page order degrades both accuracy (53.7% -> 53.4%) and speedup (1.43× -> 1.08×).
  • Global Comment 5 isolates offline intra-doc pruning on LaRA Paper 128K, lifting speedup from 1.29× to 2.68× on 64K documents (1.81× -> 2.60× on 32K documents) while preserving accuracy (77.64% / 77.04% vs. 77.71% FA-3).

Q3. lambda_PV value, Table 3 sparsity calibration, dense layers 0–1, and SIFT's degradation

  • Parameters & Table 3 calibration: Global Comment 1 and Global Comment 2 specify our default settings (α=0.001\alpha = 0.001, τ=0.6\tau = 0.6, lambda_QK = 0.8, lambda_PV = 1e-4 at 128K, layers 0–1 dense) and our two-stage schedule varying lambda_PV (25%–75% sparsity, with ~1e-4–1e-3 matching Table 2's ~50% operating point) and lambda_QK (90%–95%). Single-layer benchmarks in Table 3 measure sparse layers 2/16/31, whereas all full-model TTFT and accuracy runs (Global Comment 2 & 3) keep layers 0–1 dense.
  • SIFT implementation & degradation: Since no official SIFT code was publicly available, we implemented SIFT following its paper settings (B=64B = 64, α=0.001\alpha = 0.001, β=0.01\beta = 0.01, γ=0.1\gamma = 0.1, layers 0–1 dense). Because SIFT selects static context-independent inter-doc keys offline (#{q : A(q,k) > 0.01} / L > 0.1), causal masking severely restricts late document keys on long documents and misses query-dependent cross-document evidence—consistent with SIFT's sharp drop from 51.0% (50% sp.) to 26.8% (75% sp.) and 10.4% (90% sp.) in Global Comment 2.

Q4. Offline profiling time, mask storage, and reuse amortization

Please see Global Comment 4: profiling takes 0.77 s (152.5 KiB on disk), 2.81 s (696.6 KiB), and 10.53 s (2.67 MiB) for 4K, 8K, and 16K-token documents, amortizing in ~4, ~14, and ~50–60 retrievals. Offline profiling is thus well suited to shared multi-page corpora (>= 4K tokens), while short-chunk workloads (<= 512 tokens) can rely purely on zero-profiling online inter-doc pruning.

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

This paper proposed SudokuRAG, a training-free sparse attention method for accelerating prefill especially for RAG scenario. The paper first introduce three pilot experiments to study attention pattern for RAG prefilling, deriving three key insight covering inter-doc and intra-doc attention. Based on the insight, the paper proposed SudokuRAG methods, which first processes the prefix and retain intra-document blocks first, then uses the accumulated statistic collected from previews computation to guide QK and PV skipping for inter-document sparse attention calculation. The author implement the method on top of FlashAttention-3, and evaluates accuracy and efficiency on several RAG benchmark compared with existing method. The results shows that SudokuRAG achieve 1.34-1.64x online prefill-attention speedup on H100 at nearly 50% sparsity for over 32K context length.

Critical strengths
  1. The research problem is practical especially the design for document-reuse structure of RAG. The training-free characteristic is also friendly for applying to new SOTA language model.
  2. The motivation and the intuition for designing the SudokuRAG is sufficient. The author describes three pilot experiments and their corresponding results in Section 3, which conclude three valuable insight of attention pattern for RAG prefill.
  3. The implementation addresses practical GPU execution constraints. Section 4.4 discusses shared KV loads, synchronization participation by skipped heads, and a three-buffer pipeline. The paper appropriately distinguishes entry-level recall from executable block sparsity.
Critical weaknesses
  1. The independent benefit of the mechanism is not well established. Specifically, the most interesting contribution of the proposed method is the coordination between offline and online selection: processing prefix and intra-document blocks first and then using their accumulated statistics to guide inter-document pruning. However, the experiments do not isolate the benefit of this mechanism from simply combining its constituent components. An additional ablation study can better reveal the effectiveness of each component.
  2. The current experimental result is not sufficient to reveal the advantage of current method. Section 5.1 reports a fixed configuration yielding approximately 50% sparsity, whereas Section 5.2 sweeps target sparsity from 0% to 95% without explaining how each operating point is obtained. In particular, it is unclear whether the 50% point in Table 3 uses exactly the configuration evaluated in Table 2. The highest speedups at 95% sparsity also lack corresponding performance measurements and therefore should not be interpreted as accuracy-preserving speedups. Besides, Section 5.2 comparison is not fair because the SudokuRAG use the FlashAttention-3 kernel but the dense baseline only use cuDNN SDPA. Further, the two backbone model for testing, i.e. Llama-3.1-8B and Qwen3-8B have similar parameter, which can not generalize the conclusion on the language model at different scale.
  3. The missing configuration details limit reproducibility and interpretation. For example, Algorithm 1 uses (\lambda_{\mathrm{PV}}), but the implementation details in Section 5.1 report only (\lambda_{\mathrm{QK}}=0.8), omitting the value of (\lambda_{\mathrm{PV}}). Since this parameter directly affects both accuracy and computational cost, this is an vital for reproducibility.
Questions for authors
  1. Does Table 3 include all online selection and data-preparation overheads? For the configuration used in Table 2, what are the absolute latencies relative to cuDNN SDPA and standalone FA3?
  2. Could the authors provide a limited ablation comparing the complete method against variants without QK skipping, without PV skipping, and with a different traversal order? Reporting accuracy, realized computational budget, and latency together would help better reveal the characteristic of current method.
  3. Would it be possible to evaluate the method on language models at different scale such as Qwen series model varying from 1.7B to 32B. This would help enhance the generaliziblity of the method.
1 comment

Thank you for your constructive review and for recognizing the practical value of exploiting RAG document reuse without fine-tuning, our pilot study insights, and our GPU execution design. Below, we address your concerns and questions directly.

W1 & Q2. Independent benefit of the coordinated mechanism and controlled ablations

Please see Global Comment 3 and Global Comment 5:

  • Mechanism ablation (Global Comment 3): On LOFT NQ 128K, complete SudokuRAG achieves 53.7% subspan_em and 5.83 s (1.43×) full-prefill latency (68.53% QK sparsity, 71.96% PV sparsity). Removing pre-QK skipping eliminates the speedup (8.96 s, 0.93×), removing post-QK PV skipping reduces speedup (6.53 s, 1.28×), and replacing Prefix -> Intra-doc -> Inter-doc with ordinary causal page order (0->1->...->a) degrades both accuracy (53.4%) and speedup (7.74 s, 1.08×).
  • Component ablation (Global Comment 5): While completely dropping inter-doc attention (Block-Attention) collapses accuracy (Section 3.1 / Table 2), enabling offline intra-doc masks alongside online inter-doc pruning lifts speedup over standalone FA-3 from 1.29× to 2.68× on 64K documents (1.81× -> 2.60× on 32K documents) without sacrificing accuracy.

W2. Connection between Table 2 and Table 3, high-sparsity quality, and standalone FA-3 baseline

Please see Global Comment 2:

  • Sparsity calibration & high-sparsity quality: Global Comment 2 explains our coarse-to-fine parameter schedule across 0%–95% sparsity (90%–95% are explicitly marked as operator throughput stress tests) and evaluates task accuracy and full-model TTFT across 25%–90% sparsity on LOFT NQ 128K—where SudokuRAG preserves 54.0% accuracy at 50% sparsity (1.25× TTFT) and 53.7% at 75% sparsity (1.67× TTFT), consistently outperforming both FlexPrefill and SIFT.
  • Fair comparison against standalone FA-3: We re-benchmarked Table 3 against standalone FlashAttention-3 alongside cuDNN SDPA across all context lengths (1.24× / 1.38× / 1.45× over FA-3 at 50% sparsity and 2.13× / 2.38× / 2.57× at 75% sparsity) and will update our manuscript to use standalone FA-3 as the primary dense baseline.

W3. Missing lambda_PV configuration details

We apologize for this omission. Global Comment 1 provides the complete configuration (α=0.001\alpha = 0.001, τ=0.6\tau = 0.6, lambda_QK = 0.8, and lambda_PV = 1e-4 at 128K, with layers 0–1 and decode steps dense), which we will add to Section 5.1 of the revised manuscript.

Q1. Online overheads in Table 3 and absolute latencies relative to cuDNN SDPA and standalone FA-3

Table 3 includes all online selection and data-preparation overheads (Q/K block means, coherence checks, scoring, selection, command compaction, and QKV packing) prior to sparse kernel execution. As shown in Global Comment 2, at Table 2's ~50% sparsity operating point (lambda_QK = 0.8, lambda_PV = 1e-4), online attention latencies are:

  • 32K: 10.62 ms vs. 13.16 ms standalone FA-3 (1.24×) and 12.92 ms cuDNN SDPA (1.22×).
  • 64K: 39.53 ms vs. 54.44 ms standalone FA-3 (1.38×) and 54.19 ms cuDNN SDPA (1.37×).
  • 128K: 157.41 ms vs. 228.00 ms standalone FA-3 (1.45×) and 251.88 ms cuDNN SDPA (1.60×).

Q3. Generalization across language model scales

Following your suggestion, we additionally evaluated Qwen3-0.6B (GQA 2:1) and Qwen3-4B (GQA 4:1) alongside Qwen3-8B and Llama-3.1-8B-Instruct on official LOFT NQ 128K RAG (4× YaRN to 128K, single 80GB H100; 32B+ models exceed 80GB HBM capacity for 128K BF16 KV caches without multi-GPU tensor parallelism). At 0.6B, even dense attention hits a 128K retrieval capacity floor (3.0% subspan_em), while our coherence guard (τ=0.6\tau = 0.6) automatically restricts over-pruning (4.0% subspan_em). Once model capacity supports 128K retrieval, SudokuRAG generalizes consistently across scales: on Qwen3-4B, it matches dense FA-3 at the conservative default (34.0% vs. 34.0%) and reaches 38.0% subspan_em with a 1.15× full-prefill speedup (9.13 s -> 7.92 s) at higher sparsity, consistent with our gains on Qwen3-8B (52.0% vs. 50.0% for FlexPrefill/SIFT/MInference, Table 2) and Llama-3.1-8B (Global Comment 2).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.