Towards Optimal Caching and Model Selection for Large Model Inference
Authors: Banghua Zhu
Ying Sheng
Lianmin Zheng
Clark Barrett
Michael Jordan
Jiantao Jiao
Venue: NeurIPS 2023 poster (2023)
Keywords: caching
model selection
large language models
foundation models
inference
bandit
regret

Abstract: Large Language Models (LLMs) and other large foundation models have achieved impressive results, 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 selector 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 selector, we achieve optimal rates in both offline and online settings. Empirically, simulations show that our caching and model selection algorithm greatly improves over the baselines, with up to $50\times$ improvement over the baseline when the ratio between the maximum cost and minimum cost is $100$.  Experiments on real datasets show a $4.3\times$ improvement in FLOPs over the baseline when the ratio for FLOPs is $10$, and a $1.8\times$ improvement in latency when the ratio for average latency is $1.85$.

On Optimal Caching and Model Multiplexing for Large Model Inference
Banghua Zhu
Ying Sheng Computer Science Department Stanford University
Lianmin Zheng Department of EECS UC Berkeley 1mzhengGberkeleey edu
Department of EECS
UC Berkeley banghua@berkeley.oo edu
Ying. Songgg@he@@@tafff ord. edu
Clark Barrett
Michael L. Jordan
Jiantao Jiao Department EECS
Computer Science Department
Department of EECS
Stanford University barrettêcs. stanf ord. edu
UC Berkeley j jordan@berkeley.co edu
UC Berkeley
j jianta@@berkeeey.co edu
Abstract
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 cache store previous queries and learning a model multiplexer to choose from an ensemble of models for query processing.
Theoretically, we provide optimal algorithm for jointly optimizing both approaches 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 (L.EC), 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 x0x improvement over the baseline when the ratio between the maximum cost and minimum cost is 100. Experiments on real datasets show 4.3x improvement in FLOPs over the baseline when the ratio for FLOPs is 10, and a 1.8x improvement in latency when the ratio for average latency is 1.85.
1 Introduction
The recent emergence of Large Language Models (LLMs) and foundation models has significantly
increased the capabilities of AI systems (Bubeck et al. 2023 Nori et al. [023 Ziegler et al.
2019
Ouyang al. 2022) OpenAl 2023 Beeching al. 2023 Chowdhery et al.) [022] Wei al. 2022a
Google, 2023). ). This progress comes at cost, however, of increased resource consumption and
latency during both training and inference, presenting challenges only in real- world deployment
but also in terms of environmental impact and energy usage (Sharir et al. [020 Patterson et al. 2021
Bommasani et al. 2022). For instance, LLM--bsed chatbots typically consist of large transformer- based networks with parameter counts ranging from one to several hundred billion (Zhou al.) 2023). Moreover, the auto-regressive nature LLMs exacerbates the issue of latency and resource consumption because the model can only generate token a time. Thus, compared to traditional Al-powered services, language model inference costs are much higher and the latency is significantly
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

longer, making it nearly impossible to process each query using LLMs in systems such as search engines.
query
In this paper, we explore two simple yet effective strategies to mitigate this problem: (1) employing caching system to store previous queries, and (2) developing model multiplexer choose the most appropriate model from a set of models for processing the queries. The general workflow of our proposed LLM-based inference system is shown in Figure [ upon receiving query or prompt, we initially check if it can be retrieved from the cache. If the query is not found in the cache, we employ the model multiplexer to determine which model should be used for processing it first, based on the estimated cost for both models.
The choice of cost function and models can vary based the goal. One measure of cost, for example, could be floating point operations (FLOPs). Other alternatives could include the number of API calls measure of resource consumption, latency as measure of time consumption, by a user as a measure of user satisfaction. The cost could also be a weighted sum of multiple factors. For the models, a natural choice would be to have small and a large model, where the small model costs less and is also less accurate, and the large model has a higher cost and also provides higher accuracy. Another alternative would be to have models with expertise in different areas, i.e., each model has high accuracy in its own area of expertise. We provide more discussion in Appendix
score provided
Small Model
5 S
Cache
Multiplexer
query
Large Model
>
CI
hit
Figure 1: A workflow for LLM--based inference with caching and model multiplexing.
There is a long history of existing literature on caching algorithms, with prominent applications including computer architecture and web retrieval (Smith) 1982 Wang 1999 Kumar and Singh 2016). Existing caching algorithms deal with queries with different frequencies and cost, and must also provide guidelines for choosing the cache size. In addition these well-known known difficulties, the use of caching for LLMs raises new challenges, including:
The need for fuzzy search. Since the prompt lies in discrete space that is exponentially large with respect to the token size, it is impossible to match and save all distinct queries. Thus, be at all useful, approximate matching and grouping is required when retrieving queries saved in the cache.
The randomness of the cost. The cost for processing each query is a random variable that depends on the query and has large variance due to the auto-regressive generation procedure and the difference in the length and quality of generated responses. When combined with the long-tailed distribution of the query frequency, the estimation of the cost requires a non-trivial algorithm design.
The effect of model multiplexing. When the cache system is combined with the model multiplexer, the estimation of cost must change accordingly to take into consideration the different costs induced by various models.
For the fuzzy search problem, semantic search or cector-mbeedding-bee based idcas provide a systematic solution that includes embedding extraction and matching algorithms (Bast et al. 2016 Chang et al. 2020) Kamalloo et al. 2023). To simplify the problem, we assume that there exists some semantic search oracle that can group the prompts with the same semantic meaning and that the total cache size is limited by the number of queries, ignoring the difference in cache size between each individual query and response.
The remainder of this paper is organized as follows. In Section 2 we formally define the pipeline of caching and model multiplexing. In Section 3 we study the optimality of the Least Expected Cost (LEC) caching strategy, which estimates the trequency and cost of processing each query, and evicts the one with the least estimated expected cost when there is only model to call. In section 4

---

consider the case when we have access to two models, and jointly design optimal caching and model multiplexer. In both sections, we start by assuming there are infinite samples and then analyze the offline and online learning cases where the cost and frequency need to be learned from data. The experimental results are presented in Section [ We discuss the potential choices of cost, model, and output in the real world in Appendix[A] We provide a brief discussion of the generalization to variable cache sizes in Appendix and of the generalization to multi-model multiplexing in Appendix
1.1 Related work
Cache replacement algorithms Traditional cache replacement algorithms investigate optimal ways to cache queries with different frequencies, costs, and cache sizes. To address varying frequencies, a standard approach is to use Least Frequently Used (LFUU) or Least Recently Used (LRU) cache eviction strategy (Lee et al., 2001). These have been proven be optimal for both adversarial and stochastic queries (Stallings and Paul 2012 Bura et al. (021). Caching has also been combined with machine learning advice and online learning analysis ysis in the literature (Chang et al. 2018
Shuja et al. [021]] Jiang et al. 2019 He et al. 2017; Mukhopadhyay and Sinha 202 Faizal et al. 2023). When varying costs and varying frequencies exist simultaneously. Iy, Jin and Bestavros (2000); Arlitt et al. (2000) propose and study the Greedy Dual-Size with Frequency (GDSF) replacement algorithm, which takes both frequency and cost into consideration. [Bahn] (2005) proposes the Least Expected Cost (LFC) algorithm, which is similar to GDSF, except that it estimates frequency from data. Our work extends this idea by attempting to learn model for both frequency and cost from data. Moreover we explore the statistical optimality of these algorithms in both offline and online settings. We also investigate combining caching algorithms with model multiplexing in order to boost performance.
Acceleration of LLM inference Much effort has been devoted to reducing the cost and latency of LLMs during inference. For example, post-training quantization-basee
approaches aim to compress the model size by using lower-precision arithmetic without losing too much accuracy (Gholami et al. 202T; Frantar et al., 2023). Early-exit frameworks aim utilize the output in the middle decoder blocks so that only small fraction of decoder blocks are called when processing query (Bakhtiarnia jtt al.) 2022; Schuster et al. 2022). The Mixture of Experts approach designs gating function that only assigns small fraction of the network for each query (Fedus et al. (022). Embedding recycling
caches activations from an intermediate layer of a pre-trained model to accelerate the training and inference procedure (Du et al. 2020 Wei et al. 2022b Saad-Falcon et al. 2023). LLM cascade starts with the smallest model and continues to call larger models if the output is not acceptable (Chen
et al. 2023b). The big little transformer decoder framework uses smaller model to generate draft response and calls the large model to identify the unreliable tokens and perform correction (Kim) et al.) 2023). Similar ideas have been combined with speculative sampling to guarantee that the output remains the same in distribution as that of the large models (Chen et al., 2023a Leviathan et al. 2022
Formulation
We formalize the workflow in Figure | Consider the set of (finite) prompts / queries Q C Rd In the t-th round, a query q: E Q is sampled from fixed population distribution Pe AQQ). We maintain a small set of cache L, C Q with |4,| < L. We say the query hits the cache if the query satisfies l: E L.. When the query hits the cache, the incurred cost is zero. When the query does not hit the cache, we choose among the existing models to process the query.
In the processing stage, we first describe the setting of caching without model multiplexing, and extend it to the case of caching with model multiplexing.
2.1 Caching without model multiplexing
In the case when we only have one model, let Ci(g) denote the random variable of the cost when processing the query with the model. Assume that Ci(g) supported on [B, Bz) with B2 > B > being the upper and lower bounds for the cost. Let ot (q) E(Ci(g)) be the expected true cost of
3

---

processing the query 9. The cost for given query and cache L can be written as:
cost(g, () 14 & C)E(C((a) 1(4 & (a). By taking the expectation over the distribution q, we have the expected cost as
cost (C) Σ P(a) & ())
In the offline learning setting, we collect an offline dataset and hope to learn a caching policy E such that cost(L) is minimized.
In the online setting, the query comes in a streaming fashion. At the beginning of each round, receive a query If the query misses the current cache L,, we let the model process the query and receive a cost Ct ~ Pc, Then we can choose to update the cache Le by adding the current query and response to the cache, and replacing one of the existing cached items if the cache C; is full. If the query hits the cache qi E L.. then the cost for this round is set zero with no more observations. In this case, we are interested in characterizing the average difference in the cost throughout the execution of the online learning process. This can be characterized by the regret:
Rache (T)
E|cost(q:; fi) cost(a;
2.2 Caching with model multiplexing
For the simplicity of the notation, we focus on the case of selecting from a small model and large model" and discuss how it can be generalized to the case of selecting from multiple models in Appendix
C Let (q( denote the random variable of the cost when processing the query with the small model, and Ci(g) denote the random variable of the cost when processing the query with the large model. We assume that both random variables are supported on [B,, B2]- We observe i.i.d. draws of the random variables (g) when executing the small model, and Ci(g) when executing the large model. Denote the expected cost as (g) = (4) and c7 = E[Ci(g)].
Let Q + [0, 1] be the (possibly random) model multiplexing policy that maps the query g to values in [0, 1J. where (q) = represents that the query is always sent to the small model, and π (q) represents the query is always sent to the large model. The randomness in the policy is independent of the cost (.).), Ci()). The total cost can be written as the following function of the query g, cache L and policy
cost(g, L, = 1(q & C))(C.(()T()))) + (1 -())) l(q & ())) + (1)(
=())).
By taking the expectation over q, we have the expected cost as
cost(L, = Σ p(a)1(1 -CC000++)))00000000000000+0000+1 -
In the offline learning setting. we collect an offline dataset and hope to learn a caching policy 2 and a multiplexer स such that cost(C, +) is minimized. In the online setting, we get to update the cache in each round by adding the current query into the cache and evicting the ones the cache if full. When the query di misses the cache in round f, we will observe a sample from C.(g)) if it is processed by the small model, or sample from Cg(g.) if it processed by the large model. There will be no observations of cost if q hits the cache. We aim at minimizing the regret:
T
Regret (T) Σ E(cost(q.. Lis Ti) cost L*, TT))
Note that although we name the models as small and large models, we do not impose any assumption on the relationship between their costs. Moreover, the model size and cost function be arbitrary for both models.

---

