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
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
Figure 1. Surplus serves this Web search paraphrase within δ , while a fixed threshold overspends δ and a per-entry bound calls the LLM. Its cached entry holds one label. Example schematic. The query concrete cost per cubic yard matches the cached query concrete price per cubic yard with similarity 0.991, and that entry holds one label of its own. Three lanes follow the query. A fixed threshold serves the cached answer, and its error bar runs past the budget. A per-entry bound calls the LLM because the entry has a single label, a missed reuse, and its error bar fills only part of the budget. Surplus serves the cached answer from a risk bin that pools labels across entries, and its error bar stays within the budget.
Figure 2. Existing caches waste or break the error budget. (a) An entry serves hits only after four own labels. (b) Reusable queries still reach the LLM. (c) A prefix-calibrated threshold breaks the budget under drift. Three schematic cards. (a) Few own labels. Five cache entries hold one, two, zero, eight and three labels of their own in a row of four slots, and only the entry with eight labels serves a hit while the others call the LLM. (b) Reuse goes to the LLM. Six queries arrive over time, reusable ones marked with a cache card, and only the first reusable query hits while the next three reusable queries still call the LLM, marked as missed reuse. (c) Prefix threshold drifts. A threshold is calibrated on a prefix of class A and then frozen with a lock, and as classes B to E arrive the errors pile up past the budget line delta.
Figure 3. The three failures of Figure 2 measured at δ=1% on the test streams LmA., Cls. and SQ. Three measured panels. (a) Bars give the share of vCache decisions whose nearest entry has fewer than four labels of its own, 33, 35 and 64 percent on LmArena, Classification and SearchQueries. (b) Grouped bars give the hit rate of a per-entry hindsight oracle, vCache and Conformal on the three streams, with the oracle several times higher. (c) Lines give the cumulative error over delta along ClassificationSorted for vCache, GD and Conformal on a log scale, with Conformal rising far above the dashed line at one while vCache and GD stay below it.
Figure 4. Overview of Surplus. Each query gets a shared risk score and is served from an open risk bin or sent to the LLM, whose answers become free labels. System diagram. Top left, a cache state table lists each entry with a short segmented bar and a count of its own labels, dark for correct and light red for wrong, its cluster and its risk bin, and a dashed row shows a query that an LLM call inserted into its cluster. Three bands follow. Rank embeds a query, finds its nearest entry with similarity s and its cluster, scores a pessimistic risk r and places the query in a risk bin ordered from low to high risk. Decide serves the cached answer when the bin is open, that is below the largest open bin J, and an audit coin sends some open-bin queries to the LLM. Learn calls the LLM on a miss or an audit, and the answer gives a correct or wrong label, a free label that updates the counts of the bin and is inserted into the cache. Below, panel a fits curves to the labels of an entry and of its cluster, falls back to a prior by the count of correct labels, keeps the smaller threshold, gives the pessimistic risk r and ranks queries by it. Panel b shows the bins, open or closed at J, each with a bar for its estimated wrong rate that grows with risk, counts the served decisions and estimates the wrong rate of each bin, and sets J as the most bins whose upper bound on the served error stays within the budget. Panel c turns every LLM call into a free label for its bin, drawn as one more cell on the count bar of bin b, and takes the spent error W as the larger of the believed and the audited errors, and when W runs ahead of the budget the factor g drops below one and tightens J.
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
Table 1. Test hit rate (%) per stream and budget.
Figure 5. Test hit rate against the share of δ spent at δ=1% , one marker per method of Table 1 . Four scatter panels of hit rate against mean error over delta on a log axis, with a dashed line at one. In each panel the Surplus star is the highest marker left of the line, the baselines that hold delta lie further left, and the fixed thresholds with more hits lie right of the line with hollow markers.
Figure 6. Test hit rate of Surplus, vCache, Conformal, GD and the three GPTCache thresholds across five error budgets, where hollow markers break δ in some run. Four panels of hit rate against the error budget for Surplus, vCache, Conformal, GD and the three GPTCache thresholds, one each for LmArena, Classification, SearchQueries and Combo.
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
Table 2. Hit-rate change in points when parts of Surplus are removed, pooled over shuffled or drifting streams, and the worst error over δ , where values above 1 break δ and dashes mark streams not run.
Figure 7. Surplus serves sparsely labeled entries and keeps the error under δ on a sorted stream where Conformal and Surplus without the threshold drift above it, at δ=1% . Left, bars of hit rate by the number of labels of the nearest entry for Surplus, vCache, Conformal and GD, pooled over the shuffled streams, where vCache has no hits below four labels and Surplus has hits in every bucket. Right, cumulative error over the budget along ClassificationSorted on a log axis for GD, vCache, Conformal, Surplus without the threshold and Surplus, with bands over five seeds, where Conformal and the control rise above one and Surplus stays below it.
Figure 8. Hit rate in consecutive windows of 2,000 queries at δ=1% , averaged over the test orders, for the methods that hold δ on each stream. Three line charts of hit rate per window along the stream for Surplus and the baselines that hold the budget on each stream, vCache and Conformal on all three and also GD and GPTCache 0.97 on Classification. The Surplus line rises earlier and lies above the vCache line in most windows.
Figure 9. Correct hits per bucket of SearchQueries at δ=1% , with each bucket’s share of the stream under its label and its reusable share above its bars. Two vertical bar charts side by side over SearchQueries buckets. By class size, singleton queries are 30 percent of the stream and never reusable, while classes of 20 or more queries are 96 percent reusable and Surplus serves about twice vCache's correct hits there. By query length, with Conformal and GD added, reusable shares rise from 57 percent for five-word queries to 76 percent for eight or more words, and Surplus leads vCache in every bucket.
Figure 10. Search queries that Surplus serves from the cache and vCache sends to the LLM at δ=1% , all judged correct by a human reviewer. Four pairs of an incoming search query and the cached query it reuses, for example credit card for very bad credit and credit cards for horrible credit, with their cosine similarity and the number of labels the matched entry had under vCache, between 0 and 12.
δ=0.5%
δ=1%
δ=2%
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
Table 3. Hit rate (%) and error over δ on one LmArena test order when Qwen3.8-27B labels the misses and judges the hits, with the higher hit rate per budget in bold.
Figure 11. Hit rate with other embeddings and budgets (top) and under an LRU cap at δ=1% (bottom), where LmA., Cls. and SQ denote LmArena, Classification and SearchQueries. Top, hit rate on a log axis in five groups, LmArena with the gte and TE3-small embeddings at budgets of 0.5, 1 and 2 percent, SearchQueries with Qwen3-Embedding at 1 and 2 percent, and LmArena and Classification at 3 and 5 percent, where the Surplus star is the highest marker that holds delta in every group and GD markers are hollow on LmArena. Bottom, four panels of hit rate against an LRU cap of 10, 25, 50 and 100 percent of the stream on LmArena, Classification, SearchQueries and Quora QQP, where Surplus lies above vCache at every cap.
Figure 12. Surplus against MVR-cache on the full SearchQueries stream with the bge-base embedding. Left, grouped bars of hit rate at budgets of 0.5, 1 and 2 percent for MVR-cache, vCache from the MVR-cache code, vCache and Surplus, where Surplus reaches 2.0, 1.9 and 1.8 times the hit rate of MVR-cache. Right, the worst error over delta of the same four, all below a dashed line at one.
Figure 13. Mean end-to-end latency of LmArena queries served by vLLM at δ=1% and its cut from serving without a cache, where the load is a multiple of the closed-loop throughput of the backend. Left, a line chart of mean latency in seconds against the load under Poisson arrivals, where Surplus lies below vCache and both lie below serving without a cache. Right, horizontal bars of the latency cut from serving without a cache on the Azure conversation and code traces and with a Llama backend at two loads, where Surplus cuts more than vCache in every row. The legend gives 327 cache hits for vCache and 483 for Surplus.
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
Setting
Value
Risk bins
48, 12 per decade from 10−4
Control interval
100 decisions
Audit rate ϕ
0.2
Target share β
0.75
Bound width z
1.5
Prior strength m
4
Appendix
Table 4. Settings of Surplus, fixed on the validation split and used unchanged for every stream, budget and test run.
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]
Appendix
Table 5. Hit rate (%) of vCache and Surplus with other embeddings and budgets, on Quora QQP and under an LRU cap, with the gain in points and its nested bootstrap 95% CI.
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
Appendix
Table 6. Hit rate (%) of MVR-cache and Surplus with the same bge-base embedding, each beside the vCache of its own code, with the top two in bold and underline.
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
Appendix
Table 7. Decision time in milliseconds, wall-clock time of a whole test run and peak memory at δ=1% , on one CPU core.
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]
Appendix
Table 8. Error over δ of vCache and Surplus per cell and the gain of Surplus in points over the best baseline that holds δ , with its 95% CI.
δ=0.5%
δ=1%
δ=2%
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
Appendix
Table 9. Hit rate (%) and worst error over δ when Qwen3-8B labels the misses and judges the hits, or only judges the hits on Quora QQP, with the higher hit rate of each pair in bold.