acceptodds
Under review as a conference paper at ICLR 2027

Rent or Recompute?: Learning-Augmented Placement of Agent KV Caches Across Memory and Shared Storage Tiers

Abstract

LLM agents keep contexts of 100K tokens or more alive across dozens of turns. Most of that time, they sit idle, waiting on tool calls, sub-agents, and people. Each idle gap forces a serving system to decide whether a session's KV cache is worth keeping and where it should live. Production traces show that prefix-cache hit rates collapse once a session idles for minutes, and a miss costs several times the pre-fill for the next turn. Today, this decision is made based on recency or fixed time-to-live rules. We show that placing an idle session's KV cache across GPU memory, host memory, and storage is an instance of multi-state dynamic power management. Each tier is a state with a rent rate. Returning from a tier, by reload or by recomputation, is its wake-up cost. This lets us import learning-augmented ski-rental guarantees directly: a policy that consumes a predicted idle gap is -consistent and -robust per gap, for a trust parameter . We train an idle-gap predictor on features observable when a request finishes, and evaluate it on 346K idle gaps from 4,265 real coding-agent sessions, split by user. Whether a gap ends in a tool result or a human reply is observable, and it matters (seconds versus minutes). The length of the gap within each kind is only weakly predictable: 42% of tool gaps and 24% of human gaps fall within of the prediction, against 26% and 23% for a per-tool lookup table. On held-out users, the learning-augmented policy meets its per-gap bounds exactly. At a reference parameter set, a hedged policy with a validation-tuned trust parameter uses 11% fewer GPU-seconds than the best prediction-free policy; exact predictions would save 20%. Using the same predictions without hedging costs the clairvoyant optimum. A closed-form crossover context length, , says when a storage tier beats recomputation. We measured its inputs with vLLM for an 8B model on H100, A100, and L40 GPUs, and for a 72B model on four H100S GPUs, across five kinds of storage paths from seven clients on three clusters. The binding quantity is usually the client's network link, not the storage system: tiers cap at the link (1.2 GB/s on 10 GbE nodes, 3.0 GB/s on 25 GbE). At measured prefill costs, an L40 breaks even against every mount we measured; an A100 against a 10 GbE NFS mount at 34K tokens; and an H100 against a 25 GbE mount at 32K tokens, or a node-local NVMe at every length. The 72B model prefills slower than the 8B model because tensor parallelism over PCIe returns only a third of the four GPUs. It therefore needs only 1.1 GB/s, and a 1.3 GB/s NFS mount beats recomputing it at every length. Re-running the policy comparison with the measured parameters, where prefill is 4–28 costlier per token than the assumed reference set, removes the learned policy's advantage (0-3%). With a 1 s host-memory round trip against a 9-32s re-prefill, the decision points move into the tails, where the predictor has no skill. Our analysis identifies this as the regime where prediction has the least to decide, and the advantage returns (10%) only when host memory becomes expensive. Because the policy consumes only the predicted tier, the measurements turn into targets: a predictor must flag the long tool calls that a regression on gap length misses, and a link must deliver 2.5 GB/s to an H100 for storage to pay. We release the harness, simulator, and predictor as a testbed for both.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
generative models, infrastructure, supervised representation learning, hardware

Reviews

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

This paper examines where to keep the KV caches of inactive agent sessions: in GPU memory, host memory, storage, or nowhere (by recomputing them later). The authors model these choices as a multi-state dynamic power-management problem. Each tier has a cost for retaining a cache and a cost for bringing it back into use, allowing the paper to draw on learning-augmented ski-rental algorithms with stated consistency and robustness guarantees.

Using real coding-agent traces, the authors train a predictor based on information available when a request ends. The type of request—tool call or human interaction—provides a useful signal, but the model has trouble estimating the idle duration within each category. With the paper’s reference costs, a policy tuned on validation data cuts modeled GPU-seconds by roughly 11% compared with the prediction-free lower-envelope policy. That improvement mostly vanishes when the authors use measured hardware costs instead. The paper also derives a crossover context length for loading versus recomputation and measures the relevant costs across several GPU and storage setups.

