# On Optimal Caching and Model Multiplexing for Large Model Inference

arXiv: https://arxiv.org/abs/2306.02003 · HTML: https://mlsanity.com/paper/2306.02003/

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 53 references that are in the map.
- First posted on arXiv 3 Jun 2023.

## Builds on (most cited first, 30 of 32)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [PaLM: Scaling Language Modeling with Pathways](https://mlsanity.com/paper/2204.02311/) (2022)
- [OPT: Open Pre-trained Transformer Language Models](https://mlsanity.com/paper/2205.01068/) (2022)
- [Sparks of Artificial General Intelligence: Early experiments with GPT-4](https://mlsanity.com/paper/2303.12712/) (2023)
- [Emergent Abilities of Large Language Models](https://mlsanity.com/paper/2206.07682/) (2022)
- [G-Eval: NLG Evaluation using GPT-4 with Better Human Alignment](https://mlsanity.com/paper/2303.16634/) (2023)
- [Fine-Tuning Language Models from Human Preferences](https://mlsanity.com/paper/1909.08593/) (2019)
- [GPTQ: Accurate Post-Training Quantization for Generative Pre-trained Transformers](https://mlsanity.com/paper/2210.17323/) (2022)
- [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022)
- [Accelerating Large Language Model Decoding with Speculative Sampling](https://mlsanity.com/paper/2302.01318/) (2023)
- [The LAMBADA dataset: Word prediction requiring a broad discourse context](https://mlsanity.com/paper/1606.06031/) (2016)
- [FrugalGPT: How to Use Large Language Models While Reducing Cost and Improving Performance](https://mlsanity.com/paper/2305.05176/) (2023)
- [A Survey of Quantization Methods for Efficient Neural Network Inference](https://mlsanity.com/paper/2103.13630/) (2021)
- [OpenAssistant Conversations -- Democratizing Large Language Model Alignment](https://mlsanity.com/paper/2304.07327/) (2023)
- [Capabilities of GPT-4 on Medical Challenge Problems](https://mlsanity.com/paper/2303.13375/) (2023)
- [Carbon Emissions and Large Neural Network Training](https://mlsanity.com/paper/2104.10350/) (2021)
- [A Comprehensive Survey on Pretrained Foundation Models: A History from BERT to ChatGPT](https://mlsanity.com/paper/2302.09419/) (2023)
- [Is Pessimism Provably Efficient for Offline RL?](https://mlsanity.com/paper/2012.15085/) (2020)
- [Confident Adaptive Language Modeling](https://mlsanity.com/paper/2207.07061/) (2022)
- [Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism](https://mlsanity.com/paper/2103.12021/) (2021)
- [Pre-training Tasks for Embedding-based Large-scale Retrieval](https://mlsanity.com/paper/2002.03932/) (2020)
- [A Review of Sparse Expert Models in Deep Learning](https://mlsanity.com/paper/2209.01667/) (2022)
- [The Cost of Training NLP Models: A Concise Overview](https://mlsanity.com/paper/2004.08900/) (2020)
- [Single-Layer Vision Transformers for More Accurate Early Exits with Less Overhead](https://mlsanity.com/paper/2105.09121/) (2021)
- [Online Caching with Optimal Switching Regret](https://mlsanity.com/paper/2101.07043/) (2021)
- [Evaluating Embedding APIs for Information Retrieval](https://mlsanity.com/paper/2305.06300/) (2023)
- [General Purpose Text Embeddings from Pre-trained Language Models for Scalable Inference](https://mlsanity.com/paper/2004.14287/) (2020)
- [Embedding Recycling for Language Models](https://mlsanity.com/paper/2207.04993/) (2022)
- [Regret-Optimal Online Caching for Adversarial and Stochastic Arrivals](https://mlsanity.com/paper/2211.16051/) (2022)

## Built on by (most cited first, 20 of 20)

- [LMSYS-Chat-1M: A Large-Scale Real-World LLM Conversation Dataset](https://mlsanity.com/paper/2309.11998/) (2023)
- [GraphRouter: A Graph-based Router for LLM Selections](https://mlsanity.com/paper/2410.03834/) (2024)
- [AutoMix: Automatically Mixing Language Models](https://mlsanity.com/paper/2310.12963/) (2023)
- [Towards Efficient Generative Large Language Model Serving: A Survey from Algorithms to Systems](https://mlsanity.com/paper/2312.15234/) (2023)
- [Model Compression and Efficient Inference for Large Language Models: A Survey](https://mlsanity.com/paper/2402.09748/) (2024)
- [Cost-Effective Online Multi-LLM Selection with Versatile Reward Models](https://mlsanity.com/paper/2405.16587/) (2024)
- [Teola: Towards End-to-End Optimization of LLM-based Applications](https://mlsanity.com/paper/2407.00326/) (2024)
- [Online Scheduling for LLM Inference with KV Cache Constraints](https://mlsanity.com/paper/2502.07115/) (2025)
- [SCALM: Towards Semantic Caching for Automated Chat Services with Large Language Models](https://mlsanity.com/paper/2406.00025/) (2024)
- [Cascaded Language Models for Cost-effective Human-AI Decision-Making](https://mlsanity.com/paper/2506.11887/) (2025)
- [Efficient Prompt Caching via Embedding Similarity](https://mlsanity.com/paper/2402.01173/) (2024)
- [Cache & Distil: Optimising API Calls to Large Language Models](https://mlsanity.com/paper/2310.13561/) (2023)
- [PersonalizedRouter: Personalized LLM Routing via Graph-based User Preference Modeling](https://mlsanity.com/paper/2511.16883/) (2025)
- [A Generative Caching System for Large Language Models](https://mlsanity.com/paper/2503.17603/) (2025)
- [A Plan Reuse Mechanism for LLM-Driven Agent](https://mlsanity.com/paper/2512.21309/) (2025)
- [SMART: Automatically Scaling Down Language Models with Accuracy Guarantees for Reduced Processing Fees](https://mlsanity.com/paper/2403.13835/) (2024)
- [EACO-RAG: Towards Distributed Tiered LLM Deployment using Edge-Assisted and Collaborative RAG with Adaptive Knowledge Update](https://mlsanity.com/paper/2410.20299/) (2024)
- [LLM Cache Bandit Revisited: Addressing Query Heterogeneity for Cost-Effective LLM Inference](https://mlsanity.com/paper/2509.15515/) (2025)
- [Optimising for Energy Efficiency and Performance in Machine Learning](https://mlsanity.com/paper/2601.08991/) (2026)
- [When Efficiency Backfires: Cascading LLMs Trigger Cascade Failure under Adversarial Attack](https://mlsanity.com/paper/2605.17288/) (2026)

## Abstract (arXiv)

Large Language Models (LLMs) and other large foundation models have achieved noteworthy success, but their size exacerbates existing resource consumption and latency challenges. In particular, the large-scale deployment of these models is hindered by the significant resource requirements during inference. In this paper, we study two approaches for mitigating these challenges: employing a cache to store previous queries and learning a model multiplexer to choose from an ensemble of models for query processing. Theoretically, we provide an optimal algorithm for jointly optimizing both approaches to reduce the inference cost in both offline and online tabular settings. By combining a caching algorithm, namely Greedy Dual Size with Frequency (GDSF) or Least Expected Cost (LEC), with a model multiplexer, we achieve optimal rates in both offline and online settings. Empirically, simulations show that the combination of our caching and model multiplexing algorithms greatly improves over the baselines, with up to 50× improvement over the baseline when the ratio between the maximum cost and minimum cost is 100. Experiments on real datasets show a 4.3× improvement in FLOPs over the baseline when the ratio for FLOPs is 10, and a 1.8× improvement in latency when the ratio for average latency is 1.85.