Retrospective Sparse Attention for Efficient Long-Context Generation
Authors: Seonghwan Choi
Beomseok Kang
Dongwon Jo
Jae-Joon Kim
Venue: ICLR 2026 Poster (2026)
Keywords: Long Generation
KV Cache
Compression
Primary area: foundation or frontier models, including LLMs

Abstract: Large Language Models (LLMs) are increasingly deployed in long-context tasks such as reasoning, code generation, and multi-turn dialogue. However, inference over extended contexts is bottlenecked by the Key-Value (KV) cache, whose memory footprint grows linearly with sequence length and dominates latency at each decoding step. While recent KV cache compression methods identify and load important few tokens, they focus predominantly on input contexts and fail to address the cumulative attention errors that arise during long decoding. In this paper, we introduce RetroAttention, a novel KV cache update technique that retrospectively revises past attention outputs using newly arrived KV entries from subsequent decoding steps. By maintaining a lightweight output cache, RetroAttention enables past queries to be efficiently supplemented with more contexts, while incurring minimal latency overhead. This breaks the fixed-attention-output paradigm and allows continual correction of prior approximations. Extensive experiments on long-generation benchmarks show that RetroAttention consistently outperforms state-of-the-art (SOTA) KV compression methods, increasing effective KV exposure by up to 1.6$\times$ and accuracy by up to 21.9\%. We provide anonymized code in the supplementary material.

Published as a conference paper at ICLR 2026
RETROSPECTIVE SPARSE ATTENTION FOR EFFICIENT LONG-CONTEXT GENERATION
Seonghwan Choi', Beomseok Kang', Dongwon Jo, Jae-Joon Kim
Seoul National University
(cah3695, beomseok, dongwonjo, jomjaaejoon@ssmu
ABSTRACT
Large Language Models (LLMs) are increasingly deployed in long-contedn tasks such as reasoning, code generation, and multi-turn dialogue. However, inference over extended contexts is bottlenecked by the Key-Value (KV) cache, whose mem- ory footprint grows linearly with sequence length and dominates latency at each decoding step. While recent KV cache compression methods identify and load im- portant few tokens, they focus predominantly the cumulative attention errors that arise during long decoding. this paper, we introduce RetroAttention, novel KV cache update technique that retrospectively revises past attention outputs using newly arrived KV entries from subsequent de- coding steps. By maintaining lightweight output cache, RetroAAttentin enables past queries to be efficiently supplemented with more contexts, while incurring minimal latency overhead. This breaks the Axed-attentioon-uupuu paradigm and allows continual correction of prior approximations. Extensive experiments on oog-generattion benchmarks show that RetroAttention consistently outperforms state-of-the thftthe-rrt art (SOTA) KV compression methods, increasing effective KV ex- posure by up to 1.6x and accuracy by up 21.9%. The code available at: com http:///ccccoe////eeettttttttte
input contexts and fail to address
INTRODUCTION
With the growing demand for long-context tasks such as reasoning (Jaech et al. 2024 Guo et al,
2025
Comanici et al. 2025), code generation (Chen et al. 2021 Jiang et al. 2024). and multi-
turn dialogue (Yi et al. 2024 Large Language Models (LI Ms) are increasingly expected to handle extended sequences of input and output. However, supporting such long-context scenarios imposes substantial computational challenges. A key constraint is the Key- (KV) cache, whose memory footprint grows linearly with context length. In practice, the KV cache can occupy several GBs, and fetching it at every decoding step often becomes the main latency bottleneck for inference (Zadouri al. 2025] Yuan al. (024). As result, efficient KV cache management has emerged as a critical technique for enabling scalable long-context inference in modern LLMs.
Recent studies have demonstrated that only small portion of the KV cache plays critical role in attention computation (Ribar et al. 2023 Zhang et al.) 2023 Li et al., 2024). Motivated by this, several KV cache compression techniques have been proposed to identify and only retain important tokens (Liu et al. 2023; Cai et al.) 2024 Singhania et al. 2024 Chen et al.) 2024b). However, these methods primarily focus on processing long-context inputs, rather than outputs. Long generation introduces distinct challenge: errors from approximated attention, due evicted KV entries, cursively accumulate in the model's hidden states over extended decoding steps. As illustrated in Figure bb). which evaluates generation quality on PG-19 (Rae et al. 2019), J. long-range language modeling benchmark, the performance gap between models using full and compressed KV cache is initially marginal but becomes substantial as generation progresses. This trend highlights the inher- ent weakness of existing approaches, which emphasize token selection for the current decoding step while leaving previously decoded tokens unchanged (Yang al. 2024 Tang et al.) 2024 Xiao al.) Liu et al. 2024a). A naive solution would be to allocate more KV cache budget (i.e., load more KV entries). but doing so increases memory usage and latency, defeating the main purpose
2024
Both authors contributed equally this work.

---

Published as a conference paper at ICLR 2026
Generated KV cache token Attended KV cache token
Dthers: Sparis Attention
Ours:
Relativa Purgfiaityy (1)
Quest
Batraspactivv Sparse Attention
Decoding Step
ta
Perplesity (4)
10
1.18
1.12
Quest
Full cache
LLaaed
I Loaded
1k 2k 3K 4k Sk 6k
7%. Bk
2x
8k 5K
4k
5K
7%
Used Usedioonly only torty stagl
Used i and (multistop)
Generation length
Generation
Figure I: High-level idea of RetroAttention. (a) illustrates the key distinction between conven- tional sparse attention (e.g., Quest) and the proposed Retrospective Sparse Attention. In our ap- proach, KV entries that are currently retrieved (4a) but were unseen in previous decoding steps (16-12) are reused to augment past attention computations. (b) demonstrates the average Perplexity depending on the range of generation lengths and relative Perplexity between full and compressed KV cache models (right), indicating significant quality degradation as generation continues.
of compression. This raises a fundamental research question: How can we mitigate the cumulative attention errors during long generation without increasing the KV cache budget?
In this paper, we propose novel KV cache update technique, called Retrospective Sparse Attention Attentonnnnnonn which enhances approximated attention for past Queries by leveraging future KV entries arriving in subsequent decoding steps (see Figure Ta)). RetroAttention builds on a query- aware non-eviction KV selection scheme, where the model assumes that some relevant KV entries may not be observable at the time Query is processed but can be loaded later during decoding. To efficiently leverage this behavior, we allocate a lightweight output cuche that stores the attention outputs of past Queries. As new KV entries arrive in subsequent steps, we retrospectively compute additional attention outputs for past Queries to update their previous outputs in the cache. This process effectively compensates for errors in the initial attention outputs, thereby improving the quality of KV representations passed to deeper layers. Consequently, each Query benefits from exposure more KV entries than the static cache budget would allow, without extra KV memory traffic. Our key contributions are as follows:
We propose RetroAttention, a novel KV cache update method for long-context genera- tion that retrospectively refines past attention outputs using newly retrieved KV entries. RetroAttention leverages a lightweight output cache, enabling efficient access and updates of past computations as future KV entries arrive.
We exploit the memory-boune nature of long-context inference, where the proposed retro- spective updates incur negligible latency. We analytically demonstrate this property using Arithmetic Intensity (AI) and empirically confirm that RetroAttention adds only marginal end-to-end latency overhead.
We extensively validate that retrospective updates effectively expand the number of KV entries exposed to queries (the effective KV budget) by up to 1.6x, without increasing the actual KV budget. RetroAAtention achieves up to 21.9% and on average 5.6% accuracy gains over SOTA methods on long-generation benchmarks.
2 PROPOSED APPROACH
2.1 BACKGROUND
Dynamic Sparse Attention. RetroAutention adopts Quest's KV cache selection strategy TTag al. 2024) address evolving importance of KV cache pages during decoding. Quest abstracts each KV cache page into Kmm and K Kmax, the element-wise minima and maxima of Key vectors within page, which highlight extreme feature values. The importance of the j-th cache page to
given Query is then estimated as:
score;(() Σ max(QuKk QcKeaaa))
(1)
2

---

Published as a conference paper at ICLR 2026
Model Imput
top-k (now) - top-k (past)
top-k (now] (op-(2X,30) (past)
Answer question step by step.
top-lt (now) -tppppppppp top-pkk (1, (past)
top (now] beyand top (post)
Question Bretchen has 110 coins. There are 30 more gold coins coins does Gretchen have?
silver How
tots- tokerne
100%
82.8
79.6
78.3
Effechve KV cache budget
200%
180%
Question N. Jemes decides run 3 sprints 3 times a week. He runs 60 meters
80%
73.8
150%
135%
total meters does week??
117%
Overlap of
60%
Outpun
100%
Answer Let's say of goid coins is a-50, 2x+30-110 10; 4040; The number of gold coins x130+60 30+70.
coins
number
15.2
16.9
50%
Original budget
20%
Answer N: James runs 3 sprints 3 times a week, it sprints week. Each sprintts is 60 meters, he runs x0 meterrs
[-1
2422
2-4
1-8
x=0 Supplemented for steps
n-1
Compared to c-step past
[a]
Figure 2: Long-generation accuracy analysis. (a) illustrates an example in LONGGENBENCH, long-generation benchmark, where the imput prompt includes concatenated questions. (b) presents the semantic correlation of the current top-k KV entries in the t-step prior decoding, categorized into different top-k intervals, demonstrating how often current important tokens would have been important in the past. (c) analyzes the effective KV cache budget (i.e., total KV entries exposed to a given Query) when supplemented with entries from n future decoding steps. Note that this growth may not scale linearly to n. as supplemented KV entries can be duplicated across updates. Results experimented with LLAMA3. 1-8-11ISRU----- and GSM8K in LONGGENBENCH.
where indexes the feature dimensions. This can be computed without loading full pages and enables efficient top-k selection of relevant pages at each decoding step.
This approach features that unselected KV entries are not permanently ture retrieval if they become relevant. While Quest emphasizes the Query- deeendee variability of optimal KV entries, we shift the focus to their reusability, using currently loaded entries to retro- spectively refine past attention outputs.
available for fu-
2.2 MOTIVATIONAL STUDY
Our motivation primarily arises from oonggeeneration scenarios, where even small amounts of KV cache supplementation can accumulate over many decoding steps and ultimately lead to non-trivial performance gains. We emphasize that the dependency on the KV cache budget differs substantially between long-context imput tasks and long-context output tasks.
Long-generation Tasks are More Sensitive to KV Budget. Our observation shows that, in LoNGBENCH (long-input, short-output), Quest with only a 5% KV budget already achieves ac- curacy (46.3%), comparable to the full-cache bascline (47.3%). This indicates that reducing or increasing the budget has only marginal influence these settings. In contrast, in LONGGEN- BENCH (long-output), using the same 5% budget leads to substantial performance degradation in Quest (e.g., 60.8% 17.6% on GSM8K). Notably, increasing the budget to 10%, 15%, and 20%, improves the accuracy to 32.3%, 50.9%, and 56.0%, respectively. This trend because either miss- ing or supplementing KV cache in long generation repeats over far more decoding steps, amplifying their influences (see Appendix for full discussion).
Motivated by this observation, RetroAAtennion aims to efficiently supplement the KV cache by ex- ploiting KV entries loaded by adjacent Queries in local window; specifically, KV entries that are loaded by the current Query but were not available to previous Queries, as illustrated in Figure a)). However, this idea introduces two critical questions: (1) Are the currently loaded KV entries actu- ally useful for improving the attention outputs of past Queries? and (2) How much informational benefit can we expect from leveraging such retrospective refinement?
Usefulness of Loaded KV Entries for Past Queries. Consecutive tokens often exhibit strong semantic correlations (Dai et al.) 2024: Wu et al. 2024), suggesting that KV entries retrieved for the current Query may also be informative for nearby past Queries. To evaluate this, we compute the rank of currently loaded KV entries in past Queries. As shown in Figure 2))), about 70-80% of current KV entries were previously within the top-k set (navy bar). while 20-30% were not selected at all. Notably, the second-largest coup-aaouu 15-20% are ranked within the next-k
3

