Semantic Caches for LLM Web Services Leave Their Error Budget Unspent
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
| Shuffled streams | Drifting streams | ||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| LmArena | Classification | SearchQueries | ClassificationSorted | Combo | Worst | ||||||||||||
| Method (%) | 0.5 | 1 | 2 | 0.5 | 1 | 2 | 0.5 | 1 | 2 | 0.5 | 1 | 2 | 0.5 | 1 | 2 | Held | err./ |
| GPTCache 0.97 ( Bang, 2023 ) | 65.612 | 65.612 | 65.612 | 15.947 | 15.947 | 15.947 | 23.197 | 23.197 | 23.197 | 16.260 | 16.260 | 16.260 | 0.324 | 0.324 | 0.324 | 9/15 | 10.326 |
| GPTCache 0.98 ( Bang, 2023 ) | 51.507 | 51.507 | 51.507 | 15.411 | 15.411 | 15.411 | 16.988 | 16.988 | 16.988 | 15.613 | 15.613 | 15.613 | 0.251 | 0.251 | 0.251 | 9/15 | 7.990 |
| GPTCache 0.99 ( Bang, 2023 ) | 32.335 | 32.335 | 32.335 | 14.803 | 14.803 | 14.803 | 8.558 | 8.558 | 8.558 | 14.933 | 14.933 | 14.933 | 0.135 | 0.135 | 0.135 | 10/15 | 5.173 |
| Static ( Bang, 2023 ) | 13.534 | 13.534 | 32.335 | 27.823 | 33.565 | 40.944 | 8.558 | 16.988 | 23.197 | – | – | – | – | – | – | 0/9 | 2.706 |
| Hit change | Worst err./ | |||
| Variant | Shuffled | Drifting | Shuffled | Drifting |
| w/o cluster sharing | 2.82 | – | 0.710 | – |
| w/o stratified prior | 0.645 | – | 0.722 | – |
| w/o admission | 1.34 | +5.72 | 0.693 | 0.680 |
| w/o free labels | 0.900 | +0.137 | 0.733 | 0.816 |
| w/o ledger | +0.412 | +1.45 | 0.765 | 0.924 |
| Method | Hit | Err./ | Hit | Err./ | Hit | Err./ |
|---|---|---|---|---|---|---|
| vCache ( Schroeder et al., 2026 ) | 1.64 | 0.513 | 3.00 | 0.460 | 6.06 | 0.409 |
| Surplus | 2.53 | 0.482 | 4.82 | 0.652 | 7.87 | 0.641 |
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
| Setting | Value |
|---|---|
| Risk bins | 48, 12 per decade from |
| Control interval | 100 decisions |
| Audit rate | 0.2 |
| Target share | 0.75 |
| Bound width | 1.5 |
| Prior strength | 4 |
| Setting | (%) | vCache | Surplus | Gain | CI |
|---|---|---|---|---|---|
| LmArena, gte | 0.5 | 9.17 | 27.09 | +17.92 | [17.46, 18.36] |
| 1 | 17.71 | 30.78 | +13.07 | [12.56, 13.57] | |
| 2 | 32.55 | 36.80 | +4.25 | [3.85, 4.63] | |
| LmArena, TE3-small | 0.5 | 11.04 | 35.21 | +24.16 | [23.85, 24.49] |
| 1 | 20.86 | 38.31 | +17.44 | [17.13, 17.76] | |
| 2 | 37.94 | 43.66 | +5.72 | [5.22, 6.27] |
| Classification | SearchQueries | |||||
|---|---|---|---|---|---|---|
| Method (%) | 0.5 | 1 | 2 | 0.5 | 1 | 2 |
| MVR-cache | 12.27 | 16.91 | 33.09 | 1.75 | 3.17 | 6.06 |
| vCache, MVR code | 9.14 | 16.46 | 32.49 | 1.67 | 3.01 | 5.75 |
| vCache, our code | 8.43 | 15.62 | 30.48 | 1.59 | 2.87 | 5.46 |
| Surplus | 13.26 | 19.43 | 31.13 | 3.49 | 5.95 | 10.68 |
| Decision (ms) | ||||||
|---|---|---|---|---|---|---|
| Stream | Method | Median | p99 | Mean | Wall (s) | MB |
| LmArena | vCache | 7.58 | 14.23 | 5.62 | 1480 | 558 |
| Surplus | 0.402 | 11.43 | 1.89 | 1323 | 560 | |
| Classification | vCache | 0.441 | 13.27 | 4.89 | 670 | 504 |
| Surplus | 0.327 | 10.67 | 0.870 | 1322 | 578 | |
| SearchQueries | vCache | 0.028 | 13.77 | 3.03 | 6555 | 1158 |
| Err./ | |||||||
| Stream | (%) | vCache | Surplus | Best baseline | Hit (%) | Gain | CI |
| LmArena | 0.5 | 0.144 | 0.463 | vCache | 8.37 | +13.77 | [12.87, 14.63] |
| 1 | 0.122 | 0.520 | vCache | 16.35 | +9.16 | [8.33, 10.15] | |
| 2 | 0.131 | 0.624 | vCache | 30.49 | +1.94 | [1.18, 2.77] | |
| Classification | 0.5 | 0.538 | 0.487 | GPTCache 0.97 | 15.95 | +1.52 | [0.86, 2.54] |
| 1 | 0.499 | 0.626 | Conformal | 19.21 | +6.28 | [4.38, 8.48] | |
| Stream | Method | Hit | Err./ | Hit | Err./ | Hit | Err./ |
|---|---|---|---|---|---|---|---|
| LmArena, | vCache | 3.37 | 0.533 | 6.70 | 0.574 | 13.63 | 0.643 |
| order 1 | Surplus | 4.97 | 0.615 | 8.46 | 0.652 | 12.67 | 0.629 |
| LmArena, | vCache | 3.49 | 0.568 | 6.67 | 0.517 | 13.13 | 0.554 |
| order 2 | Surplus | 4.93 | 0.631 | 8.84 | 0.680 | 13.03 | 0.616 |
| LmArena, | vCache | 3.47 | 0.603 | 6.56 | 0.494 | 13.21 | 0.571 |
Semantic Caching
Semantic caching reuses results for meaningfully similar queries to reduce the latency and cost of AI, retrieval, and database systems.
See all 25 papers