cs.LGOct 31, 2026

Multi-Turn Semantic Caching for Low-Cost LLM Serving

Authors: Baran Atalar, Selly Beyene, Xutong Liu, Carlee Joe-Wong

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 O~(N)\tilde O(\sqrt N) regret over NN 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

Appendix figures & tables18 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Semantic Caches for LLM Web Services Leave Their Error Budget Unspent

    Nov 2, 2026Hanshuai Cui, Qianli Ma, Zhiqing TangSemantic CachingLLM Serving

  2. Continuous Semantic Caching for Low-Cost LLM Serving

    Apr 21, 2026Baran Atalar, Xutong Liu, Jinhang Zuo +3LLM ServingCost-Aware Inference

  3. Intent-Aware Caching for Efficient LLM Serving

    Nov 6, 2026Kazi Hasan Ibn Arif, JinYi Yoon, Dimitrios S. Nikolopoulos +3LLM Inference EfficiencyLLM Serving