Critical strengths
  • This is a worthwhile systems problem. Keeping KV caches for inactive agent sessions consumes expensive memory, while evicting them too soon can mean substantial recomputation and added delay when a session resumes.
  • The model is clear and easy to interpret. Treating each cache tier in terms of holding and wake-up costs connects the problem to established online algorithms and makes the assumptions behind the guarantees visible.
  • The trace evaluation takes care to avoid leakage and separates data by user. In particular, excluding tool latency observed during an idle interval is important for making the predictability results credible.
Critical weaknesses
  • The case for deploying the learned policy is still narrow. Its roughly 11% gain is tied to a chosen reference configuration; across the measured configurations, the improvement is only 0–0.9%. This leaves limited evidence that prediction is preferable to a robust policy that does not use predictions.
  • The per-session model does not account for shared capacity limits or competition among sessions. Host-memory pressure is captured by a fixed rent parameter, even though that choice has a strong influence on whether prediction and storage help.
  • The evaluation pairs trace simulation with component-level measurements, rather than running the policy inside a serving system. As a result, modeled GPU-seconds alone do not demonstrate improvements in throughput, resource use, or latency under concurrent workloads.
Questions for authors

Thank you for a well-prepared submission. I found the paper’s formulation clean and its analysis of when prediction helps—and when it does not—careful and useful. The combination of real traces, explicit robustness guarantees, and measured hardware costs gives readers a helpful view of the problem. I am generally positive about the paper and lean toward acceptance.

My main reservation is about the operating conditions in which the learned policy is actually useful.

The measurements change the picture suggested by the reference configuration. When host-memory transfers are inexpensive relative to recomputation, the prediction-free policy already performs well, and validation mostly opts not to trust the predictor. At present, the strongest practical takeaway may therefore be a robust prediction-free placement policy, along with guidance on when learning is worth adding.

It would help to make that deployment choice more concrete. How can a system relate the host-memory rent parameter to observable resource pressure, and decide whether it is in a regime where prediction is likely to save much? The roughly 10% gain at higher host-memory rent is intriguing, but its real-world relevance depends on whether those rent values occur in practical fleet settings.

I also have several questions:

  • How should a deployed system set the holding-cost parameters? The interpretation of HBM occupancy is intuitive, but the DRAM and storage rents still seem to be modeling choices. Could they be tied to queueing effects, memory pressure, or useful work displaced by retaining caches?
  • What happens when host memory has a hard capacity limit? Independent per-session decisions could send many caches to DRAM at once, creating contention or forcing evictions that are not covered by the current guarantees.
  • Could the authors compare the duration regressor with a direct breakpoint classifier or a cost-sensitive tier predictor? Because duration accuracy does not necessarily translate into good placement decisions, this comparison could show whether the modest gains come from limited predictive signal or from optimizing the wrong target.
  • How much do the learned policy and trust parameters vary across user splits? The trace contains many gaps but only 43 developers, and the appendix includes a case where the validation-selected trust level does not transfer. Repeated user-level splits with confidence intervals would help establish how robust the results are.
Reviewer_3WoPOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

This work studies where to keep a KV cache during the idle gaps of agent sessions. The authors view this as multi-state dynamic power management, where each tier is a state with a rent rate, and import learning-augmented ski-rental guarantees to obtain a policy with provable consistency and robustness. They train an idle-gap predictor on public coding-agent traces and show that a hedged policy saves GPU-seconds under a reference parameter set. However, with cost parameters measured on real GPUs and storage paths, the advantage of the learned policy largely disappears.

Critical strengths
  1. The cost parameters are actually measured, not assumed, they use four GPU configurations, three clusters, five kinds of storage paths. That is solid work, and the finding that the network link is the real bottleneck is useful.
  2. The authors re-run everything with the measured parameters and report that the learned policy barely saves anything. Reporting it anyway makes the paper much more trustworthy.
Critical weaknesses
  1. The abstract is far too long and hard to follow. It is close to a full page and reads like a dump of every number in the paper (crossover formulas, GB/s per link, token counts per GPU). After reading it I still could not tell what the main claim is: a learned policy, a crossover formula, or a measurement study.
  2. The positive result only exists under the reference parameters, which the authors chose themselves and admit are not a measurement. With the measured parameters, the learned policy saves 0–1% over the prediction-free lower-envelope policy. The learning part of the paper therefore does not deliver on real hardware, and the paper does not include the experiments that would show whether anything is actually learned.