3 Optimal Caching without Model multiplexing
3.1 Population setting
We start with the population setting where the probability distribution P and the cost of are both known. In the case with only one model, the optimal caching strategy is the Least Expected Cost (LEC) or Greedy Dual Size with Frequency (GDSF) algorithm:
L LEEC
arg min cost(L) = arg min
Σ P(a) & (1)
L: gE@
The traditional frequency-basee based caching strategy, including Least Recent Used (LRU) and Least Frequently Used (LFU), aims at caching the most frequent queries:
CLFU
arg min Σ P(g)a(q $ L).
CI DE
We show in Appendix D that the ratio between the cost of and LEC can be as high as maxge of (g) in the worst case, which shows that LFU can be highly suboptimal when the cost varies significantly.
minge a o (4)
3.2 Finite sample setting: Offline learning
The previous section characterizes the optimal caching strategy in the population setting. We now consider the snite-sample offline learning setting, where we hope produce cache L based on prior data such that the introduced cost minimized. Denote D, N {gg, G1). ... (4N, cx)]. where qi is sampled from the distribution P(-), and c; is sample from random variable Ci(4s). We consider estimating P. of from oracles p DenEstOracle(gg) ... 9N ). (g(g) RegressionOracle( v. In practice, one may remove the last layer of the pre-trained language model and concatenate it with linear head and fine-tune the model the estimator. For theoretical analysis, we focus on the tabular case, where we set both P and (g) to be the plug-in estimator:
Ei= 1(g =q)
P(g)
N
DN 1)==g)e Di 1((=0)
E N if Di=1 1(: -
a(9))
(2)
B1.
if N 14:=)) =0
In practice, the distribution of q may have long tail. Although the estimation of P(q) is uniformly
good for all the estimation of c² c²(g) can be bad for the queries that are visited less. To select the maximum L elements from the imbalanced samples. we compensate the plug-in estimator by
introducing pessimism (Rashidinejad et al. 2021 Jin et al. 2021 As we show in Lemma [ the true frequency for any query y E L' is lower bounded by some constant that depends on B1, B2, Q Thus the pessimism helps eliminate those less visited queries in the long tail of the distribution and encourages caching the queries L* The lower-confidence-bonn
based estimator
log(6N1Q1/0)
È arg min Σ1(6 1l & P))() max B1, ((()) (B2)-(B2- (B2 -Bi)
2 N (gg =
L: TEQ
We show how the cost for the caching from the empirical estimate differs from the optimal cost.
Theorem 1. Assume that N > &B, log(3L/5) and taking 8 = 1/N. We have
B B log(N
E(cost(C) (oostt))) CBB
N NB
The proof is deferred to Appendix where we prove a stronger high-probabilit bound rather than a bound in expectation. From the theorem, know that the cost of the finite-sample caching policy converges to the cost of the optimal policy a rate of 1/ /NN, which achieves the optimal dependence on N. The insights from the tabular case also indicate that the cost needs to be estimated a conservative fashion when considered for the cache replacement algorithm.
IIf we impose uniform lower bound on the probability P(g). then the pessimism can be replaced with the plug-in in estimator. However, it is usually not the case in practice since P(g) usually comes with long tail.
5

---

3.3 Finite sample setting: Online learning
We summarize the caching algorithm pipeline T which relies on the two estimation oracles,
DenEstOracle and RegressionOracle, which estimate both the frequency and cost of models from data.
Algorithm Caching Online Learning
1: Initialize the set of cache L1 = O. past observations Hi = 0. cr,(g)) B1, Vg E Q.
2: For iteration 1.
3: Receive query Qt-
4: Update the density estimation P. DenEstOracle(n, ,.))
5: qt E fr:
6: Output the cached result, set ét, C1,-1, update the past observation H. H4-1 U(qs x),
and continue.
7: Use the large model to process the query, and observe cost ~ PCrie)
8:
Update the past observation Hi = He-1 U(e.4))
9:
Update C,,1 RegressionOracle((4))
10:
If Lel < L:
Let L1+1 be the union of L, and qt-
12: Else if Pc(q:) (,,(9)) > mingec. P((g) c,,(9)
13:
Replace the minimizer element of P:(g) (q)(4) in the cache L, with to get L++1.
For theoretical analysis, we focus on the tabular case and define the oracles as follows:
El= 1(x =
(((g)=
B1, max (B1, Ei 1(0 Lisi (c.
if i 1(1 & x, =0
(g((g)
(B2 Bi)
>> [o (o=+x.0==)]
66T 21/6)
otherwise
For the estimation of density, we use plug-in estimator since there is no imbalance in the sampling process. For the estimation the cost, we subtract the confidence bound include pessimism. We have the following regret guarantee.
Theorem 2. When substituting the DenEstOracle and RegressionOracle with Equation and and set 5 1/T, we have for some universal constant C:
4
Regret (T) < CL(B, B,) 2. VT.
B1
On the other hand, for any eaching policy {C,)T= there exist some cases of P(g), (q) such that for some universal constant C²,
Regret (T) C'VT.
The proof is deferred to Appendix[F] Different from the offline case, one interesting feature of the online case is the partial observation phenomenon: when the query hits the cache, it will not be processed by the model, and thus we cannot observe the sample from Ci(q) in this round. This is different from the traditional bandit literature where selected arm is always observed in each round. Thus the partial observation thus requires new upper and lower bound analysis.
4 Optimal Caching and Model multiplexing
4.1 Population setting
In the case when we have access to two models, we need to design good caching and model multiplexing strategy jointly. We can compute the optimal caching and model multiplexing policy as

---

L* ",""= = arg min cost(L, m), which gives the following solution:
x (q) (g) S (9))),
L -arg min Σ P4 & L) min (c)))) 2/CC/T gE
Such optimal strategies are straightforward: x' always assigns the query to the model with smaller cost, and L saves the L queries with the largest P(g) min (c) of (q)).
For the model multiplexing algorithm, we consider two baselines: (a) one always uses large model (T) O; (b) one always uses the small model IT. (4) = 0. This is related to the LLM cascade idea in the concurrent work of Chen et al. (2023b). We provide more discussion in Appendix A and present comparisons between baselines and π in Appendix D
4.2 Finite sample setting: Offline learning
We now consider the finite sample case. Let Dx = C,,, (.N) Ca,N, C.N)), where Ca, sample from random variable Cs (gx), ) the observed for processing query qa with the small model in round n. And Ct, is a sample from random variable Ci(gn). the observed cost for processing query 9r. with the large model in round n. We consider estimating P, c, of with some oracles P DenEstOracleequ ... 2N),, (g), & (q) RegressionOracle" (DN). We focus on the tabular case for theoretical analysis, where we set P, (g) and (g(g) to be the plug-in estimator:
P(q) EE 1(q. 4) (0(1)
ΣN 1(9.=9)o
if i i= ((: q) >
L. 1()=9)
N
B1,
i i= 1(g: g) 0,
ΣN 1g 1g:=g)ew ΣN 1()=0)
if ir N
i 1 (g: = =q) >
(g) =
B1,
if ir 1(: =9) 0.
Similar to the case of caching without model multiplexing, for long-tailed distribution P(g). the estimation of (g).) (q) can be bad for the queries that are visited less. To select the maximum elements from the plug-in estimator, we introduce pessimism to the estimate of é and é, This leads to the following design of caching and model multiplexer L and a: A (q) = (2,(a) I a()),
Σ1(1 E L))(() max (B,, (i, - (B2 - Bi), 2:CCEL qEQ
log (og(8|Q14) (8)2
A = arg min
> 1(g, = 4)
We now show the cost for the caching and model multiplexer obtained from the empirical estimate is close to the optimal cost. The proof is deferred to Appendix G
Theorem 3. Assume that 2
8Bg (og(41./))
and take å = 1/N. We have
B
B2 O log (gg(8)[[N)
Elcost( #) cost(L" πt CL(B2- -i)
B N
4.3 Finite sample setting: Online learning
We turn to the online case. We first propose a meta-algorithm in Algorithm analysis of the meta-algorithm for the tabular case, with DenEstOracle P((g) the RegressionOracle defined as follows:
We provide a theoretical
Eim 1(w=g))
and
B1,
if D c 1= 1(s; 0,
(.)(g)
max
B1, Eis, 1(s=00nm=0)a Ei= 1(x;=0.g::g)
(B, - (B2
2
log(87 /5)
((x;=0,0:=g)
otherwise,
B1,
if D
1(8;
1,4
0, otherwise.
(g)
max
BB,,
Ei 1(s;=10;:q)c. Eis, 1(x;=1g;=0)
(Bg B1)
2 > (1;=111;=0))
log(ST @1/6)
We provide the following theorem on the regret of the overall algorithm.
7

---

Algorithm 2 Joint Design of Caching and Model multiplexing
1: Initialize the set of cache L1 (). past observations Hi = 0. cro(4) B1, cs,0(4) = B1. model multiplexing policy mo(g) = 1, 14 E Q
2: For iteration / = 1.2.....
3: Receive query 9t-
4: Update the density estimation P: = DenEstOrrccee(g, ,q))
5: If qu E C:: output the cached result, set C₁2t Cs.--1, Et,t c1,--1, Te-1. update the
past observation H4 = H4-1 U(e. x, x) and continue.
6: Select the models according St TT. (gt).
7: Update the past observation H4 = H4-1 U(ge, St, (t).
8:
Update C,,t, Ca.t RegressionOracle((H), Set T++1 ((x, < xq,(()))
9:
L,l < L: let Lu+1 be the union of L2 and qr-
10: Else if (g.)) min (C.,,(9:), C1,,), > mingec. P((g) min (C., (q). cr (g)):
11:
replace the minimizer element the cache L. on RHS with q to get Lr+1.
Theorem 4. Substituting the oracles in Algorithm 2 with the oracles above and ō 1/T, have
Regret (T) CL(B2 B2) log VT.
B1
The proof deferred Appendix H Compared with the lower bound in Theorem 2 we that the dependency on 7 is tight. The pessimism plays two different roles here: on the one hand, encourages the exploration for model multiplexing choose the ones with more uncertainty in the cost; on the other hand, it encourages the exploitation to be conservative about which query to save into the cache.
For the model multiplexer to work well, one needs to have a small yet accurate model multiplexer. In the when the model multiplexer is not accurate, the small model always comes with much smaller cost, and we are allowed to regenerate the responses and make corrections for the output, one may combine LEC with cascade (Chen et al. 2023b) achieve better performance.
5
Experiments
We conduct both simulations and real-world experiments with our proposed methods. The code is available at https:///ithhb: www.shuu..oom/m//// www./ioon/////////ooo caching haw.-mm-aaccciiinnnilileleii
5.1 Simulations for algorithm analysis
We conduct synthetic online and offline experiments for joint optimization of caching and model switching. In Figure 2 caching algorithms. For LFU, we consider model switchers which always select the small or large models the baselines. We consider 20 distinct prompts and set the cache size be 10. We set the frequency distribution as power distribution with a = 0.9. The ground truth cost for each query processed by both models generated from Bernoulli distribution with the parameter 0.5. We repeat the simulation 100 times and plot the mean and standard deviation in the figure. Our simulation suggests that LEC with model switcher greatly improves the two baselines by a factor of 50x when the cost ratio is 100. We include additional results the synthetic datasets for both online and offline settings with different a values, cost ratios, and switcher accuracy in Appendix [.]
we plot the cumulative cost and regret in online learning for LFU and LEC
sample from 100.X + 1, where X is random variable
5.2 Experiments on real datasets
We evaluate algorithms on two tasks: next-token prediction the Lambada (Paperno et al. 2016) dataset and chat assistant on the OpenAssistant (Köpf et al.] 2023) dataset.
For the next-token prediction task, we run the offline algorithm with two models: OPT-1.3B and OPT-13B (Zhang al., (202)) and use FLOPss as the cost. The target performance metric the number of correct tokens predicted, where get the ground-truth token from the Lambada dataset.

---

lus
Optims
Figure 2: Comparisons between LFU with either small or large model switching and LEC with model switcher. Both the z-axis and y-axis are logarithmic scales. The shaded regime represents the standard deviation calculated from the repeated experiments.
For given query, an algorithm can choose to run the small model or the large model. the small model is chosen but its result is wrong, the large model must be run and it will incur an additional penalty. We fine-tune a BERT base model with 2000 samples as the model switcher by predicting whether the small model give the correct result and achieve 80.2% accuracy. We work with 100 unseen distinct prompts in the offline setting with total queries 10000 and cache size 40. We compare our offline caching and switcher algorithms against LFU, carge-model-onig (which always calls the small model first). As shown in Table LEC is better than LFU in all cases. Combining LEC and switcher brings up 4.3x cost reduction compared to the baseline "LFU + Large." However, as the predictor accuracy limited, the model switcher may not be as good as the cascade algorithm in some cases. We leave the training of better switcher as future work.
and cascade
the chat assistant task, we run the online algorithm with two models: FastChat-TS-- and Vicuna-13B (Chiang et al.] (202)), and use the inference latency as the cost. The quality of response is evaluated by GPT4 evaluation (Liu et al., 2023). We say a response is satisfying if the score is larger than 6 out of 10, and unsatisfying otherwise. If the response from the small model is unsatisfying, will call the large model again and incur an additional cost in latency. The ratio between the average latency of the large model and the small model is 1.85. We work with 100 distinct prompts in the online setting with total queries 10000 and cache size 40. After a sufficient number of online learning steps, the switcher learns the accurate costs of two models on this finite prompts set, "LEC + switcher" outperforms other algorithms in all cases on Table 2 with up to 1.8x latency reduction compared to "LFU large" baseline.
selector accuracy
LFU+ large
LFU+ cascade
LFU+ selector
LEC+ large
LEC+ cascade
LEC+ selector
0.2
80%
3.49
3.81
2.60
3.44
1.50
2.00
0.8
80%
10.81
11.80
8.06
10.36
4.11
4.76
0.2
100%
3.49
3.81
1.91
3.44
1.50
0.99
0.8
100%
10.81
11.80
5.90
10.36
4.11
2.50
Table 1: Evaluation of offline algorithms the Lambada dataset with OPT-1.3B and OPT-13B, 100 distinct prompts, total query size 10000 and cache size 40. a is the parameter of the power distribution of the prompts. The table lists cumulative costs (103) for different algorithms.
We provide more experiments in Appendix | where we evaluate both FL.OPs and latency for both offline and online setting on both synthetic and real dataset, with varying cache size, query size and distinct prompts.

---

a
LFU+ large
LFU+ cascade
LFU+ selector
LEC+ large
LEC+ cascade
LEC+
selector
0.2
9.31
13.88
7.24
8.74
8,82
5.93
0.5
20.04
29.88
15.11
18.68
16,90
11.87
0.8
28.24
42.12
21.14
26.07
20.31
15.49
Table 2: Evaluation of online algorithms the OpenAssistant dataset with FastChat-T5-3B and Vicuna- 13B, 100 distinct prompts, total query size 10000 and cache size 40. a is the parameter of the power distribution of the prompts. The table lists cumulative costs (103) for different algorithms.
6 Conclusions
We have studied the joint optimization of caching and model multiplexing and proposed an optimal algorithm for the tabular case. There variety of further work that can be pursued in this vein, including:
Designing the optimal caching and model multiplexing algorithm when there query queue, such that the query arrives at a random interval rather than fixed interval. A more complicated serving pattern also needs to take batching strategies into consideration.
Understanding the scaling law of the predictors. We hope for prediction to reduce overhead introduced by the predictor. It is important to understand the trade-off between prediction accuracy, model size, and training data size.
small yet accurate model
Designing optimal caching algorithm when the responses generated in each round have diverse qualities.
Acknowledgements
Banghua and Jiantao are partially supported by NSF 11S-1901252, CIF-1909499 and CIF-221 1209.. Michael I. Jordan is partially supported by NSF IIS-1901252. Ying Sheng and Clark Barrett are supported in part by NSF-2110397 and the Stanford Center for Automated Reasoning.
References
M. Arlitt, L. Cherkasova, Dilley, R. Friedrich, and T. Jin. Evaluating content management techniques for web proxy caches. ACM SIGMETRICS Performance Evaluation Review, 27(4): 3-11, 2000.
H. Bahn. Web cache management based on the expected cost of web objects. Information and Software Technology, 47(9):609-6211 2005.
A. Bakhtiarnia, Q. Zhang, and A. Iosifidis. Single-layer vision transformers for accurate early exits with less overhead, 2022.
H. Bast, B. Buchhold, E. Haussmann, et al. Semantic search on text and knowledge bases. Foundations and Trends Information Retrieval, 10(2-3): 19-271, 2016.
E. Beeching, Y. Belkada, K. Rasul, L. Tunstall, L. von Werra, N. Rajani, and N. Lambert. StackLLaMA: An RL fine-tuned LLaMA model for Stack Exchange question and answering, 2023. URL hattps://huggingee
co/ bllg/stackllammm.t
R. Bommasani, D. A. Hudson, E. Adeli, R. Altman, S. Arora, S. von Arx, M. S. Bernstein, Bohg, Bosselut, E. Brunskill, Brynjolfsson, Buch, Card, Castellon, N. Chatterji, A. Chen, K. Creel, J. Q. Davis, D. Demszky, C. Donahue, M. Doumbouya, E. Durmus, S. Ermon, Etchemendy, K. Ethayarajh, L. Fei-Fei, C. Finn, T. Gale, L. Gillespie,
Goel, Goodman, S. Grossman, N. Guha," T. Hashimoto, P. Henderson, J. Hewitt, D. F. Ho, J. Hong. K. Hsu, J. Huang, Keeling, F. Khani, O. Khattab, W. Koh, M. Krass, R. Krishna, R. Kuditipudi, A. Kumar, F. Ladhak, M. Lee, T. Lee, J. Leskovec, Levent,
leard, S. Jain, D. Jurafsky, Kalluri, S. Karamcheti,
10

---

L., T. Ma. A. Malik, C. D. Manning, S. Mirchandani, E. Mitchell, Z. Munyikwa, S. Nair, A. Narayan, D. Narayanan, B. Newman, A. Nie. C. Niebles, H. Nilforoshan, J. Nyarko. G. Ogut, I. Orr, I. Papadimitriou, J. S. Park, C. Piech, E. Portelance, C. Potts, A. Raghunathan, R. Reich, H. Ren, F. Rong. Y. Roohani, C. Ruiz, Ryan, C. Ré, D. Sadigh, S. Sagawa, K. Santhanam, A. Shih, K. Srinivasan, A. Tamkin, R. Taori, A. W. Thomas, F. Tramèr, R. E. Wang, W. Wang. B. Wu, J. Wu, Y. Wu, S. M. Xie, M. Yasunaga, J. You, M. Zaharia, M. Zhang, T. Zhang, X. Zhang, Y. Zhang, L. Zheng, K. Zhou, and P. Liang. On the opportunities and risks of foundation models, 2022.
S. Bubeck, V. Chandrasekaran, R. Eldan, J. Gehrke, E. Horvitz, E. Kamar, P. Lee, Y. T. Lee, Y. Li, S. Lundberg, et al. Sparks of artificial general intelligence: Early experiments with GPT-4, arXiv preprint arXiv:2303.12711 2023.
A. Bura, D. Rengarajan, D. Kalathil, S. Shakkottai, and J.-F. Chamberland. Learning cache and caching to learn: Regret analysis of caching algorithms. JEEE/ACM Transactions on Networking, 30(1):18 31, 2021.
W.-C. Chang, X. Yu, Y.-W. Chang, Yang, and S. Kumar. Pre-training tasks for embedding large-scale retrieval, 2020.
Z. Chang, L. Lei, Z. Zhou, S. Mao, and T. Ristaniemi. Learn cache: Machine learning for network edge caching in the big data era. IEEE Wireless Communications, 25(3):28-35, 2018.
C. Chen, S. Borgeaud, G. Irving, J.-B. Lespiau, L. Sifre, and J. Jumper. Accelerating large language model decoding with speculative sampling, 2023a.
L. Chen, M. Zaharia, and J. Zou. FrugalGPT: How to use large language models while reducing cost and improving performance, 2023b.
W.-L. Chiang, Z. Li, Z. Lin, Y. Sheng. Z. Wu, H. Zhang, L. Zheng, S. Zhuang. Y. Zhuang. J. Gonzalez, I. Stoica, and E. P. Xing. Vicuna: An open-source chatbot impressing GPT-4 with 90%* ChatGPT quality, March 2023. URL
hrtp:/sss..rrbbo///222222/// -3- vicuna/
A. Chowdhery, S. Narang, J. Devlin, M. Bosma, G. Mishra, A. Roberts, P. Barham, H. W. Chung, C. Sutton, S. Gehrmann, et al. PaLM: Scaling language modeling with pathways. arXiv preprini arXiv:2204.02311, 2022.
Du, M. Ott, H. Li, X. Zhou, and V. Stoyanov. General purpose text embeddings from pre-trained language models for scalable inference, 2020.
F. Z. Faizal, P. Singh, N. Karamchandani, and S. Moharir. Regret-optimal online caching for adversarial and stochastic arrivals. In Performance Evaluation Methodologies and Tools: 15th EAI International Conference, VALUETOOLS 2022, Virtual Event, November 2022, Proceedings, pages 147-163. Springer, 2023.
W. Fedus, J. Dean, and B. Zoph. A review of sparse expert models in deep learning, arXiv preprint 2.XXi:2209.01667, 2022.
E. Frantar, S. Ashkboos, T. Hoefler, and D. Alistarh. GPTQ: Accurate post-training quantization for generative pre-trained transformers, 2023.
A. Gholami, S. Kim, Z. Dong, Z. Yao, M. W. Mahoney, and K. Keutzer. A survey of quantization methods for efficient neural network inference, 2021.
Google. PaLM-2 technical report. 2023.
Y. He, Z. Zhang, F. R. Yu, N. Zhao, H. Yin. V. C. Leung, and Y. Zhang. Deep-reinforcement-lcnn based optimization for cache-enabled opportunistic interference alignment wireless networks. IEEE Transactions on Vehicular Technology, (6(11):1043-110455 2017.
W. Jiang, G. Feng, S. Qin, T. S. P. Yum, and G. Cao. Multi-agent reinforcement learning for efficient content caching in mobile d2d networks. IEEE Transactions on Wireless Communications, 18(3): 1610-1622, 2019.
11

---

S. Jin and A. Bestavros. Popularity- aware greedy dual-size web proxy caching algorithms. In Proceedings 20th IEEE International Conference on Distributed Computing Systems, pages 254- 261. IEFE, 2000.
Y. Jin, Z. Yang, and Z. Wang- Is pessimism provably efficient for offline RL? In International Conference on Machine Learning, pages 5084-5096. PMLR, 2021.
E. Kamalloo, X. Zhang, O. Ogundepo. N. Thakur, D. Alfonso- M. Rezagholizadeh, and Lin. Evaluating embedding APIS for information retrieval, 2023.
S. Kim, K. Mangalam, J. Malik, M. W. Mahoney, A. Gholami, and K. Keutzer. Big little transformer decoder, 2023.
A. Köpf, Y. Kilcher, D. von Rütte, S. Anagnostidis, Z.-R. Tam, K. Stevens, A. Barhoum, N. M. Duc, O. Stanley, R. Nagyfi, et al. Openassistant conversations-dddrorriinnn large language model alignment. arXiv preprint arXiv:2304.07327, 2023.
S. Kumar and P. Singh. An overview of modern cache memory and performance analysis of replacement policies. In 2016 IEEE International Conference on Engineering and Technology (ICETECH), pages 210-214. IEEE, 2016.
D. Lee, J. Choi, J.-H. Kim, S. H. Noh, S. L. Min, Y. Cho, and C. S. Kim. LRFU: A spectrum of policies that subsumes the least recently used and least frequently used policies. IEEE Transactions on Computers, 50(12): 0ee111132231111 2001.
Y. Leviathan, M. Kalman, and Y. Matias. Fast inference from transformers via speculative decoding. arXiv preprint arXiv:2211.17192. 2022.
Y. Liu, D. Iter, Y. Xu, S. Wang, R. Xu, and C. Zhu. Gpteval: Nlg evaluation using gpt-4 with better human alignment. arXiv preprint arXiv:2303.1663 2023.
S. Mukhopadhyay and A. Sinha. Online caching with optimal switching regret. In 202/ IEEE International Symposium on Information Theory (ISIT), pages 1546-1551. IEEE, 2021.
H. Nori, N. King, S. M. McKinney, D. Carignan, and E. Horvitz. Capabilities of GPT-4 on medical challenge problems. arXiv preprint 3xXi:23303.13373 2023.
OpenAl. GPT-4 technical report. arXiv preprint arXiv:3303.087744 2023.
L. Ouyang, J. Wu, X. Jiang, D. Almeida, C. L. Wainwright, P. Mishkin, C. Zhang, S. Agarwal, K. Slama, A. Ray, et al. Training language models to follow instructions with human feedback. arXiv preprint arXiv:2203.02// 2022.
D. Paperno, G. Kruszewski, Lazaridou, Q. N. Pham, R. Bernardi, S. Pezzelle, M. Baroni, G. Boleda, and R. Fernández. The LAMBADA dataset: Word prediction requiring broad discourse context. arXiv preprint arXiv:1606 1606.063,,, 2016.
D. Patterson, J. Gonzalez, Q. Le,, C. Liang, L.-M. Munguia, D. Rothchild, D. So, M. Texier, and Dean. Carbon emissions and large neural network training. arXiv preprint 104. 2021.
Rashidinejad, B. Zhu, C. Ma. J. Jiao, and Russell. Bridging offline reinforcement learning and imitation learning: A tale of pessimism. Advances in Neural Information Processing Systems, 34: 11702-11716, 2021.
Rigollet and J.-C. Hütter: High dimensional statistics. Lecture notes for course 18S997, 813(814): 46, 2015.
J. Saad-Falcon, A. Singh, L. Soldaini, M. D' D'Arcy, A. Cohan, and D. Downey. Embedding recycling for language models, 2023.
Schuster, Fisch, J. Gupta, M. Dehghani, D. Bahri, Q. Tran, Y. Tay, and D. Metzler. Confident adaptive language modeling, 2022.
12

---

O. Sharir, B. Peleg, and Y. Shoham. The cost of training NLP models: A concise overview. arXiv preprint arXiv:2004. 088000, 2020.
Shuja, K. Bilal, W. Alasmary, H. Sinky, and E. Alanazi. Applying machine learning techniques for caching in next-generation edge networks: A comprehensive survey, Journal of Network and Computer Applications, 181:103005, 2021.
A. J. Smith. Cache memories. ACM Computing Surveys (CSUR), 14())473-530, 1982.
W. Stallings and G. K. Paul. Operating Systems: Internals and Design Principles, volume 9. Pearson New York, 2012.
Wang. A survey of web caching schemes for the internet. ACM SIGCOMM Computer Communication 29(5) 1999.
J. Wei, Y. Tay, R. Bommasani, C. Raffel, B. Zoph, S. Borgeaud, D. Yogatama, M. Bosma, D. Zhou, D. Metzler, et al. Emergent abilities of large language models. arXiv preprint arXiv:2206.07688 07682, 2022a.
T. Wei, J. Qi, and S. He. A flexible multi-task model for BERT serving, 2022b.
S. Zhang, S. Roller, N. Goyal, M. Artetxe, M. Chen, S. Chen, C. Dewan, M. Diab, X. Li, X. V. Lin, ct al. Opt: Open pre-trained transformer language models. arXiv preprint arXiv:2205.01068 2022.
C. Zhou, Q. Li, Li, J. Yu, Y. Liu, G. Wang, K. Zhang, C. Ji, Q. Yan, L. He, H. Peng, J. Li. Wu, Z. Liu, P. Xie. C. Xiong, J. Pei, P. S. Yu, and L. Sun. A comprehensive survey on pretrained foundation models: A history from BERT to ChatGPT, 2023.
D. M. Ziegler, N. Stiennon, J. Wu, T. B. Brown, A. Radford, D. Amodei, P. Christiano, and G. Irving. Fine-tuning language models from human preferences. arXiv preprint arXiv: 1909.08593 2019.
13

---

Appendix
A Discussions on the Choice of Output, Model and Cost
The proposed framework is flexible in the choice of outputs, models and costs. Below we diseuss several possible choices and combinations of output, models and costs that are most practically relevant.
Per-token Output and Per-sentence Output. We have two design choices of the desired output in each round, namely per-token output and per-sentence output.
For per-token output, we aim at generating one token at each round as a response of the queries. In this case, we only cache the next token for given query and estimate the cost for generating next token. We also have the flexibility of choosing different models to generate each token in each round.
For per-sentence output, we aim at generating complete response at each round. In this case, cache the whole responses for given query, and estimate the cost for generating the whole responses. This may introduce more variance in the cost due to the variation and randomness in the length of the generated responses.
Choices of Costs
The cost can be chosen as FLOPS, latency of the model, the price for API calls, user satisfaction of the results, or combination of all the four factors.
Model multiplexing A common choice of model ensembles is a pair of small and large models. The cost for small model Cg(g) can be written as C9)4) = Ce.o(g) + (())),,, Here (gg) is binary random variable, indicating whether the small model outputs satisfying results (g) = 0) or not (Y (Y) L). In the case when the small model outputs satisfying response, the incurred cost is (4)) In the case when the small model outputs a bad response, the incurred cost is Cg,0(9) + (q) We discuss two possible choices of Y Cz,u(g) and Cs,1(g) based on two different evaluation pipeline as below.
One-time evaluation pipeline. For the one-time evaluation pipeline, we can only call one of the models once and the generated content cannot be changed. In this case, (g) can be set as the cost for running the small model to generate responses, Y (q) is set to be 1 if the user is not satisfied with the response, and C²,1 (g) the incurred cost for unsatisfactory of the user. One can similarly set the same cost for the large model.
Correction-based evaluation pipeline. For correction-based evaluation, we may re- generate the content with a different model if it is unsatisfying, and get extra cost for fixing the content. Such evaluation can be easily combined with L.M Cascade (Frantar et al., 2023) or the idea from Big Little Transformer Decoder (Kim et al. (023) and Spectulative sampling (Chen et al. 2023a). For example, after running the small model, we run the large model once to infer all the log probabilities of the small model output in parallel, and reject its output if the log probabilities are low. If the small model output is rejected, we will set Y()) = and run large model to re- re-generate the responses. In this case, C²,((4) the cost of running the small model for generating responses, and running the large model once for checking the probability. And C., (q) the cost of running the large model to generate the response.
We also remark here that in the special case when the cost for the small model is much smaller than that of the large model under the correction-basee always runs the small model first may give better performance than the model multiplexer if the accuracy of the model multiplexer is low, since running small model does not introduce too much cost compared to running large model. In this situation, the cascade selector also be combined with LEC caching to further improve the performance.
evaluation pipeline, the cascade selector which
On the other hand, we may also choose among models with similar size but different expertise, including coding, summarization and chat etc. this case, we also expect to see different qualities and cost of responses for specific queries.
14

---

B Generalization to Variable Size Cache
For the variable-size caching problem, assume that the cache size of q deterministic scalar, denoted as S(q). In the population case we design the cache as follows:
Σ P(a)1(q & L) min (c) (T)) ge@
arg min D.E S(g)
In the case when all S, P. C of are known, one may solve the above constrained optimization problem for the optimal caching. When S(q) replaces the query with the smallest expected cost per-size (g) min (c](g), (g))) SQ) rather than expected cost per-query.
good cache replacement algorithm is GDSF itself, which
more practical setting is the case when the cache size for each query S(q) a random variable. Due to the randomness in the generation procedure, we expect see responses of different lengths even when we use the same model to process the same query. In each round, we will have generated response with size sq) that sampled from the random variable S(g:). We conjecture that the optimal cache replacement algorithm is to replace the query with the smallest expected cost per-size P(g) min (c) of (q)) /s()) as well, where s()) the size of the cached queries and responses.
C Generalization to Multiplexing of Multiple Models
The proposed algorithm can be generalized to model multiplexing with multiple models. Assume that we have K models, and each model has a random cost function Ck(g) with expectation cg(g). In this case, the optimal population algorithm is
π (g) = arg min o7 (g),
kE[K]
C arg min
Pla) L) min ct()).
CISL
kE(K]
QE
And the finite sample algorithm natural follow. practice, one may train neural network with K dimensional output to predict the cost for each of the models.
D Differences Between the Optimal Policy and the Baseline
Consider the population setting in Section B where we optimize caching without model multiplexing. We show via a simple example below that without considering the cost for individual query, LFU can be highly sub-optimal compared to the optimal caching strategy in the population. The ratio
Proposition For any fixed cost function o;, one can design some distribution of queries such that for any e > 0,
cost (LFU) cost( CLEC)
maxge @ (g mingeo (4)
The construction can be seen from two-query example. Let (q1) = c1. (92) C2 with e₁ < oz. Let P(q:) =, ((4)) = This shows that when the individual cost varies drastically for different queries, the total expected cost for LFU can highly sub-optimal compared with the cost-aware caching strategy.
To compare the performance of the model multiplexing in Section 4 take the cache size L 0. We have the following proposition for the performance improvement of the model multiplexer.
Proposition Let L = O. The difference cost between the baseline and the model multiplexer can be written as
cost(L", T.) cost(L* ;-),'")== = Σ P(g) max (g) -0---tt0 (4)),
QE
cost(C*, ()) cost(L",
P(g) max(0, (g) c)))))
QEQ
15

