acceptodds
Under review as a conference paper at ICLR 2027

Temporal Working Sets for Sparse Attention

Abstract

Sparse attention algorithms output the attention support over a small subset of input tokens, but finding this subset can require full cache search at each step in the decoder. We prove that this search has further structure not captured by the sparsity of attention support compared to previous attention supports. Larger working sets in two pretrained models are useful for finding subsequent attention sets. Query permutation against fixed memory reduces working set lifetimes from 22.9 and 19.7 to 4.3 and 3.9 steps for the Llama-3.1-8B and Qwen3-8B models respectively, without affecting each query's answer. Recurrent Attention Routing (RAR) maintains working sets and updates bounds from previous page visits instead of learning these bounds. Each query ranks the best set of current candidates and the best scores for new keys, and expands attention search to pages that may change its top-. We prove that this algorithm exhaustively selects all relevant tokens, derive sufficient conditions to reuse working sets by margins in query ranks and query displacements, and show a RAR speedup in routing with 128K context of and , and a decoding speedup for both models. All 65,069,056 selected head routes coincide with exhaustive selection. Temporal working sets lower the cost of computing each new attention support without training.

Primary area:
foundation or frontier models, including LLMs
Keywords:
sparse attention, long-context inference, attention routing, KV cache

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_4NYYOpenReview ↗
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
AuthorsOpenReview ↗

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-kk 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.

WorkloadTidalDecode scoreRAR scoreTidalDecode request, sRAR request, sRAR request speedup [95% CI]
QA49.049.20.5620.5381.04× [1.02, 1.07]
Code completion51.051.30.8050.7661.05× [1.02, 1.08]

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=4096K=4096, dense layers 0–1, and selection at layers 2 and 13, whereas RAR uses k=4096,m=8192k=4096, m=8192 across sparse layers (Appendix D.6). Preserving head-specific top-kk 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=64k=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-kk 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.

AuthorsOpenReview ↗

Response to 4NYY (2/3): Near-dense quality and complete-request speedups

Scaling RAR's selection budget kk brings task accuracy within 0.1 points of Dense and preserves complete-request speedups. Revised Table 4 sweeps k∈{2048,4096,8192}k\in\{2048,4096,8192\} with m=2km=2k alongside Dense, Quest, and TidalDecode under identical free-running autoregressive generation.

MethodQA F1QA request, sCode similarityCode request, s
Dense49.70.62151.50.910
Quest, budget 204847.30.59349.80.862
TidalDecode, K=4096K=409649.00.56251.00.805
RAR, k=2048k=204847.90.52950.60.753
RAR, k=4096k=409649.20.53851.30.766
RAR, k=8192k=819249.60.56751.40.814