Questions for authors
  1. Where do the reference parameters come from? A sweep over prefill cost would help, so readers can see where the 11% turns into 0%.
  2. How was c1=0.05c_1 = 0.05 chosen? It is a price, not something you can measure, and Table 7 shows the conclusion depends on it. Please justify the value or report results across a range.
  3. The “TTL = predicted gap” baseline is attributed to Continuum, but Continuum only sets TTLs for tool-call gaps and its traces have no human turns. Here it is also applied to human gaps, which is where most of the 5.9× comes from. Is this a fair comparison? What does the baseline get on tool gaps only?
Reviewer_ZSdHOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper formulates KV-cache placement for long-running LLM agent sessions as a learning-augmented multi-state ski-rental problem. The authors model GPU memory, host memory, external storage, and recomputation as alternative states with different retention costs and restoration penalties. Building on established results in learning-augmented online algorithms, the proposed policy uses predictions of agent idle durations to determine cache placement while retaining theoretical consistency and robustness guarantees. The authors train an idle-gap predictor using observable session features and evaluate the framework on idle gaps from different coding-agent sessions. Under reference cost parameters, the proposed policy reduces GPU-seconds by approximately 11% relative to the best prediction-free policy. However, hardware measurements across several GPU and storage configurations reveal that the advantage decreases to approximately 0–3% under measured cost parameters. The paper also derives hardware-dependent crossover conditions for determining when storage-based KV-cache restoration is preferable to recomputation.

Critical strengths

The paper is well written and provides a clear and technically grounded formulation connecting agent KV-cache placement to multi-state dynamic power management. The incorporation of learning-augmented online algorithms is particularly appropriate because agent idle times are inherently uncertain and naive reliance on predictions can result in substantial performance degradation. The theoretical consistency-robustness tradeoff offers a principled mechanism for controlling this uncertainty. Another strength is the careful distinction between information available at decision time and information that would introduce prediction leakage. The use of real coding-agent traces and user-level train-test separation strengthens the evaluation methodology. The negative experimental finding that prediction provides little benefit under some realistic hardware configurations is an important contribution, as it helps identify when sophisticated learning-based placement is actually justified.

Critical weaknesses

The technical novelty of this work is limited. The learning-augmented scheduling guarantees are inherited from existing multi-state ski-rental algorithms, and the paper's theoretical contribution largely consists of mapping KV-cache placement onto an established optimization framework. The empirical benefit of the learned predictor is limited. Even under reference parameters, the improvement over the best prediction-free baseline is not as significant, and the advantage nearly disappears under the measured hardware configurations. This raises questions about whether the additional complexity of training, deploying, and maintaining a predictor is justified in realistic systems. Moreover, the predictor exhibits limited accuracy for idle gap durations, particularly for human-driven interactions, suggesting that the predictive signal may not be sufficiently strong for reliable placement decisions. The per-gap optimization formulation also abstracts away interactions among concurrent sessions, including capacity constraints, shared cache blocks, bandwidth contention, and global eviction decisions.

Questions for authors
  1. . Can the authors identify realistic deployment regimes in which learned placement consistently outperforms simple prediction-free policies by a substantial margin?

  2. Would predicting the optimal placement tier directly, rather than regressing the complete idle duration, improve decision quality and reduce unnecessary prediction complexity?

  3. How would the consistency and robustness guarantees change when multiple sessions compete for finite GPU and host-memory capacity, and eviction decisions become coupled?

  4. Can the authors evaluate an integrated serving implementation under concurrent agent workloads and report end-to-end latency, throughput, and memory utilization improvements?

Reviewer_YvrqOpenReview ↗
Rating
2(+1)
Confidence
2(−1)
Informativeness
2
Presentation
2
Soundness
2(+1)
Read review
Paper summary

