Multi-Turn Semantic Caching for Low-Cost LLM Serving
Organizations: Carnegie Mellon University, Pittsburgh, PA, USA · University of Washington Tacoma, Tacoma, WA, USA
Abstract
Semantic caching lowers the cost of serving large language models (LLMs) by reusing stored responses for similar requests. In multi-turn conversations, whether a cached response is acceptable depends on both conversations' histories, which embedding similarity of requests and histories predicts poorly (AUC 0.62--0.74 on five workloads). We therefore learn the reuse risk, the probability that a cached response is unacceptable, from judge feedback, and choose a budgeted set of conversation states to cache by weighing the generation cost a reuse avoids against a price for unacceptable reuse. We propose CUCB-SC-MT, which learns a cache from logged conversations with a suboptimality guarantee, and CLCB-LS-MT, which learns online and has regret over requests when conversation states recur. On math-tutoring (SocraTeach) and movie-ticketing (Taskmaster-3) conversations, both achieve lower loss than prior semantic caching approaches: ContextCache, multi-turn variants of ElastiCache and vCache, and single-turn semantic caching at every cache budget. With 1,000 cache entries, CLCB-LS-MT avoids 35--41% of the generation cost through acceptable reuses, against at most 22--25% for the baselines, and lowers estimated serving latency by 19--35%.
Figures & tables
| Taskmaster-3 | SocraTeach | |||||
| Method | Prec. | False | SCA | Prec. | False | SCA |
| CLCB-LS-MT | 74.6 | 8.2 | 35.0 | 67.5 | 13.1 | 41.0 |
| ContextCache | 62.0 | 9.5 | 17.9 | 76.9 | 6.9 | 25.1 |
| ElastiCache-MT | 82.5 | 3.6 | 22.3 | 95.6 | 0.3 | 0.8 |
| vCache | 81.1 | 2.8 | 14.7 | 78.4 | 0.1 | 0.7 |
| Joint-state thr. | 70.7 | 1.0 | 2.3 | 83.5 | 2.0 | 6.0 |
| Taskmaster-3 | SocraTeach | |||
| Method | – | No budget | – | No budget |
| CLCB-LS-MT | 0.80–0.85 | 0.81 | 0.65–0.70 | 0.59 |
| ContextCache | 0.76–0.87 | 0.75 | 0.72–0.94 | 0.53 |
| ElastiCache-MT | 0.83–0.94 | 0.77 | 0.95–1.00 | 0.10 |
| vCache | 0.90–1.04 | 0.92 | 1.01 | 0.65 |
| Joint-state thr. | 1.05–1.08 | 0.99 | 0.91–1.02 | 0.41 |
| Symbol | Meaning |
| System model | |
| conversation, turn, conversation length | |
| request, history, returned response | |
| conversation state: exact-match key , embedding | |
| stratum of key ; distance within a stratum, across strata | |
| per-request law ( 1 ), law of given | |
Appendix figures & tables18 assets
Supplementary material from the paper’s appendix.
Appendix
| AUC | Safe reuse at 80% | |||
| Workload | Dist. | Learned | Dist. | Learned |
| WildChat | 0.69 | 0.76 | 1.1 | 1.8 [0.5, 3.6] |
| Taskmaster-3 | 0.74 | 0.89 | 17.3 [14.2, 22.7] | 38.9 [32.2, 46.4] |
| SocraTeach | 0.67 | 0.75 | 20.5 [10.8, 24.0] | 15.5 [8.1, 33.4] |
| MultiDoc2Dial | 0.72 | 0.81 | 0.0 [0.0, 6.3] | 22.3 [16.3, 27.1] |
| ABCD | 0.62 | 0.82 | 0.0 [0.0, 0.2] | 13.9 [10.9, 18.8] |
| Expected latency relative to no cache | ||||||||||
| Method | Embeddings (ms) | Lookup (ms) – | Hit latency (ms) | Hit rate – | no budget | |||||
| CUCB-SC-MT | 72.3 | 9.76–30.46 | 82–103 | 25.5–30.6% | 0.84 | 0.82 | 0.81 | 0.81 | 0.81 | 0.90 |
| ElastiCache-MT | 37.2 | 0.02–0.11 | 37 | 6.1–20.9% | 0.98 | 0.94 | 0.91 | 0.84 | 0.83 | 0.76 |
| ContextCache | 34.4 | 0.48–0.67 | 35 | 6.0–22.7% | 0.98 | 0.96 | 0.93 | 0.87 | 0.81 | 0.68 |
| vCache | 37.2 | 2.02–2.32 | 39–40 | 0.2–13.4% | 1.04 | 1.04 | 1.03 | 1.00 | 0.91 | 0.87 |
| Joint-state threshold | 72.3 | 0.02–0.12 | 72 | 0.3–6.1% | 1.08 | 1.06 | 1.06 | 1.03 | 1.02 | 0.96 |
| Expected latency relative to no cache | ||||||||||
| Method | Embeddings (ms) | Lookup (ms) – | Hit latency (ms) | Hit rate – | no budget | |||||
| CUCB-SC-MT | 35.7 | 10.80–76.87 | 46–113 | 6.8–47.0% | 0.99 | 0.89 | 0.84 | 0.65 | 0.61 | 0.58 |
| ElastiCache-MT | 16.5 | 0.03–0.21 | 17 | 0.4–13.2% | 1.01 | 1.01 | 1.01 | 1.01 | 0.88 | 0.02 |
| ContextCache | 16.2 | 0.45–0.58 | 17 | 1.1–20.6% | 1.00 | 1.00 | 1.00 | 0.93 | 0.81 | 0.47 |
| vCache | 16.5 | 1.65–2.71 | 18–19 | 0.0–0.2% | 1.01 | 1.01 | 1.01 | 1.01 | 1.01 | 0.69 |
| Joint-state threshold | 35.7 | 0.01–0.11 | 36 | 0.4–17.9% | 1.02 | 1.02 | 1.01 | 0.97 | 0.85 | 0.22 |
| Estimated latency relative to no cache | |||||||||||
| Method | Embeddings (ms) | Decision (ms) | Hit latency (ms) | Background (ms/request) | Hit rate – | No budget | |||||
| CLCB-LS-MT | 70.4 | 12.0–12.4 | 82–83 | 27.8–27.9 | 28.1–32.7% | 0.85 | 0.82 | 0.81 | 0.80 | 0.81 | 0.81 |
| ContextCache | 33.7 | 1.3–1.5 | 35 | 0.006–0.009 | 16.7–27.8% | 0.76 | 0.87 | 0.85 | 0.81 | 0.79 | 0.75 |
| ElastiCache-MT | 36.3 | 0.1–0.3 | 36–37 | 0.005 | 10.3–21.3% | 0.94 | 0.91 | 0.89 | 0.83 | 0.84 | 0.77 |
| vCache | 36.3 | 1.7–4.4 | 38–41 | 0.010–0.013 | 0.3–14.8% | 1.04 | 1.04 | 1.03 | 0.98 | 0.90 | 0.92 |
| Joint-state threshold | 70.4 | 0.1–0.3 | 70–71 | 0.005–0.006 | 0.7–3.5% | 1.08 | 1.06 | 1.06 | 1.05 | 1.05 | 0.99 |
| Estimated latency relative to no cache | |||||||||||
| Method | Embeddings (ms) | Decision (ms) | Hit latency (ms) | Background (ms/request) | Hit rate – | No budget | |||||
| CLCB-LS-MT | 31.8 | 7.2–7.3 | 39 | 22.6–23.2 | 35.7–40.3% | 0.70 | 0.69 | 0.69 | 0.67 | 0.65 | 0.59 |
| ContextCache | 15.4 | 0.6 | 16 | 0.002 | 7.0–29.7% | 0.82 | 0.80 | 0.94 | 0.77 | 0.72 | 0.53 |
| ElastiCache-MT | 16.3 | 0.026–0.2 | 16–17 | 0.002 | 1.8–6.9% | 0.99 | 1.00 | 0.99 | 0.97 | 0.95 | 0.10 |
| vCache | 16.3 | 1.0–1.6 | 17–18 | 0.004–0.005 | 0.1–0.7% | 1.01 | 1.01 | 1.01 | 1.01 | 1.01 | 0.65 |
| Joint-state threshold | 31.8 | 0.035–0.2 | 32 | 0.002 | 1.1–12.2% | 1.02 | 1.01 | 0.97 | 0.95 | 0.91 | 0.41 |
| Method | Budget | Hit rate | Precision | Safe reuse | False reuse | Safe cost avoided | Same-conv. hits | Loss (%) | Regret (pp) |
| CLCB-LS-MT | k = 100 | 28.1% | 73.4% | 20.6% | 7.5% | 32.4% | 22.9% | 75.0 | +19.6 |
| CLCB-LS-MT | k = 200 | 30.4% | 73.4% | 22.3% | 8.1% | 33.9% | 20.5% | 74.1 | +25.3 |
| CLCB-LS-MT | k = 300 | 32.3% | 74.2% | 23.9% | 8.3% | 35.0% | 18.4% | 73.6 | +28.4 |
| CLCB-LS-MT | k = 500 | 32.7% | 75.1% | 24.5% | 8.1% | 35.4% | 17.9% | 73.0 | +32.8 |
| CLCB-LS-MT | k = 1000 | 32.3% | 74.6% | 24.1% | 8.2% | 35.0% | 18.7% | 73.5 | +40.6 |
| CLCB-LS-MT | no budget | 31.7% | 74.0% | 23.4% | 8.2% | 34.3% | 19.4% | 74.1 | +53.1 |
| Method | Budget | Hit rate | Precision | Safe reuse | False reuse | Safe cost avoided | Same-conv. hits | Loss (%) | Regret (pp) |
| CLCB-LS-MT | k = 100 | 35.7% | 61.1% | 21.8% | 13.9% | 34.3% | 87.7% | 82.7 | +5.4 |
| CLCB-LS-MT | k = 200 | 36.4% | 63.6% | 23.2% | 13.3% | 36.6% | 77.6% | 79.9 | +18.6 |
| CLCB-LS-MT | k = 300 | 37.1% | 64.3% | 23.8% | 13.2% | 37.6% | 69.3% | 78.9 | +29.6 |
| CLCB-LS-MT | k = 500 | 38.4% | 66.2% | 25.4% | 13.0% | 39.6% | 60.4% | 77.1 | +43.8 |
| CLCB-LS-MT | k = 1000 | 40.3% | 67.5% | 27.2% | 13.1% | 41.0% | 54.4% | 76.1 | +61.6 |
| CLCB-LS-MT | no budget | 46.9% | 71.9% | 33.7% | 13.2% | 43.4% | 44.0% | 74.4 | +72.1 |
| Method | Budget | Q1 | Q2 | Q3 | Q4 | Q4 Q1 (pp) |
| CLCB-LS-MT | k = 100 | 81.6 | 73.5 | 72.5 | 72.5 | 9.1 |
| ContextCache | k = 100 | 108.4 | 109.5 | 109.1 | 109.8 | +1.4 |
| ElastiCache-MT | k = 100 | 99.1 | 99.5 | 98.2 | 99.2 | +0.1 |
| vCache | k = 100 | 100.1 | 100.4 | 100.0 | 99.8 | 0.2 |
| Joint-state threshold | k = 100 | 99.9 | 99.7 | 99.9 | 99.6 | 0.3 |
| Single-turn (CUCB-SC-Cont) | k = 100 | 102.0 | 102.2 | 102.0 | 101.5 | 0.5 |
| Method | Budget | Q1 | Q2 | Q3 | Q4 | Q4 Q1 (pp) |
| CLCB-LS-MT | k = 100 | 87.4 | 80.3 | 83.4 | 79.9 | 7.5 |
| ContextCache | k = 100 | 86.8 | 83.8 | 87.0 | 82.9 | 3.9 |
| ElastiCache-MT | k = 100 | 99.7 | 100.7 | 100.5 | 100.2 | +0.4 |
| vCache | k = 100 | 100.2 | 100.1 | 100.1 | 99.9 | 0.3 |
| Joint-state threshold | k = 100 | 100.0 | 99.6 | 99.7 | 99.9 | 0.1 |
| Single-turn (CUCB-SC-Cont) | k = 100 | 99.8 | 100.0 | 100.0 | 99.9 | +0.1 |
| Method | no budget | |||||
| CUCB-SC-MT | 77.1 | 74.6 | 74.6 | 73.2 | 72.6 | 71.2 |
| ElastiCache-MT | 94.0 | 88.1 | 85.6 | 82.2 | 80.0 | 77.3 |
| ContextCache | 97.3 | 95.4 | 94.6 | 90.3 | 86.3 | 87.2 |
| vCache | 100.2 | 100.3 | 98.7 | 97.9 | 94.4 | 82.7 |
| Joint-state threshold | 100.2 | 100.3 | 100.6 | 98.6 | 98.1 | 93.1 |
| Single-turn | 99.3 | 98.0 | 99.1 | 100.1 | 99.0 | 99.3 |
| Method | no budget | |||||
| CLCB-LS-MT | 75.0 | 74.1 | 73.6 | 73.0 | 73.5 | 74.1 |
| ContextCache | 109.2 | 101.1 | 100.2 | 99.4 | 97.2 | 94.6 |
| ElastiCache-MT | 99.0 | 95.6 | 92.9 | 90.2 | 85.0 | 81.9 |
| vCache | 100.1 | 99.6 | 98.8 | 93.9 | 90.4 | 87.3 |
| Joint-state threshold | 99.8 | 100.4 | 100.1 | 100.1 | 99.6 | 97.6 |
| Single-turn (CUCB-SC-Cont) | 101.9 | 102.8 | 102.1 | 100.2 | 102.3 | 102.4 |
| Method | no budget | |||||
| CUCB-SC-MT | 94.3 | 88.1 | 81.6 | 77.9 | 69.1 | 67.3 |
| ElastiCache-MT | 99.9 | 100.0 | 100.0 | 100.0 | 101.0 | 88.0 |
| ContextCache | 99.6 | 99.9 | 100.6 | 98.8 | 97.4 | 87.7 |
| vCache | 100.6 | 100.0 | 100.3 | 100.0 | 99.9 | 93.1 |
| Joint-state threshold | 99.7 | 100.0 | 98.7 | 98.0 | 97.4 | 79.2 |
| Single-turn | 100.6 | 101.0 | 99.1 | 99.2 | 96.2 | 89.5 |
| Method | No budget | |||||
| CLCB-LS-MT | 82.7 | 79.9 | 78.9 | 77.1 | 76.1 | 74.4 |
| ContextCache | 85.1 | 85.1 | 97.1 | 85.2 | 85.3 | 81.9 |
| ElastiCache-MT | 100.3 | 100.0 | 100.0 | 100.2 | 100.1 | 154.7 |
| vCache | 100.1 | 100.2 | 100.2 | 100.1 | 99.6 | 114.3 |
| Joint-state threshold | 99.8 | 99.8 | 98.7 | 98.4 | 97.7 | 129.8 |
| Single-turn (CUCB-SC-Cont) | 99.9 | 99.4 | 99.3 | 99.3 | 99.0 | 97.2 |
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