At k=4096k=4096, 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 k=8192k=8192, 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 k=8192k=8192 (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-kk 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.

AuthorsOpenReview ↗

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 k=4096k=4096 and m=8192m=8192, complete-request speedups and 95% confidence intervals across these workloads are

Autoregressive workloadRequest speedup over Dense [95% CI]Request speedup over TidalDecode [95% CI]
Llama-3.1-8B QA, 32K1.15× [1.12, 1.18]1.04× [1.02, 1.07]
Llama-3.1-8B code, 32K1.19× [1.15, 1.22]1.05× [1.02, 1.08]
Qwen3-14B QA, 32K1.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.

MethodOutput tokens, mean [min, max]TPOT, ms [95% CI]Complete request, s [95% CI]
Dense914.8 [587, 1024]27.64 [26.48, 28.95]31.86 [25.54, 34.96]
TidalDecode876.3 [438, 1024]25.01 [23.97, 26.19]28.57 [21.02, 32.26]
RAR906.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 k=8192k=8192, 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.

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

This paper proposes Recurrent Attention Routing (RAR) to accelerate exact top-k sparse attention during decoding. RAR maintains a candidate working set and historical page-level score bounds, allowing it to skip keys that cannot affect the current selection.

Critical strengths
  1. RAR preserves the exhaustive top-k result. The correctness argument is supported by agreement checks over 65 million head-level routes.
  2. The query-order intervention and component ablations provide useful evidence that temporal reuse contributes to the speedup.
  3. Using common scoring and attention kernels makes the internal comparisons reasonably controlled.
Critical weaknesses
  1. The novelty is insufficiently established. LServe, TokenSelect, and ReTopK already reuse selections or rerank historical candidates, but are not discussed.
  2. The comparisons rely heavily on custom baselines. EMA-Proposal does not reproduce the full PRR runtime, so it cannot establish an advantage over that method.
  3. Efficiency measurements use teacher-forced continuations from only four PG-19 books, with two timed repetitions and no uncertainty estimates. Relative to EMA-Proposal, the decoding speedup is about 1.08×.
  4. The quality–latency tradeoff remains unclear. Evaluation mainly fixes k=2048k=2048, which produces noticeable quality losses relative to full attention. Matched-quality efficiency comparisons are missing.
Questions for authors
  1. What specifically distinguishes RAR from LServe, TokenSelect, and ReTopK? Can you provide matched comparisons?
  2. Do the speedups hold during autoregressive QA, code generation, and longer continuations? Please report uncertainty across independent requests.
  3. How does the quality–latency tradeoff change with kk, including comparisons with full attention?
7 comments
AuthorsOpenReview ↗

Response to iKYg (1/4): Contribution beyond selection reuse

We thank you for recognizing our top-kk equivalence guarantee, query-permutation intervention, and controlled kernel comparisons. Here we clarify how RAR introduces a temporal search method beyond reuse of past selections, followed in parts 2–4 by controlled baseline analyses and end-to-end autoregressive quality–latency benchmarks.

RAR recovers each query's exhaustive full-cache top-kk support from compact state even as selected tokens change from step to step. RAR retains a wider m>km>k working set, rescores that pool plus the causal append frontier on every query, and tests excluded prefix keys against the current kkth-score threshold via outward-rounded bounds. Unresolved pages undergo targeted fallback visits and local anchor refreshes.

MethodReused state and query-time decision rule
LServe [1]Reuses selected pages across a fixed token chunk (four-step default interval in Section 3.5.3).
TokenSelect [2]Reuses cached top-kk indices unchanged whenever query cosine similarity exceeds a threshold (Algorithm 1).
ReTopK [3]Unions historical supports from similar past queries with recent tokens and reranks that union, using similarity fallbacks and periodic refreshes.
RARReranks a wider m>km>k pool and append frontier each step, verifying excluded prefix keys via scalar global and locally refreshed page bounds.

TokenSelect's invariance analysis (Appendix C) gives conditions under which the top-kk set remains unchanged. RAR's Proposition 1 uses the score gap between ranks kk and m+1m+1, preserving candidate coverage as competitive tokens swap ranks across the rank-kk cutoff. ReTopK recovers full-cache top-kk only when its candidate union contains every current top-kk key. RAR supplies an operational bound check and selective page expansion that guarantee current-query coverage over an append-only cache (Theorem 1).

Controlled interventions isolate both components of RAR's temporal state. Shuffling recorded queries against a frozen cache leaves every single-step retrieval target identical yet cuts mean working-set lifetimes from 22.9 to 4.3 steps on Llama-3.1-8B and from 19.7 to 3.9 on Qwen3-8B. Even in the lowest quartile of adjacent top-kk overlap, the working set plus append frontier covers 85.4% of the next top-kk support, and 42.7% of routes require no excluded-key scoring. Furthermore, resetting page anchors after every step raises routing latency by 31.4% at a fixed candidate budget mm, showing that anchor-refreshed temporal bounds contribute substantial pruning beyond candidate retention alone.

RetrievalAttention [4] develops attention-specific vector retrieval to reduce KV access costs. RAR advances this retrieval problem through temporal search state, using previous queries to accelerate the next search with exhaustive top-kk preservation and no router training.

References

[1] Shang Yang et al. LServe: Efficient Long-sequence LLM Serving with Unified Sparse Attention. MLSys, 2025.

[2] Wu et al. TokenSelect: Efficient Long-Context Inference and Length Extrapolation for LLMs via Dynamic Token-Level KV Cache Selection. EMNLP, 2025.

[3] Yao et al. Recall Before You Rank: Similarity-Guided Top-K Reuse for Efficient Long-Context Attention. arXiv preprint, 2026.

[4] Liu et al. RetrievalAttention: Accelerating Long-Context LLM Inference via Vector Retrieval. NeurIPS, 2025.

AuthorsOpenReview ↗

Response to iKYg (2/4): Controlled routing comparisons and PRR

Under identical scoring arithmetic, tie breaking, and value-aggregation kernels, RAR cuts routing latency by over one third against stateful temporal candidate proposals. Table 2 holds the target top-kk operator and attention kernel fixed so every router returns the identical output, isolating true search overhead and physical memory traffic.

EMA-Proposal serves as a controlled common-kernel baseline that proposes candidates from exponentially weighted selection history. At 128K context and k=2048k=2048, RAR outperforms this stateful baseline across both models.

ModelEMA routing, msRAR routing, msRouting-time reductionPhysical key-traffic reduction
Llama-3.1-8B5.223.3835.2%27.6%
Qwen3-8B6.294.1933.4%24.9%

These routing savings reduce full token-decoding latency from 23.78 to 21.96 ms on Llama-3.1-8B and from 27.05 to 24.91 ms on Qwen3-8B (roughly 1.08× end-to-end decoding speedup over an already stateful router). Relative to exhaustive top-kk, RAR accelerates routing by 3.90× and 3.60× and full token decoding by roughly 1.44× on both models.

PRR and RAR target complementary stages of sparse decoding. PRR [1] predicts blocks from prior steps, overlaps speculative attention execution with an underlying selector, and repairs missed blocks once selection finishes. PRR invokes its underlying selector on every step. RAR reduces the metadata and key reads performed by the selector itself. EMA-Proposal isolates historical candidate prediction within our shared routing implementation, whereas RAR shrinks selector work directly through two-level temporal bounds and local anchor refreshes. To evaluate end-to-end systems, part 3 compares RAR directly against Quest and TidalDecode.

Recent systems literature underscores why cutting physical key reads drives decoding speed. SparQ Attention [2] shows that full key scans bottleneck sparse value aggregation, Native Sparse Attention [3] links GQA memory coalescing to HBM bandwidth, and RetroInfer [4] builds dedicated storage indexing to curb KV access traffic.

Component ablations in Table 7 confirm that each piece of RAR's state eliminates physical work under a fixed attention operator. Dropping the scalar global check raises routing latency to 1.23× and metadata reads from 68.9 to 193.4 MiB per output token. Replacing temporal bounds with static coordinate bounds raises routing latency to 1.57× and scored keys from 17.6% to 33.2%. Disabling local page-anchor refresh increases routing latency to 1.34×. Part 3 shows how these mechanism-level savings translate into superior autoregressive quality–latency tradeoffs.

References

[1] Wang et al. Predict, Reuse, and Repair: Accelerating Dynamic Sparse Attention for Long-Context LLM Decoding. arXiv preprint, 2026.

[2] Ribar et al. SparQ Attention: Bandwidth-Efficient LLM Inference. ICML, 2024.

[3] Yuan et al. Native Sparse Attention: Hardware-Aligned and Natively Trainable Sparse Attention. ACL, 2025.

[4] Chen et al. RetroInfer: A Vector Storage Engine for Scalable Long-Context LLM Inference. PVLDB 19(5), 1016–1031, 2026.

AuthorsOpenReview ↗

Response to iKYg (3/4): Autoregressive quality and latency across budgets

At k=4096k=4096, RAR beats TidalDecode and Quest in both task accuracy and complete-request latency, and scaling to k=8192k=8192 brings scores within 0.1 points of Dense with end-to-end request speedups. These free-running benchmarks directly address downstream quality–latency scaling as kk increases.

Revised Table 4 evaluates Llama-3.1-8B-Instruct with a 32K sequence budget and 128-token output cap at batch size one in BF16 on one H100-SXM 80GB. QA macro-averages F1 across three datasets (96 requests), and code completion macro-averages edit similarity across two datasets (64 requests). Every method generates its own autoregressive continuation from identical prompts, and complete-request latency includes prefill, state initialization, per-step updates, and decoding.

MethodQA F1QA request, sCode similarityCode request, s
Dense49.70.62151.50.910
Quest, budget 204847.30.59349.80.862
TidalDecode, K=4096K=409649.00.56251.00.805
RAR, k=2048k=204847.90.52950.60.753
RAR, k=4096k=409649.20.53851.30.766
RAR, k=8192k=819249.60.56751.40.814

The sweep with m=2km=2k identifies favorable quality–latency operating points. At k=4096k=4096, RAR achieves higher accuracy and faster complete requests than both TidalDecode (K=4096K=4096) and Quest (budget 2048). At k=8192k=8192, RAR reaches 49.6 vs. 49.7 F1 on QA and 51.4 vs. 51.5 similarity on code, sustaining complete-request speedups over Dense of 1.10× [1.07, 1.12] on QA and 1.12× [1.09, 1.15] on code (95% CIs).

Evaluating accuracy–latency frontiers across token budgets follows standard practice in Quest [1], TidalDecode [2], and DuoAttention [3]. Theorem 1 preserves full-cache top-kk selection at each chosen budget. The 8K measurements show that increasing the budget recovers near-dense task scores and retains request speedups, with no additional selection approximation introduced by the router.

For reproducibility, TidalDecode uses dense layers 0–1, full selection at layers 2 and 13, and position-persistent sparse attention elsewhere without cache correction, matching its primary evaluation [2], and Quest uses budget 2048 with page size 16 (Appendix D.6). Together, these operating points confirm simultaneous accuracy and latency wins over sparse baselines at 4K and near-dense quality with end-to-end speedups at 8K.

References

[1] Tang et al. Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inference. ICML, 2024.

[2] Lijie Yang et al. TidalDecode: Fast and Accurate LLM Decoding with Position Persistent Sparse Attention. ICLR, 2025.

[3] Xiao et al. DuoAttention: Efficient Long-Context LLM Inference with Retrieval and Streaming Heads. ICLR, 2025.

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

This work proposes Recurrent Attention Routing (RAR), an efficient routing algorithm for sparse attention computation. The key idea is to consider temporal locality across queries by maintaining a reusable working set and page-level score constraits. The method accelerates sparse attentin by avoid search the entire KV cache while keeping the top-k attention support. Experiments on LLaMa-3.1-8B and Qwen3-8B show good efficiency results.

Critical strengths
  1. This paper identifies an important weak point for existing sparse attention methods. Even if we only need to select a small subset of tokens, identifying this subset can require costly searches over the entire KV cache. This is well-motivated and can have good potential impact.

  2. The empirical result of this paper is convincing. Among all baselines, the proposed method shows significant improvements. The alignment with exaustive selection across more than 65m head routes is also good.

  3. The theoretical analysis of this paper is solid. The algorithm preserves the exhaustive top-k support and will not introduce additional approximation error, which is an impressive result.

Critical weaknesses
  1. The presentation quality in Section 3 can be improved. It will be better if the authors show a simple running example in appendix, and give a \ref link in Section 3, so the readers can better understand the method.

  2. The empirical evaluation only gives results on two 8B models and small batch sizes. It would be better if the authors conider larger models and larger batch sizes.

  3. Theorem 1 looks like a correctness guarantee and is directly obtained from the assumptions. It would be better if the authors clarify the non-triviality of this guarantee and explain the assumptions.

Questions for authors
  1. Please refer to weakness 2

  2. How frequently are the assumptions for Theorem 1 satisfied in practice?

3 comments
AuthorsOpenReview ↗

Response to RUGt (1/3): Larger models and batched execution

We warmly appreciate your supportive recommendation and your positive assessment of our motivation, empirical efficiency gains, and theoretical analysis. Your emphasis on preserving exhaustive top-kk attention captures a primary advantage of RAR. Below, we present the 14B-scale experiments and batched execution results requested in your review.

On Qwen3-14B, RAR improves both QA accuracy and complete-request latency over TidalDecode. Revised Table 5 evaluates this 14.8B-parameter model across the same three QA datasets tested on Llama-3.1-8B. Every method shares identical prompts, a 32K sequence budget, a 128-token output cap, BF16 weights and KV caches, decoding settings, and single H100-SXM 80GB hardware across 96 requests with two timing repetitions per request.

MethodQA F1TPOT, msComplete request, s
Dense48.926.180.882
TidalDecode48.222.840.849
RAR48.720.370.818

RAR achieves complete-request speedups of 1.08× over Dense and 1.04× over TidalDecode. RAR transfers directly with the same four settings used in the 8B comparison (k=4096k=4096, m=8192m=8192, page capacity B=128B=128, renewal horizon H=64H=64). TidalDecode runs K=4096K=4096, dense layers 0–1, full selection at layers 2 and 12, and position-persistent sparse attention elsewhere without cache correction, following TidalDecode's evaluation setup [1]. These gains extend the quality–latency advantage to Qwen3-14B.

Batched decoding uses shared KV geometry and coalesced reads across grouped-query heads. At batch size two and 64K context, RAR reaches 96.8 tokens/s on Llama-3.1-8B and 87.4 tokens/s on Qwen3-8B (Table 13). RAR maintains temporal state per request and query head, shares static page summaries within each GQA group, and coalesces overlapping fallback page reads across grouped heads. Read coalescing cuts physical HBM key traffic by 27.9% on Llama-3.1-8B and 25.6% on Qwen3-8B.

Native Sparse Attention [2] highlights how group-level KV memory access governs practical GPU decoding speed. By coalescing fallback page loads across grouped heads, RAR translates temporal state reuse directly into lower memory-bandwidth demand during multi-request execution.

Thank you for suggesting these experiments, which demonstrate RAR's effectiveness at larger scale and under batched serving.

References

[1] Lijie Yang et al. TidalDecode: Fast and Accurate LLM Decoding with Position Persistent Sparse Attention. ICLR, 2025.

[2] Yuan et al. Native Sparse Attention: Hardware-Aligned and Natively Trainable Sparse Attention. ACL, 2025.

AuthorsOpenReview ↗

Response to RUGt (2/3): Theorem 1 and its constructive conditions

RAR maintains all conditions of Theorem 1 by construction at every decoding step. Theorem 1 rests on computable invariants enforced by RAR's state updates and applies under arbitrary query displacement.

For any excluded key ziz_i on completed page bb, RAR stores page center μb\mu_b, radius rbr_b bounding centered key norms, and maximum centered score vbv_b over excluded keys recorded when the head last visited page bb at anchor query pbp_b. By Cauchy–Schwarz,

qt⊤zi≤qt⊤μb+vb+rb∥qt−pb∥2.q_t^\top z_i \le q_t^\top \mu_b + v_b + r_b \lVert q_t-p_b \rVert_2.

This inequality holds unconditionally for any query displacement. RAR pairs it with static coordinate-extrema bounds and a scalar global bound from the renewal query. Because each bound is sound individually, their minimum remains sound. Extending query-aware page bounds such as Quest [1], RAR's anchor-refreshed maximum lets each fallback visit tighten pruning on subsequent steps.

Four algorithmic invariants preserve safe pruning across an append-only cache.

  1. Newly appended keys enter the append frontier and are scored directly each step, keeping completed-page domains and exclusion masks fixed between renewals.
  2. A page is skipped only when its upper bound lies strictly below the provisional kkth-score threshold. Ties trigger a page visit.
  3. Visiting a page refreshes its anchor query pbp_b and excluded maximum vbv_b. Scoring additional keys can only raise the running kkth threshold, so all prior skips remain valid.
  4. Renewal updates the working-set mask prior to rebuilding per-page excluded maxima.

Appendix B realizes these invariants on GPUs via outward floating-point rounding and error allowances. Paired with shared dot-product evaluation, index-based tie breaking, and deterministic value-reduction order, RAR matches exhaustive top-kk selection across all 65,069,056 evaluated head routes and every greedy and paired stochastic completion test (Table 10).

Our companion theory characterizes how often retained state avoids fallback work. Proposition 1 guarantees full-cache top-kk coverage by the working set and frontier whenever

2R∥qt−qa∥2<s(k)(qa)−s(m+1)(qa),2R \lVert q_t-q_a \rVert_2 < s_{(k)}(q_a)-s_{(m+1)}(q_a),

allowing arbitrary rank swaps across the rank-kk cutoff inside the wider mm-key pool. Proposition 2 bounds temporal page slack by 2rb∥qt−pb∥22 r_b \lVert q_t-p_b \rVert_2, and Equation 16 relates renewal frequency to cumulative query-path length and working-set margins. Large query shifts simply trigger selective page visits or renewal, preserving output equivalence throughout.

Empirical route distributions reflect these bounds. The scalar global check resolves 63.8% of routes on Llama-3.1-8B and 59.4% on Qwen3-8B without reading page metadata, page-level bounds handle another 31.4% and 34.8%, and renewals occur on just 4.8% and 5.8% of steps (Figure 3). MagicPIG [2] combines theoretical sampling analysis with practical inference speedups. RAR develops the theory and GPU implementation for recurrent top-kk search, including support preservation throughout cache growth.

References

[1] Tang et al. Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inference. ICML, 2024.

[2] Chen et al. MagicPIG: LSH Sampling for Efficient LLM Generation. ICLR, 2025.

AuthorsOpenReview ↗

Response to RUGt (3/3): Running example added to Appendix E

Thank you for this helpful suggestion. Following your recommendation, we have added a step-by-step numerical running example in Appendix E (pages 27 to 28 of the revised manuscript) and placed a direct reference at the beginning of Section 3.1 so readers can easily trace the mechanics alongside our main exposition and the state-transition algorithms in Appendix B.3.

To make the state updates concrete, the example tracks one attention head across four queries using two-dimensional keys, three initial pages, and budgets k=1k=1, m=2m=2, and B=2B=2, with Table 19 summarizing the page geometry and routing decisions. Across these steps, the walkthrough illustrates four core behaviors.

  1. Initialization selects index 11 and retains the working set E0={1,3}E_0=\{1,3\}.
  2. On the second query, index 33 is selected within the retained working set, and the global bound resolves the query without reading any page metadata.
  3. A subsequent query visits only page P1P_1, where excluded key 22 becomes the active selection. RAR refreshes only that page's anchor and centered maximum, leaving the working set unchanged.
  4. At the final query, a newly appended key is selected, and the refreshed bound skips the previously visited page without reading excluded prefix keys.

Appendix E provides the candidate scores, thresholds, and bound calculations for each step, and demonstrates how newly appended keys remain in the frontier after filling a physical page. All four selections match exhaustive search.

We appreciate your encouraging evaluation of our method and analysis, as well as this constructive suggestion to make the paper clearer.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of revisions and responses

Dear All,

We sincerely thank Reviewers RUGt, iKYg, and 4NYY for their time, constructive feedback, and thoughtful engagement with our submission. We are very encouraged by the strengths highlighted across the reviews. Reviewer RUGt notes that addressing the full-cache search bottleneck is "well-motivated and can have good potential impact" for sparse attention, and Reviewer 4NYY highlights how identifying "persistent temporal working sets" succeeds in "providing a concrete mechanism for reducing repeated retrieval work" across decoding steps.

Regarding our theoretical guarantees, Reviewer RUGt remarks that our analysis is "solid" and finds it "an impressive result" that RAR "will not introduce additional approximation error" relative to exhaustive top-kk selection. Reviewer 4NYY similarly reports having "no substantive concerns about the paper’s soundness" and notes how our bounds succeed in "enabling acceleration without introducing additional approximation beyond the chosen sparse operator" during routing, complemented by Reviewer iKYg's recognition of our "agreement checks over 65 million head-level routes" verifying support preservation.

In evaluating our experiments, Reviewer RUGt describes the empirical results as "convincing" with "significant improvements" among all baselines, Reviewer 4NYY highlights our "approximately 1.44× faster decoding at 128K context" on Llama and Qwen, and Reviewer iKYg commends our "reasonably controlled" kernel comparisons together with ablations providing "useful evidence that temporal reuse contributes to the speedup" in practice.

Guided by your comments and suggestions, we have revised the manuscript and provided detailed point-by-point responses. Below, we summarize the main additions to the paper and the supporting evidence in our rebuttal:

  • Autoregressive generation quality and latency. We added evaluations of QA and code completion in Table 4 using each method's own generated outputs. At a matched 4096-token selection budget, RAR achieves higher task scores and lower complete-request latency than TidalDecode on both tasks. Increasing the budget to 8192 brings both task scores within 0.1 points of Dense and maintains complete-request speedups of 1.10x and 1.12x over Dense.
  • Scaling to larger models and long generation. We expanded our empirical study in Tables 5 and 6 to include Qwen3-14B QA and 128K PG-19 generation with natural EOS stopping. Using the same four settings on the 14B model, RAR improves both QA accuracy and complete-request latency over TidalDecode. On 128K PG-19 generation, RAR reaches TPOT speedups of 1.21x over Dense and 1.09x over TidalDecode.
  • Request-level variability. In our responses to reviewers iKYg and 4NYY, we added uncertainty estimates for both task quality and latency across independent requests, quantifying cross-request variation in our autoregressive comparisons.
  • Comparison with selection-reuse methods and ablations. Our responses contextualize RAR's retained working sets and refreshed page bounds alongside LServe, TokenSelect, ReTopK, and PRR. RAR recomputes the selected support at every query and preserves exhaustive top-kk selection as the KV cache grows. Query-order interventions and component ablations further link the empirical speedups to our retained candidates and page-level measurements.
  • Clarity and running example. We added a four-step numerical running example in Appendix E (summarized in Table 19 and referenced at the start of Section 3.1) to illustrate candidate reuse, selective page visits, frontier growth, and local anchor updates. We also revised the abstract and introduction to present the full study more clearly and cohesively.

We believe these updates have substantially strengthened the manuscript, and we remain happy to address any further questions during the discussion phase. Thank you again for your time and dedication in reviewing our work.

Sincerely,

The Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.