acceptodds
Under review as a conference paper at ICLR 2027

RelaxKV: Query-Aware Recomputation with Sparse Context Attention for Efficient KV Cache Reuse

Abstract

Cross-request KV caching reduces the prefill cost of Retrieval-Augmented Generation (RAG), but conventional prefix caching severely limits cache reuse across requests. Position-Independent Caching (PIC) removes this constraint by reusing independent chunks, but their KV states miss cross-chunk interactions. Existing methods selectively recompute token states to recover these missing interactions, but primarily allocate the recomputation budget to selecting which states to recompute, while fixing the recomputation context to the full causal prefix. We introduce RelaxKV, which formulates selective cache repair as a joint allocation problem over repair targets and recomputation context. Guided by the user query, RelaxKV identifies layer-specific repair targets and restricts their recomputation to a query-relevant context, reducing attention computation. Across four decoder models, RelaxKV at a 15% anchor ratio improves aggregate LongBench performance over ProphetKV on all models. On Qwen3-14B, RelaxKV provides a stronger quality–TTFT trade-off than ProphetKV across a 5%–30% anchor-ratio sweep, and achieves the best selective results on RULER-MV and LV-Eval at 16K and 32K context lengths. Controlled ablations further demonstrate the importance of recomputation context selection. Our code will be released upon acceptance.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Large Language Model, Sparse Attention, Position-Independent Caching

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_cL3nOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

Summary

This paper proposes RelaxKV, a training-free method for selectively recomputing independently cached document chunks in RAG. It uses layer-wise query attention to select repair anchors, derives active recomputation paths from each token's deepest selected layer, and restricts recomputation attention to the causal subset of the anchor union. Experiments across four models and several long-context benchmarks show competitive quality–latency trade-offs.

Critical strengths

Strengths

  • The method is clearly motivated and described. Distinguishing repair targets from the context available during recomputation provides a useful perspective on selective KV cache repair.
  • The evaluation is reasonably comprehensive, including multiple models, natural and synthetic tasks, quality–TTFT curves, and sensitivity to anchor ratio and chunk size.
  • The controlled experiments are valuable. RelaxKV-G, the context-construction ablations, and the full-prefix control help separate the effects of repair-target selection and recomputation context.
Critical weaknesses

Weaknesses

  1. Missing comparison with InfoFlow KV. InfoFlow KV is directly relevant as it also uses query-conditioned attention to select tokens for KV recomputation and uses reordering to modify the recomputation scope. A direct comparison under a unified evaluation protocol is needed to establish the incremental benefits of RelaxKV's layer-specific repair schedule and sparse recomputation context. Without this comparison, the reported quality–latency trade-off is not fully positioned against closely related work.

  2. The repair schedule needs stronger validation. Recomputing each token from the input through its deepest selected layer and stopping thereafter is intuitive, but layer-wise attention importance alone does not establish that this is the most effective schedule. Alternative schedules should be compared, particularly recomputing the entire anchor union through all layers. The appendix's Target-Union configuration matches the target count rather than directly using the anchor union as the repair set, so it does not fully address this question. Such comparisons would clarify the benefit of the proposed stopping rule.

  3. The denoising interpretation lacks direct evidence. The existing controls support the effectiveness of context restriction, but do not directly establish the suggested implicit denoising effect. Restricting the context can remove distracting information, but can also discard useful within-chunk dependencies that were present in the original cache. Case studies and failure analyses would help explain when sparse recomputation improves the representations relevant to answering the query and when it loses necessary information.

  4. Generality across token selection strategies remains unclear. RelaxKV-G is a useful control using ProphetKV's repair targets, but both target-selection approaches rely on query attention. Evaluating sparse recomputation with selectors based on different criteria, such as those used by CacheBlend and Lego, would clarify whether its benefits extend beyond query-guided selection and whether the recomputation strategy can serve as a more general component.

Questions for authors