---

Published as a conference paper at ICLR 2026
Original Alzention Output (0
Generated KV cáche token KV cache
Supplementary Attention Ourput (Oasp.c)
Retrospective Attention flow
Updated Altention Ourput (Oup,
Output cache
Nest
Oamp
push
Parp 5
Previousty unseen
Reuse
Ous
update
Qup.ty Ozep.
Oong
push
layer
Decoding Step
Reuse
Oep,ts
O Oesp.n nt
updato
update
Oep,
layer
Oung 5
O Dirph
Retrospective
(e w=3)
Oup,t
O Dag
update
pop
Next
update
Oup.ty
Ounp
push
Derguts
foed KV entries based on current Quary
Step 1:
Step search eentries unseon past Quaries iss and Rouse
Step 3: compute sparse
Step 4: upciate Output Cache for the nood decoding stop
attention output
Figure 3: Retrospective attention output update. Overview of RetroAttention across three de- coding steps, illustrating how previously unseen KV entries are retrospectively reused to refine past attention outputs via supplementary computation and output cache updates. This illustration sumes a retrospective window size of w=3.
range (orange bar), implying that they are still highly relevant yet were omitted in the past. This highlights the potential of currently loaded KV entries supplement semantically meaningful but ignored content in the original top-k selection (see Appendix for results on other datasets).
Informational Benefit of Retrospective Updates. Retrospective updates enable past Queries to access KV entries beyond their original top-k set. As decoding progresses, each past attention can be revised multiple times in subsequent decoding steps, leading to cumulative expansion of supple- mented KV entries. To quantify the total set of KV entries exposed a Query over time-ree referreferred to as the effective KV cache budget-wo count how many KV entries loaded by future Queries were previously unseen by a given Query (Figure c)). The effective budget is computed as the union of all KV entries seen by Query, excluding duplicates. Even with single future Query (n=1), where each attention updates only its immediate predecessor, the effective budget increases by 1.17x. As more future Queries supplement, the effective budget continues to grow, reaching up 1.60 at n=7. Notably, this benefit is achieved without increasing the actual KV cache budget.
Relationship to Cache Selection Reuse. Recent works (Yang et al. 2025 Wu et al. 2024) report that adjacent Queries tend to retrieve highly similar top-k pages, motivating the reuse of previously selected pages. We observe the same trend in our setting (Figure (())). However, in long- renggenneaation tasks, the impact of missing pages persists and accumulates over extended decoding. For exam- ple, integrating top-k selection reuse into Quest reduces mean accuracy from 52.6% to 25.2% on GSM8K and from 56.8% to 29.2% on CSQA LONGGENBENCH (Table Appendix B)) These results suggest that reuse alone does not adequately preserve performance in long-generation set- tings, motivating mechanisms that mitigate error accumulation.
2.3 RETROSPECTIVE ATTENTION OUTPUT UPDATE
Building on insights from our motivational study, we hypothesize that currently loaded KV entries effectively compensate for attention errors made in earlier steps. These errors stem from the lack of relevant Keys and Values in the attention output (O) computation. To correct this, our objective to revise the previously computed O vector in a retrospective manner. We introduce two key components to implement this idea: (1) supplementary attention output and (2) attention output cache. 3 an overview of the retrospective attention update process.
Supplementary Attention Output. As illustrated in Steps 2 and of Figure 3 RetroAttention computes attention outputs not only for the current decoding step but also retrospectively for pre-
4

---

Published as a conference paper at ICLR 2026
vious steps. For the current step, attention is computed using sparse attention methods e.g., Quest, yielding the output Oorg. (blue box). For past steps, RetroAttention computes attention between previous Queries and the currently loaded- previously unseen entries, producing Sup,. (yellow box). We refer to this additional attention output as the supplementary attention output. While omitted in the figure, we maintain mask that tracks the most recent decoding step in which each KV page was loaded, allowing us to identify previously unseen entries. Formally, the attention outputs are defined as follows:
Σ Σ JEB, IEPage;
E Ct mu
Σ
Oorg.
O
JES
5m iEPage
Σ Σ #E IEPage
Qakj lva
Σ 1E81) a Memer
eeck, Iva
8m
le IePage
where Qi is the t-th Query vector, St denotes the set of top-k page indices loaded by Q2, and Page; is the set of token indices in i-th page. O refers to supplementary output generated at the s++s-t decoding step (0 < s < w) for Qt. As described in Figure 3 the supplementation not limited to adjacent steps. It is rather applied across multiple past Queries within retrospective window w.
By combining Oorg.t and Ottp, for all 8, we can extend the attention computation for the past Query beyond its original KV cache budget. Accordingly, our goal is to update Oorg,t to (a:tmax(Q:k' /VVvV, computed over K, in Page, where U0seewS14s.
Inspired by the aggregation of partial attention results in FlashAttention (Dao et al. 2022). the softmax equation can be rewritten to a linear combination of the original and supplementary atten- tion outputs (see details in Appendix C which we refer to as Oup. t. This allows us to update earlier outputs using newly available KV entries, efficiently correcting their errors. Discussions on the pol- icy for unseen page detection appear in Appendix C.2 (Retrospective Mask paragraph), The merging of original and supplementary attention outputs detailed in Appendix C.2 and their schedule described in Appendix C.I (Algorithm[]) D.
Attention Output Cache. Retrospective updates require access to the previous attention outputs of past Queries, which are typically discarded after their decoding steps. Recomputing these outputs would necessitate reloading the top-k KV pages for each past Query, increasing the required KV cache budget in proportion to the retrospective window size, which is undesirable. To avoid this, we introduce an attention output cache, which stores multiple attention outputs (current and previous steps). This cache consumes marginal memory, with a size of (w-1. B, L, D)- corresponding to the restrospective window size w, batch size B, number of layers L, and hidden dimension D and is independent of the generation length, unlike KV cache.
The cache operates via three actions, as depicted Step 4 of Figure 3 (1) Push: attention output computed at each decoding step is stored in the cache. (2) Update: when supplementary attention outputs become available, the cached outputs, either the original Oorg or previously updated Oup- reused to compute revised outputs via weighted combination. This allows both initial updates (Oorg + Oup) and re-updates (Oup -> Oup). (3) Pop: when the number of cached entries exceeds the window size, the oldest entry is evicted.
2.4 RETROSPECTIVE KV CACHE UPDATE
The above components describe how attention is updated within single layer. However, they do not fully describe how refined past outputs propagate across layers and influence final generation. Here, we show how retrospective updates modify the KV cache in deeper layers.
Inffuences on Deeper Layers. As shown in Figure 4 the output cache from the layer / pro- vides multiple embeddings (e.g., Oup. t (1) and Oorg, ta (I)) to the layer I + 1. For the most recent step ts, the layer + has not yet been computed. Thus, the projection layers gener- ate Query Qt - 1). Key Ke, (L + 1), and Value Vi, + 1) for the first time. These Key and Value are newly appended to the KV cache (blue line). For previous steps f1-2, we re-embed Oup, (() to compute new Queries (1 1), Keys K,,,(L 1), and Values Vi (l + 1). These differ from the original KV entries generated using Oorg, (1=(() (i.e.. Kt,_( + 1) and VI, + 1)), which are now outdated. Hence, we overwrite the previous KV entries with up-
dated ones: (l + 1) 2 1) and Ve + 1) + Vo + 1) (green line).
5

---