---

The proof is a direct result of plugging in the cost definition. We see that the gap between n, and the optimal model multiplexer becomes larger when large fraction the queries have smaller cost when processed by the large models, and vice versa.
E Proof of Theorem 1
Proof. We first prove the following lemma on the lower bound of P(ạ) for any a E L*.
Lemma 1. For any E , we have P(a) 2 /
Proof. From the fact that Eyeo p(g) 1 and for any q E C and any d' L* P(a) z
P(I)) 2 Bi B2, we know that for any g E L P(g) 2 B1/ Q1).
We define the following three events:
2 (6g(6
E1
Vg 2, (P(2) - P(a)l S
N
log(6)(1/6)
E2 =
Vg E 2, (a(g))) - ca)i s (B2 B1)
ΣΣ n=1 1(gn 9)
N
N
B,N
E3
Ag Lr,
Σ 1am :) Z 2B
n=l
We know that the first two events hold simutaneously with probability least 25/3 from Lemma For the third event, from the Chernoff bound, we know that for any E Q, we have
N
P
Σ (gn - q) 2 NP(1)/2 2 21-exp(-NP())5)
From Lemma further implies
we know that for any g E Lr, P(4) 2 (1/ Thus the above inequality
N
N
B
8
Σ
(gn q) 2
2 1 - exep
2 1
2B Q
8B2|
3L
n=1
The last inequality is due our assumption that N > 8B. Q (32(3)/6))
B,
We condition on the three events from now on. The last two events imply that for any a L*
B2| (og()/111)))
(2)(0) ct) s (B2 -Bi)
NB
We have
cost(L) co) = Σ P(g) (1(9 & 2) 2) 1(9 L*)) (i
9EΩ
Σ P(g) (1(g - = E 2))
oj (g).
QEQ
Let Ce (4) = =(( - (B2 B1)
1ng(6 /1))
Note that for any a E L*, we know that
1(4
2log(66/8) N
(7(00) 2(BB - Bi)
B2 log 6 ())))
P(g) (g) 2 max
P(g)
NB,
O2| (og(6//1///
2 (())((()) CCB2 B1).
NB,
16

---

And similarly, for any q & L", we know that
((()) S P(g)e(()) + B2y 2log(6/0)
2 2lg(6//8)
pe (0) = P(g) +
Now consider any E L but & L and any other of E L but o' & 2. We have P(d)cT(a') P(a)eT
log(61//))
<P(d))cppeo( C( (1) + C(B2 B1)
NB1
B2 Q) log (o ()/6))
SC(B2-BA) Bi)
N NB1
Overall, we know that conditioned on E1 n Eg n Es, we have
B2 2 log
(6
21/0)
cost( cost((*) SC Bi)L /
NB1
And this implies that
B₂ log (6) 21/0)
[|cost(()- cost(c*) C(B2 B.)L.
+ 8B2.
N NB,
Taking = 1/N finishes the proof.
F Proof of Theorem 2
Proof. Upper Bound. We start with the upper bound by the following lemma.
Lemma 2. In each round [T', we always have
Ci+1 E arg min Σ P.(g)1(q & C)a,(())-
Proof. We prove this lemma by induction. First, consider the case when |C++1l < L. In this scenario, we always put the query into the cache. And Lt+1 contains all queries with non-zero P.. Thus such f141 is always one of the minimizers.
Now consider the case when [2+1/= L. Assume that the conclusion holds for time step t. Now consider the case of + 2. When the new query is in the cache 4++1 Cr+1, the cache will remain unchanged Li+2 L1+1. In this case, the estimated probability for 9++1 is increased, while the others are decreased, and 6t,41 is not changed for any query. Thus L still the minimizer. When the new query does not hit the cache, the estimated probability times costs for all other queries except for @t+1 are decreased proportionally since P.+1 is decreased proportionally while 4,,+1 is not changed for all other queries. Thus the only potential change in the relative order of costs that of gr+1. Since we can add 4+++1 the end of query, we know that after this round Le42 is still the minimizer.
Let (q) be the length of the interval between the k-th and A: + 1-th arrival of query in the sequence of received queries (we set gl (q) = if l: exceeds the total number times g queried.). Define the following three events:
Vq E 2 (.(P)-())) P(g) S min (1./
2 log 6T
E1,-
1.
1-1
log (6T' Q
E2,1 =
Vq E Q, ( - (g) -2(B2 - -B1) min
I,
.0
((G )==
x,
Bg Q log(3TL/6))
Eg = E C (T <
B
We prove that the three events hold simultancously with probability at least 1 8:
17

---

Lemma 3. We have
(h
n M=T4/3
P
E Ez, n
ns Es 2 - 6.
Proof. From the Dvoretzky Kiefer-Wolloeee incquality, we have
P(max (P((g) P(a) c) S exxp(
9E
By taking = V (og(GT/6) we see that max (P((g) P(a) S e holds with probability at least
1 (37) for any fixed E (7]. Now by taking union bound over all [7], know that ni Ei,t holds with probability at least 1 6/3.
For the second event, from Hoeffding's inequality, we have for any g E Q.
(0,((1) a (4)) & (B2 B1) min (1. 2 1(cs * x, 9. =
2
37 Q
Now taking union bound over 1 - 8/33.
[T' and q E gives that n Eg. holds with probability least
For the third event, know that the interval (x(() satisfies geometric distribution with success probability P(g). For any g E Lr we have
B1
P (9x 2 (1- <
By taking s BalQ (L/8))/8)
Bi we know that
Bg 1 log(3TL/8))
B1
8
P
()((0)
B1
Bg
3TT
By taking union bounds over all E L and k we get the result.
Let E
n FA,. n E2,s- We can write the regret as follows.
Regret(T)
Elcost(g,, f.) + E|cost cost(ss,
[[cost(gr, L.) cott(
C8T +
Σ B|cost(qr, C.) Coss()
1=1
Note that the sampling distribution of is independent of E*. Thus we can write the expectation as
T
E[cost(ge, L.) cost(qr. (')1(E)) < Σ B(P(g) (,) 1 L*)) E (=1
Let Tx(g) = E (y: & Li 9). Note that the event = is equivalent to that ys Li. Now each round conditioned on event Er, we know that for any g E L'
P=-1(9)(,-199) 2 max P(g) min (1, 1..
(6T( t-1
(g) 2(B2 - B1) min (1.1)
log 1og(662)2//))
))
.0
Ti
log 67 Q1/8)
P(g)c(()) C(B2 Bi) min (
Tr(1)
18

---

And similarly, for any & Lt, we know that
P((0)),-11005 - P(() min 1. 1.1/2oo((T//00
)) ( S (1)) + B2 min
(
t
t-1
Now consider any 9 E Le but q Lt, and any other o' L* but o' & Lt. We have
-()))(()-P(a1))) (g)
1og(61122100) Tr(1)
(1, 1,
2 log (6T/6))))
<P(d))a=-1(1) P(a))t,-1(1)) + C(B2 B1) min
(11
+ B2 min
SC(B2 - B1) min (1.
1og(())2)/5) T((9)
2 1oog(877) /6)
+ B2 min
1.
t
Thus we know that
Blcost(yr, fx) - cost(y::
B2 min (1.
1og(671(1/5)
2 log log(6T/0)
<C
Σ 4EEL*
1(1 E (B2 -
min 1, min
1,
E
Te(4)
Thus have
Elcost(qt (4t, L.) (1)(((())))((E)
log (6T 21/))
T8 Σ
Σ
ll E LB) B1) min (1.V
Te(q)
4EEL
2 (8T
+ B2 min 1,
E Es
t-1
SC.
B,T8 + LB2 2T (og(67/0)
+ (B2 - log
ΣΣ E REC* t=1
1 & f.) min (L. Ti(a)) )
E n Esg
Now for each g L" we look the term Σ prove the following lemma:
1(g L.) min (1, (
E n Eg We
Lemma 4. We have
T
1(g z Le) min (1. T((g)
CB₂ Q log (3TL/ L/
E² n Es
<
+ T8.
B
19

---

Proof. Let (9) = Ei== (g)g) be the step that the k-th query of q arrives, with tu(g) = 0. And let
E (N Ex) Eig.
The summation can be written
r
E
( & L,) min
(
1.
E n Eg
Tr(a)
1
E
( & (.) min
1, ('V T((a)
E
+ T5
(1)1(1)
Σ
E
Σ
1(9 E Li) min (1 Tila)
E
+ T5
k=0
(x)+
T
(x+1())
1(g o L(e)))) min (1, V. T(xe))+(())
E
Σ
E
+ T8.
k=0
(=
The last inequality is due to (a) Tz(4) does not change if at round t the query is not (b) if q E ((r) we will have q E L, for any & [tx(q) + 1,4x+1 (4)] since q never arrives in the middle and must remain in the cache set until 14+1 (2). Now from event Ez, we know that
P
t++1()) (e)
E
Σ
14 & Ciuts(e)) min (".V Truco++(a))
E
k=0
(x)+
T
la & L(a-)()): gv(g) min (1V Testeiti())
E
E
k=0
B2
Q log(3TTL/88
T
1(g E foerl()) min Ten(o)+((a) )
Σ
E
B1
(g) T ( (g) + = Te (2) + if & Ciers(a) since the query q missing the cache will be sent the model. Thus overall, we know that we have either
We know that T, T
+1 (
(1))(())1 = (1) + 1, or 1(q & C(ur2(g)) Teg())+14)) = 0 and T (())(())1(()) = + (g). Thus overall, we have
T
l(q $ Clar)(a)) min (tiv Tuco+t(a))
EE
S CVT.
Vk
By taking 8 1/T, /T, we know the final regret can be bounded by
Regret(T) S CL(B2
B₁ B2 Q L log log VT.
B₁
Lower bound. Now we turn to the lower bound. We apply Le Cam's two point lemma for the regret. Consider any family of algorithm (Lo)= where L, can be dependent on observations prior to time step f. We aim to design two instances with the same P(q) and different random variable Ci(q) such that for any algorithm, the incurred cost for one of the instance is at least ((VT). Consider the case when only have two candidate queries Q 92). Set P(gi) P(92) 1/2 for both instances and the cache size = 1. For instance one, we let C (q1) ~ Bern(1 C (qz) ~
Bern[1/2 + A). For instance two, we let cf (q1) (ern(1/2), C (ge) Bern(1/2 A). We have
inf sup Regret(T) 2 inf (C.YT, P.C,
sup (C:)7- C ,
Regret(T)
inf (C.)aan 1
sup
Σ
1 & (.) Σ
1( & ())((a))
20

---

Let Regret())() (T) be the total regret when C₁ c and Regret(2) (T) be the total regret when C = c(2). Then we can verify that for any sequence of L.,
AT
Regret (2) (T) + Regret (2) (T) 2
Thus from Le Cam's Lemma, we have
AT
inf sup Regret(T)
(1 - TV(PP (u..Paa))) (m)))
(C.)_1 P.C.
4
AT
-epp( - DKL (PP (1) IP m))
8
AT
IV
exp(-222E, (T]))
Here E1 [T]] is the expected times of observing the cost of 92 under instance one. Taking A 77-1/2 and minimizing the above equation with E, [72] gives the desired bound.
G Proof of Theorem
Proof. We define the following four events:
2 2log(8/5)
E1 =
Vq E 2, P(o) <
N
log (8] 21/0)
V E (,(4(1)) cT01 s (B2 -ii)
>> 1(gn = 9)
N
log (8 21/6)
E3 =
Aq E - s (B2 - B1)
> == 1(g, = 9)
E,
Aq E Lr Σ 1(g, 9) 2 N P(g)22
We know that the above events hold simultaneously with probability at least - 8 from Lemma We condition on the four events from now on. We first decompose the cost difference as
cost Ć, #) cost(C*, T²) = cost (Ć, .) cost(L, π²) + cost(L, क cost(L", m*)
The first difference can be further written
cost(2. Ć, #) cost(L, x²) = Σ
P(g) ( ((C3))))) - +40 -(0)) (3())= -
qEQ
Σ + - (g)(1 #())
min(((()))))
gE@
x Σ P(llC(() -1)())(()))))))))))))))))))))))) m())))))((()
4EQ
= Σ P(a) (C(()))))))))))))) s + +c a(4) - min (in
ge@
Note that if (.(g) (q)) has the same sign as c;(g) oi (g), the difference c(()) <
a(())) + o7 (g) ((,((g) > a())) min(c (g)) becomes 0. Otherwise, if cg(g) - c7(9) > 0.
we know that
()(g) - (g) (g) a()) + (g) c5) + a()) d < (e)(g) c3 + (((g) ci
21

---

And similarly if (g) - (g) - O, we know that (g) (g) - +(()) - (g))
Overall, have
Elcost(C, R) cost cost(L, x,, S E
-
9E
(P)
E
P(a)((.(a) - ct(1))²
(1(00(())((1()))
9EQ
qEQ
(8))
E
Σ
P(a)(ea(9) - cg)
E
Σ
P()) - (9)
SEQ
((68) C B1)
Q log(N)
N
Here (i) is due to Cauchy-Schwarz, and (ii) is from Jensen's inequality, and (iii) is the standard rate of the least squared estimator (Rigollet and Hütter 2015).
For the second difference, we have
cost(L, T²) cost( (6 )²)
Σ P(a) ((1 (2)) min(((())e(1))))
qEQ
Σ P(a) - mln()(())
- 1(ge
MEQ
Note that for any E L" we know that
log (og(8)21/0)
P(g)
min (c,(4), ((())) - (B2 ( 2 > 1(gn 9)
2 2200((8/0) (21g(1/00),0) //00000 min (c)()), (g)) - 2(B22 Bi)
log( (gg())))8)
2 max P(a) -1
N
> 1(g. =
log( (8) 11/8))
2 P(g) min (()) C(B2 Bí)
Dami 1(gn 4)
B2 Q log(8) 21/5)
2 P() min (c)()), 4 (4)) - -B))
-B)
N
The last inequality uses event Es and Lemma
And similarly, for any g & L", we know that
P()) min (min()))), - (B2 Bily 2 > N 1( = 9))
log(8121/8)
2 2lg(8/8)
s P(() +
min (ct o7 (g))
N
2 1og((8/))
$ P(g) min (c)(g). BBy
N
Now consider any g E Le but q L*, and any other o' L but o' & L.. We have P(d)) min (c(()),)()) P(4) min (c) of (a))
log(8 (81))/)
<P(d) min (2.(1), (B2 -Bi)
En=1 14 =()) 2 2Σ
log 21/5)
B2 Q log( (8 21/8) B,N
P(g) min (c.(g),(((g) (B2 - B1),
+ +C(B, Bt)
2 Nn 1 (g =9)
Bal Q log 21/8) B, N
<C(Br B1)
22

---

Here the last inequality uses the fact that is inside L, and thus the difference between the first two terms are upper bounded by Finally, we know that conditioned on E Eg n E3 E4, we have
B2 log 8|Q1/6)
cost(L, costoc" SCL(B2- - -B))
B,N
Overall, we know that
B2 2 log(8 (/210)) N
Elcost(L, #) cost(2, S B2 + CL(B2 - Bt)
Taking 8 1/N finishes the proof.
H Proof of Theorem
Proof. Let gl (g) be the length of the interval between the k-th and (k + 1)-th arrival of query q in the sequence of received queries (we set (4) if exceeds the total number times g is queried.).
Define the following four events:
P(u)l S min 11.
}
}
F1,
Au E 2, (,)))
log(87121/0)
E2,t
Va E 2 (,,1-119) E
(g) 22BB2 B1) min
1,
.c(1
2 Σ i=l
[(s; = 0, = =q)
log(87 (87 21/6)
E3,1
Vq E Q (2 E
()(4) 2(B2 B1) min
1,
.c((a)
2
1==
1(s, = 1,
B2 Q log 4TL/6)
F4
E k (1)
S
B
From the same analysis as Lemma 3
we know that the four events (N'm L1,5 n 12 n Es,s) n E hold simultaneously with probability at least 5.
Let E =N Fi,s O E2,a Fg.s. The regret can be decomposed as follows.
(eg
E E|cost(q,, Lr, mT) cost(g;, L" x*)]
TE [ccost(yt, Le; m.) L", (*)) + E[cost(qt, L., cost(ge, L*, (F)
EE clcost(yt, Le, m.) cost(gr, L", (", 8TB2
Σ ((((oos(q, cost(gr, Le, π²) + cos
STB.
t=1
The first difference can be further written as
Elcost(q,, f,, m.) cost(gr: E+]
=E]1(q & ()) + (g:) - (1
ET
=[ & + Fe(q)) - mmn(((()))(((())) L71
((lcl(aa)m((a++(0))0))))+))))))0 -min((((a).((())
+4)) - m EE).
23

---

Note that if (9)) - (q)) has the same sign as (g)) - c7 (gt), the difference (g))))) + oi ( [ (c,,, (,,(9:)) (in ( çi (g:) becomes 0. Otherwise, if c (9:)
-
(())) and ,, (g)) - (x)) s 0, we know that 8, and
() (4) (0),((g) (L)(1) +(BB2 B1) min
L
(8: = 1, 1 = g)
log (
S2(B2 B1) min 1,
2 2
18; - 1, 4i 4)
And similarly if (g) (1) I 0 and e, (9))
21 > 0, we know that s; 0 and of (q)
(g) s 2(B2 B1 min 1, D 1ss, (s.=0))))g))
log(87 [1)]]
Overall, we have
Σ B[(cost(g:, Lr, mT)
cost(gr: LT,
T
(
<2(B2 B1)
E
(s: = 1,90 = 4) min 1, (1. 2 1 1s; = 1, = ②)
t=1 Q
+ 1(s = 0. q) min 1, log 87 Q1/8)
11 (8; = 0, q)
<2(B2 Bi
Here the last inequality uses the fact that each y E Q, the summation over time step is upper bounded by 2 2 / /olo(S7]()//)/2) < ( where T(4) is the number of steps of receiving query q total T' steps. Optimizing over T()) gives the final bound.
For the second difference, we have
Blcost(Cs, n²) cost(L',
=E
P(a) (1(g $ f.) 1(g min(c(())) E*
=E
P(a) (I(EE 110 min F²
UEQ
Note that for any y E L*, we know that
Pr(g) min (C,, (r)(4))
2(B2 - Bi) min 2 max P(g)) V 2l0g(8/0) 00 [(Te(q) = =1) (g(())
log 21/5)
2Σ 1(x: = 1, = ④)
+ +1(T((g) 0) (7(())
(0(())) - 2(B, - B1) min 1
(11(8)
2
1(s; = 0, 4)
=0,
2log(8/0)
PP(g) min (G(g), - (B, - BB)
P(g)
[((e(() = 1)
(c(()- - B1) min [1,
log(8 21/6)
2 =1=1
1(s; = 1,4 = 9)
+ 1(x((g) 0) (t(9))
(0(6)) - 2(B, Bi) min
1 V
log (8) 21/0)
-min(c(((),
2
Σ
i=1 1(s; = 0, 4. = ④)
log(81Q1/0)
> PP(2) min (c)(g). C(B, B1) min
1
-ーー 1=1 1(x = Te(g), 9:
24

---

Below we justify the last inequality. First, note that (g) is equivalent to that (g I (g)(()) Thus if (9.) (L(())) has the same sign as c (q:) cf (q+), the above inequality holds. Now consider the case when (g)( - (q.) has different sign as c, ((:) (g)) Assume that (s,(():) > (q)) and og (1t) < of (qt). We know that (1) 0, and
log (8) (1/6)
( 2(B2
B1) min
1,
(g)
2
2 1= 1(s = 0. =
log(8 21/6)
2( B1) min ("V
2 [s; 0, qi g)
Similarly we can prove that for the reversed case. Now for any q & L we know that
(g( min (C.,(1), (,(()) < P(() + 2 2log(8/0)
min (c) (g) of (4))
2 log(8/0)
S P()) min (c,()), (1)) + B2
/
Now consider any E L. but q & L* and any other o' EL but d' & L.. We have P(d') min ( P(z) min (c)(w).
<P,(d)) min (c),) (d) P(( min (9))(())
log (8 21)0)
log(88/)
+ +C(B2 B1) min
BB
t- 1(s: (e) =q)
log (og(8)211 (8121/8)
log 2log(8/0)
SC(B2 - Bi) min 1,
+ B2
- 1st Fe( 9)
Here the last inequality uses the fact that is inside Le. Thus we have
Elcost(Lo, - -000)))))(((("
E Elcost C2, x*) - cost((",="')((") ( E4)] + B8
T
1(4 & (B2 B1) min (1, 1,
log (8| (8)//8))
< T8 + C E
Σ
2
1(: Tx mx(g), 2: = ②)
1=1
9EE-
21og(8/8)
+ BBy
E Ea
SC.
B2TH+ + LB2 v 2T log(/8/)) + (B2 B,) log(TT)
T
Σ
Σg
1( L.) min 1/1 E 1(s, x((g). ) 1 Fas
GEL* 1=1
=C.
B2Tō + 2T -B2 Bog 21/0)
)
LE'DE)) E, ))
ΣΣ Σ E 1(g & L., x) min (1 E 1(s F, = 9)
E
nEL* TE(1.2)
Let Tetg. = E 1(s, =
= n. = =q). Now for each q E L and {0, 1}. we look the term
Σ E 1 L, ग. m) min (1. T((..)) E Ei]. We prove the following lemma:
25

---

Lemma 5. We have
CB2 (3T (3TL))/
Σ
E 1=1
1lq & Telg)= σ) min l'v Ie(g, x)
EE' n Ea
+
B1
Proof. Let (x) (1) -1=1 91 (g) be the step that the k-th query of q arrives. And let E = (i== E E4. The summation can be written
T
1
E 1(1 & (x(g) = -+) min
1,
EE' n
Pa
Tx)
1
E
1(q & Li, =x()) = 7) min (IV Te(a
E
+ TT
(++1(9)
Σg
E
1(q E (.( m)) min 1.V
|E
+ T8
T((a, m)
k=0
(
E
1(q & (() tea (1) T) 1=
Σ
min
E
+ T8.
(1
km0
The last inequality is due to (a). (g π) does not change if at round the query is not qi (b). if q E (g)= we will have q L. for any & (t) + 1, 1 (4)] since q never arrives in the middle and must remain in the cache set until 4++1 (g): (c) For / [lx(4) since both the frequency and cost estimator does not change for From the definition of (z))), we know that Tr, (1) (q, x) 2 1 and thus we can drop the the minimum in the above equation. Now from event E4, we know that
(x++1 (4)). क, does change
(4)
E
Σ
14g & feenlle) (1)) (ta =x) min ('i Tel xx)
E
k=0
T
E
(e(g) [q & fiutsla): Teae (4) σ) min L. T(
E
By Q log((TL/R
T
1(1 E Leemi(9)) The (g) = т) min (". T Ti
E
B
K=
We know that T ( R)) T (g, 4) + = +1 т) + if & figes(() and Teo.i (g) = π since the query missing the cache will be sent to one of the models, and only the one selected will observe the cost. Thus overall, know that we have either Tr 11)1(())
1 1, or 1(q & Cearr(s); Teaes (q) x)
min 1, (1
and
T (an100+1(9.m) TT(())+19, x). Thus overall, we have
T
Σ 1(g & Fumn()) Fea1 (g) = T) mii (1. Tueg))a(a))))
S CVT.
VI
k=
Thus we know that the second difference satisfies
T
E(cost(Li, - cost((", SC.
sc.
B2T5 + T.B2 2T
L(B, - B1) @ L log (1/6) vT)
+
B
26

---

Overall by taking = 1/T, we know that
CL(B2 B1) 2g) (T) VT.
Regret(T) v
B1
I Additional Experiments
I.1 Synthetic Datasets
We conduct synthetic online and offline experiments for joint optimization of caching and model multiplexing, We use iid. Bermoulli distributions for two models because we want to mimic the model ensemble cumulative cost and regret in online learning for LFU and LEC caching algorithms. We present more data points in Table 3] and Table under the same setting of 10000 requests with 20 different queries and cache size 10. Similar to the real dataset setting, we compare all combinations of caching strategy choices and model multiplexer choices. We consider the frequency distribution as power distribution with a = 0.5 and 0.8. The ground truth cost for each query processed by both models is set as sample from X + 1, where is called cost ratio and X is random variable generated from a Bernoulli distribution with the parameter 0.5. We consider the model multiplexer accuracy with 0.8 and We repeat the simulation 1000 times and take the mean. Consistent with Figure 2] our simulation suggests that LEC with perfect model multiplexer significantly improves the baselines when the cost ratio is large. Simulation 1000 times cannot remove all randomness so we can observe some fluctuations. Theoretically, the columns of choosing model and the columns of choosing model 2 should behave similarly.
case and give large penalty the wrong output. In Figure 2 plot the
cost ratio
selector accuracy
LFU+ model
LFU+ model 2
LFU+ selector
LEC+ model
LEC+ model 2
LEC+ selector
0.5
1.5
0.8
5.25
5.24
4.09
4.40
4.36
3.59
0.8
1.5
0.8
7.61
7.60
5.93
5.73
5.68
4.85
0.5
1.5
5.25
5.24
3.31
4.40
4.36
2.74
0.8
1.5
7.61
7.60
4.81
5.73
5.68
3.68
0.5
100
0.8
148.05
147.38
103.43
29.93
26.83
39.32
0.8
100
0.8
214.93
213.88
150.31
43.77
39.02
49.88
0.5
100
148.05
147.38
73.94
29.93
26.83
3.12
0.8
100
214.93
213.88
107.63
43.77
39.02
4.19
Table 3: offline synthetic dataset
cost ratio
LFU+ model
LFU+ model 2
LFU+ selector
LEC+ model
LEC+ model
LEC+ selector
0.5
1.5
5.35
5.34
4.34
4.60
4.59
3.75
0.8
1.5
7.79
7.78
6.32
6.01
5.98
5.09
0.5
100
150.93
150.37
76.80
31.88
28.65
4.85
0.8
100
220.19
219.49
112.26
46.44
41.45
6.31
Table 4: online synthetic dataset
1.2
Real Datasets
In this section, we provide additional experiments on real-world dataset. We run both offline and online algorithms on Lambada dataset and Opentssittant dataset, with OPT-1.3B vs OPT-13B or FastChat-TS. T5-3B Vieuna- 13B. We mainly consider three settings:
27

---

In Table 5-12, we consider distinct prompt size 100, total query size 10000, cache size 40, same as the experiments the main text.
In Table 13-20, we consider distinct prompt size 1000, total query size 2000, cache size 100. In Table 21-28, consider distinct prompt size 1000, total query size 2000, cache size 0, same as the experiments in the main text.
Our proposed algorithm mostly gives dominant results other baselines. In Table 21-28, the cache size is set to be so there is no difference between LFU and LEC.
LFU+ large
LFU+ cascade
LFU+ selector
LEC+ large
LEC+ cascade
LEC+ selector
0.2
3.77
4.11
2.17
3.71
1.83
1.26
0.5
8.11
8.85
4.54
7.93
3.51
2.29
0.8
11.43
12.47
6.35
10.91
4.63
2.86
Table 5: FLOPs for online lambda dataset, opt-1.3b opt- 13b
LFU+ large
LFU+ cascade
LFU+ selector
LEC+ large
LEC+ cascade
LEC+ selector
0.2
349.44
425.05
224.33
349.47
241.89
170.02
0.5
751.78
916.58
469.74
751.77
462.34
321.46
0.8
1059.95
1290.26
656.61
1060.01
596.92
397.01
Table 6:
Latency for online lambda dataset, opt-1.3b vs opt-13b
a
LFU+ large
LFU+ cascade
LFU+ selector
LEC+ large
LEC+ cascade
LEC+ selector
0.2
1.66
1.68
0.90
1.12
0.67
0.48
0.5
3.56
3.61
1.88
2.20
1.22
0.87
0.8
5.01
5.09
2.64
2.75
1.49
1.04
Table 7: FLOPs for online oasst dataset, fastchat-t5 vs vicuna
28

---

LFU+ large
LFU+ cascade
LFU+ selector
LEC+ large
LEC+ cascade
LEC+
selector
0.2
9.31
13.88
7.24
8.74
8.82
5.93
0.5
20.04
29.88
15.11
18.68
16.90
11.87
0.8
28.24
42.12
21.14
26.07
20.31
15.49
Table 8: Latency for online oasst dataset, fastchat-t5 vs vicuna
selector accuracy
LFU+ large
LFU+ cascade
LFU+ selector
LEC+ large
LEC+ cascade
LEC+
selector
0.2
0.8
3.49
3.81
2.60
3.44
1.50
2.00
0.5
0.8
7.71
8.43
5.76
7.54
3.09
3.94
0.8
0.8
10.81
11.80
8.06
10.36
4.11
4.76
0.2
3.49
3.81
1.91
3.44
1.50
0.99
0.5
7.71
8.43
4.22
7.54
3.09
1.97
0.8
10.81
11.80
5.90
10.36
4.11
2.50
Table 9: FLOPs for offline lambda dataset, opt-1.3b vs opt-13b
Q selector accuracy
LFU+ large
LFU+ cascade
LFU+ selector
LEC+ large
LEC+ cascade
LEC+
selector
0.2
0.8
324.02
394.22
261.89
324.02
207.71
214.03
0.5
0.8
714.87
872.60
578.91
714.87
417.01
442.05
0.8
0.8
1002.26
1220.93
810.45
1002.25
538.56
549.06
0.2
324.02
394.22
197.00
324.02
207.71
141.55
0.5
714.87
872.60
435.74
714.87
417.01
287.72
0.8
1002.26
1220.93
609.95
1002.25
538.56
358.33
Table 10: Latency for offline lambda dataset, opt- 1.3b vs opt-
selector accuracy
LFU+ large
LFU+ cascade
LFU+ selector
LEC+ large
LEC+ cascade
LEC+ selector
0.2
0.8
1.54
1.55
1.09
1.01
0.56
0.66
0.5
0.8
3.39
3.42
2.41
2.08
1.10
1.31
0.8
0.8
4.74
4.82
3.38
2.61
1.36
1.62
0.2
1.54
1.55
0.79
1.01
0.56
0.38
0.5
3.39
3.42
1.75
2.08
1.10
0.76
0.8
4.74
4.82
2.45
2.61
1.36
0.93
Table 11: FLOPs for offline oasst dataset, fastchat-t5 vs vieuna
selector accuracy
LFU+ large
LFU+ cascade
LFU+ selector
LEC+ large
LEC+ cascade
LEC+ selector
0.2
0.8
8.64
12.86
8,06
8.03
7.76
6.73
0.5
0.8
19.07
28.42
17.81
17.66
15.63
14.14
0.8
0.8
26.70
39.91
24.98
24.53
19.01
18.12
0.2
8.64
12.86
6.28
8.03
7.76
4.86
0.5
19.07
28.42
13.86
17.66
15.63
10.43
0.8
26.70
39.91
19.44
24.53
19.01
13.80
Table 12: Latency for offline oasst dataset, fastchat-t5 vicuna
29

---

a LFU+ large
LFU+ cascade
LFU+ selector
LEC+ large
LEC+ cascade
LEC+
selector
0.2
1.81
1.97
1.62
1.80
1.72
1.52
0.5
3.14
3.42
2.59
3.12
3,01
2.41
0.8
3.67
3.99
2.95
3.64
3.57
2.76
Table 13: FLOPs for online lambda dataset, opt-1.3b opt-13b
a
LFU+ large
LFU+ cascade
LFU+ selector
LEC+ large
LEC+ cascade
LEC+
selector
0.2
0.17
0.21
0.17
0.17
0.19
0.17
0.5
0.30
0.36
0.27
0.30
0.33
0.26
0.8
0.35
0.42
0.31
0.35
0.39
0.30
Table 14: Latency for online lambda dataset, opt-1.3b vs opt-13b
a
LFU+ large
LFU+ cascade
LFU+ selector
LEC+ large
LEC+ cascade
LEC+ selector
0.2
1.03
1.16
0.96
0.88
0.91
0.85
0.5
1.78
2.01
1.52
1.45
1.47
1.27
0.8
2.08
2.34
1.73
1.64
1.69
1.43
Table 15: FLOPs for online oasst dataset, fastchat-t5 vs vicuna
Q LFU+ large
LFU+ cascade
LFU+ selector
LEC+ large
LEC+ cascade
LEC+ selector
0.2
4.60
7.12
5.86
4.53
6.54
5.73
0.5
7.98
12.33
9.33
7.86
11.27
9.08
0.8
9.31
14.38
10.64
9.19
13.12
10.35
Table 16: Latency for online oasst dataset, fastchat-t5 vieuna
selector accuracy
LFU+ large
LFU+ cascade
LFU+ selector
LEC+ large
LEC+ cascade
LEC+
selector
0.2
0.8
1.40
1.52
1.04
1.38
1.06
0.91
0.5
0.8
2.62
2.85
1.95
2.59
2.15
1.69
0.8
0.8
3.09
3.37
2.30
3.05
2.62
1.98
0.2
1.40
1.52
0.76
1.38
1.06
0.57
0.5
2.62
2.85
1.43
2.59
2.15
1.13
0.8
3.09
3.37
1.68
3.05
2.62
1.35
Table 17: FLOPs for offline lambda dataset, 1pt-1.3b opt-13b
30

---

selector accuracy
LFU+ large
LFU+ cascade
LFU+ selector
LEC+ large
LEC+ cascade
LEC+
selector
0.2
0.8
0.13
0.16
0.11
0.13
0.12
0.10
0.5
0.8
0.25
0.30
0.20
0.25
0.24
0.18
0.8
0.8
0.29
0.36
0.24
0.29
0.29
0.21
0.2
0.13
0.16
0.08
0.13
0.12
0.07
0.5
0.25
0.30
0.15
0.25
0.24
0.13
0.8
0.29
0.36
0.18
0.29
0.29
0.15
Table 18: Latency for offline lambda dataset, opt-1.3b vs opt-13b
selector accuracy
LFU+ large
LFU+ cascade
LFU+ selector
LEC+ large
LEC+ cascade
LEC+ selector
0.2
0.8
0.79
0.90
0.61
0.51
0.41
0.35
0.5
0.8
1.48
1.67
1.13
0.97
0.84
0.68
0.8
0.8
1.75
1.97
1.34
1.13
0.99
0.79
0.2
0.79
0.90
0.45
0.51
0.41
0.23
0.5
1.48
1.67
0.84
0.97
0.84
0.46
0.8
1.75
1.97
0.99
1.13
0.99
0.54
Table 19: FLOPs for offline oasst dataset, fastchat-t5 vs vieuna
selector accuracy
LFU+ large
LFU+ cascade
LFU+ selector
LEC+ large
LEC+ cascade
LEC+ selector
0.2
0.8
3.55
5.49
3.42
3.41
4.43
3.15
0.5
0.8
6.65
10.28
6.41
6.45
8.50
5.90
0.8
0.8
7.86
12.14
7.57
7.61
10.06
6.95
0.2
3,55
5.49
2.69
3.41
4,43
2.40
0.5
6.65
10.28
5.04
6.45
8.50
4.59
0.8
7.86
12.14
5.95
7.61
10.06
5.44
Table 20: Latency for offline oasst dataset, fastchat-t5 vs vicuna
LFU+ large
LFU+ cascade
LFU+ selector
LEC+ large
LEC+ cascade
LEC+ selector
0.2
4.13
4.49
2.88
4.13
4.49
2.88
0.5
4.13
4.49
3.12
4.13
4.49
3.12
0.8
4.13
4.49
3.21
4.13
4.49
3.21
Table 21: FLOPs for online lambda dataset, opt-1.3b vs opt- 13b
LFU+ large
LFU+ cascade
LFU+ selector
LEC+ large
LEC+ cascade
LEC+ selector
0.2
0.39
0.48
0.31
0.39
0.48
0.31
0.5
0.39
0.48
0.33
0.39
0.48
0.33
0.8
0.39
0.48
0.34
0.39
0.48
0.34
Table 22; Latency for online lambda dataset, 1pt-1.3b vs opt-130
31

---

LFU+ large
LFU+ cascade
LFU+ selector
LEC+ large
LEC+ cascade
LEC+
selector
0.2
2.50
2.66
1.72
2.50
2.66
1.72
0.5
2.36
2.63
1.84
2.36
2.63
1.84
0.8
2.34
2.64
1.88
2.34
2.64
1.88
Table 23: FLOPSs for online oasst dataset, fastchat-t5 vs vicuna
LFU+ large
LFU+ cascade
LFU+ selector
LEC+ large
LEC+ cascade
LEC+ selector
0.2
10.45
16.08
10.37
10.45
16.08
10.37
0.5
10.48
16.18
11.25
10.48
16.18
11.25
0.8
10.48
16.19
11.54
10.48
16.19
11.54
Table 24: Latency for online oasst dataset, fastchat-t5 vs vicuna
selector accuracy
LFU+ large
LFU+ cascade
LFU+ selector
LEC+ large
LEC+ cascade
LEC+ selector
0.2
0.8
4.13
4.49
3.07
4.13
4.49
3.07
0.5
4.13
4.49
3.07
4.13
4.49
3.07
0.8
0.8
4.13
4.49
3.07
4.13
4.49
3.07
0.2
4.13
4.49
2.24
4.13
4.49
2.24
0.5
4.13
4.49
2.25
4.13
4,49
2.25
0.8
4.13
4.49
2.25
4.13
4.49
2.25
Table 25: FLOPs for offline lambda dataset, opt-1.3b opt-13b
Cx
selector accuracy
LFU+ large
LFU+ cascade
LFU+ selector
LEC+ large
LEC+ cascade
LEC+ selector
0.2
0.8
0.39
0.48
0.32
0.39
0.48
0.32
0.5
0.8
0.39
0.48
0.32
0.39
0.48
0.32
0.8
0.8
0.39
0.48
0.32
0.39
0.48
0.32
0.2
0.39
0.48
0.24
0.39
0.48
0.24
0.5
I
0.39
0.48
0.24
0.39
0.48
0.24
0.8
0.39
0.48
0.24
0.39
0.48
0.24
Table 26: Latency offline lambda dataset, opt-1.3b vs opt-13b
selector accuracy
LFU+ large
LFU+ cascade
LFU+ selector
LEC+ large
LEC+ cascade
LEC+ selector
0.2
0.8
2.50
2.66
1.84
2.50
2.66
1.84
0.5
0.8
2.36
2.63
1.79
2.36
2.63
1.79
0.8
0.8
2.34
2.64
1.79
2.34
2.64
1.79
0.2
1
2.50
2.66
1.35
2.50
2.66
1.35
0.5
2.36
2.63
1.32
2.36
2.63
1.32
0.8
2.34
2.64
1.32
2.34
2.64
1.32
Table 27: FLOPs for offline oasst dataset, fastchat-tS vs vicuna
32

---

selector accuracy
LFU+ large
LFU+ cascade
LFU+
LEC+
LEC+
LEC+
selector
large
cascade
selector
0.2
0.8
10.45
16.08
10.05
10.45
16.08
10.05
0.5
0.8
10.48
16.18
10.09
10.48
16.18
10.09
0.8
0.8
10.48
16.19
10.10
10.48
16.19
10.10
0.2
10.45
16.08
7.91
10.45
16.08
7.91
0.5
10.48
16.18
7.94
10.48
16.18
7.94
0.8
10.48
16.19
7.94
10.48
16.19
7.94
Table 28: Latency for offline oasst dataset, fastchat-t5 vs vicuna
33


Reviews:
[{"review_id": "3Ks70u0jBH", "reviewer": "Reviewer_13j8", "summary": "The paper investigates the combination of caching and model selection strategies to reduce the inference costs of large models (LLMs in particular). In the result, the authors propose a theoretically grounded algorithm that demonstrates promising results in practice. ", "questions": "The following questions will help to address my concerns about the empirical contribution in Section 5.2:\n\n* How is the performance measured for each task?\n* For a fair comparison, all methods within each row (Tables 1,2) should provide the same model quality. \n    * Does this hold true in both cases? If yes, how is it guaranteed for the chat assistant task?\n    * What is the target performance for each task?\n    * What is the criterion to quantify if the output of the small model satisfies or not (especially in the chat assistant task)?\n* In the offline setting, the predictor is not accurate enough to outperform \"cascade\" while it is not the case in the online setting. I am curious why it happens.\n    * Is the chat assistant task easier for the selector? Or is it caused by the difference in the online/offline settings?\n    * What selector is used in the online setting? How accurate is it at convergence? What portion of queries does the predictor observe until convergence?\n   * What if one tries the online and offline settings for the Lambada and chat assistant tasks, respectively?\n* How do the costs and gains depend on the cache size? What are the cache sizes in both settings? How are they selected?\n* It might be useful to report the \"large\", \"cascade,\" and \"selector\" costs without caching to understand the LFU/LEC gains better.", "limitations": "Limitations are well discussed. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The problem of the cost-effective LLM inference is in high demand.\n2. The paper is well written and easy to follow.\n3. Theoretical contribution seems novel and complete. \n4. Synthetic experiments are promising, especially when the ratio between min/max query costs is large. ", "weaknesses": "In my opinion, Section 5.2 lacks some important details and clarifications. It makes it difficult to estimate the practical contribution of the proposed approach. I highly recommend adding the detailed evaluation protocols for both tasks to the appendix. \n\n**Minor**\n* In Figure 2, please specify which plot corresponds to the offline/online setting.\n* In L132 and L152, one can introduce $\\mathcal{L}^{\\star}$ and $\\pi^{\\star}$ that appear in the corresponding equations.\n* Consider adding the cost measures to the captions in Tables 1,2 \n* Consider specifying the hardware specs used for the latency evaluation and corresponding std values in Table 2.\n* Typos: L168 \"last year\" -> \"last layer\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable comments and suggestions. We have corrected all the typos and added all the suggested details in the revision. Please find our responses to each comment below.\n\n## Comment 1\n\n**Reviewer:** \n\n\n> In my opinion, Section 5.2 lacks some important details and clarifications. It makes it difficult to estimate the practical contribution of the proposed approach. I highly recommend adding the detailed evaluation protocols for both tasks to the appendix.\n\n**Response:** \n\nThank you for your comments and sorry for missing the details! We will include all the detailed evaluation protocols in the Appendix. Please find below for our responses to the individual questions.\n\n\n\n## Comment 2\n\n**Reviewer:** \n\n\n> How is the performance measured for each task? What is the target performance for each task? What is the criterion to quantify if the output of the small model satisfies or not (especially in the chat assistant task)?\n\n\n\n**Response:** \n\nFor the offline next-token prediction task, the target performance metric is the number of correct tokens predicted. We have the ground-truth token from the Lambada dataset. Thus it is easy to measure the success. If the small model is chosen but its result is wrong, the large\nmodel must be run and it will incur an additional FLOPs.\n\nFor the online chat assistant task, the quality of response is evaluated by GPT4 judgement. We say a response is satisfying if the score is larger than 6 out of 10, and unsatisfying otherwise. If the response from the small model is unsatisfying, we will call the large model again and incur an additional cost in latency.\n\n## Comment 3\n\n**Reviewer:** \n\n\n> For a fair comparison, all methods within each row (Tables 1,2) should provide the same model quality.\nDoes this hold true in both cases? If yes, how is it guaranteed for the chat assistant task?\n\n**Response:** \n\nThank you for your comments! Yes, in the next-token prediction task, if the small model fails to predict the ground-truth, we will call the large model again to re-generate. Thus it provides the same quality. In the chat assistant task, if the response of the small model is evaluated as unsatisfying (score less than 6 out of 10 in GPT 4 judgement), the large model will be called to ensure the output quality is as good, at a cost of higher latency due to calling both small and large model sequentially. Thus all the methods are providing the same model quality. One may adjust the GPT 4 judgement score to be more strict on the quality of the output.\n\n\n\n\n## Comment 4\n\n**Reviewer:** \n\n\n> In the offline setting, the predictor is not accurate enough to outperform \"cascade\" while it is not the case in the online setting. I am curious why it happens. Is the chat assistant task easier for the selector? Or is it caused by the difference in the online/offline settings? What selector is used in the online setting? How accurate is it at convergence? What portion of queries does the predictor observe until convergence? What if one tries the online and offline settings for the Lambada and chat assistant tasks, respectively?\n\n\n**Response:** \n\nThank you for your comments! In both offline and online settings, we work with 100 distinct prompts. In offline setting, we train a BERT-based model for predicting based on 2k prompt-responses pairs. In the online setting, we consider a tabular case selector where one memorizes the cost for each prompt after seeing them once, and thus the selector converges when it sees each of the query once. \nIn the online setting, the initialization for the selector is calling the small model first (same with cascade) and changing to call the larger model when it learns that the larger model is better. This makes our method better than cascade.\n\nIn practice, the quality of the predictor continues to improve as we have more online data. And we can have good  estimation for those that are seen multiple times (and more likely saved in cache). The shaded area in Figure 2 shows the variance which shows the convergence rate.\n\nWe added new experiments of the online and offline settings for the Lambada and chat assistant tasks which are included in the attached pdf.\n\n\n\n\n## Comment 5\n\n**Reviewer:** \n\n\n> How do the costs and gains depend on the cache size? What are the cache sizes in both settings? How are they selected?\nIt might be useful to report the \"large\", \"cascade,\" and \"selector\" costs without caching to understand the LFU/LEC gains better.\n\n\n**Response:** \n\nThank you for your comments! The gains for caching largely depend on the number of cached items and the distributions of real-world queries. In our experiments, we work with 100 distinct queries and cache 40 queries. Thus the gain for caching is relatively large compared to the case without caching. If we only save 5 queries, the gain for caching can be lower. \n\nTo provide a more comprehensive comparison, we have added new experiments for different cache size, including no cache, 40 cache out of 100 queries, and 100 cache out of 1000 queries in the revised version (along with the uploaded PDF). \n"}, {"review_id": "yXacEljYQY", "reviewer": "Reviewer_puCe", "summary": "The paper addresses the computation costs of large language models. Specifically, the paper proposes a framework where previous queries are cached and retrieved and where given a query to process, an appropriate model is selected to answer based on the query. The framework flow is the following: given a query in test time, we check whether the response can be retrieved from the cache. If so, we return from the cache. If not, we select one of two models based on the query, where a natural configuration is to have two models - a large more accurate model with large computation cost and a small less accurate model with smaller computation costs (the com. cost can be measured in various ways). \n\n\nCache:\nThe method estimates two oracle - the first oracle DenEstOracle estimates the probability distribution that a query q will be observed. This is useful in defining the cache, sense we want to cache the most frequent queries.  The second oracle is RegressionOracle which estimates the cost of processing a query. This is useful since we want to cache the queries which cost the most to process. Then, in the online setting, in time step q we can have a cache which in stores the most frequent queries which also have the most cost. Remember that the cache is finite, so formally, in time step t the cache which is denoted L_t holds the L caches such that for query q in L_t the value P_t(q) * Cl_t(q) is larger than all previously seen queries that are not in the cache. This basically means that the set of queries in the cache is optimal, in the sense that the estimated cost of encountering those queries is the largest given both the probability that we will encounter them and the cost of processing them. \n\nModel selector:\nNow, for the model selector, the method assume that the cost of a query is weighed sum of the C_0(q) + Y(q) * C_1(q), where C_0(q) is the compute cost of the small model assuming the user is satisfied with the results, C_1(q) is the cost if the user is not satisfied with the results and Y(q) is a random binary variable denoting whether or not the user is satisfied. Appendix A discusses the costs and model selection and considers options such as C_1(q) == cost of user dissatisfaction or C_1(q) == cost of re-running the large model on q where the latter is used in the online experiment presented in the paper.\n\nNow, in the online setting the model selector simply chooses the model with the smaller cost and the cache stores the queries with largest P(q) * min(C*_s(q), C*_l(q)) where C* is the estimated cost for the RegressionOracle.\n\nThe paper provides experimental results in synthetic, offline and online setting (online setting is done using the open assist dataset). The paper compares against baseline such as simple Least Frequently Used (LFU) cache as baseline cache and simple cascade (calling the large model if the result of the small model is un-satisfactory) as model selector. The paper compares the baselines against the proposed cache and model selector, separately and jointly. ", "questions": "Can you discuss how to ensure the cache diversity? the top most probable queries might be very similar to each other. I understand that the method does not cacher queries, but \"query groups\" where similar queries are cached as one group (it is assumed in the paper that there exists some semantic search oracle that can group the prompts with the same semantic meaning). Still, due to the long tail distribution of queries, the bottom most frequent queries in the cache might be less similar to each other than the top ones, which might motivates grouping the queries differently, i.e. taking into account P(q) and varying the minimal distance to group two queries together by semantic search oracle that groups prompts close embedding. If the cache is not diversified enough, less common queries would be processed slower. This is especially true if we want to ensure the system is not biased towards specific user population.  \n", "limitations": "The authors did not specifically addressed limitations or potential negative societal impact of their work. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "* The paper addresses an important real-world problem in a novel manner with both a detailed theoretical discussion and practical experiments and results.\n* The presented framework is general and can be extended/adjusted to various use cases and practical applications.  \n* The paper is well written and easy to follow.", "weaknesses": "IMO, the experiments can benefit from further analysis, e.g.:\n* Performance/accuracy analysis as function of number of steps in the online setting.\n* What is the cost of running the model selector and how does that affect the performance of the system?\n* Can you provide some accuracy measure of the oracles? for example, in the online setting, how many steps are required so that the oracles would be properly estimated? What is the accuracy as a function of the step number?\n ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable comments and suggestions. We have corrected all the typos and added all the suggested details in the revision. Please find our responses to each comment below.\n\n\n\n## Comment 1\n\n**Reviewer:** \n\n\n> The experiments can benefit from further analysis, e.g.: \n- Performance/accuracy analysis as function of number of steps in the online setting. \n- What is the cost of running the model selector and how does that affect the performance of the system? \n- Can you provide some accuracy measure of the oracles? for example, in the online setting, how many steps are required so that the oracles would be properly estimated? What is the accuracy as a function of the step number?\n\n\n**Response:** \n\nThank you for your comments! \n\n- For the online case, the accuracy w.r.t. step size largely depends on the number of distinct queries we face. In our experiments, we use 100 distinct queries. And thus the oracle quickly converges after seeing the cost most of the queries once. The accuracy is thus proportional to the fraction of seen queries, and is directly affected by the distribution of the queries. We are happy to add more details in the revised paper. \n\n- The cost of running the model selector is equivalent to one forward call of the used model (BERT or causal language models). In contrast, for a response with 1000 tokens, the causal language models like LLama, Vicuna and GPT 3.5 require 1000 times of forward call. Thus the cost of running the model selector is neglibile compared to the cost used to generate the responses.\n\n- The shaded area in Figure 2 shows the variance which shows the convergence rate of the oracle selector. In practice, the quality of the predictor continues to improve as we have more online data. And we can have good estimation for those that are seen multiple times (and more likely saved in cache). \n\n\n\n\n## Comment 2\n\n**Reviewer:** \n\n\n> Can you discuss how to ensure the cache diversity? the top most probable queries might be very similar to each other. I understand that the method does not cache queries, but \"query groups\" where similar queries are cached as one group (it is assumed in the paper that there exists some semantic search oracle that can group the prompts with the same semantic meaning). Still, due to the long tail distribution of queries, the bottom most frequent queries in the cache might be less similar to each other than the top ones, which might motivates grouping the queries differently, i.e. taking into account P(q) and varying the minimal distance to group two queries together by semantic search oracle that groups prompts close embedding. If the cache is not diversified enough, less common queries would be processed slower. This is especially true if we want to ensure the system is not biased towards specific user population.\n\n\n\n**Response:** \n\n\nThank you for the comment! We are happy to include more discussions on the cache diversity. You are absolutely correct that in the case when the bottom most frequent queries in the cache are less similar to each other, we may want to motivate grouping differently. Vector database is popular for retrieving relevant documents by matching queries with similar embeddings into the same group, thus grouping responses with similar semantic meaning. In the case of caching, we may want to design new embedding method that takes into account the frequency $P(q)$ and design different thresholds for grouping. This will be a very interesting open problem to be further explored.\n\n\n\n\n## Comment 3\n\n**Reviewer:** \n\n\n> The authors did not specifically addressed limitations or potential negative societal impact of their work.\n\n\n\n**Response:** \n\nThank you for your comments! We will include more discussions on the limitations or potential negative societal impacts of the work. For example, this may lead to biased processing speed towards specific user population when the group sends more queries than other groups. \n"}, {"review_id": "TvHsrQsfrm", "reviewer": "Reviewer_FCsT", "summary": "This paper presents an LLM inference framework design that aims to reduce inference cost by caching and model selection. This work first provides an optimal formulation for jointly optimizing both caching and model selection in both offline and online settings. Then, evaluations on simulations and two tasks show that proposed work achieves cost saving compared to baseline.", "questions": "(1) In section 5.2, the next-token prediction task uses FLOPs as the cost, and the chat assistant task uses latency as the cost. Is there a reason to use different cost definition here? Or why not evaluate both cost definitions in both cases?", "limitations": "The authors acknowledged some limitations, such as “We leave the training of a better selector as future work.”.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "(1) The high-level idea of caching + model selection sounds reasonable for LLM inference.\n\n(2) Detailed formulation of the optimization problem.\n", "weaknesses": "(1) My most unsatisfying part of this work is that the problem that authors try to solve should not be simplified to “cost saving” only, but it should be formulated as “a cost-accuracy trade-off”. I do see that the authors acknowledge that it is a trade-off (e.g., “The need for fuzzy search.” In introduction, and in section 5.2 “If the small model is chosen but its result is wrong, the large model must be run and it will incur an additional penalty.”), but I really want the authors to investigate more about this instead of simply comparing on the cost. For example, for fuzzy search during caching, how much will it actually affect inference accuracy? For model selection, what if there are more than two models, and what if there is no way to know whether the inference result is correct or not (so that you cannot use multiple models). Ultimately, the results should be presented as a cost-accuracy Pareto curve, and the proposed work has to show how it advances the Pareto frontier compared to baseline (achieving better accuracy under same cost, or achieving same accuracy under less cost). The unbalance between formulation (5 pages) and experiments (1.5 pages) exacerbates this issue.\n\n(2) In introduction it says “For the fuzzy search problem, semantic search or vector-embedding-based ideas provide a systematic solution that includes embedding extraction and matching algorithms. To simplify the problem, we assume that there exists some semantic search oracle that can group the prompts with the same semantic meaning…”. To me this assumption oversimplify the caching problem. In order to demonstrate the feasibility of caching, it’s needed to actually build yourself a semantic search-based cache, and actually evaluate how it affects the accuracy-cost tradeoff.\n\n(3) In section 5.2 it says “We fine-tune a BERT-base model as the model selector by predicting whether the small model can give the correct result and achieve 80.2% accuracy.”. But I can’t find any further information such as the fine-tune hyperparameters, and whether this 80.2% accuracy is training accuracy or validation accuracy.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable comments and suggestions. Please find our responses to each comment below.\n\n## Comment 1\n\n**Reviewer:** \n\n\n> That authors try to solve should not be simplified to “cost saving” only, but it should be formulated as “a cost-accuracy trade-off”. I really want the authors to investigate more about this instead of simply comparing on the cost. The results should be presented as a cost-accuracy Pareto curve, and the proposed work has to show how it advances the Pareto frontier compared to baseline (achieving better accuracy under same cost, or achieving same accuracy under less cost). \n\n**Response:** \n\nIt is a misunderstanding that we only focus on \"cost saving\". In both theory and experiments, we focus on the **cost-accuracy trade-off rather than cost**. Additionally, our framework is not limited to cost-accuracy trade-off. It optimizes for the objective, which can be defined as any reward depending on the scenario. In small-large model selection which is the motivating example in our paper, the reward is defined as the cost-accuracy trade-off. While in the model ensemble setting, the objective can be simply defined as accuracy. See below for more details.\n\n- It might be misleading that we call $c$ as a cost function (a terminology in bandit), which is indeed a trade-off term between the cost in real world and accuracy. For example, a common choice of $c$ can be chosen as $c(q) =$ cost of $q - \\lambda\\times$ accuracy of $q$. Our theoretical analysis shows that once we choose the target function $c$ regarding how one combines cost and accuracy (i.e. fix a $\\lambda$), the proposed algorithms always give the minimax-optimal trade-off between cost and accuracy. Thus our framework is general enough to incorporate any trade-off between cost and accuracy.\n\n- In our experiments, we **always guarantee the output quality at the same level**, and compare the cost. Thus the proposed algorithm advances the Pareto frontier compared to the baseline. In all experiments, if we call small model and find that it is not giving satisfying result (the evaluation score from GPT4 is smaller than 6 out of 10), we will call the large model again to fix the output. This incurs extra cost due to the error induced and the extra compute needed to call the large model. No matter whether we hit or miss the cache, and whether we select the wrong model or the correct model, the output will always be satisfying with score larger than 6. One may also change the reward from binary satisfying vs unsatisfying to the actual scalar of GPT 4 eval.\n\n\n## Comment 2\n\n**Reviewer:** \n\n>  For model selection, what if there are more than two models, and what if there is no way to know whether the inference result is correct.\n\n**Response:** \n\nWe briefly discuss how to generalize to multiple models in Appendix C. If there're $K$ models, we can train a neural network with $K$  dimensional output, each predicting the cost for one model. If there is no way to evaluate the result, the model selection algorithm would not work. However, there have been a good amount of evaluation methods, like judgement from GPT4, or a reward model trained from human preference data. \n\n## Comment 3\n\n**Reviewer:** \n\n> In introduction “We assume that there exists some semantic search oracle that can group the prompts with the same semantic meaning…”. This assumption oversimplify the caching problem. In order to demonstrate the feasibility of caching, it’s needed to build a semantic search-based cache, and evaluate how it affects the accuracy-cost tradeoff. For fuzzy search during caching, how much will it actually affect inference accuracy?\n\n**Response:** \n\n- There have been some preliminary studies and systems using vector database for caching in [1], which represents the query as a vector from the embedding of a pre-trained or fine-tuned large language model specifically designed for retrieval. Thus the effectiveness of simple caching has been demonstrated, and building such a semantic search system only for caching is not our main focus given existing efforts.\n\n- According to [2], the cache hit rate in web search systems is usually 30%-60%. The semantic matching part in large models shall be very similar to the existing ones used in the web search systems. And thus there are been mature systems in industry that validate the effectiveness of caching system.\n\n- Even without semantic search and fuzzy matching, the exact-match-based caching is useful in practice. When it comes to using LLM for API calls to software, we expect more redundant and identical queries. And the cache hit rate can be much higher than chat even if we do exact match. Our experiments with exact match also validates the effectiveness of the proposed algorithms.\n\n- In our paper, we focus on identifying the information-theoretic optimal algorithms for jointly optimizing the caching and model selection system. We believe that the most appropriate fuzzy search deserves a serious and comprehensive study. But this may be out of the scope of our current focus.\n\n[1] GPTCache: https://github.com/zilliztech/GPTCache\n\n[2] Jeff Dean, Building Software Systems at Google and Lessons Learned\n\n## Comment 4\n\n**Reviewer:** \n\n> - In section 5.2 it says “We fine-tune a BERT-base model and achieve 80.2% accuracy.”. But I can’t find any further information such as the fine-tune hyperparameters, and whether this 80.2% accuracy is training accuracy or validation accuracy.\n> - In section 5.2, the next-token prediction task uses FLOPs as the cost, and the chat assistant task uses latency as the cost. Is there a reason to use different cost definition here? Or why not evaluate both cost definitions in both cases?\n\n**Response:** \n\n- We will include all the details on the fine-tune hyperparameters and the models. This 80.2% accuracy is test accuracy on the unseen prompts. \n\n- We have included experiments for both FLOPs and latency for both cases in the revised paper, along with the one page PDF. \n"}, {"review_id": "Our4gsgRRR", "reviewer": "Reviewer_X4Ge", "summary": "* this paper proposes a theoretically optimal algorithm for efficient large-scale deployment of LLMs\n* particularly; they combine caching and model selection to reduce the inference cost\n* they provide theoretical guarantees for both caching w and w/o model selection", "questions": "* how can we assess whether caching is relevant in a particular setup? for example, when using publicly available datasets like OpenAssistant; what if there are no redundant queries? ", "limitations": "yes, the authors discussed limitations and future work directions", "rating": 8, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* large scale models are deployed everywhere and the motivation to make inference more efficient is very strong\n* the paper comes with strong theoretical guarantees\n* the method's efficiency gains are demonstrated in relevant real-world settings using models up to 13B\n* the idea to perform model selection on the fly in an online fashion seems clever", "weaknesses": "I have to admit that this paper is out of my depth. The considered (problem, solution) seems very convincing and relevant to me, but I'm not familiar with its literature and cannot identify any obvious weaknesses. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable comments and suggestions. Please find our responses to your comment below.\n\n## Comment 1\n\n**Reviewer:** \n\n> How can we assess whether caching is relevant in a particular setup? for example, when using publicly available datasets like OpenAssistant; what if there are no redundant queries?\n\n\n**Response:** \n\nThank you for your comment! The cache hit rate depends heavily on the application. Below are three cases:\n\n- According to [1], the cache hit rate in web search systems is usually 30%-60%.\n- According to our own calculation from the public data in [2], the cache hit rate for saving 3k conversations in real-world chatbot over 33k chat data is 31%. There may not be too many queries that are exactly the same. However, one can match the queries with the same semantic meaning. Thus we use fuzzy matching by constructing a vector database for all the queries, and match them when their cosine similarity is large enough so that they have very close semantic meaning. \n- When it comes to using LLM for API calls to software in enterprise, we shall expect more redundant queries and the cache hit rate might be much higher than chat even if we do exact match. \n\n\n[1] Jeff Dean, Building Software Systems at Google and Lessons Learned\n\n[2] Lianmin Zheng et al., Judging LLM-as-a-judge with MT-Bench and Chatbot Arena"}, {"review_id": "tS7oX5DJmK", "reviewer": "Reviewer_rcfj", "summary": "The paper presents an innovative approach to mitigating the challenges posed by large language models (LLMs), namely high resource consumption and latency, by employing a cache to store previous queries and a model selector to choose the most efficient model for query processing. The authors propose an optimal algorithm that jointly optimizes both these approaches in offline and online tabular settings, and demonstrate its effectiveness through a series of simulations and real-world dataset experiments. The paper concludes by suggesting potential future research directions in caching and model selection optimization.", "questions": "1)  How does the proposed algorithm scale when selecting from a large number of models, possibly in the order of thousands or millions? Can you provide any theoretical or experimental insight on this scenario?\n\n2) While you discuss inserting prompts into a cache, the paper does not fully address how prompts are represented in the cache. Could you elaborate on this aspect of your approach?", "limitations": "The authors have touched upon potential future work related to this study, highlighting open problems that require further investigation. However, a discussion on the limitations of their approach and its potential negative societal impacts seems to be missing. An exploration of the potential risks associated with the approach, such as the possible amplification of biases if the model selector disproportionately selects certain models, would be beneficial. Further, a discussion on how this approach could contribute to increasing centralization and monopolization in AI due to the computational requirements of maintaining and selecting from large model ensembles could offer a balanced perspective.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) This paper introduces a novel approach to dealing with the resource-intensive nature of LLMs by jointly optimizing the usage of a cache and a model selector. It creatively merges established concepts of caching with model selection.\n\n2) The theoretical grounding and empirical validation of the proposed algorithm underline the quality of the research. The authors have effectively leveraged the Greedy Dual Size with Frequency (GDSF) and Least Expected Cost (LEC) caching algorithms alongside a model selector to achieve optimal rates.\n\n3) The paper is well-structured and effectively communicates complex ideas and methodologies in a clear and comprehensive manner. The stepwise progression from basic principles to specific techniques is particularly commendable.\n\n4) Addressing the issues of resource consumption and latency in LLM deployment is of critical significance in modern AI. The proposed solutions have a potentially broad impact, improving efficiency and feasibility of real-world AI applications.", "weaknesses": "1) Model Selection Scope: The experiments seem to consider a limited number of model options. The approach may encounter difficulties when scaling up to situations where selection is to be made from thousands or millions of models, which is a realistic scenario in complex AI systems.\n\n2) Prompt Representation in Caching: While the paper does a good job of exploring how to insert into a cache, it doesn't delve into the challenge of representing each prompt in the cache. This is an important aspect of LLM serving, as a comprehensive strategy for hashing, differentiating knowledge, and specifying unit information is necessary for efficient caching.\n\n3) The idea and each problem is well known. I am not sure about the novelty of the approach. The application and problem is critical though.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nThank you for your valuable comments and suggestions. Please find our responses to each comment below.\n\n## Comment 1\n\n**Reviewer:** \n\n\n> Model Selection Scope: The experiments seem to consider a limited number of model options. The approach may encounter difficulties when scaling up to situations where selection is to be made from thousands or millions of models, which is a realistic scenario in complex AI systems. How does the proposed algorithm scale when selecting from a large number of models, possibly in the order of thousands or millions? Can you provide any theoretical or experimental insight on this scenario?\n\n**Response:** \n\nThank you for your comments! We briefly discuss how to generalize to multiple models in Appendix C. If there's $K$ models, we can train a neural network with $K$ dimensional output, each predicting the cost for one of the models. So as the number of models $K$ grows, only the last layer of the neural network scales linearly with $K$. However, this won't be able ideal to deal with the case of millions of the models, since that require a large amount of training data for the selector to estimate accurately the cost for all the models.\n\nGiven the current size of large langauge models (billions of parameters -> tens of Gb per model size and memory consumption), it is not yet realistic to simutaneously run thousands or millions models at a time for serving. Also, there may not be that many high-quality language model that needs to be served at the same time. So we believe our setting is a realistic setting especially in the field of large language models.\n\n\n\n\n\n\n\n## Comment 2\n\n**Reviewer:** \n\n\n> Prompt Representation in Caching: While the paper does a good job of exploring how to insert into a cache, it doesn't delve into the challenge of representing each prompt in the cache. This is an important aspect of LLM serving, as a comprehensive strategy for hashing, differentiating knowledge, and specifying unit information is necessary for efficient caching. While you discuss inserting prompts into a cache, the paper does not fully address how prompts are represented in the cache. Could you elaborate on this aspect of your approach?\n\n\n\n**Response:** \n\nThank you for the comments! We agree that prompt representation is very important problem left open. There have been some preliminary solutions from vector database in [1], which represents the query as a vector from the embedding of a pre-trained or fine-tuned large language model specifically designed for retrieval. And one can compute the cosine similarity between the vectors of prompts to determine whether they're similar in semantic meaning or not. However, we still don't see a comprehensive research study on which method leads to best caching problem. \n\nFor this paper, we focus on the optimal algorithm for caching and model selection. We assume that we either do exact match (with simple hashing on the prompts) or the existing semantic matching algorithms are good. The exact match case can also be applied to practical scenarios, especially when the large language models are used for serving API calls enterprise softwares and the prompts are simple and more repetitive. In our experiments, we focus on exact match case and directly use hashing to represent the prompts for caching. We believe that the appropriate prompt representation deserves a serious and comprehensive study, but this may be out of the scope of our current focus.\n\n\n[1] GPTCache: https://github.com/zilliztech/GPTCache\n\n## Comment 3\n\n**Reviewer:** \n\n\n> The idea and each problem is well known. I am not sure about the novelty of the approach. The application and problem is critical though.\n\n\n**Response:** \n\nThank you for your comments! \n\n\n- In terms of formulation, we are the first to formulate the joint optimization of caching and model selection for large language models. Different from most of the traditional caching problems, where the cost of each query is the same, the queries for large language model differ a lot in terms of the response lengths, and thus leading to varying costs. Furthermore, when we have multiple models, this would lead to further variations in the cost for generating responses. Thus the formulation we propose is new. \n\n- Theoretically, we prove the minimax-optimality of the LEC + model selector idea in both offline and online settings. The upper bound analysis is very different from traditional bandit problems. In traditional bandit, one has the ability to choose which action to explore in each round. However, in our setting, the actions (queries) come passively as samples from a fixed query distribution, and we can only choose caches which hurt the exploration of cached queries. This brings a brand new theoretical question and requires completely new analysis. \n\n- We show that the optimal model selector requires a lower confidence bound adjustment on the estimated performance. Such a correction term is new and critical for the optimality of the algorithms in both offline and online settings.\n\n- Empirically, we are the first to systematically benchmark the existing caching and multi-model serving ideas for large language models. We demonstrate the superiority of both LEC and the proposed model selector compared with existing ideas like LFU or cascading. \n\n\n\n## Comment 4\n\n**Reviewer:** \n\n\n> A discussion on the limitations of their approach and its potential negative societal impacts seems to be missing. \n\n\n\n**Response:** \n\nThank you for your comments! We will add more discussions on the limitation of the paper in the revised version, including potential biases introduced due to caching and model selector, and how this approach could lead to centralization and monopolization in AI due to the computational requirements of maintaining and selecting from large model ensembles."}]

Author rebuttal:
We would like to thank the reviewers for the valuable comments and suggestions, which have helped us greatly improve the paper. Here we briefly summarize our additional experiments done for the rebuttal period.

In our original experiments in the main text, we include 2 experiment tables with $100$ distinct queries, $40$ cache size and $10k$ total number of queries on both FLOPs for offline next-token-prediction task and latency for online chat task.

In our revised version, we include **22 extra experiment tables on different parameters and tasks**, listed as below:

- For the original set of parameters ($100$ distinct queries, $40$ cache size and $10k$ total number of queries), we include 6 extra experiment tables. Combined with the two original tables, they form the metric [FLOPs, latency] on [offline, online]  [next-token-prediction, chat] task, thus in total 8 tables. 

- We include another 8 tables with parameters ($1000$ distinct queries, $0$ cache size and $2000$ total number of queries), with the metric [FLOPs, latency] on [offline, online]  [next-token-prediction, chat] task.

- We include another 8 tables with parameters ($1000$ distinct queries, $100$ cache size and $2000$ total number of queries), with the metric [FLOPs, latency] on [offline, online]  [next-token-prediction, chat] task.

Due to space limit of one page PDF for uploading during rebuttal, we only include the first 6 extra experiments on the same parameters for different metrics and different tasks / settings. We also include two extra tables on the case without any cache ($1000$ distinct queries, $0$ cache size and $2000$ total number of queries) below. The rest will be available in the revised paper. The tables list cumulative costs ($10^3$).

> FLOPs on offline lambda dataset, opt-1.3b vs opt-13b 

| \(\alpha\) | selector accuracy | large | cascade | selector |
|------------|-------------------|------------|--------------|---------------|
| 0.2        | 0.8               | 4.07       | 5.65         | **3.22**     |
| 0.5        | 0.8               | 4.16       | 4.57         | **3.02**     |
| 0.8        | 0.8               | 4.12       | 4.42         | **3.09**     |
| 0.2        | 1                 | 4.14       | 3.82         | **1.87**     |
| 0.5        | 1                 | 4.13       | 4.35         | **2.28**        |
| 0.8        | 1                 | 4.13       | 4.46         | **2.24**     |


> Latency on offline lambda set, opt-1.3b vs opt-13b

| \(\alpha\) | selector accuracy | large | cascade | selector |
|------------|-------------------|------------|--------------|---------------|
| 0.2        | 0.8               | 0.39       | 0.54         | **0.35**     |
| 0.5        | 0.8               | 0.39       | 0.48         | **0.32**         |
| 0.8        | 0.8               | 0.39       | 0.48         | **0.32**         |
| 0.2        | 1                 | 0.39       | 0.47         | **0.19**     |
| 0.5        | 1                 | 0.39       | 0.45         | **0.23**     |
| 0.8        | 1                 | 0.39       | 0.46         |**0.24**         |



Meta-review: This paper presents an algorithm for speeding up inference of large models via two methods: 1) caching prior queries, and 2) selecting an appropriate model that minimizes cost while attaining reasonable performance. An algorithm is developed to perform caching and model selection optimally, and experiments show that the algorithm provides significant speedups. Reviewers generally agreed about the soundness of the method, and the post-rebuttal consensus was to accept this paper (particularly given the large amount of additional experiments included).
Decision: Accept (poster)