Questions

  1. Could the authors compare against InfoFlow KV under the same evaluation protocol and report the quality–latency trade-off?

  2. How does the proposed repair schedule compare with alternative schedules, particularly recomputing all tokens in the anchor union through all layers?

  3. Could the authors provide case studies or failure analyses to clarify the proposed denoising effect and the potential loss of useful within-chunk context?

  4. Does the sparse recomputation mechanism also benefit different token selection strategies, such as CacheBlend and Lego?

  5. Beyond the current RULER-MV evaluation up to 32K, could the authors evaluate longer contexts within the models' supported ranges and examine sensitivity to evidence position?

7 comments
AuthorsOpenReview ↗

Response (Part 1)

W1&Q1: Thank you for the helpful suggestion.

In the revision, we cite InfoFlow-KV [1] and add a comparison under the same evaluation protocol with MuSiQue and Qwen3-14B. We report both answer quality and latency to provide a direct quality–latency comparison with this baseline, with the results presented in Figure 6 of the revised PDF.

[1] https://arxiv.org/pdf/2603.05353v3. InfoFlow KV: Information-Flow-Aware KV Recomputation for Long Context.

AuthorsOpenReview ↗

Response (Part 2)

W2&Q2:

We will add theoretical elaboration and analysis on the cost of RelaxKV compared with alternative schedules in the appendix. Thank you for the questions raised by the reviewers.

The all-layer union schedule would recompute the union of anchors at every layer, causing the total repair cost to grow approximately as L∣∪lAl∣L|\cup_l A_l|, where LL is the number of layers.

This can be substantially larger than RelaxKV’s layer-wise cost ∑l∣Al∣\sum_l |A_l|, making it impractical under a fixed recomputation budget. RelaxKV therefore uses layer-specific repair sets to maintain a controlled repair cost while adapting the schedule to each layer’s query relevance.

We further validate this analysis experimentally, as shown in Figure 9 of Appendix A.7. On RULER-MV 16K, RelaxKV achieves a 100% score with approximately 3.5s TTFT, whereas the all-layer anchor union requires approximately 4.9s to reach the same score, reducing latency by about 28%. These results demonstrate the superior quality–latency trade-off of layer-wise recomputation scheduling.

AuthorsOpenReview ↗

Response (Part 3)

W3&Q3:

To investigate the proposed denoising effect and the potential loss of useful within-chunk context, we conduct an additional evidence-preservation analysis and provide representative success and failure cases.

(1) Evidence preservation. We map RelaxKV's selected context union to 512-token chunks on RULER-MV, covering context lengths from 4K to 32K with evidence distributed across 1, 2, or 4 chunks based on the [1]. At a 15% anchor ratio, RelaxKV achieves 100% evidence-chunk coverage across all evaluated settings, retaining 98.20%–99.96% of tokens within evidence-bearing chunks. Even when evidence spans four chunks, token retention remains above 99%.

MetricEvidence Chunks4K8K16K32K
Evidence Chunk Coverage (%)1100100100100
2100100100100
4100100100100
Evidence Token Retention (%)199.1899.7499.6298.20
299.8699.9699.9199.87
499.9199.9199.9399.93
  • Success case. On MuSiQue, answering the question requires connecting the evidence chain INSAT-4CR → ISRO → ATS-6. RelaxKV preserves the relevant evidence across both supporting passages and correctly generates “ATS-6”, matching full recomputation while retaining only 64.1% of the context tokens in its selected context union.

  • Failure case. In another MuSiQue example, RelaxKV incorrectly generates “James Chadwick” instead of “Manhattan Project”, although the complete evidence span “worked on the Manhattan Project” remains in the selected union and full recomputation answers correctly. This indicates that preserving the answer-bearing evidence alone does not guarantee correct answer generation.