Published as a conference paper at ICLR 2026
Once the updated Key- Value for t1 to overwritten in the KV cache, all subsequent decoding steps (t tz) automatically lever- age these changes during attention. No special logic is required for deeper layers; they read from the KV cache as usual. This process nat- urally leads progressive reduction in atten- tion errors across layers, as later queries attend higher-qualie representations of the past to- kens.
Output Cache from layer
Wi
R
Overwiite
Fl
previous 2v
Oxp
Dup
We
Write
Oarg
Wy
V,
new it,] KV
of layer (+1
loaded
KVentties
Wg
On
(K2, .
Figure 4: Retrospective KV cache update. Out- put cache from the previous layer provides mul- tiple embeddings (f1-3) to the current layer. The most recent output (4z) used to generate new KV entries, while earlier outputs (412) produce updated KV entries that overwrite previous ones in the current layer's 's KV cache. Feed-foree feedard and normalization layers are omitted.
2.5 OVERHEAD ANALYSIS
Conventional attention operations heavily rely
on GEMV (General Matrix-Vector Vector multiplica- tion) during decoding, leading to extremely low PE (Processing Element) utilization. We strate- gically design RetroAttention to exploit this idle parallelism for retrospectively updating past atten- tion outputs and KV entries, using currently loaded KV entries. As a result, the additional computa- tion in RetroAAttetion incurs only marginal overhead in memory and latency. To support this claim, we provide a per-layer overhead analysis.
Reteninttnnsion's Overhead in Attention Layers. We analyze RetroAttention's Arithmetic In- tensity (Al)-the ratio of FI T.PSs to bytes accessed from main memory-to show it operates a memory-bound regime. Its FLOPs scale with the retrospective window size w, number of loaded KV pages k Kgage Query heads hgg tokens per page P. and head dimension d, and is estimated as 4w Kpage hy Pd in FP16. This involves four types of memory access: (1) loading 2w hy bytes for Query vectors, (2) loading 4 kppae h4 P d bytes for KV cache pages, (3) accessing 4 hy Kpage bytes for a mask tracking KV page usage, and (4) writing 2w h d bytes for the output.
kipage lig Pd
Alattention hg + Kiuage hys d + by Kiuge
As w hi < kipage P and h4 < Pd, Equation 3 simplifies approximately to why Given that modern GPUs typically shift to compute-bound above AI values of 200-400 (Zhu al., 2025). RetroAttention remains memory-bowe mooudd for moderate window sizes (e.g., w< 100), making latency primarily memory-driven. That is, traffic. Baseline (e.g., Quest) sparse attention loads had for Queries and hipage hy P d for KV cache pages. The memory traffic ratio is:
quantify the latency overhead by comparing memory
Our Mem I/O ur hy kipage by. P Pd. + hy hag by d + kipags he P
(4)
Baseline Mem I/O
As KV loads (kipage hy Pd) dominate both numerator and denominator, our memory communication overhead is negligible (i.e., the ratio stays near for moderate w.). This indicates marginal latency overhead from RetroAttention.
RetroAAtenntion' Overhead in Linear Layers. Linear layers RetroAttention are accompanied by embeddings, processing input matrices of shape wh x D. where b is batch size and D is the feature dimension. The Al of RetroAttention's 's linear layers is as follows:
bDD Dont
ATiinaa w b( + Dout) Dio Dout
(5)
where Di and Dout are the input and output dimensions of linear layer. They remain memory- bound as long as wh below a few hundred, with overhead scaling with memory traffic rather than computation. Our method increases memory traffic (denominator in (5)) in the first term by times, but the second term Di,,DDot dominates, yiclding only minor latency overhead. See Appendix D for details.

---

Published as a conference paper at ICLR 2026
Table 1: Comparison with SOTA methods. Accuracy results on GSM8K, MMLU and CSQA in LONGGENBENCH with three (i.e., the number of questions in prompt) values are summa- rized. All methods use relative KV cache budget of 0.15, which dynamically changes the budget to context length x 0.15 as decoding continues, with the minimum budget of 256 tokens. We set the retrospective window size (w) to
n-question
GSMSK (1)
n-qqeesionn MMLU (1)
n-question CSQA (1)
Method Benchmark
15
30
45
Mean Acc.
15
30
45
Mean Acc.
15
30
45
Mean Acc.
Full Attention
66.7
60.8
58.0
61.8
62.5
58.7
57.1
59.4
73.5
74.1
71.9
73.2
StreamingLLLM
0.0
0.0
0.0
0.0
1.2
2.1
2.5
1.9
0.8
1.1
4.0
2.0
TOVA
0.2
0.3
0.2
0.2
9.7
8.7
9.4
9.3
6.7
6.3
11.1
8.1
Quest
58.2
50.9
48.6
52.6
58.8
54.9
50.6
54.8
70.9
53.5
46.1
56.8
RetroAttention (Ours)
61.3
52.6
55.4
56.5
59.3
55.4
51.2
55.3
68.8
59.1
53.0
60.3
Ours Quest
+3.1
+1.7
+6.8
+3.9
+0.5
+0.5
+0.6
+0.5
-2.1
+5.7
+6.9
+3.5
EXPERIMENTAL RESULTS
3.1 EXPERIMENTAL SETUP
Datasets and Implementation Details. Our main benchmark is LONGGENBENCH (Liu et al. 2024c) in which multiple reasoning tasks are sequentially concatenated into a single input prompt (details in Appendix F). Such prompt scheme is applied to CSQA (Talmor al. 2019). MMLU (Hendrycks et al. 2021), and GSM8K (Cobbe et al.] 2021) datasets, and a parameter n determines the number of questions in a prompt. We follow the prompt construction and greedy decoding scheme according to the official repository
benchmarks such as AIME 2024, GPQA- DIAMOND (Rein al., 2024). and LIVECODEBENCH (Jain al. 2024) are included. We also include PG-19 19 (Rae et al. 2019) benchmark to estimate long-sequence language modeling performance using perplexity. Experiments are mostly performed with LLAMA-3.1-88 INSTRUCT but with DEEPSEEK-RP ---IIITILLLLLAAAAAAA implementation adopts Quest's page selector [Tang et al.. 2024) and built on FlashInfer (Ye al.)
Geasoning-intensio
for the reasoning-intensinn tasks. Our 2025). highly optimized implementation of attention.
Baselines. We compare three recent KV-cache compression methods Striindd--SSeeanngLLLLL. (Xiao et al.) 2023). TOVA (Wu et al., 2024), and Quest (Tang et al.] 2024)-each each employing dis- linct token-selection strategy. StreamingLLM and TOVA are both eviction-based techniques. StreamingLLMM relies on a static cache window whereas TOVA adaptively retains KV entries based on heuristic token significance estimation. We include these methods as they have not been rig- orously evaluated under -enggeenratiin scenarios. Our primary baseline is Quest, SOTA non- eviction method that selects a subset of tokens through Query-aware, paged sparse attention.
3.2 COMPARISON WITH SOTA METHODS
We compare the proposed method with the baselines in long-generation GSM8K, MMLU, and CSQA datasets, provided in LONGGENBENCH Table summarizes accuracy results on the three datasets as the number of questions concatenated in prompt (n) increases. Overall input and output tokens range between about 1.3k-5.78 7k and 0. 0.6k-4.2k, respectively. A higher n indicates longer input and output lengths. See data statistics in Appendix [F]
Accuracy Analysis for Eviction-basee Baselines. StreamingLLMM and TOVA fail across all three datasets, even when is small. This suggests that their failure stems from an inherent limitation of the methods in sequential question-answe -nnweer scenarios, rather than a challenge specific to long generation. Both approaches permanently evict KV cache entries, meaning that tokens relevant to later questions may be discarded during earlier decoding steps and can never be recovered. Thus, the model is unable to attend to upcoming content when needed, revealing critical weakness of eviction-based strategies.
Accuracy Analysis for Non-eviction Baseline. While exhibiting higher accuracy. Quest also ex- periences noticeable accuracy drop at high (see Table [ In particular, the performance gap between full cache and Quest becomes larger as grows (e.g., -2.6%p, -20.6%p. and -25.8%p in
https://gi http://gtttttttcco http://////.aaaacooo///////////a

---

Published as a conference paper at ICLR 2026
Table 2: Comparison in larger models. Accuracy results in OWEN2.5-32B-INSTIN and
QWEN2.5- 14B-INSTRUCT models. Experiment settings are identical with Table !
n-question GSM8K (1)
n-question MMLU (t)
n-question CSQA (f)
Method / Benchmark
30
4$
Mean Acc.
15
30
Mean Acc.
30
45
Mean Acc.
QWEN2.5-327 INSTRUCT
Full Attention
92.1
91.7
90.8
91.5
81.8
81.0
81.2
81.3
86.1
87.0
87.1
86.7
Quest
89.2
83.3
83.8
$1.0
79.4
82.3
69.3
74.4
75.4
RetroAttentton (Ours)
89.8
89.1
84.4
87.8
80.9
80.3
79.9
85.3
75.0
78.7
79.7
QWEN2.5-18
A-B-INSTUCCT
Full Attention
88.7
84.4
76.6
83.2
78.2
76.6
73.6
76.1
83.7
83.5
83.5
83.6
Quest
79.0
76.5
64.1
73.2
76.0
73.0
71.1
73.3
69.4
46.8
58.1
58.1
Retro-Ateention (Ours)
83.1
80.7
69.1
77.6
75.8
73.7
71.0
73.5
73.3
59.5
63.6
65.5
80
Full cache
80
6-0,55
Tull cache
65
75
8m0.10
full cacho
70
55
Accuarry (99)
Accuratt
68
Retrospective
Accuntt
60
Accunaty
50
windoww (w/++,
80
CSQA
85
MMLU
40
GSMBK
40
1
Ques:
Quest
Quest
30
30
35
CSQA
MMLU
G8M8K
42
52
62
72
02
92
80
100
120
140
160
180
60
78
96
114
132
150
Benchmark
Compressed memary [MBitatch)
memory
Compressed memory (MB/batch)
(MB/hatch)
(A)
[0]
Figure 5: Ablation studies. (a) Comparison between full cache (no compression), Quest, and ours in LONGGENBENCH with three retrospective window sizes. We set the relative budget to 0.15.
(b)-(d) present the trade-off between the attention memory traffic and accuracy with three relative budget (b) values CSQA, MMI.U, and GSM8K, respectively. We set n to 30.
CSQA), implying the cumulative errors caused by approximated attention. In contrast, our approach robust to such performance degradation, consistently outperforming Quest in nearly all configu- rations. The performance gain of RetroAttention over Quest is particularly large with higher (e.g., 6.8%p in GSM8K, 6.9%p in CSQA), highlighting the effectiveness of our retrospective updates. Comparison with other non-eviction baselines is also discussed in Appendix [F3
Accuracy Improvements in Larger Models. RetroAttention also delivers consistent gains in larger models (>8B). Table 2 reports results on LONGGEN using QWEN2.5-32B- INSTRUCT and QWEN2.5 1-----1--IISUCCCT For the 14B model, RetroAttention achieves an average improvement Quest of +7.4% CSQA, +4.4% GSM8K, and +0.2% MMLU. For the 32B model, the corresponding gains are +4.3% (CSQA), +4.0% (GSM8K), and +0.4% (MMLU). This trend mirrors the results in Table 1 further demonstrating the generality and scalability of Retroonttntion in larger models.
We also compare method against Quest with larger retrospective window sizes (w.) Figure a)a shows accuracy results of full cache, Quest, and RetroAttention under the three window sizes (w E {2, 4, 8)). ). As w increases, RetroAttention approaches the performance of the full cache base- line more closely across all benchmarks.
3.3 COMPUTATIONAL EFFICIENY
Memory Analysis. Increasing the KV budget is straightforward way to improve the accuracy at the cost of additional memory traffic. Our method redesigns such trade-off through retrospective updates. Figures bd) show comprehensive comparisons between Quest and ours with three relative KV cache budgets (b). The relative budget adaptively changes the amount of KV entries to be loaded by context length x b. As shown in the figure, RetroAttention yields significant accuracy gains over Quest at given budget with negligible memory traffic overhead of 3.0% in CSQA, 1.6% MMLU, and 2.0% GSM8K on average.
End-to-Enn Latency. Figure ([(a) presents the average end-to-end latency per decoding step for the full-cache baseline, Quest, and ours (setup details in Appendix F Atteotintention consistently
8

---

Published as a conference paper at ICLR 2026
QKY = sQore(
topsk
Oura
mask
Oup and Oup = ourput project = KVupdate
250
Contert Bingh-r-
Contest longhh+64k
Contest langh
Latenoyyee per decode (11es
200
Ours
cache
198.1
Full
Full
Full
Quest
Quest
Quest
150
110.2
Ours
W
Ours
Wm2
Ours
100
Retrospectiie
window [W))2, 4,8
Ours
Wid
Durs
wH8
Ouns
WF8
Ouns
15k
32k
64k
266k
0.06 0.12 0.18 0.24 0.30
0.2
0.4
0.6
0.0
1.0
0.5 1.0
1.5
2.0 2.5 3.0
length
Latency per operation (ms]
Latency per kernet operation (mms
Latency per kernel openstion (ms)
(9)
(b)
[6)
(0]
Figure 6: Latency analysis. (a) Comparison of end-to-end latency per decoding between full cache (no compression), Quest, and ours with three retrospective window sizes. (b)-(d) Comparison of kernel-level latency breakdown between full cache (denoted as Full), Quest, and ours with three context lengths. Latency results estimated and then averaged in the 1024 decoding steps followed by prefill with context length. We set the relative budget (b) to 0.15.
11.5
1.0
Table 3: Comparison in reasoning-intensive tasks. Accuracy results AIME 2024, GPQA-DIAMOND and LIVECODEBENCH-VV datasets summarized with four retrospective window sizes. We set b and w to 0.15 and 2.
11.0
Retative Perpieater (4)
U)
10.5
0.94
10.0
0.90
9.5
Quest
0.80
Ouri
Retrospectvve (w]= 8,8,15
Full cacho
0.68
0.5
1k 2k 3k Ak Sk 6k 7K 8k
1k 2k 3k 4k Sk 6k 7k 0k
AIME24
GPQA-D
LCBv5
Generation
Generation
Method Benchmark
Pass@1 (1)
Pass@1 (f)
Pass@1 (f)
(b)
Full Attention
47.1
38.9
37.6
Figure 7: Comparison in language modeling. The average Perplexity results of the full-cache, Quest, and ours PG-19 19 are compared. First 8k tokens are prefilled with full KV, followed by 8k sparse decoding. Relative Perplexity denotes ratio between Quest's and ours. We set b to 0.15.
StrcamingLLMM TOVA
0.4
19.7
1.5
0.4
0.0
7.0
Quest
33.8
33.6
32.7
RetroAttention (Ours)
39,2
33.6
34.1
A Ours Quest
+5.4
0.0
+1.4
outperforms the full-cache baseline and remains at similar latency with Quest across all context lengths. The additional latency of RetroAttention over Quest is minimal. less than Ims per token for w=2 and around 2ms for w=8.. Importantly, this overhead remains effectively constant regardless of context length retrieved cache size, aligned with our theoretical analysis in Section 2.5 which attributes the overhead primarily to additional memory I/O.
Kernel-level Attention Latency. Figures (d) show the average kernel-level latency involved in the attention operation. The latency for scoring each KV page (score(Q)) and top-k selection remain unchanged from Quest to RetroAAttention, as they operate only the most recent Query. Ad- ditional operations introduced by Retro-Attentionn-see -uchi as projecting historical Queries and Keys, overwriting the KV cache, managing masks, and merging attention outputs- incur overhead. How- ever, these costs are small and largely constant across context lengths, making their relative impact increasingly negligible as the context grows.
3.4 COMPARISON IN OTHER TASKS
Reasoning Tasks. Table 3 presents accuracy results on AIME 2024, GPQA-DIAMOND, and LIVECODEBENCHH-S.. Similarly LONGGENBENCH, the eviction-based methods suffer large degradation compared with full attention; for example, TOVA often fails to follow instructed format during decoding in GPQA-DIS GPQA-DIAMOND. RetroAttention exhibits similar accuracy in GPQA-D yet significant gains over Quest are observed in the others.
Long-context Input. While our method is not designed for long-context inputs, we also evaluate Retrotttention LONGBENCH (Bai et al.) 2023), benchmark for long-context inputs (see Ap- pendix G). The evaluated categories include Single-doc and Multi-doc QA, Summarization, Code, and Few-shot tasks. RetroAttention achieves comparable performance to Quest, likely because the examples in LONGBENCE are mostly short- chort-generation (<100 tokens), where the benefits of retro- spective updates are less pronounced.

---

Published as a conference paper at ICLR 2026
Language Modeling, Figure compares Perplexity PG-19 measured at 1k-token intervals during decoding. Our method consistently achieves lower Perplexity across all intervals than Quest (Figure (b)), with particularly strong improvements in later stages of generation. This verifies that the retrospective updates reliably enhance output logits across different window sizes (w) We note that the gains saturate beyond w==,, implying an upper bound in improvements from RetroAttention.
Performance Gain Saturation. A larger retrospective window increases the effective KV bud- get. Hence, the observed performance saturation in RetroAttention can be understood by asking why increasing the effective budget does not yield continuous accuracy improvements. As shown in Appendix 3. most of the informative KV elements (those with high attention weights) are in- cluded first. As the window size increases, the additional KV elements become progressively less important. Their marginal contribution to accuracy becomes smaller, which explains why the gains diminish and eventually saturate beyond w=8.. Importantly, this behavior is not specific to RetroAt- tention. Even when increasing the actual KV cache size, accuracy improvements also plateau once the model has already incorporated the dominant, high-importance tokens (see Figures ((anress(c)))0 (d))
4 RELATED WORKS
Eviction-based KV Cache Compression. Several KV cache eviction strategies have been proposed to reduce memory usage and accelerate attention computation. Methods such as StreamingL.LM (Xiao al., 2023) retain only the earliest and most recent tokens, while Fast- Gen (Ge et al. 2023) and SnapK Li et al., (024) evicts low-importance tokens after the prefill stage assuming stable attention patterns. Dynamic approaches such as H2O (Zhang et al. (023), KeyFormer (Adnan et al. 2024), and TOVA (Oren et al.) 2024) adaptively determine which tokens to retain based on historical attention statistics. However, all these methods permanently discard se- lected KV entries, overlooking possible later relevance of evicted or missed dependencies.
cumulative errors
Non-eviction KV Cache Compression. Non-eviction methods preserve the full KV cache but reduce computation by sparsely loading only relevant tokens per decoding step, allowing revisitation of previously irrelevant entries. Pioneering works, Quest (Tang et al.) 2024) and Vale (Chen) eet al. 2024a) identify top-k relevant pages of KV cache (Kwon al. (2023) via similarity between Queries and page-level summaries. InfLLM (Xiao et al.) 2024). SqueezedAttention (Hooper et al.] 2024), and ClusterKV (Liu et al.] 2024b) use representative
centroid Key vectors to generate
these summaries. Other methods such as RetrievalAAtennion (Liu et al. 2024a) and TokenSelect (Wul al. 2024) dynamically select relevant cache subsets token granularity. While effective for long- context inputs, these approaches still overlook cumulative attention errors during generation.
KV Cache Compression for Long Generation. Few studies address KV cache compression for long generation. (Song et al. (2025) exploit the semantic sparsity of reasoning traces by periodically evicting low- (ow-importance entries, but may inherit limitations common to eviction- based methods, especially under evolving attention patterns. Concurrent with our work, [Sun et al.) (2025) raise similar concern about the cumulative errors caused by sparse attention and propose periodically refreshing previous attention outputs using dense attention (i.e,, full KV cache). However, this incurs significant computational overhead due to repeated dense attention, in contrast to our contri- outions-reduche the errors without additional KV cache budget.
CONCLUSION
We introduce RetroAttention, a lightweight yet effective KV cache compression technique, to mit- igate cumulative attention errors in long-context generation. Our approach fundamentally differs from conventional sparse attention. Previous methods treat attention output as fixed: Once com- puted, the loaded KV entries are discarded and the errors persist throughout the model. RetroAt- tention instead reuses those KV entries to retrospectively revise past outputs and overwrite stale KV states, enabling consistent correction of cumulative attention without increasing KV cache budget. This design yields consistent accuracy improvements in long-context generation, while maintaining negligible memory and latency overhead.
10

---

Published as a conference paper at ICLR 2026
ETHICS STATEMENT
Our work seeks to improve the efficiency and accuracy of long-context inference in large language models by proposing a new KV cache update mechanism. While language models inherently raise concerns around potential misuse, bias, and fairness, contributions are confined to algorithmic and efficiency-foeuuee improvements. We do not anticipate introducing risks beyond those already inherent in the underlying models.
Large Language Models (LLMs) were not involved in formulating research ideas, designing meth- ods, conducting analysis. Their use was strietly limited polishing the manuscript, such as improving clarity, grammar, and style of sentences originally written by the authors. No scientific content, arguments, or experimental descriptions were generated by LLMs, and their role was con- fined to editorial assistance only.
REPRODUCIBILITY STATEMENT
This paper introduces novel method that retrospectively revises past attention outputs with new KV entries, enabling long-context models to correct accumulated approximation errors efficiently. To facilitate reproducibility, we provide the complete source code as a downloadable repository along with documentation detailing evaluation procedures. All benchmark datasets used in our periments are publicly available, and we provide the scripts employed during evaluation to ensure consistency with our reported results. We provide further clarification and an extended analysis of our theoretical claims in the appendix. In particular, we elaborate on the underlying assumptions, present additional derivations that were omitted from the main text for brevity, and supplement our arguments with supporting empirical evidence where appropriate. These resources allow indepen- dent researchers to reliably replicate and validate our findings.
REFERENCES
Muhammad Adnan, Akhil Arunkumar, Gaurav Jain, Prashant Nair, Ilya Soloveychik, and Pu- rushotham Kamath. Keyformer: Kv cache reduction through key tokens selection for efficient generative inference. Proceedings of Machine Learning and Systems, 6:1 14-127, 2024.
Yushi Bai, Xin Lv, Jiajie Zhang, Hongehang Lyu, Jiankai Tang, Zhidian Huang, Zhengxiao Du, Xiao Liu, Aohan Zeng, Lei Hou, et al. Longbench: A bilingual, multitask benchmark for long context understanding. arXiv preprint arXiv:2308. 14508, 2023.
Zefan Cai, Yichi Zhang. Bofei Gao, Yuliang Liu, Yucheng Li, Tianyu Liu, Keming Lu, Wayne Xiong, Yue Dong, Junjie Hu, et al. Pyramidkv: Dynamic kv cache compression based on pyra- midal information funneling. arXiv preprint arXiv:2406.02069 2024.
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde De Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, al. Evaluating large language models trained on code. arXiv preprint arXiv:2107.03374 2021.
Renze Chen, Zhuofeng Wang, Beiquan Cao, Tong Wu, Size Zheng, Xiuhong Li, Xuechao Wei, Shengen Yan, Meng Li, and Yun Liang. Arkvale: Efficient generative Ilm inference with recallable key-value eviction. Advances in Neural Information Processing Systems, 37:113134-113155, 2024a.
Zhuoming Chen, Ranajoy Sadhukhan, Zihao Ye, Yang Zhou, Jianyu Zhang, Niklas Nolte, Yuandong Tian, Matthijs Douze, Leon Bottou, Zhihao Jia, et al. Magicpig: Lsh sampling for efficient 11m generation. arXiv preprint arXiv:2410.16179 2024b.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jemy Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14166 14168, 2021.
11

---

Published as a conference paper at ICLR 2026
Gheorghe Comanici, Eric Bieber, Mike Schackermann, Ice Pasupat, Noveen Sachdeva, Inderjit Dhillon, Marcel Blistein, Ori Ram, Dan Zhang, Evan Rosen, et al. Gemini 2.5: Pushing the frontier with advanced reasoning, multimodality, long context, and next generation agentic capa- bilities. arXiv preprint arXiv:2507.0626/ 2025.
Jincheng Dai, Zhuowei Huang, Haiyun Jiang, Chen Chen, Deng Cai, Wei Bi, and Shuming Shi. Corm: Cache optimization with recent message for large language model inference. arXiv preprint arXiv:2404. 1ate:24444.99994 /5949, 2024.
Tri Dao, Dan Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. Flashattention: Fast and memory- efficient exact attention with io-awareness. Advances neural information processing systems, 35: 133444166339, 2022.
Yao Fu. Challenges in deploying long-context transformers: A theoretical peak performance analy- sis. arXiv preprint 2Xiv:2405.089444 2024.
Suyu Ge. Yunan Zhang, Liyuan Liu, Minjia Zhang, Jiawei Han, and Jianfeng Gao. Model tells you what to discard: Adaptive kv cache compression for llms. arXiv preprint arXiv:2310.01801, 2023.
Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song. Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, et al. Deepseek-rl: Incentivizing reasoning capability in llms via reinforcement learning. arXiv preprint arXiv:2501. 12948, 2025.
Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt. Measuring massive multitask language understanding. Proceedings of the Interna- fional Conference on Learning Representations (ICLR), 2021.
Coleman Hooper, Schoon Kim, Hiva Mohammadzadeh, Monishwaran Maheswaran, June Paik, Michael W Mahoney, Kurt Keutzer, and Amir Gholami. Squeezed attention: Accelerating long context length IIm inference. arXiv preprint arXiv:2411.09688 2024.
Aaron Jaech, Adam Kalai, Adam Lerer, Adam Richardson, Ahmed El-Kishky, Aiden Low, Alec Helyar, Aleksander Madry, Alex Beutel, Alex Carney, et al. Openai ol system card. arXiv preprint ar arXiv:2412.1677 2024.
Naman Jain, King Han, Alex Gu, Wen-Ding Li, Fanjia Yan, Tianjun Zhang, Sida Wang, Armando Solar-Lezama, Koushik Sen, and Ion Stoica. Livecodebench: Holistic and contamination free evaluation of large language models for code. arXiv preprint MxXi:2443.00997. 2024.
Juyong Jiang, Fan Wang. Jiasi Shen, Sungju Kim, and Sunghun Kim. A survey large language models for code generation. arXiv preprint 200v02200600055, 2024.
Woosuk Kwon, Zhuohan Li, Siyuan Zhuang. Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica. Efficient memory management for large language model serving with pagedattention. In Proceedings of the 29th symposium operating systems princi- ples, pp. 61 1-666, 2023.
Yuhong Li, Yingbing Huang, Bowen Yang, Bharat Venkitesh, Acyr Locatelli, Hanchen Ye, Tianle Cai, Patrick Lewis, and Deming Chen. Snapkv: Llm knows what you are looking for before generation. Advances in Neural Information Processing Systems, 37:22947-229700 2024.
Di Liu, Meng Chen, Baotong Lu, Huiqiang Jiang, Zhenhua Han, Qianxi Zhang, Qi Chen, Chen- gruidong Zhang, Bailu Ding, Kai Zhang, al. Retrievalattention: Accelerating long-context 11m inference via vector retrieval. arXiv preprint arXiv:2409, 10516, 16, 2024a.
Guangda Liu, Chengwei Li, Jieru Zhao, Chenqi Zhang, and Minyi Guo. Clusterkv: Manipulating Ilm kv cache in semantic space for recallable compression. arXiv preprint arXiv:2412.03213, 2024b.
Xiang Liu, Peijie Dong, Xuming Hu, and Xiaowen Chu. Longgenbench: Long-context generation benchmark. arXiv preprint arXiv:2410.04/99 2024c.
12

---

Published as a conference paper at ICLR 2026
Zichang Liu, Aditya Desai, Fangshuo Liao, Weitao Wang, Victor Xie, Zhaozhuo Xu, Anastasios Kyrillidis, and Anshumali Shrivastava. Scissorhands: Exploiting the persistence of importance hypothesis for 11m kv cache compression at test time. Advances in Neural Information Processing Systems, 36:52342-52364, 2023.
Matanel Oren, Michael Hassid, Nir Yarden, Yossi Adi, and Roy Schwartz. Transformers multi- state mas. arXiv preprint arXiv:2401.06104 2024.
Jack W Rae, Anna Potapenko, Siddhant M Jayakumar, Chloe Hillier, and Timothy P Lillicrap. Compressive transformers for long-range sequence modelling. arXiv preprint, 2019. URL
https:://arxiw.or////a 00110000000011100000
David Rein, Betty Li Hou, Asa Cooper Stickland, Jackson Petty, Richard Yuanzhe Pang, Julien Di- rani, Julian Michael, and Samuel R Bowman. Gpqa: A graduate-level google-pros q&a bench- mark. In First Conference on Language Modeling, 2024.
Luka Ribar, Ivan Chelombiev, Luke Hudlass- Gallee,, Charlie Blake, Carlo Luschi, and Douglas Orr. Sparq attention: Bandwidth-efficien IIm inference. arXiv preprint arXiv:2312.04988, 2023.
Prajwal Singhania, Siddharth Singh. Shwai He, Soheil Feizi, and Abhinav Bhatele. Loki: Low- rank keys for efficient sparse attention. Advances in Neural Information Processing Systems, 37: 16692-16723, 2024.
Jiwon Song, Dongwon Jo, Yulhwa Kim, and Jae-Joon Kim. Reasoning path compression: Com- pressing generation trajectories for efficient Ilm reasoning. arXiv preprint arXiv:2505.1386. 2025.
Yutao Sun, Tianzhu Ye, Li Dong, Yuqing Xia, Jian Chen, Yizhao Gao, Shijie Cao, Jianyong Wang, and Furu Wei. Rectified sparse attention. arXiv preprint arXiv:2506.04108, 2025.
Alon Talmor, Jonathan Herzig, Nicholas Lourie, and Jonathan Berant. CommonsenseQA: A ques- tion answering challenge targeting commonsense knowledge. In Proceedings of the 2019 Con- ference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies. Volume (Long and Short Papers), pp. 4149-4158, Minneapolis, Min- nesota, June 2019. Association for Computational Linguistics. doi: 10. 10.18653/v1/N191111 URL
org/N19 1421
Jiaming Tang, Yilong Zhao, Kan Zhu, Guangxuan Xiao, Baris Kasikci, and Song Han. Quest: Query-aware sparsity for efficient long-context Ilm inference. arXiv preprint arXiv:2406. 10774, 2024.
Wei Wu, Zhuoshi Pan, Chao Wang, Liyi Chen, Yunchu Bai, Tianfu Wang, Kun Fu, Zheng Wang, and Hui Xiong. Tokenselect: Efficient long-context inference and length extrapolation for 1lms via dynamic token-level kv cache selection. arXiv preprint arXiv:241 2..0286, 2024.
Chaojun Xiao, Pengle Zhang, Xu Han, Guangxuan Xiao, Yankai Lin, Zhengyan Zhang, Zhiyuan Liu, and Maosong Sun. Infllm: Training-free long-context extrapolation for llms with an efficient context memory. arXiv preprint arXiv:2402.04617, 2024.
Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. Efficient streaming language models with attention sinks. arXiv, 2023.
Shang Yang. Junxian Guo. Haotian Tang, Qinghao Hu, Guangxuan Xiao, Jiaming Tang, Yujun Lin, Zhijian Liu, Yao Lu, and Song Han. Lserve: Efficient long-sequence Ilm serving with unified sparse attention. arXiv preprint arXiv:2502. 258. 2025.
Shuo Yang, Ying Sheng, Joseph E Gonzalez, lon Stoica, and Lianmin Zheng. Post-training sparse attention with double sparsity. arXiv preprint w.Xiv:2408.07099 2024.
Zihao Ye, Lequn Chen, Ruihang Lai, Wuwei Lin, Yineng Zhang, Stephanie Wang. Tianqi Chen, Baris Kasikci, Vinod Grover, Arvind Krishnamurthy, et al. Flashinfer: Efficient and customizable attention engine for um inference serving. arXiv preprint vrXiv:2501.00000 2025.
13

---

Published as a conference paper at ICLR 2026
Zihao Yi, Jiarui Ouyang, Yuwen Liu, Tianhao Liao, Zhe Xu, and Ying Shen. A survey recent advances in lim-based multi-tum dialogue systems. arXiv preprint 1xXi::2402.180133, 2024.
Zhihang Yuan, Yuzhang Shang, Yang Zhou, Zhen Dong, Zhe Zhou, Chenhao Xue, Bingzhe Wu, Zhikai Li, Qingyi Gu, Yong Jae Lee, et al. Llm inference unveiled: Survey and roofline model 2024.
insights, arXiv preprint urXiv:2402.16333
Ted Zadouri, Hubert Strauss, and Tri Dao. Hardware-efficien attention for fast decoding. arXiv preprint arXiv:2505.2 00..00..21477. 2025.
Zhenyu Zhang, Ying Sheng. Tianyi Zhou, Tianlong Chen, Lianmin Zheng, Ruisi Cai, Zhao Song, Yuandong Tian, Christopher Ré, Clark Barrett, al. H2o: Heavy-hitter oracle for efficient gen- erative inference of large language models. Advances in Neural Information Processing Systems, 36:34661-3477 347710 2023.
Kan Zhu, Yufei Gao, Yilong Zhao, Liangyu Zhao, Gefei Zuo, Yile Gu, Dedong Xie, Zihao Ye, Keisuke Kamahori, Chien- Yu Lin, et al. [NanoFlow): Towards optimal large language model serving throughput. In 19th USENIX Symposium on Operating Systems Design and Implementa- tion (OSDI 25), pp. 749-765, 2025.
14

---

Published as a conference paper at ICLR 2026
A OVERVIEW
This appendix provides supplementary material for our manuscript, "Retrospective Sparse Attention for Efficient Long-Conters Generation." includes additional implementation details and theoreti- cal analysis that complement Section and provides detailed descriptions of the motivation and ex- perimental settings. Section discusses the motivation behind our method in detail with additional experimental evidence. Section describes additional implementation details of the main At- C
tention algorithm, including attention output updates and the retrospective mask logic. In Section [ extending the discussion in Section 2.5 of the main paper, we claborate the overhead analysis for linear layers, showing that the additional latency remains negligible due to their memory-bound nature. Section E quantifies RetroAttention's memory footprint in addition the memory traffic discussion in Section 2.5 Section F outlines dataset statistics, prompt formats, and experimental configurations for our latency and accuracy evaluations. Lastly, Section G shows evaluation results on long-contex: input benchmarks.
B MOTIVATIONAL STUDY
In the motivational study (main paper), we discuss the difference between long-context input and output tasks with respect to their dependency on the KV budget. This motivates us to consistently supplement missing KV cache, efficiently within small local window, as they will benefit across longer decoding steps and effectively mitigates the error accumulation. However, the differences of top-k pages in adjacent Queries are often considered negligible (Yang et al. 2025), little degradation when reusing top-k pages from previous Queries in certain tasks. We further strengthen our argument through the following experimental evidence: (1) 20% of top-k pages are not shared in adjacent Queries (in multiple datasets), and (2) such amount can make significant influences in genegeenrttioon tasks. These results highlight that though the amount of missed or supplemented KV cache is seemingly small, their influences can be large in long generation.
showing
How many top-k pages are shared in adjacent Queries? We demonstrate that adjacent Queries share 82.8% (interval: 1) 73.8% (interval: 8) top-k pages in Figure b)... In Figure 8 (c)( we examine the token distribution across the three datasets, including GSMSK, CSQA, and MMLU. More than a quarter of top-k pages do not overlap in the 8-step interval in common, which we do not consider little. particularly given that we can leverage them without increasing the actual KV budget. In addition, retrospective supplementation is influenced by all the past queries in the window (not like a single query influences only one), reaching minimum 17.2% (w=2; GSM8K) to maximum 69.8 69.8% (w=8; MMLU) increases in the effective KV budget. We confirm such trends hold across multiple datasets, including GSM8K, CSQA, and MMLU,
Are the non-overlapping 20% of top-k pages important? Methods based on reusing previously selected top-k pages across multiple decoding steps have shown strong empirical performance, par- ticularly in long-input benchmarks (e.g., LONGBENCH, NIAH). Such approaches implicitly assume that the overlalllg portion (approximately 20% of top-k pages) has limited impact on down- stream decoding. To examine this in oong-genrration settings, we integrate a reuse-based cache selection strategy into Quest and evaluate it on LONGGENBENCH. We observe substantial accuracy degradation even with reuse interval of 2 decoding steps: mean accuracy decreases from 52.6% to 25.2% on GSM8K, from 54.8% to 34.7% on MMLU, and from 56.8% to 29.2% on CSQA (Top-k Reuse (f= in 4). These results indicate that the non-overlapping portion of top-k pages can influence decoding trajectories in oong-generation tasks.
C IMPLEMENTATION DETAILS
C.I RETROATTENTION ALGORITHM FLOW
Algorithm presents the detailed logic of RetroAttention. Lines 2 and shows the additional operations introduced by RetroAttennton: updating previous KV caches, updating the attended mask cache and building masks for the attention kernel, merging cached and current partial outputs, and caching current outputs. The attention operation (Line () processes w Queries instead of a single
15

---

Published as a conference paper at ICLR 2026
top-k (now) top-k (pest)
top-k (now) (opppp....... 34) (pest]
top- (now) (k, (past]
top & (new) beyond top. Ske (past)
100%
100%
100%
82.8
79.6
76.9
74.8
68.0
Overlap of top-k takemss
00.2
71:1
80%
60%
80%
20%
16.9
17.4
20%
18.3
16.4
19.0
20%
16.2
17.8
18.2
11:-1
21-22
1944
11:48
20--1
10-22
11-4
11-88
31-1
11:22
1144
10
1/5t8p past
11:
1-stop past
p1-toop
200%
200N
160%
170N
Effective cachre bustpet
189%
190%
13395
180%
142%
150%
142%
117%
11896
220%
100%
100%
100%
Effective
Original budggt
Effective
Original budigtt
Oriiinal
burgger
0%
0%
0%
W=1 mn2
W- (W]
H=1
w=2 wnd
W-0
w-1
1
Retrospoctive window size
Retraspactive sizeowsize (v) (6]
Retrospecitue window (W)
16)
Figure 8: Token distribution analysis in long generation. (a)-(c) present the overlap of the current top-k KV entries the t-step prior decoding, categorized into different top-k intervals, GSM8K, CSQA, and MMLU datasets, respectively. (d)-(f) are the effective KV budget depending on the retrospective window sizes, in GSM8K, CSQA, and MMLU datasets, respectively.
Table 4: Comparison against top-k selection reuse. The reuse-based strategy reuses previously loaded top-k pages and integrated into Quest. Here, f=2 indicates that top-k pages are refreshed every two decoding steps. We set the relative budget to 0.15.
n-question GSM8K (f)
n--qeestion MMLU (f)
rz-qeesionn CSQA (1)
Method Benchmark
30
Mcan Acc.
15
45
Mcan Acc.
30
Mean Acc.
Full Attention
66.7
60.8
58.0
61.8
62.5
58.7
57.1
59.4
73.5
74.1
71.9
73.2
Quest
58.2
50.9
48.6
$2.6
58.8
54.9
50.6
54.8
70.9
53.5
46.1
56.8
Top-k Reuse (f=2)
22.4
22.3 31.0
25.2
39.6
32.5
32.0
34.7
40.7
25.1
21.9
29.2
RetroAttention (w=2)
61.3
52.6
55.4
56.5
59.3
55.4
51.2
55.3
68.8
59.1
53.0
63.0
Query. As our method not constrained by specific top-k page selection method (e.g., Quest), we can integrate RetroAAtention into any non-eviction dynamic sparse attention methods. To effi- ciently support these additional operations, we implement custom CUDA kernels-fie for page masking (Line 2) and incremental updates (Line 7))and and modify the main attention kernel to handle custom attention masking. We also extend the KV cache append kernel to support updates. Our modified attention kernel builds FlashInfer Ye et al. 2025), high-performance attention computation framework.
C.2 UPDATED ATTENTION OUTPUT
the updated attention output Oup. is computed by weighted linear combination of the original and supplementary attention outputs. Let us rewrite Oorg, and Osup. in Equation 2 with explicit superseripts to clarify which decoding step each tensor comes from as follows:
As diseussed in Section 2
Σ Σ JES, LEPage
Q.KT IV5Vt
Oorg,
(6)
Σ Σ
QKKT IVa
VES. lE lePage
16

---

Published as a conference paper at ICLR 2026
Algorithm 1: RETROATTENTION
Input: page selector PAGESELECT; queries Qui keys Kgt, values VeG K/V cache C;; cached output Ó cached attention-Ise Zi:-1;; window size w Output: outputs Oz:; updated cache C
i f
// Window start index
(odateKV(K..--a Via-1,
AppendKV(Kr Vi, C);
S₁ t PAGESELECT(QU. C);
M + UpdateAnddBulddMassSS.. C);
(Oz:; Z4:1) &- Attention Qia, St, C);
(Ost-1, Z=:1-) +- MergeOutput(Oss-- Zua-1, O Zia-1); CacheOutput(( max(i,t- 2+ mmxx(i,) -aannnttttttt)))) 2):)t C);
return Ozt, C'
Σ
Σ
cl Kt+sT /Vaptts
O' JESe4a Nutter 1ta-1 Sm. lEPage,
Σ E
Q QilxklloT//
iE8 (U Su Paga
where the superscripts and + indicate the decoding step in which the tensor (QKVO)
was
computed and the subscript indicates its corresponding token index. As discussed in Section 2.4 retrospective updates to the hidden states of previous tokens propagate to subsequent layers, where the corresponding QKV vectors are also updated. Therefore, it is necessary to distinguish QKV V vectors for the same token index using superseripts that indicate the time at which they were com- puted. For example, Qe is generated at the decoding step for the first time, but at + the updated attention outputs from the previous layer provide new embeddings to the current layer and then gen- erates another Qt (omitted in green line in Figure 4 To distinguish these two Qts, we denote the first Qt generated at as Q and the second Q, generated at + 8 as Q+++.
As the first supplementary attention becomes available at step t+1 (i.e., s=1), RetroAttention merges Oorg,t and O sup,t by a weighted average whose coefficients are the respective softmax nor-
malizers:
aorg Oorg, + sup
0++1 up:
sup,
Gorg + Osup
+++
A+1 Oup
Coorg + assu
++1
Σ
Σ
e OKKTIva IVa
(8)
Coog
iESt jEPage
1+1
Σ
Σ
Q K /va
iES (S, SEPage;
This procedure applied recursively additional supplementary outputs arrive- thrive-thatiio is, O++2 and O++1 are merged through 4+2 and up up,t
f+1 by the same mechanism:
0+++1
app
1+s Ot+s 1+++1
sup
O
1++ 14+41
Oup
dsup
up
14++1
aup
+ 14++1
Suuup
(9)
1++41 aup
Σ
Σ
Oftetiggtare /Va
iES
U SeAr jEPage,
Evolving Query Representations in Past Attention. As discussed in the above paragraph, the updated attention output is transferred to the next layer and then projected into new Query repre-
17

---

Published as a conference paper at ICLR 2026
Table 5: Relative attention-score gain by retrospective updates. Across the three datasets of GSM8K, MMLU, and CSQA, the first update provides the largest recovery, while later updates contribute diminishing gains. We use few sampled data in LONGGENBENCH n-question prompts and set n=30, w=8, and 6=0.15.
Query indices in retrospective updates (current -ppat)
Benchmark
t=0~0
t=1-0
t=2-00
[=3-0
t=4-+0
(=5-0
1=6-0
t=7-0
MMLU
1,000
0.054
0.018
0.011
0.007
0.007
0.005
0.004
GSM8K
1.000
0.044
0.016
0.009
0,006
0.004
0.004
0.004
CSQA
1.000
0.650
0.028
0.015
0.013
0.010
0.010
0.009
sentation. This implies that Query representation at given layer evolve as the update repeats. Dao jet al. (2022) analytically show that the aggregation of two partial softmax outputs can be exactly same as the original softmax output. This assumes the partial outputs are generated at the same decoding steps (i.e., based on the same Query representation), whereas RetroAtttenton merges the attention output asynchronously generated across retrospective window. This leads to mismatch in Query representations due to their evolution during retrospective updates.
Our updated attention output, merging multiple outputs across retrospective window, is an approx- imation of the attention output on the total supplemented KV entries that would have been computed as normal sparse attention. We assume that the QKV representations evolve smoothly across de- coding steps, such that those from consecutive steps can regarded as approximately equivalent. Empirically, the &g distance between the same vector across adjacent steps (i.e., the change induced by one retrospective update) is typically less than 5% of its original &g norm for Query and Key vectors on average across various tasks, and less than 10% for Value vectors.
Retrospective Mask. The supplementary attention outputs are computed only on unseen KV cache pages. We introduce retrospective mask (AA) identify which pages have been already attended before and avoid their duplicated updates. Specifically, for each page we store As.p), the last decoding step in which the page was loaded for head h. This indicates that the attention outputs preceding the A, [p]-th decoding step are already supplemented with the page if unseen. Accordingly, when computing the supplementary attention for the past (e.g., decoding step f) Query and head h. we mask out any page such that A, [p] 2 t. Let kpage be the number of loaded pages, P the global page pool (i.e., the entire KV cache), the sequence length, and P the page size. This incremental masking logic relies only on tracking the latest Query per page, requiring h2 [P] = hy L/P integers per layer for tracking and h& kiage integers to be loaded per kernel call, assuming wwise page selection. Algorithm 2 describe the detailed mask management logic.
C.3 SUPPLEMENTED ATTENTION WEIGHTS
This section provides empirical evidence on why performance gain saturates in RetroArtention dis- cussed in Section 3.4 We suggest that such saturation is attributed from that the most informative KV elements (high attention weights) are selected first, and the supplemented ones become progres- sively less important (low attention scores), as the retrospective update progresses.
To demonstrate this, we measured the relative attention-score gain contributed by each update. For example, in Table 5 (w=8 setting), the first column represents the attention scores, i.e. (e(eee((((/()))) at 1=0 Query (its original attention), and the next columns represent the at- tention scores supplemented from the next t=1, t=2, ... t=7 Queries to this t=0 Query. Each supplementation normalized by its original attention scores.
Empirically, the first retrospective update recovers 4-7% of the baseline attention mass, but subse- quent updates contribute progressively less, indicating that later updates add only marginal signal. This is because attention weights are heavily concentrated on small subset of tokens, expanding the retrospective window yields a non-linear and diminishing recovery of full-cache information. This directly explains the observed saturation in performance.
18

---

Published as a conference paper at ICLR 2026
Letency pe: Mereeee operation (mS)
0.34
Latency 06: Herne operatoo (n5
0.40
Latency per Narnen opomtoon (ms)
1.4
Letency pe: Keerne operation (ms)
6.0
0.12
Dm)
Input (P))
1.2
(0
( 38k
0.10
0,5
Outpur din (Par))
0.25
Outpur Wann!
1.0
Output (Par)
4.0
Outpot din (Pne)
18k,
0.23
3.0
0.08
0.8
0.04
0.15
0.10
0.4
2.0
0.02
0.2
1.0
200
612
235
Inpunch (wb)
Input channel (wb)
channel (wb)
Input channel (wbb)
[a]
(b)
(C)
(d)
Figure 9: Latency analysis for linear layers. Kerne latency of RetroAttention a linear layer with various input and output dimensions (denoted in the figure) and input channel sizes. For RetroAt- tention, the input channel size equals w x b, where w is the retrospective window size and b is the batch size.
C.4 SENSITIVITY TO RETROSPECTIVE WINDOW
The trade-off between accuracy and computation is essentially controlled by the retrospective win- dow size w, the only control parameter in RetroAttention. The optimal trade-off would be achieved when accuracy gain significant (or saturated) while computation (particularly latency) overhead is still marginal.
The accuracy is most sensitive when moving from w=0 to small windows (w=2 and 4); beyond that, gains quickly exhibit diminishing returns and largely saturate around w=8 (as also seen in Figure 5 and Figure 7). This aligns with our attention-mass analysis given in the answer above.
Accuracy.
Computation. As described in Section 2.5 (Overlead Analysis), the overhead scales roughly lin- early with w, as each additional update adds extra query loads and FFN activations. However, this cost remains small, the additional computation does not significantly contribute to the latency in memory-bound regimes.
This mismatch in how accuracy and overhead scale determines the practical trade-off. In typical oonggeneratiinn scenarios, where decoding is strongly memory-bound, using a larger window (e.g., w=8) generally preferred: provides near-saturated accuracy gains while the added latency re- mains minimal due to the bandwidth-bound regime. However, in settings where latency is more critical or the workload not strictly memory- (w=2 or 4) to further reduce overhead while still recovering substantial portion of the accuracy benefits, Thus, Attentitention offers a knob that can be tuned depending on the runtime constraints.
practitioners may choose smaller windows
D LINEAR LAYER OVERHEAD ANALYSIS
For an input of shape n x Din and a projection weight of shape Di x Dout. the arithmetic intensity (AI) of linear layers in FP16 precision is given:
Allinear nin + Din Dow + n2 DD
(10)
where n is batch x sequence length. This shows that when n & Dout (which is typical in decoding stage), the becomes small, indicating that the operation is memory-bound rather than compute- bound. This allows models to have capacity for more computation with only negligible latency overhead. Figure / shows that the linear layer latency remains nearly constant until n exceeds certain threshold diverse Dr, and Dout combinations. These observations validate that the overhead per decoding step introduced by RetroAttention whose linear layers process w times larger input per step (i.e., n is x batch)-is practically negligible unless is around 128-256. Moreover, this overhead is independent of sequence length and the number of loaded KV entries, making it suitable for long generation scenarios.
Batch-size impacts on decoding throughput. We report with and without RetroAttention across a range of batch sizes and long-context settings (see Ta- ble 6). Because recent models (e.g., oeasen)) often generate more than 10k tokens,
measurements
19

---

Published as a conference paper at ICLR 2026
Table 6: Batch-size impacts on throughput. Experiments are performed in Llama3. --Sttntrutt model using single A 100 80GB GPU. Throughput is estimated by estimating the average decoding latency on 1k tokens after prefilling a given context length. w=0 denotes the model without RetroAt- tention. OOM denotes out-of-memorg
Context
Retrospective window
Throughput (batch/sec) at batch B
length
B=1
B=2
B=4
B=8
B=16
w=0
48.7
92.0
170.9
298.6
OOM
w=2
47.1
90.0
166.1
288.2
OOM
32k
w=4
46.8
88.9
163.2
285.1
OOM
w=
46.2
87.2
161.8
276.8
OOM
w=0
36.6
68.7
123.6
00M
OOM
w=2
35.6
67.2
120.5
OOM
OOM
64k
w=4
35.4
66.5
118.3
0OM
OOM
w=
35.1
65.6
117.2
00M
OOM
w=0
24.6
45.5
OOM
OOM
OOM
w=2
24.2
44.7
OOM
COM
0OM
128k
w=4
24.1
44.2
OOM
OOM
OOM
w=8
23,9
43.5
0OM
OOM
0OM
focus on uon-gennraation scenarios where the total context length exceeds 32k. Retro intro- duces small but measurable throughput reduction. For example, 32k context length, throughput at batch size (B=1) decreases by 3.3% (48.7 - 47.1 batch/sec for 2= At batch size 8 (B=8), the reduction is 3.5% (298.6 288.2 batch/sec for w=2). The worst case occurs B=8 and w=8, where throughput decreases by 7.3% (298.6 + 276.8 batch/sec). This is because larger retrospective windows require generating and updating more KV elements, thus increasing linear layer operations (as illustrated in Figure 4.. Even in this worst case, however, the added latency is only 2. mmstokknn, which is still insignificant in practice.
Longer-context settings exhibit even smaller slowdowns under their maximum feasible batch sizes. At 64k context length (B=4), throughput decreases by 5.2% (123.6++177, for w=8), adding 1.8m/tooen. At 128k (B=2), the reduction is 4.4% (45.5-43.55 for w=8), adding 2.0ms/token. These observations further confirm that the window-dependent overhead remains limited even when w is large. Finally, we emphasize that query-aware KV cache load methods, including Quest and ours, assume the full KV cache fits GPU DRAM. long-generatin settings, this constraint nat- urally limits the practical batch size (typically < 16 for 8B model on 80GB GPU) to avoid the KV memory explosion. Under these realistic batch-size ranges, decoding remains strongly memory- bound, allowing Retro.Attention be integrated with only marginal throughput reduction.
E MEMORY FOOTPRINT ANALYSIS
Memory footprint is another critical factor to consider-especiilly since KV cache occupancy dom- inates attention memory usage and constrains inference concurrency in scenarios such as offload- ing (Fu) 2024). It is therefore important to analyze the peak memory consumption during decoding, which typically arises from the attention operation due to the large KV cache it requires. Following the same notation in Section 2.5 (e.g., the retrospective window size w, number of loaded KV pages kpages Query heads hy. tokens per page P, and head dimension d), the memory required for the caches involved in sparse attention computation is
kpags P h2 d B bytes
(11)
RetroAttention adds only small memory overhead by storing the attention outputs from the previous
w-1 1 steps:
(w-1) hg (d+2)
(12)
bytes, including auxiliary FP32 log-sum-exp values. This term independent of both kpage and sequence length L., making its growth negligible relative the generation length. In addition, the
20

---

Published as a conference paper at ICLR 2026
Table 7: LONGGENBENCH Prompt Template
Prompt Template
Answer each question step by step, adhering to the format shown in the examples provided. Start cach response with 'Answer' and introduce the final response with 'The answer is' Do not repeat the question. questions presented, regardless of number.
Ensure that you respond Examples:
[CoT Question 1) {CoT Question k}
[CoT Answer {CoT Answer_k}
Following Question:
[Real Question_1) ... (Real Question_n1
Table 8: Data statistics in LONGGENBENCH, Input and Output Tokens denote the average number of input tokens and output (generated from full-cache model) tokens.
Benchmark n-question
Input Tokens
Output Tokens
15
1337.9
657.8
CSQA
30
2029.8
1327.3
45
2672.3
1964.6
15
1705.8
1495.0
GSM8K
30
2649.7
2956.8
45
3530.6
4238.1
15
2615.7
951.6
MMLU
30
4200.8
1637.2
45
5744.3
2427.5
masking mechanism, which records the most recent decoding step for each KV page per head, requires
2B
(13)
bytes (assuming 32-bit integers). Overall, these additions incur minimal memory overhead com- pared to the KV cache and do not affect scalability.
F DATASET AND EXPERIMENT DETAILS
F.1 DATASET
We primarily evaluate on LONGGENBENCI,, which constructs single input prompt by concate- nating multiple reasoning questions sequence. Table 7 displays prompt template used LONGGENBENCH evaluation. We follow the original implementation for the number of in-context examples (k) (Liu et al. 2024c). Note that this differs with the number of concatenated examples in prompt (n). Also, Table & reports the input and output token statistics for the three datasets in LoNGGEN CSQA, GSM8K, and MMLU. The number of input and output tokens grows almost linearly with the number of questions in prompt. Reasoning-intensin benchmarks, AIME 2024, GPQA-DIAMONTI and LIVECODEBENCII-VS are evaluated using nucleus sampling (tem- perature 0.6; top-p 0.95) with 2, and samples per question, respectively. Language modeling benchmark, PG- 19 is evaluated on 91 out of 100 test samples exceeding 16k tokens, using the first 16k tokens of each.
F.2 LATENCY EVALUATION
We evaluate the latency per decoding in end-to-ent and kernel breakdown manner at several context lengths. For experimental details, set the batch size and relative budget 0.15, and use
21

---

Published as a conference paper at ICLR 2026
Algorithm 2: UPDATEANDBUILDMASK (Single Head)
Input: page index list S cache A; last page index Peur
Output: attention mask M; updated cache A
A(pear] <- 1=
Prevent current page from being attended by previous queries
M I
foreach p E St do Alpp)) A(pl < t;
end
return M,A
Table 9: Comparison with other method (ArkVale)) Accuracy results CSQA, MMLU, and GSM8K in LoNgGENBENCH with n=30 (i.e., the number questions prompt). Other experi-
ment settings are identical with Table
Method / Benchmark
CSQA
MMLU
GSM8K
Full Attention
74.1
58.7
60.8
Vrk
66.2
57.3
56.2
RetroAttention (w=2)
69.0
58.2
61.7
RetroAttention (w=4)
72.2
57.8
57.6
RetroAttention (w=8)
71.7
58.2
58.4
NVIDIA A100 80G GPU. Our kernel implementation is based on FlashInfer ee al. 2025), exten- sively optimizing CPU-side overheads such as scheduling, synchronization, and memory allocation.
Figures 6 (d) present the kernel-level latency breakdown. The segments labeled QKV and out- put project denote the linear projections from input hidden states to Queries, Keys, and Values, and from the attention outputs to the final projected representations, respectively. score(() corresponds to the criticality estimation step (Tang et al. 2024). where each page is scored using Quest's page digests. The top-k kernel indicates the selection of the highest-scoring & pages, while mask rep- resents the construction and update of the attention mask, as detailed in Algorithm [ The terms Oorg and Osup/Ou, account for two separate kernel executions: the attention output computation and the subsequent merging of cached and supplementary outputs when required. Here, Oorg de- notes the attention operation time without RetroAttenttinn, while the additional cost introduced by RetroAttentton is given by the difference between the combined kernel time and Oorg. denoted as Osup/ upp This term reflects the net overhead incurred in attention output computation. Finally, KV update reflects the cost of appending and maintaining the key-value caches.
F.3 RETROATTENTION WITH OTHER METHOD
We further verify RetroAAtenniion in Ark Vale (Chen et al. 2024a), which is more recent dynamic KV cache compression technique. In the experiments on LONGGENBENCI (like Table RetroAt- tention consistently enhances the performance, highlighting its generality over other method. For ex- ample, in Ark Vale, 66.2% 66.2%-+69.00 +69.0% wwtthout>wwin RetroAttention; w=2) on CSQA, 57.3% 57.3%-+58.25%% on MMLU, and 56.2% +61.7% on GSM8K. The results summarized in Table 9
G RESULTS ON LONG-CONTEXT INPUT BENCHMARKS
Although our method primarily targets mitigating cumulative approximation errors during long gen- erations, additionally evaluated its performance under the long-context scenario commonly used in prior works. Table 10 reports task accuracy results on LONGBENCH, where we observe that the improvements the Quest baseline limited.
To further examine how closely sparse attention can replicate full-attention counterpart- which the fundamental expectation of sparse approximations additionally measure token-level nor-
22

---

Published as a conference paper at ICLR 2026
malized Levenshtein edit similarity between sparse- and full-attention generations (Table I1 This metric explicitly quantifies the fidelity of sparse attention outputs to the gold standard full-attention version. As seen, RetroAttention consistently achieves slightly higher similarity than QUEST. but the gains remain margina This outcome can be explained by the characteristics of the bench- mark: as shown in Table 12 most LONGBENCH tasks have extremely long inputs but relatively short outputs, whereas LONGGENBENCH (Table g contains substantially longer generations.
Since all input tokens are processed with full attention during the prefill phase, their KV caches exact, and approximation errors only arise during autoregressive decoding. That is, long-context in- put tasks exhibit far less error accumulation, because the model processes fixed context rather than repeatedly generating and conditioning on its own imperfect outputs. As result, retrieval accuracy becomes substantially more critical in long-context output scenarios. Consequently, when the output length is short, the cumulative error remains limited and the corrective effect of RetroAttention is less pronounced, while tasks with longer generations provide more room for improvement.
"Cases exist where accuracy drops while Levenshtein similarity rises, because the metric captures alignment with full-attention outputs that may themselves he incorrect with respect the ground truth.
23

---

Published as a conference paper at ICLR 2026
Table 10: Comparison of Accuracy in LONGBENCH tasks. All methods use relative KV cache
budget with the minimum budget of 256 tokens.
Single-Doc QA
Multi-Doc QA
Summarization
Code
Few-shot
Method
Budget
Avg.
MF-en
NrVQA
Qasper
2WKIMQQS
HotpotQA
Musique
GovReport
MultiNews
QMSuum
TrivinQA
LCC
RB-P
Full Attention
54.85
30.11
45.40
46.40
55.64
31.28
35.17
27.15
25.26
65.12
58.97
91.65
47.25
0.05
54.53
30.29
42.54
45.81
54.40
31.03
33.81
26.26
25.10
62.97
57.16
91.68
46.30
Quest
0.10
55.38
30.03
44.39
46.44
55.42
31.24
34.15
26.37
25.64
64.16
58.23
91.38
46.90
0.15
54.27
29.99
45.35
46,29
55,50
31.27
34.54
26.64
25.36
64.06
58.88
91.49
46.97
0.05
$3.89
29.11
43.52
44.57
54.44
31.46
33:43
26.20
25.37
63.65
57.87
91.66
46.26
RetroAtiention (w=2)
0.10
55.06
30.07
44.43
46.00
55.64
31.20
33.88
26.31
25.62
63.65
63
0.15
54.56
29.98
44.47
46,24
55.39
31.21
34.42
26.32
25.36
63,94
58.98
91.50
46.86
0.05
53.08
29.68
43.67
44,93
54.42
30,95
33.29
26.49
25.83
63.58
57.43
91.68
46.25
Retro-Atention (w=44
0.10
54.83
30.10
44.85
45,92
55.50
31.23
34.00
26.90
25.45
63.85
58.60 60
91.49
46.89
0.15
54.76
30.10
44.73
55.39
31.20
34.35
25.34
63.72
59.35
46.95
0.05
53.40
29.74
42.96
44,90
54.33
31.29
33.30
26.54
25.52
63.47
57.06
91.68
46.18
Retro-Ateetioon (10=8)
0.10
54.97
29.91
44.12
45,92
55.22
31.22
33.81
26.43
25.71
63.66
58.64
91.49
46.76
0.15
54.78
30.08
45.06
46.15
55.39
31.20
34.40
26.77
25.63
63.78
59.21
91.50
46.99
Table 11: Comparison Normalized Levenshtein Edit Similarity in LONGBENCH tasks. Each result is compared against its corresponding full-attention generation, and the similarity is computed the token level. score of indicates identical outputs, and higher scores are better.
Method
Budget
SingleDoe QA
Multi-Doc QA
Summarization
Code
Few-shot
Avg.
MF-en
NrtQQ
Qusper
2WIRMOQ
HorpotQA
Musique
GorReport
MultNews
QM
TrisisQA
LCC
RB-P
0.05
0.8920
0.8375
0,7886
0.9304
0,9582
0.9312
0.3960
0.3971
0.4843
0.5765
0.5651
0.5351
0.6908
Quest
0.187
0.8740
0.8495
0.9420
0.9721
09618
0.4366
0.4077
0.5387
0.6058
0.6315
0.6220
0.7298
0.15
0.9149
0.9016
0.8869
0.9691
0.9749
0,9322
0.4459
0.4209
0.5692
0.6478
0.6898
0.6914
0.7571
0.8904
0.7949
0.9341
0.9571
09291
0.6959
RetroAttcction (w=2)
0.10
0.9212
0.8748
0.8471
0.9422
0.9726
0.9651
0.4442
0.4170
0.5424
0.6127
0.6363
0.6425
0.7348
0.15
0.9116
0.8824
0.9819
09744
0.4623
0.4327
0.5682
0.6430
0.6968
0.7170
0.7625
0.05
0.8878
0.8515
0.8108
0.9419
0.9552
0.9298
0.4076
0.4131
0.4913
005900
0.5664
0.5552
0.7001
Retro-Atlenioon (w=4)
0.10
0.202
0.8825
0.8574
0.9413
0.9734
09630
0.4401
0.4211
0.5468
0.6192
0.6337
0.6388
0,7366
0.15
0.9248
0.9000
0.8811
0,9664
0.9819
0.9739
0.4665
0.4311
0.5841
0.6465
0.6903
0.7178
0.7637
0.05
0.8936
0.8541
0.7977
0.9386
0.9552
0.9022
0.4048
0.1161
0.4943
0.5939
0.5662
0.5531
0.6998
RetroAAteenion (w=8)
0.9177
0.8783
0.8633
0.9433
0.9699
0.9599
0.4447
0.4217
0.5426
0.6177
0.6376
0.6486
0.7376
0.15
0.9270
0.9021
0.8837
0.9677
0.9817
0.9716
0.4613
0.4266
0.5892
0.6421
0.6917
0.7139
0.7632
Table 12:
Data statistics LONGBENCH. Input/Output Tokens denote the average number of input tokens and output tokens (generated from the full-cache model).
Task
Input Tokens
Output Tokens
MF-en
6974.0
18.5
NrtvQA
29904.1
8.9
Qasper
5123.5
20.5
2WikiMQA
7203.3
6.2
HotpotQA
12889.3
4.7
Musique
15651.5
6.1
GovReport
10310.4
459.2
MultiNews
2677.1
434.6
QMSum
13951.6
107.7
LCC
3179.7
64.0
RB-P
10819.4
64.0
TriviaQA
11780.7
32.0
24


Reviews:
[{"review_id": "vAObJXCrN1", "reviewer": "Reviewer_zHKN", "summary": "This paper introduces RetroAttention, a accuracy-refinement method for efficient long-context generation in large language models (LLMs). Unlike prior approaches (e.g., Quest, StreamingLLM, TOVA), which focus solely on compressing or sparsifying the current decoding step, RetroAttention retrospectively revises past attention outputs using newly arrived Key-Value (KV) entries from later decoding steps. Experiments across multiple long-generation benchmarks (LONGGENBENCH, AIME24, GPQA-DIAMOND, LIVECODEBENCH, and PG-19) show that RetroAttention improves effective KV exposure by up to 1.6× and yields up to 21.9% accuracy gains over state-of-the-art baselines, with small latency and memory overhead.", "questions": "Q1. It is not straightforward why the proposed approach is less effective on long context, which basically also suffers from the lower retrieval accuracy problem.\n\nQ2. Would you also consider to use the retrieved context of the previous tokens to enhance the current tokens, since they are already in the GPU memory and they are expected to be in the top-k/2k/3k window? Why or why not?\n\nQ3. Whether RetroAttention will work on distributed decoding? \n\nQ4. How would RetroAttention work on MoE models?\n\nQ5. How would RetroAttention interplay with different KV cache retrieval strategies, like those listed in W3?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1. This paper tackles an important problem of the refinement of sparse KV cache selection.\n\nS2. In stead of proposing KV cache sparsification approaches, this paper proposes a refinement approach for the KV cache sparsificaitons, which has the potential to be applied to many backbone sparsifications.\n\nS3. The proposed approach is a backed up with formal time and space overhead analysis.", "weaknesses": "W1. The experiments are limited to small scale models. Experiments on at least medium size, e.g., 32B models, would be useful.\n\nW2. The comparison approaches are limited. More recent KV cache compression approaches, like ICECache, ArkVale, PQCache, MagicPIG, etc, should also be evaluated.\n\nW3. I would suggest to also test larger cache reuse depth, e.g., w > 5, to show the effectiveness of reusage.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AFAbJhl2FL", "reviewer": "Reviewer_ytzA", "summary": "RetroAttention targets the long-context inference bottleneck, the fact that the KV cache that grows linearly with sequence length, and the cumulative errors introduced by sparse/compressed attention during extended decoding. The method retrospectively revises past attention outputs using KV entries fetched at later decoding steps. It does this by computing the supplementary attention for earlier queries with currently loaded but previously unseen KV pages, and storing/updating these results in a lightweight output cache. Original and supplementary outputs are merged via a softmax-weighted linear combination, and the refined embeddings propagate upward by overwriting stale K/V entries in deeper layers.", "questions": "1. Could RetroAttention be combined with eviction-style key selection (e.g., Keyformer) or MorphKV (Dialogue without limits paper) so that retrospective updates counteract the cumulative errors introduced by permanently discarded tokens, rather than conflicting with eviction's objectives?\n\n2. Given the limited gains on long-input/short-output settings like LONGBENCH, would token-selection methods (Keyformer/MorphKV or similar strategies) fare better there? Also, could a hybrid (selection + retrospective updates) recover benefits across both regimes?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. RetroAttention has consistent gains over strong baselines while adding only marginal latency thanks to its memory-bound design.\n\n2. The scheme expands each query's effective KV budget by up to 1.6x without increasing the actual KV budget or KV memory traffic. This helps improve contextual completeness under fixed memory. This is a very nice approach and I liked this part.", "weaknesses": "1. This method works only long-generation scenarios. This approach wont help if KV cache overheads are not a problem (such as cases using extreme quantization). \n\n2. An interesting fact is that the methods are not very simple (which would have been preferred). The benefits saturate as the retrospective window increases (nearly w=8). The approach introduces extra kernel steps (mask management, output merges, KV overwrites) that, while small, add complexity and non-zero overhead.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HUTU4wXcjf", "reviewer": "Reviewer_zGZu", "summary": "The paper proposes RetroAttention, a technique that retroactively updates past attention outputs using KV entries loaded at later decoding steps. The method keeps a lightweight output cache and, within a fixed retrospective window, recomputes supplementary attention for previously “unseen” KV pages, merging them with cached outputs to correct cumulative approximation errors in long generations. Claimed benefits include expanding the effective KV exposure without increasing the actual KV budget and adding only marginal latency. Experiments on LONGGENBENCH (GSM8K, MMLU, CSQA) and PG-19 are reported; the paper claims consistent gains over Quest under the same budget, and small, context-length–independent overheads.", "questions": "- The core issue lies in the lack of convincing motivation. Within a block, the tokens are usually highly correlated, and in most sparse-attention implementations, the selected KV pages for neighboring tokens are largely identical. You should discuss in detail the perspective presented in the LServe paper, which shows that adjacent tokens typically attend to the same KV pages. To strengthen your argument, please provide additional experiments that clearly demonstrate the necessity of updating the KV cache within a sliding window and justify why such retrospective updates are beneficial.\n\n- All other detailed comments can be found in the Weaknesses section.", "limitations": "", "rating": 2, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 1, "strengths": "+ The work introduces a new method for updating past KV caches using information from future tokens, allowing the model to retrospectively correct potential errors accumulated in earlier cache entries.\n\n+ Concrete mechanism with system awareness. The design (supplementary attention + output cache + KV overwrite downstream) is explicit and connected to a memory-bound analysis; figures and pseudo-code aid clarity.", "weaknesses": "- Motivation not fully convincing relative to simpler practices. The paper assumes non-trivial benefits from recomputing within a small local window. However, in LServe-style serving (LServe: Efficient Long-sequence LLM Serving with Unified Sparse Attention), adjacent tokens often select the same pages—so neighboring queries tend to attend to similar KV slices. If adjacent queries already share top-k pages, retrospective supplementation within a small window may add little new signal while increasing complexity. The current empirical narrative does not isolate this effect or demonstrate cases where the new pages actually differ materially from what neighbors already saw.\n\n- Limited breadth of models and tasks. The main results use LLAMA-3.1-8B-Instruct and swaps to DeepSeek-R1-Distill-Llama-8B for a subset of reasoning tasks. Absent are larger and diverse foundation models (eg. Qwen); conclusions about generality are therefore weak.\n\n- Overhead and complexity vs. benefit. The method adds supplementary attention, output caching, mask bookkeeping, and KV overwrites across layers. The latency analysis argues the overhead is memory-bound and “negligible,” but even the authors’ figures indicate non-zero, window-dependent costs; moreover, these kernels complicate inference stacks and may reduce effective batch size , weakening throughput. The paper does not quantify batch-size impacts or serving-level throughput with and without the feature enabled.\n\n- Insufficient ablations on design choices. For example, the choice of window size w, the policy for “unseen” page detection, and the exact merging schedule are only partially ablated; sensitivity to k, page size, and per-head selection policy is unclear beyond the limited plots.\n\n- By the way, the paper states anonymized code is provided, but the link is not accessible on our side.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5ML3LARtrc", "reviewer": "Reviewer_A5Uv", "summary": "The paper “Retrospective Sparse Attention” introduces an efficient attention mechanism designed to reduce the memory and computation cost of attention without sacrificing long-range dependency modeling. Instead of attending to all past tokens, the proposed Retrospective Attention mechanism selectively attends to a subset of important historical tokens determined by sparsity patterns guided by attention statistics from previous layers or steps. This retrospective sparsity is dynamically adapted based on contextual relevance, allowing the model to focus on informative past activations while maintaining global context coverage. The method is evaluated on long-context language modeling and sequence tasks, showing comparable performance to dense attention while significantly lowering memory and compute usage. The method achieves up to 21.9% and on average 5.6% accuracy gains over state-of-the-art baselines across long-context benchmarks", "questions": "1. Is the proposed method only tested on multi-questions & multi-answers? Have you tested it on multi-turn conversations? It seems to be worthwhile to apply this method on multi-turn conversations\n2. How sensitive is performance to w, and what governs the optimal trade-off between accuracy and computation?", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. Effective expansion of effective KV budget: Through retrospective updates, each query effectively accesses 1.6× more KV entries than the allocated cache budget, without any increase in actual memory usage\n2. Clear motivation and empirical validation: The paper convincingly identifies a progressive degradation problem in long-sequence generation due to frozen past attention and directly addresses it via backward refinement\n3. Novel mechanism for long-context refinement: RetroAttention effectively mitigates cumulative attention degradation during long decoding, a limitation common in prior sparse attention methods", "weaknesses": "1. Weak ablation and sensitivity analysis: While the method introduces retrospective window size w as a key parameter, the results (Fig. 7) show saturation beyond w=8, but there is no discussion of why or how this affects efficiency or convergence\n2. Ambiguity in the update mechanism: The process of overwriting old KV entries and how it interacts with downstream layers is conceptually underexplained\n3. Limited scope of benchmarks: TThere are no experiments on code-completion settings where long-context dependencies differ.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)