- 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
-
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.
-
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
- What is the complete configuration used in Table 2, particularly ? 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?
- Is this method only useful in fixed corpus setting?
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:
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.0.77 s–10.53 s(0.15–2.67 MiBon disk) for4K–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_PVselection insight, and performance on Table 3's inputs.lambda_QK = 0.8, andlambda_PV = 1e-4at 128K (layers 0–1 and decode dense).lambda_PVis scaled inversely with context length (~c / N) so cumulative omitted post-QK weights stay negligible across long contexts, while sweepinglambda_PVon a log scale (1e-5to1e-1) smoothly controls25%–75%sparsity.53.7%accuracy).