(2) Discussion and limitations. These results demonstrate that RelaxKV can substantially restrict the recomputation context while preserving evidence-bearing regions, but also reveal that evidence retention does not necessarily ensure effective evidence utilization. The observed quality improvements are consistent with reduced interference from irrelevant context, although the cases do not establish denoising as a causal mechanism. We will incorporate these analyses into the revised manuscript and clarify the potential limitations of context restriction.

[1] https://github.com/NVIDIA/RULER.

Reviewer_FCgWOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
3(+1)
Read review
Paper summary

This paper proposes RelaxKV, a query-aware selective recomputation method for improving cross-request KV-cache reuse in Retrieval-Augmented Generation (RAG). The paper addresses the limitations of Position-Independent Caching (PIC), where independently computed chunk KV caches lack cross-chunk contextual interactions. Existing selective recomputation methods, such as ProphetKV, primarily focus on selecting which token states to recompute, while allowing those tokens to attend to their full causal prefixes. RelaxKV extends this approach by jointly considering repair target selection and recomputation context selection. Specifically, it uses query attention scores to identify layer-specific repair anchors, constructs dependency-closed repair targets, and uses the union of selected anchors as a shared sparse attention context during recomputation. Experiments across four language models, including Qwen3-14B, Llama-3.1-8B, Phi-4-14B, and Llama-3.2-3B, show competitive quality–TTFT trade-offs compared with existing selective cache repair methods, particularly ProphetKV.

Critical strengths
  1. A useful extension of selective KV-cache repair. RelaxKV explicitly distinguishes repair target selection from recomputation context selection. This is a reasonable design, since recomputing a small subset of tokens against their full causal prefixes can still be expensive.

  2. Competitive performance on long-context benchmarks. The method demonstrates promising results on RULER-MV and LV-Eval. The results suggest that restricting recomputation to query-relevant context can improve the quality–efficiency trade-off in certain long-context settings.

  3. Useful controlled ablations. The authors include matched-target controls, alternative context-construction methods, and a full-prefix recomputation control. These experiments help isolate the role of recomputation context selection. The additional quality–TTFT trade-off curves across multiple models are also useful.

Critical weaknesses
  1. Limited novelty relative to existing query-aware recomputation and sparse attention methods My primary concern is the relatively limited algorithmic novelty. ProphetKV has already introduced query-guided selective recomputation for reusable KV caches. RelaxKV extends this framework by selecting a restricted recomputation context and introducing layer-specific repair targets. While this extension is reasonable, the proposed context selection mechanism is primarily based on query-attention Top-k selection and the union of layer-wise selected tokens. Both query-aware token selection and sparse attention over selected context positions have been extensively explored in prior work. Consequently, the main contribution appears to be a relatively straightforward combination of established techniques rather than a fundamentally new cache reuse mechanism. The authors should more clearly explain which aspects of the proposed joint selection strategy provide nontrivial advantages over existing query-aware sparse attention and selective recomputation methods.

  2. The nominal recomputation budgets are not directly comparable In the main experiments, RelaxKV uses a 15% anchor ratio, whereas ProphetKV and other selective baselines generally use a 20% repair ratio. However, these percentages do not represent the same computational budget. Because RelaxKV selects repair anchors independently across layers and propagates deeper selected tokens through preceding layers, the actual number of recomputed layer-token states can be substantially larger than the nominal anchor ratio. For example, the paper reports that a 15% anchor ratio can result in a shared context union covering approximately 63% of token positions and dependency-closed active targets accounting for approximately 43% of layer-token states. The realized ratios are even higher for some longer-context settings. Although the authors acknowledge this distinction and provide measured quality–TTFT curves, the nominal budget comparison makes it difficult to interpret the relative computational efficiency of the methods. I would encourage a more systematic comparison at matched realized computational costs, including the number of recomputed layer-token states, effective attention edges, and measured GPU execution time.

  3. Limited improvements on standard LongBench tasks Although the paper reports improvements over ProphetKV across all four evaluated models, the average gains on the selected LongBench tasks are relatively modest for several models. For example:

