← Back to all news
arXiv Machine Learning

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

The paper introduces Prefix‑Certificate Retention (PCR), an exact optimization framework for deciding which prefix states of a language model to cache in order to balance recomputation and storage time. PCR models usable‑prefix rewards as nodes with prerequisites tied to timeout thresholds and preceding hit certificates, reducing the problem to a single minimum‑cut graph whose size scales linearly with block lookups and timeout choices. The authors provide a breakpoint theorem that extends the construction to all nonnegative timeouts without discretization error, a linear‑time dynamic program for ordered timeouts, and empirical validation on 39,632 public Mooncake requests, showing that ordered timeouts achieve the unrestricted optimum in most trace‑grouping cases and that heterogeneous retention can improve memory‑time tradeoffs. "whyItMatters":"The study offers a tractable, auditable optimization model for retention policies that directly measures usable prefix blocks and storage time, providing a concrete benchmark for evaluating memory‑time tradeoffs in language‑model serving."

Related stories

arXiv Machine Learning
Sep 25

When Fancy Eviction Fails: Rethinking Cache Replacement For LLM Prefix Reuse

The paper investigates cache replacement strategies for large language model (LLM) prefix reuse, analyzing production traces from two companies and testing 14 eviction algorithms in both high-bandwidth memory (HBM) and large memory-pool environments. It finds that sophisticated policies designed for traditional caches offer little advantage over simple LRU, because prefix reuse is largely driven by the regular pacing of active sessions, making recency a strong predictor. The study also highlights new challenges such as heavy-tailed session footprints and variable miss costs, and proposes a compute-savings ratio along with two offline oracles to better quantify these effects, suggesting that effective prefix-cache management should combine recency with selective quick demotion, compute-aware partial eviction, and capacity-dependent granularity.

By Yiyu Liu, Minlan Yu, Juncheng Yang
llmsagents
More like this →
arXiv Machine Learning
Sep 18

PrefixBench-H100: Characterizing Prefix Reuse and Time-to-First-Token in H100 LLM Serving

PrefixBench-H100 is a reproducible benchmark that evaluates how reusing prompt prefixes affects LLM serving performance on NVIDIA H100 GPUs. It tests two popular runtimes (vLLM and TensorRT-LLM) across varied workloads, measuring metrics such as time-to-first-token, latency, throughput, cache hits, and GPU memory usage. The study identifies when prefix reuse significantly reduces first‑token latency and when cache pressure diminishes those gains, noting that cache effectiveness is largely unaffected by concurrency or output length, while differences arise mainly in scheduling.

By Omkar Shewale, Deepak Kumar, Divakar Kumar Yadav
llmsragagentsefficiencybenchmarks
More like this →