This manuscript applies learning-augmented multi-state ski rental to idle agent KV-cache placement across GPU memory, host memory, storage, and recomputation. Each tier has a rent and a wake-up cost in GPU-seconds; a closed-form crossover context length K⋆K^\star indicates when loading from a tier beats recomputation, and a policy built on Antoniadis et al. (2021) is (1+λ)(1+\lambda)-consistent and (1+1/λ)(1+1/\lambda)-robust per idle gap. An idle-gap predictor is trained on features observable when a request finishes and evaluated on 346K idle gaps from 4,265 public coding-agent sessions with a user-level split. Under an author-chosen reference parameter set, the tuned policy uses about 11% fewer GPU-seconds than the best prediction-free policy; with parameters measured on vLLM across several GPUs and storage paths, the saving drops to 0–0.9%.

Critical strengths
  1. The user-disjoint evaluation keeps each user's behavior out of the test set, which makes the predictor and policy results more credible.

  2. The hardware measurements across several GPUs, clusters, and storage paths ground the cost parameters, and the authors transparently report that the gain largely disappears under them. This gives the community a useful reference point.

Critical weaknesses
  1. The model assumes independent sessions and unlimited host memory, leaving capacity coupling and transfer contention untested. It also does not reflect how vLLM/SGLang manage KV in practice: block-level eviction under PagedAttention, shared prefixes with tail-first eviction (so a drop often recomputes only a suffix), and throughput-dependent memory cost under continuous batching. In addition, Eq. (1) sets β3=R(K)\beta_3=R(K), omitting writes incurred before a cache is dropped. Since the guarantees and the reported GPU-second savings are defined relative to this model, they do not directly transfer to a real serving system.

  2. The prefill model is fitted at 2K–32K tokens but used for a 72K median context and 122K–249K crossover estimates. Savings under measured parameters are only 0–0.9%, versus 16–18% with exact predictions, and the tuned policy is evaluated on only six users from one split. Because the measured-parameter gain is already near zero, the remaining positive evidence rests on uncalibrated reference parameters and an evaluation without quantified uncertainty.

Questions for authors
  1. Please evaluate concurrent sessions under finite HBM/DRAM budgets against practical vLLM/SGLang cache-management baselines, reporting memory occupancy, transfer volume, recomputation, throughput, and tail TTFT.

  2. Please charge the transition costs consistently to online and offline policies, recheck the consistency and robustness bounds, and repeat the policy comparisons.

  3. Please directly measure longer contexts, including 64K and 128K, and reassess crossover uncertainty and policy rankings.

  4. The learned, per-type, and per-signature predictors are not compared through a clearly matched tuning procedure. Please use identical hedging and λ\lambda-selection budgets, and add tuned multi-tier TTL and prediction-free randomized baselines.

  5. Please test a cost-sensitive tier classifier or breakpoint-crossing predictor to determine whether log-duration regression misses the decisions that matter, particularly expensive long gaps.

  6. LA-Bayes selects tiers by expected cost using three predicted quantiles, but these do not uniquely determine the required expectations. Please specify the distributional approximation and tail treatment, and test sensitivity to alternative assumptions.

  7. Please repeat user-level splits, select λ\lambda exclusively on validation users, and report user-clustered confidence intervals.

Clarifications:

  1. Was the reported 1.72× per-type result tuned in the same way as the learned predictor?

  2. Table 4's description of test-set tuning should be reconciled with Section 4.3.

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

The paper casts the placement of an idle agent session's KV cache (HBM, host DRAM, storage, or drop and recompute) as multi-state ski rental, with rents and wake-up costs measured in GPU-seconds. It applies the learning-augmented policy of Antoniadis et al. (2021), which is (1+λ)(1+\lambda)-consistent and (1+1/λ)(1+1/\lambda)-robust per gap, and predicts each idle gap with a gradient-boosted quantile regressor that uses only features available when a request finishes. The policies are simulated on 46,700 held-out gaps from TraceLab coding-agent traces split by user. At a reference parameter set, a validation-tuned policy uses 10.8% fewer GPU-seconds than the prediction-free lower envelope (LE). With prefill costs and tier bandwidths measured with vLLM on H100, A100 and L40 GPUs, the advantage falls to 0–3%. A closed-form crossover context length (Prop. 1) supports the claim that the client's network link, not the storage system, decides when a storage tier beats recomputation.