• Qwen3-14B: 53.11 (ProphetKV) versus 53.14 (RelaxKV).

• Llama-3.1-8B: 57.20 versus 57.64.

• Phi-4-14B: 45.53 versus 46.27.

• Llama-3.2-3B: 41.62 versus 44.04.

The improvement is particularly small for Qwen3-14B. Moreover, the matched-target control RelaxKV_G does not consistently improve quality over ProphetKV, suggesting that changing the recomputation context alone does not always translate into better downstream accuracy. While reducing latency is a valid contribution, the paper would benefit from a clearer analysis of when the proposed context restriction improves quality and when it mainly provides computational savings. It would also be useful to report statistical uncertainty or paired significance analyses, particularly for the relatively small aggregate improvements.

  1. Limited demonstration of practical cross-request serving benefits The paper targets efficient KV-cache reuse for RAG serving. However, the reported cache-ready TTFT measurements assume that the independently precomputed chunk KV caches are already resident on the GPU. The measurements exclude retrieval latency and reusable-cache construction costs. Furthermore, experiments primarily use batch size one and independently precomputed fixed-size chunks with their final global position IDs. This setup is useful for isolating the selective recomputation mechanism, but it does not fully characterize practical cross-request serving workloads, where cached chunks may appear at different positions, cache residency may vary, and multiple requests may execute concurrently. The practical efficiency benefits could differ once cache lookup, cache movement, positional realignment, and concurrent serving overheads are considered. A more realistic end-to-end serving evaluation would strengthen the significance of the proposed approach.

  2. Limited scalability evaluation beyond 32K context lengths The method aims to improve long-context KV-cache reuse, but the length-scaling experiments only extend to 32K tokens. It remains unclear how the proposed method behaves at substantially longer context lengths, such as 64K or 128K, where cache reuse is particularly valuable. Importantly, the union of independently selected layer-wise anchors can cover a large fraction of the context. As sequence length and model depth increase, the effective recomputation context and active target set may become much larger than suggested by the nominal anchor ratio. A more comprehensive scalability analysis would help establish whether RelaxKV maintains its advantages for longer contexts.

  3. Insufficient fine-grained latency and overhead analysis The paper reports recomputation latency and end-to-end TTFT, but a more detailed breakdown of the selective repair pipeline would help identify the actual sources of efficiency gains. In particular, it would be useful to separately report:

• Query-attention scoring overhead.

• Layer-wise repair anchor selection and union construction.

• KV gathering and cache updates.

• Sparse attention computation during recomputation.

• Non-attention operations, including projections and MLP computation.

This analysis would help determine how much of the total improvement comes from reducing attention context versus the changes in repair target scheduling. The full-prefix control in Appendix A.4 is useful and reports approximately 9.9%–23.2% lower recomputation latency under matched targets. However, a more complete latency breakdown would strengthen the efficiency claims.

Questions for authors

Q1. Novelty and relationship to prior work ProphetKV already uses query-guided repair target selection, while sparse attention and query-aware context selection have been extensively studied. Could the authors clarify the essential algorithmic novelty of RelaxKV beyond combining layer-wise Top-k repair selection with sparse recomputation context restriction? In particular, why is the union of layer-wise repair anchors preferable to other established query-aware sparse context selection strategies?

Q2. Fair comparison under equivalent computational budgets Since the 15% anchor ratio used by RelaxKV is not directly comparable to the 20% repair ratio used by ProphetKV, could the authors provide comparisons under matched realized computation? For example, how do the methods compare when controlling the number of recomputed layer-token states, effective attention operations, or total GPU execution time?

Q3. Practical contribution of context selection The matched-target control RelaxKV_G provides useful evidence, but the improvement over ProphetKV is not consistent across all tasks. Could the authors further quantify the independent benefit of recomputation context restriction when repair targets are held fixed, particularly in terms of the quality–latency trade-off? What types of tasks or query distributions benefit most from removing the unselected causal context?

