- Rating
- 3(+1)
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper proposes RAR, a sparse-attention routing method that reuses candidate sets and score bounds across decoding steps to exploit temporal locality. It reduces retrieval costs while preserving exhaustive top-k attention results. Theoretical guarantees and experiments on Llama and Qwen models support its correctness and efficiency, showing approximately 3.6–3.9× faster routing and 1.44× faster decoding at 128K context.
Critical strengths
- The paper identifies persistent temporal working sets despite changes in exact top-k selections, providing a concrete mechanism for reducing repeated retrieval work.
- Certified score bounds preserve exhaustive top-k attention results, enabling acceleration without introducing additional approximation beyond the chosen sparse operator.
- Experiments on Llama and Qwen demonstrate approximately 1.44× faster decoding at 128K context. Ablations further support temporal locality as the source of the improvement.
Critical weaknesses
-
The paper discusses reuse-based approaches such as TidalDecode but does not experimentally compare against them. Comparisons under matched attention-quality settings are needed to establish whether RAR offers a meaningful advantage over existing approaches.
-
The timing evaluation covers two 8B models on a single H100, using only four PG19 books and two repetitions. Limited workload diversity and the lack of uncertainty estimates reduce confidence in the robustness and generalizability of the reported speedups.
Questions for authors
-
How does RAR compare with reuse-based methods such as TidalDecode under matched models, context lengths, and output-quality settings?
-
How much do the reported speedups vary across individual PG19 books and repeated runs? Could you provide uncertainty estimates and evidence that the gains persist on more diverse decoding workloads?
-
Since RAR preserves top-k attention rather than dense attention, how does its end-to-end latency compare with dense attention and Quest at matched downstream accuracy, particularly when increasing k to reduce the quality gap?
5 comments
Response to 4NYY (2/3): Near-dense quality and complete-request speedups
Scaling RAR's selection budget brings task accuracy within 0.1 points of Dense and preserves complete-request speedups. Revised Table 4 sweeps with alongside Dense, Quest, and TidalDecode under identical free-running autoregressive generation.
| Method | QA F1 | QA request, s | Code similarity | Code request, s |
|---|---|---|---|---|
| Dense | 49.7 | 0.621 | 51.5 | 0.910 |
| Quest, budget 2048 | 47.3 | 0.593 | 49.8 | 0.862 |
| TidalDecode, | 49.0 | 0.562 | 51.0 | 0.805 |
| RAR, | 47.9 | 0.529 | 50.6 | 0.753 |
| RAR, | 49.2 | 0.538 | 51.3 | 0.766 |
| RAR, | 49.6 | 0.567 | 51.4 | 0.814 |
At , RAR surpasses both Quest and TidalDecode in task accuracy and request speed, achieving complete-request speedups over Dense of 1.15× [1.12, 1.18] on QA and 1.19× [1.15, 1.22] on code completion.
At , RAR reaches 49.6 F1 on QA (within 0.1 of Dense's 49.7) and 51.4 similarity on code (within 0.1 of Dense's 51.5), retaining complete-request speedups over Dense of 1.10× [1.07, 1.12] and 1.12× [1.09, 1.15] with 95% confidence intervals. Generated continuation lengths match Dense closely at (30.9 vs. 30.8 mean tokens on QA and 76.5 vs. 76.4 on code), and request wall-clock times include prefill and routing-state management alongside decoding.
Tracing accuracy–latency frontiers across token budgets aligns with standard evaluation methodology in Quest [1], TokenSelect [2], and DuoAttention [3]. RAR amortizes candidate retrieval through temporal working sets and sound bounds, preserving exhaustive top- selection at each budget (Theorem 1). The 8K results demonstrate near-dense task quality together with faster complete requests.
References
[1] Tang et al. Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inference. ICML, 2024.
[2] Wu et al. TokenSelect: Efficient Long-Context Inference and Length Extrapolation for LLMs via Dynamic Token-Level KV Cache Selection. EMNLP, 2025.
[3] Xiao et al. DuoAttention: Efficient Long-Context LLM Inference with Retrieval and Streaming Heads. ICLR, 2025.
Response to 4NYY (3/3): Workload diversity and timing variability
Our expanded autoregressive suite establishes consistent speedups with 95% confidence intervals across diverse multi-dataset tasks, 14B model scale, and long 128K continuations. QA spans Qasper, HotpotQA, and 2WikiMultihopQA (32 fixed prompts per dataset, 96 requests per model), and code completion spans LCC and RepoBench-P (64 requests). Scores are macro-averaged across datasets in our evaluation. LongBench [1] supplies these QA and code tasks, including the repository-context completion task from RepoBench [2].
At and , complete-request speedups and 95% confidence intervals across these workloads are
| Autoregressive workload | Request speedup over Dense [95% CI] | Request speedup over TidalDecode [95% CI] |
|---|---|---|
| Llama-3.1-8B QA, 32K | 1.15× [1.12, 1.18] | 1.04× [1.02, 1.07] |
| Llama-3.1-8B code, 32K | 1.19× [1.15, 1.22] | 1.05× [1.02, 1.08] |
| Qwen3-14B QA, 32K | 1.08× [1.05, 1.11] | 1.04× [1.02, 1.06] |
Every confidence interval lies strictly above 1.0 relative to both Dense and TidalDecode, accompanied by higher task scores than TidalDecode in all three settings.
To measure request variability during sustained generation under natural EOS stopping, revised Table 6 decodes four independent 128K PG-19 test-book requests up to 1024 output tokens with two timing repetitions per request.
| Method | Output tokens, mean [min, max] | TPOT, ms [95% CI] | Complete request, s [95% CI] |
|---|---|---|---|
| Dense | 914.8 [587, 1024] | 27.64 [26.48, 28.95] | 31.86 [25.54, 34.96] |
| TidalDecode | 876.3 [438, 1024] | 25.01 [23.97, 26.19] | 28.57 [21.02, 32.26] |
| RAR | 906.5 [554, 1024] | 22.86 [21.93, 23.91] | 27.74 [22.18, 30.52] |
RAR achieves TPOT speedups of 1.21× [1.16, 1.26] over Dense and 1.09× [1.05, 1.14] over TidalDecode. RAR and Dense each reach the 1024-token limit on three of the four independent book requests (compared with two for TidalDecode), and RAR generates longer continuations on average than TidalDecode with lower mean complete-request latency. Reporting output-length ranges alongside TPOT and request-time confidence intervals makes natural stopping variation transparent.
These results establish faster, higher-scoring requests than TidalDecode on the QA and code comparisons, near-dense quality at , and sustained 128K generation speedups. They connect RAR's theoretical foundation to the practical quality and efficiency questions in your review. We would be grateful if you could reconsider your recommendation in light of this evidence.
References
[1] Bai et al. LongBench: A Bilingual, Multitask Benchmark for Long Context Understanding. ACL, 2024.
[2] Liu et al. RepoBench: Benchmarking Repository-Level Code Auto-Completion Systems. ICLR, 2024.
Response to 4NYY (1/3): Direct comparisons with TidalDecode
We thank you for recognizing persistent temporal working sets as a concrete mechanism for cutting retrieval work, noting our exhaustive top-k guarantee, and reporting no substantive soundness concerns. Our revised experiments directly provide the head-to-head autoregressive comparison against TidalDecode at matched or higher task quality requested in your review.
At a matched 4096-token budget, RAR achieves higher task scores and lower complete-request latency than TidalDecode on both QA and code completion. Using Llama-3.1-8B-Instruct on one H100-SXM 80GB (batch size one, BF16 weights and KV caches, 32K sequence budget, 128-token output cap), every method decodes autoregressively from identical prompts, and complete-request timing covers prefill, state setup, per-step updates, and generation.
RAR lowers TPOT from 9.92 to 8.72 ms on QA and from 8.10 to 7.39 ms on code completion, with closely matched generated lengths (31.2 vs. 31.0 mean tokens on QA and 76.9 vs. 76.8 on code for TidalDecode and RAR).
TidalDecode [1] performs full selection at designated layers and shares selected token positions across subsequent layers. Following its main evaluation setup without cache correction, TidalDecode uses K=4096, dense layers 0–1, and selection at layers 2 and 13, whereas RAR uses k=4096,m=8192 across sparse layers (Appendix D.6). Preserving head-specific top-k supports via temporal working sets and excluded-key bounds delivers both higher downstream accuracy and faster wall-clock requests than cross-layer index reuse.
This quality and latency advantage transfers unchanged to Qwen3-14B. Across 96 QA requests with two timing repetitions each, RAR improves F1 over TidalDecode from 48.2 to 48.7, cuts TPOT from 22.84 to 20.37 ms, and lowers complete-request time from 0.849 to 0.818 s, yielding a 1.04× [1.02, 1.06] request speedup with the same four RAR settings (k=4096,m=8192,B=128,H=64) against TidalDecode with selection layers 2 and 12 (Table 5 and Appendix D.7).
RetrievalAttention [2] and RetroInfer [3] develop attention-specific retrieval and storage systems to reduce KV access costs. RAR advances this problem through temporal search state with full-cache top-k preservation. The direct comparisons above establish higher task scores and lower complete-request latency than TidalDecode on QA and code, with the same pattern on Qwen3-14B QA.
References
[1] Lijie Yang et al. TidalDecode: Fast and Accurate LLM Decoding with Position Persistent Sparse Attention. ICLR, 2025.
[2] Liu et al. RetrievalAttention: Accelerating Long-Context LLM Inference via Vector Retrieval. NeurIPS, 2025.
[3] Chen et al. RetroInfer: A Vector Storage Engine for Scalable Long-Context LLM Inference. PVLDB 19(5), 1016–1031, 2026.