acceptodds
Under review as a conference paper at ICLR 2027

TailAlloc: Allocating the KV Cache by Tail-Risk Contribution, Not Standalone Risk

Abstract

Long-context inference caches key-value (KV) pairs for every token read, and at long contexts that cache dominates serving cost. Quantisation and sparse attention shrink it without choosing how many tokens each attention head keeps; KV eviction does, under a fixed budget, so a scoring rule picks which tokens a head discards and an allocator sets how much budget it gets. Every published allocator minimises a sum of per-head risks, and that sum is the wrong quantity: it is the model's tail risk only when heads are comonotonic, failing on the same requests, and otherwise overstates it by a median 55% over six captures on three model families. What governs the tail is each head's Euler risk contribution, its average error on the requests where the model's total error is worst; by it, 6–38% of heads are tail hedges whose error moves against the model's, and rescored on the tail risk itself no published allocation beats a uniform budget. We therefore propose TailAlloc, which estimates these Euler risk contributions on a calibration set and allocates against them with a marginal-gain greedy algorithm. This replaces direct tail averaging with a covariance-based closed-form estimator where tail samples are scarce. Against the exactly solved optimum of the separable objective — the strongest published allocator, its dual gap certified — TailAlloc wins 124 of 140 rows under leave-one-capture-out, by a median 1.96 percentage points. Task metrics move too: a contribution-built allocation gains +2.59 [+1.78, +3.40] over a matched uniform budget on RULER at 4096, and on LongBench it clears an equal split on two captures of six, the separable optimum on none. We further note that when design-space effects fall below an evaluation's resolution, average benchmark scores do not provide evidence for the corresponding design choice.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
KV cache, long-context inference, budget allocation, Conditional Value-at-Risk, Euler risk contributions, evaluation methodology

Reviews

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

The paper argues that current KV-cache budget allocators for long-context LLMs optimize the wrong objective: they minimize a sum of per-head standalone tail risks, which only matches the model’s aggregate tail risk under comonotonic failures across heads. The authors propose TailAlloc, which allocates budgets by each head’s Euler risk contribution—expected head error conditional on the model’s aggregate tail—estimated efficiently and optimized with a marginal-gain greedy. Empirically, TailAlloc consistently reduces aggregate tail risk vs. the exactly-solved separable optimum across six captures and three model families.

Critical strengths

S1. Easy to follow: TailAlloc is a training‑free method that is easy to reproduce.

S2. Novelty: The paper introduces Euler risk contributions from risk theory into KV cache allocation, which has some research value.

Critical weaknesses

W1. Although TailAlloc improves the tail-risk metric over SepAlloc, its task-level advantage remains limited and inconsistent. On RULER-4096, the 90% confidence interval for the improvement is [−0.52, +0.83], which includes the possibility of a performance decrease. Thus, the current evidence does not sufficiently establish that optimizing aggregate tail risk yields consistent downstream task improvements.

W2. The description of the calibration dataset is insufficient, despite its importance for offline KV cache eviction methods. The resulting KV cache budget allocation is likely to depend strongly on the characteristics of the calibration dataset.

Questions for authors

Q1. The paper optimizes a tail-risk surrogate constructed from local attention errors, but does not establish a theoretical connection between improvements in this surrogate and reductions in the sum of errors across all queries. The downstream task experiments also suggest that improvements in the surrogate do not consistently translate into better task performance. Could the authors provide theoretical analysis or empirical evidence clarifying the relationship between this tail-risk surrogate and the total error across all queries?

Q2. TailAlloc relies on offline calibration, so the quality of its budget allocation is likely to depend strongly on the characteristics of the calibration corpus. However, the results in Section 6.5 show that calibration on in-distribution text does not outperform novel-based calibration in the reported comparisons. How can practitioners select an effective calibration corpus without repeatedly running downstream evaluations?

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

This paper studies how to allocate a fixed KV-cache budget across attention heads. Existing methods minimize the sum of each head’s standalone tail risk, but this generally differs from the tail risk of the model’s aggregate error. The paper proposes TailAlloc, which allocates cache using each head’s Euler risk contribution—its average error when the model’s total error is in the worst tail. TailAlloc estimates these contributions with a covariance-based regression and alternates between contribution estimation and budget allocation. Across six captures and three model families, it improves the aggregate tail-risk objective over a strong separable baseline. However, its advantage on downstream benchmarks is limited and inconsistent.

Critical strengths
  1. This paper identifies an important mismatch between per-head risk and aggregate model risk and provides a principled formulation based on Euler risk contribution.

  2. This paper shows consistent improvements on the proposed aggregate-error objective.

  3. The authors transparently reports negative and inconclusive results and TailAlloc has low offline computational overhead.

Critical weaknesses
  1. TailAlloc clearly improves over uniform allocation on some settings, but its advantage over the separable baseline is usually insignificant. Adding more direct TailAlloc-versus-SepAlloc experiments with larger sample sizes and more benchmarks will enhance this paper.

  2. The reported 140 rows are highly correlated variants of six captures. Evaluating more independent captures will be helpful.

  3. The greedy subproblem is exact, but the complete non-separable procedure is heuristic.

  4. The experiments cover only 7B–8B models, and calibration transfer is unstable.

Questions for authors

refer to weaknesses

Reviewer_trEbOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how to allocate a fixed token budget across attention heads for KV-cache eviction in long-context inference. It shows that the "sum of per-head risks" minimized by existing allocators is not the model's tail risk, and proposes TailAlloc, which allocates budget according to each head's Euler risk contribution.

Critical strengths

To be honest, this paper reads like it was written by AI and is rather disorganized; apart from the fact that the research question it addresses is fairly important, I don't see any real strengths in it.

Critical weaknesses
  1. The experiments are insufficient. It lacks direct task-based comparisons between TailAlloc and SepAlloc across various compression ratios. Given that existing literature (e.g., AdaKV, LU-KV) has already demonstrated that non-uniform allocation schemes outperform uniform ones, it would be beneficial to include a comparison between TailAlloc and SepAlloc in Figure 3. Furthermore, the absence of experiments covering different tasks at varying compression ratios makes it difficult to determine whether the core modifications proposed in this paper remain effective across different compression intensities. It is recommended to provide a comparative analysis of performance across multiple sub-tasks within the LongBench and RULER benchmarks at various compression ratios.

  2. Insufficient validation across different token-scoring criteria. Although the paper employs multiple token-selection strategies, it fails to present a systematic evaluation of TailAlloc/SepAlloc using these strategies on the LongBench and RULER benchmarks. Existing experiments primarily focus on assessing the risks associated with proxy-based approaches, but the authors do not directly demonstrate that TailAlloc can improve generation quality when different, practical token-selection rules are applied.

  3. The technical novelty is limited. The proposed framework looks very similar with LU-KV, with new contributions primarily centered on the objective function and the estimation of risk-related contributions. Therefore, the authors need to illustrate the differences between SepAlloc and the original LU-KV, and to include a performance comparison against the original LU-KV on LongBench and RULER under identical experimental conditions.

Questions for authors
  1. What's the key difference between the proposed method and LU-KV. How is the performance comparison results with LU-KV.
  2. What's the performance of the proposed method across different token-scoring criteria?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.