Q4. Scalability to longer contexts and practical RAG serving Does RelaxKV maintain its quality–latency advantages at 64K or 128K contexts? Moreover, how does its end-to-end performance change when accounting for cache lookup, positional realignment, GPU cache residency, and concurrent requests in a realistic cross-request RAG serving workload?

Q5. Detailed computational breakdown Could the authors provide a fine-grained latency breakdown of query scoring, repair-target selection, KV gathering, sparse attention, and non-attention recomputation? This would clarify which components dominate runtime and how much of the acceleration is specifically attributable to the proposed sparse recomputation context.

7 comments
AuthorsOpenReview ↗

Response (Part 1)

W1&Q1: Thank you very much for your efforts and time to review our paper and give us many helpful comments!

We clarify the essential algorithmic novelty of RelaxKV and its distinction from existing query-aware sparse attention methods.

(1) Top-k sparse inference vs. sparse cache repair. Conventional top-k sparse attention selects query-relevant KV positions to reduce inference costs. In contrast, PIC reuses precomputed KV states lacking cross-chunk interactions, requiring selective repair to recover missing information. Since sparse inference and cache repair serve different purposes, their most valuable KV positions may differ. Motivated by this distinction, RelaxKV aims to improve the quality–efficiency trade-off by jointly considering which KV states to repair and which context they should attend to, rather than focusing solely on repair target selection as in ProphetKV. Whether and how these two settings differ may warrant further investigation.

(2) Controlled validation. To validate this design, we compare RelaxKV with two alternative query-aware context selection strategies: Global Sparse, which uses averaged attention scores across layers, and Layerwise Sparse, which independently selects Top-k context tokens at each layer. All variants maintain identical repair anchors, active repair targets, and nominal context budgets, differing only in context construction.

As shown in Table 3, RelaxKV achieves 38.08 F1 on MuSiQue, outperforming Global Sparse (34.81) and Layerwise Sparse (31.78). Similar improvements are observed on LV-Eval 16K (28.71 vs. 27.32 and 18.18), with comparable recomputation latency. These results demonstrate the effectiveness of repair-aware context construction beyond conventional layer-wise Top-k selection.

In summary, RelaxKV's novelty lies in a repair-aware target–context selection mechanism for PIC, where recomputation targets and their attention context are coordinated rather than selected independently.

AuthorsOpenReview ↗

Response (Part 2)

W2&Q2:

We agree that the nominal anchor ratio in RelaxKV is not directly comparable to the repair ratio in ProphetKV, as the two methods involve different recomputation workloads.

(1) Comparison under matched execution latency. To address this concern, we conduct additional quality–TTFT evaluations on RULER-MV at 16K and 32K, sweeping the nominal ratios from 5% to 30%. Importantly, our measured TTFT directly reflects the overall online inference execution cost under GPU-resident KV caches. Therefore, comparing methods at matched TTFT provides a practical measure of their realized execution costs, rather than relying on nominal recomputation ratios or theoretical operation counts.

As shown in the Figure 5 of the revised PDF, RelaxKV achieves a favorable quality–latency trade-off compared with ProphetKV. For example, at 32K, RelaxKV (15%) achieves approximately 95.5% accuracy with 15.5s TTFT, while ProphetKV (30%) achieves approximately 94.5% accuracy with 26s TTFT. Thus, RelaxKV achieves slightly higher accuracy while reducing measured execution latency.

(2) Realized computation budgets. We further clarify the distinction between nominal ratios and realized computation. As reported in Appendix A.4, at a 15% anchor ratio on RULER-MV 32K, RelaxKV recomputes 55.2% of layer-token states after dependency closure, while the shared-context union covers 78.1% of context positions. These quantities demonstrate why nominal ratios alone cannot represent equivalent computational budgets.

