cs.LGNov 2, 2026

Semantic Caches for LLM Web Services Leave Their Error Budget Unspent

Authors: Hanshuai Cui, Qianli Ma, Zhiqing Tang

Organizations: School of Artificial Intelligence, Beijing Normal University, Beijing 100875, China · Institute of Artificial Intelligence and Future Networks, Beijing Normal University, Zhuhai 519087, China

Abstract

Web services built on large language models (LLMs) receive many paraphrases of earlier queries, which a semantic cache answers from stored responses. A reused answer can be wrong, so wrong answers must stay below a share δδ of the queries. Existing caches reuse above a fixed similarity threshold or, like vCache, learn a per-entry rule that bounds each query's error by δδ. However, fixed thresholds break the budget on new streams, and per-entry rules need labels on every entry before reusing it. We find an unspent error budget, as vCache realizes only 12-55% of δδ on three public query streams. Surplus spends this budget where reuse is most likely correct. It ranks queries by a risk score shared across paraphrase clusters and opens risk bins as far as an audited error estimate allows. Free labels from every LLM call and a ledger of realized errors keep this threshold safe under drift. On five streams, including ORCAS search queries, Surplus holds δδ in every test cell, which no baseline does. On the shuffled streams it serves 40% more hits than vCache, and its pooled hit rate beats the best baseline holding δδ in each cell by 4.10 points. In a vLLM testbed it cuts the mean latency by 31.59% at the highest load, against 23.67% for vCache.

Figures & tables

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Multi-Turn Semantic Caching for Low-Cost LLM Serving

    Oct 31, 2026Baran Atalar, Selly Beyene, Xutong Liu +1Semantic CachingLLM Serving

  2. Risk-Constrained Freshness-Aware Semantic Caching for Open-Web Retrieval-Augmented LLMs

    Jul 5, 2026Muhammad Mansoor, Tahir Ahmad, Yeo-Chan YoonLLM Inference EfficiencyRetrieval-Augmented Generation

  3. Beyond Query Similarity: Safety-Conditioned Cache Routing for LLM Response Reuse

    Nov 7, 2026Shilong Pan, Zhiliang Tian, Weiguo Chen +2Semantic CachingSafety-Utility Trade-Off in Language Models