# Exact Memory-Time Optimization for Prefix-Cached Language Model Serving

arXiv: https://arxiv.org/abs/2610.02766 · HTML: https://mlsanity.com/paper/2610.02766/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 16 references that are in the map.
- First posted on arXiv 2 Oct 2026.

## Builds on (most cited first, 8 of 8)

- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [SGLang: Efficient Execution of Structured Language Model Programs](https://mlsanity.com/paper/2312.07104/) (2023)
- [Cost-Efficient Large Language Model Serving for Multi-turn Conversations with CachedAttention](https://mlsanity.com/paper/2403.19708/) (2024)
- [SAGA: Workflow-Atomic Scheduling for AI Agent Inference on GPU Clusters](https://mlsanity.com/paper/2605.00528/) (2026)
- [Soft-TTL: Time-Varying Fractional Caching](https://mlsanity.com/paper/1807.03537/) (2018)
- [Learning Agent Execution for KV-Cache Management in Agentic Serving](https://mlsanity.com/paper/2608.14624/) (2026)
- [Dependency-Aware Online Caching](https://mlsanity.com/paper/2401.17146/) (2024)
- [Adaptive Multi-Objective Tiered Storage Configuration for KV Cache in LLM Service](https://mlsanity.com/paper/2603.08739/) (2026)

## Abstract (arXiv)

Retaining language-model prefix states trades recomputation against storage time. Optimizing each cached block independently can overcount savings: a resident block is usable only when the required preceding prefix is also available. We introduce Prefix-Certificate Retention (PCR), an exact finite-trace formulation for static, grouped, reset-on-access timeouts. Usable-prefix rewards become nodes whose prerequisites are timeout thresholds and preceding hit certificates. The resulting maximum-weight closure reduces to one minimum cut, with graph size linear in the number of block lookups and timeout choices. A breakpoint theorem extends the construction to all nonnegative timeouts without discretization error. We also derive a linear-time-in-grid-size dynamic program for ordered timeouts and bounds that certify the cost of this restriction. Exhaustive small-instance checks and chronological replay of 39,632 public Mooncake requests validate the formulation. On the fixed grid, ordered timeouts attain the unrestricted training optimum in 118 of 120 trace-grouping-price cases. Heterogeneous retention improves several held-out memory-time tradeoffs, but finer training optimization does not uniformly improve transfer. The contribution is a tractable optimization model and an auditable benchmark for retention policies; the experiments measure usable prefix blocks and storage time, not GPU latency.