Together, the quality–TTFT curves demonstrate that RelaxKV maintains a more favorable quality–latency trade-off when compared using actual measured inference execution latency, accounting for the computational consequences of different target and context selection strategies.

AuthorsOpenReview ↗

Response (Part 3)

W3&Q3: We thank the reviewer for this insightful comment.

We agree that isolating the contribution of recomputation context selection is important for understanding RelaxKV's effectiveness.

(1) Quality versus computational benefits. Context restriction does not necessarily improve accuracy on every task. When the original recomputation context already contains sufficient relevant information, its main benefit is reducing redundant attention computation while preserving comparable quality. Our matched-target RelaxKV-G control supports this distinction: on RULER-MV 16K, it reduces TTFT by 28.4% relative to ProphetKV while keeping repair targets fixed.

(2) Independent benefit of context selection. To further quantify this contribution, we conduct additional controlled experiments with two different repair target selection strategies, CacheBlend [1] and LegoLink (Algorithm in EPIC) [2]. For each method, we retain its original repair targets while replacing the full causal recomputation context with our selected RelaxKV context. This allows us to isolate the effect of context restriction without changing the repair targets.

The results demonstrate consistent improvements in both generation quality and inference latency:

  • CacheBlend: The RULER score improves from 44.17 to 50.67 (+6.50 percentage points), while mean TTFT decreases from 5360.82 ms to 3281.56 ms, achieving a 1.63× speedup.

  • LegoLink: The RULER score improves from 56.00 to 60.67 (+4.67 percentage points), while mean TTFT decreases from 5367.24 ms to 3361.26 ms, achieving a 1.60× speedup.

ModelMethodRULER Score (%)TTFT Mean (ms)Speedup
Qwen3-14BCacheBlend + Full Context44.175360.821.00×
CacheBlend + RelaxKV Context50.673281.561.63×
LegoLink + Full Context56.005367.241.00×
LegoLink + RelaxKV Context60.673361.261.60×

These results provide direct evidence that restricting the recomputation context can simultaneously improve answer quality and reduce latency.

(3) Task and query characteristics. We expect context restriction to be particularly beneficial when the causal prefix contains substantial query-irrelevant information, as restricting attention can reduce both unnecessary computation and interference from irrelevant context. However, the additional results above are aggregate measurements and do not establish which specific task categories or query distributions benefit most.

We will further clarify the design objectives of RelaxKV and provide a more comprehensive discussion of the experimental results and quality–latency trade-offs in the revised manuscript.

[1] https://arxiv.org/abs/2405.16444. CacheBlend: Fast Large Language Model Serving for RAG with Cached Knowledge Fusion.

[2] https://arxiv.org/abs/2410.15332. EPIC: Efficient Position-Independent Caching for Serving Large Language Models.

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

This paper proposes RelaxKV, a method for selective repair of independently precomputed KV caches in retrieval-augmented generation. Unlike existing approaches that mainly focus on selecting which token states to recompute, RelaxKV additionally restricts the attention context used during recomputation. It uses layer-wise query attention to select repair anchors, constructs dependency-closed recomputation schedules, and uses the union of anchors as a shared sparse context. Experiments across four decoder models and multiple long-context benchmarks demonstrate competitive task quality and reduced recomputation latency.

Critical strengths
  1. Practical problem and a meaningful extension to selective cache repair. The paper identifies recomputation context selection as an additional optimization dimension beyond repair target selection.

  2. Useful controlled evaluations. The paper evaluates four models across multiple long-context benchmarks and compares against several relevant baselines. The matched-target and full-prefix controls help isolate the contribution of sparse recomputation context, while the quality–TTFT measurements provide evidence of its efficiency benefits.

