arXiv：cs.LG· Shivam Gupta·· 3 小时前AI 评分35
面向前缀缓存语言模型服务的精确内存-时间优化
Exact Memory-Time Optimization for Prefix-Cached Language Model Serving
AI 导读
研究者提出 Prefix-Certificate Retention（PCR），一种针对静态、分组、访问重置超时的精确有限轨迹形式化方法，将可用前缀收益建模为以超时阈值和前置命中证书为前置条件的节点，最大权闭合问题归约为一次最小割，图规模与块查找次数和超时选择数线性相关。
正文
Abstract: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.
| Comments: | 16 pages, 5 figures. Code and reproducibility artifacts: this https URL |
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.02766 [cs.LG] |
| (or arXiv:2610.02766v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.02766 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Shivam Gupta [view email]
[v1]
Fri, 2 Oct 2026 03:47:10 UTC (121 KB)
来源：arXiv：cs.LG · arxiv.org