Critical strengths
  1. The paper reports its own negative result and avoids the obvious shortcuts. Traces are split by user, and the tool-latency field is excluded because it is measured during the gap, even though it would raise tool-gap accuracy from 42% to 85%. Table 4 then shows the advantage disappearing at measured parameters. With these controls in place, the released harness and simulator are a fair testbed for other gap predictors rather than a setup tuned to this one.

  2. Table 8 shows that clients behind a 10 GbE link read NFS and local SSD at about 1.1–1.2 GB/s regardless of the storage system, and the read-only crossovers in Table 3 follow from the reported aa, bb and bandwidths (I reproduced 34K tokens on the A100 and about 250K on the H100 parallel file system). The storage question therefore becomes a per-server bandwidth target that others can check on their own hardware.

Critical weaknesses
  1. The learned predictor is not shown to reduce cost at parameters the stated hardware can reach. At the four measured configurations in Table 4, the tuned policy saves 0–0.9% over LE, and LA-Bayes is up to 5% worse. The 10.8% saving holds only at the reference set, whose a=10−5a=10^{-5} s/token implies 100K tokens/s of 8B prefill, above the dense BF16 peak of an H100 SXM (989989 TFLOPS$/(2\times 8\times 10^{9})\approx 62$K tokens/s). Even at that set, λtool=1\lambda_{\text{tool}}=1 reduces the tuned policy to LE on tool gaps. On human gaps, the predictor is within 2×2\times for 24% of gaps against 22% for the per-type median, and the per-type median is evaluated only at λ=0.5\lambda=0.5. Sec. 4.1 describes Thm. 1 as the deterministic case of Antoniadis et al. (2021, Lemma 3), so the contribution depends on the prediction, and the paper does not show that the prediction adds value beyond the observable tool/human flag.

  2. Write costs are charged inconsistently, and both practical conclusions depend on them. Sec. 3.1 charges a policy that ends in tier jj only βj\beta_j, with β3=R(K)\beta_3=R(K), so the host-DRAM write W1W_1 paid on an HBM$\to$DRAM$\to$drop path is not counted. At the reference set with K=150K=150K, W1≈0.98W_1\approx 0.98 s against R(K)=2.4R(K)=2.4 s, so LE just after its DRAM-to-drop breakpoint costs about 2.41 OPT2.41\,\mathrm{OPT}. The per-gap maxima of exactly 1+1/λ1+1/\lambda in Tables 2 and 5 are therefore a consequence of the simulator using the proof's accounting, not an independent check. Prop. 1 also omits the write leg that β2\beta_2 includes. With the measured write rates, the A100 NFS crossover moves from 34K to about 112K tokens, and the 72B research-NFS result changes from "every length" to about 311K tokens. Both the guarantee transfer and the storage targets stated in the Abstract would need to be re-derived with writes charged.

Questions for authors
  1. On the same test half and under the same tuned (λtool,λhuman)=(1,0.25)(\lambda_{\text{tool}},\lambda_{\text{human}})=(1,0.25), what cost/OPT do the per-type median and LA-Bayes using the per-signature lookup's quantiles reach? If either comes close to 1.54, what does the learned regressor add?

  2. Does the simulator charge W1W_1 (and W2W_2) when a session passes through DRAM or storage before it is dropped? If not, please report cost/OPT and the per-gap maxima of LE and LA with those writes charged, and state whether Thm. 1 still holds.

  3. Should K⋆K^\star in Prop. 1 include the write leg that β2\beta_2 charges? If writes are assumed to be off the critical path or amortized across turns (only appended tokens rewritten), please model that in (1). Otherwise, please give K⋆K^\star with writes charged for Table 3.

  4. How was a=10−5a=10^{-5} s/token chosen for the reference set? Is there a measured configuration (for example SXM with NVLink, FP8, or batched prefill) whose breakpoints fall in the range where the tool/human flag changes the policy's decision?

  5. λ\lambda is selected on 6 users and reported on the other 6 from one seed-0 split, and at c1=1c_1=1 the tuned policy is 12.9% worse than LE on the test half (Table 7). What is the spread of the 10.8% saving over several random user splits?

One suggestion beyond these questions: measuring N⋆N^\star for Prop. 2 under contention would test the fan-out claim, which is currently only derived.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.