Critical weaknesses
  1. Limited methodological novelty. The method brings together query-aware scoring, layer-wise token selection, and sparse attention. Applying these ideas to KV cache repair is meaningful, but the proposed “joint allocation” is largely a heuristic: the repair schedule and context are both derived from the same anchor sets, without explicitly balancing their respective costs and benefits. The paper does compare simpler context-selection alternatives, and these experiments show that the choice of context matters.

  2. Incomplete quality–latency comparison. Table 2 reports strong long-context quality gains over ProphetKV without corresponding latency measurements. Since anchor ratios and repair ratios do not represent equivalent computational budgets, these scores alone do not establish an efficiency advantage. Figure 4 provides useful trade-off curves, but does not directly cover the long-context settings in Table 2.

  3. Limited long-context coverage. The strongest long-context gains are reported on RULER-MV and LV-Eval, where longer inputs can contain substantial distracting information without a proportional increase in relevant evidence. While these settings are relevant to RAG, they may particularly favor query-aware context filtering. It remains unclear whether RelaxKV provides similar benefits when relevant information is more widely distributed or cross-chunk dependencies become denser. Evaluations with varying evidence densities would help establish the generality of the proposed approach.

Questions for authors
  1. What specific mechanism distinguishes RelaxKV from a direct combination of query-aware selective recomputation and sparse attention? Could the authors provide further evidence that the proposed layer-wise schedule and anchor-union context are jointly necessary, rather than independently applying these two techniques?

  2. Could the authors provide matched-quality or matched-TTFT comparisons with ProphetKV for the 16K/32K settings in Table 2, together with the realized target and context ratios? A latency breakdown would also help explain the sources of the gains and the cost of selection.

  3. How were the long-context inputs constructed, and how does the amount of supporting evidence change with length? Could a controlled comparison at fixed context length clarify whether the gains persist as evidence density or cross-chunk dependencies increase?

3 comments
AuthorsOpenReview ↗

Response (Part 1)

W1&Q1: We thank the reviewer for this important question.

We clarify that RelaxKV's novelty lies not in simply combining selective recomputation with sparse attention, but in their coupled construction for KV cache repair.

(1) Coupled repair scheduling and context construction. A direct combination of selective recomputation and sparse attention would independently select repair targets and attention context, without explicitly considering their relationship. In contrast, RelaxKV derives both from the same layer-wise query-conditioned anchors SlS_l. Specifically, the repair schedule Rl=⋃d≥lSdR_l=\bigcup_{d\geq l}S_d preserves cross-layer dependencies, while the shared context U=⋃dSdU=\bigcup_d S_d incorporates query-relevant anchors selected across layers. This coordinated construction aligns the recomputation context with the repair targets, rather than treating them as two independent selection problems. Importantly, it preserves cross-layer anchor coverage without requiring all anchors to be recomputed at every layer.

(2) Controlled ablations. We conduct three controlled comparisons to evaluate the contributions of these design choices:

  • Context restriction with fixed targets. RelaxKV-G retains ProphetKV's repair targets while restricting their recomputation context. On RULER-MV 16K, attention latency decreases from 2151.2 to 1404.5 ms (34.7% reduction), reducing total TTFT from 2540.2 to 1817.8 ms (28.4% reduction).

  • Context construction with a fixed repair schedule. As shown in Table 3, with identical anchors, repair targets, and context budgets, RelaxKV achieves 38.08 F1 on MuSiQue, outperforming Global Sparse (34.81) and Layerwise Sparse (31.78) at comparable recomputation latency.

  • Layer-wise scheduling vs. all-layer union. As shown in Figure 9, RelaxKV achieves 100% accuracy on RULER-MV 16K with approximately 3.5s TTFT, compared with 4.9s for recomputing the entire anchor union at every layer, reducing latency by approximately 28.6%.

Together, these results demonstrate the complementary benefits of context restriction, repair-aware context construction, and layer-wise scheduling. RelaxKV's contribution is their coordinated construction for PIC, rather than independently applying existing selective recomputation and sparse attention techniques.

AuthorsOpenReview ↗

Response (Part 2)

W2&Q2:

(1) Matched-quality and matched-TTFT comparisons. To provide a more direct comparison beyond the fixed-budget results in Table 2, we include additional quality–TTFT trade-off curves on RULER-MV at both 16K and 32K, sweeping the nominal ratios from 5% to 30%.

(2) Latency breakdown. We additionally profile the major components of RelaxKV's online inference latency, with the extended experimental results presented in Figure 5 of the revised PDF. At 10% and 15% anchor ratios, query scoring takes approximately 133ms, while target selection and KV gathering together require only 10.1ms and 10.9ms, respectively, accounting for less than 0.5% of total TTFT. In contrast, attention computation dominates the execution time, accounting for approximately 77.8% and 80.7% of TTFT.

Metric (ms)RelaxKV (0.10)RelaxKV (0.15)
Total TTFT2334.33218.3
Query scoring133.5133.3
Target selection7.37.5
KV gathering2.83.4
Sparse attention1815.82598.4
Non-attention recompute185.0246.9
Other recompute120.0158.6

These observations indicate that the additional selection and gathering overheads are relatively small, while attention computation remains the primary optimization target. Together with the quality–TTFT curves, they support the effectiveness of jointly optimizing repair targets and recomputation context.

AuthorsOpenReview ↗

Response (Part 3)

W3&Q3:

We clarify the long-context input construction and provide an additional controlled evaluation of evidence distribution.

(1) Input construction and evidence density. We strictly follow the official RULER NIAH [1] generation protocol and use its niah_multivalue configuration (type_haystack=essay, num_needle_k=1, num_needle_v=4, and num_needle_q=1) specified in the official synthetic.yaml. Following RULER's configurable-length pipeline, we keep the four target values fixed and extend the essay haystack to obtain longer contexts. Thus, the amount of supporting evidence remains constant, while its relative density decreases as the context length increases.

(2) Controlled evidence dispersion. Since RULER provides an official configurable data generation pipeline, we further construct a controlled experiment to examine the effect of evidence distribution. Specifically, we use RULER's niah_multivalue setting with one key and four target values. For each context length, we keep the four values fixed while varying their distribution across chunks. Here, L-1, L-2, and L-4 indicate that the four values are distributed across 1, 2, and 4 chunks, respectively, at a fixed context length LL.

The results show that RelaxKV maintains near-full-recomputation accuracy across all evaluated settings (99.25%–100%). These results demonstrate that RelaxKV remains robust as evidence density decreases with context length and supporting evidence becomes more dispersed across chunks.

ModelMethod4K-14K-24K-48K-18K-28K-416K-116K-216K-432K-132K-232K-4
Qwen3-14BFull Recompute100100100100100100100100100100100100
Naive Concat99.2549.7534.25985038.591.7548.7539.7530.7533.2525.25
CacheBlend99.2560.7558.259956.55686.755555.2551.253426
KVShare9650.53798.2549.7537.575.2550.2541.7546.53427.25
ProphetKV99.7510097.7510010098.7510099.599.7599.259998.75
RelaxKV99.7510099.510010099.7510099.2510099.59999.75

[1] https://github.com/NVIDIA/RULER.

Comments on the paper

2 comments

Dear Authors,

The author-reviewer discussion period is ending soon, but no rebuttal has been submitted yet. We encourage you to respond to the reviewers' comments and address their key concerns before the discussion period closes.

AC

AuthorsOpenReview ↗

Gentle Follow-up on Our Rebuttal

Dear Reviewers cL3n, ihS5, and FCgW,

Thank you very much for your time and effort in reviewing our submission. We sincerely appreciate your valuable comments and constructive suggestions, which have helped us improve our work.

As the author–reviewer discussion period will close in approximately one day, we would be grateful if you could kindly revisit our rebuttal and let us know whether your concerns have been adequately addressed. We would be happy to provide any further clarifications if needed.

Thank you again for your time and consideration.

Best regards, The Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.