Cache Management for Mixture-of-Experts LLMs – extended version Spyros Angelopoulos, Loris Marchal, Adrien Obrecht, Bertrand Simon Abstract Large language models (LLMs) have demonstrated remarkable capabilities across a variety of tasks. One of the main challenges towards the successful deployment of LLMs is memory management, since they typically involve billions of parameters. To this end, architectures based on Mixture-of-Experts have been proposed, which aim to reduce the size of the parameters that are activated when producing a token. This raises the equally critical issue of efficiently managing the limited cache of the system, in that frequently used experts should be stored in the fast cache rather than in the slower secondary memory. In this work, we introduce and study a new paging problem that models expert management optimization. Our formulation captures both the layered architecture of LLMs and the requirement that experts are cached efficiently. We first present lower bounds on the competitive ratio of both deterministic and randomized algorithms, which show that under mild assumptions, LRU-like policies have good theoretical competitive performance. We then propose a layer-based extension of LRU that is tailored to the problem at hand. Extensive simulations on both synthetic datasets and actual traces of MoE usage show that our algorithm outperforms policies for the classic paging problem, such as the standard LRU. 1 Introduction Large Language Models (LLMs) have revolutionized the application of AI in fields as diverse as text generation, machine translation, and natural language understanding. LLMs such as GPT-4, PaLM and LLaMA are at the core of applications ranging from conversational agents to code generation tools, bringing unprecedented fluency and accuracy to text production. The performance of LLMs is closely tied to their size , with modern models consisting of billions or even trillions of parameters [ 22 ] . While this scale greatly enhances performance, it also poses a major challenge: the management of the immense computational resources required for their training and usage. Once trained, LLMs are deployed for inference , the process of generating text or predictions, which typically needs to be rapid for real-time applications. However, inference is computationally intensive, and thus particularly demanding in resource-constrained environments such as mobile devices or systems with limited memory and processing power. This challenge has led to extensive research into optimization methods that enhance efficiency without significantly compromising model accuracy. Notable approaches include model compression techniques such as quantization [ 24 ] , which reduces the precision of model parameters (commonly known as weights ), and sparsification [ 14 ] , which prunes less important parameters. One well-established strategy for model sparsification is the Mixture of Experts (MoE) architecture. We provide a high-level overview of this model, and we refer to [ 9 , 27 ] for a more detailed technical definition. A MoE model consists of a sequence of transformer layers (or layers, for simplicity). Each layer is composed of an attention mechanism, which selectively focuses on the most relevant parts of the input, and a MoE block, as depicted in Figure 1 . A gating function uses the attention output to determine which experts in the MoE block are activated, while the others remain inactive. This approach offers two key advantages: first, it achieves high accuracy in text generation tasks because the model can leverage a large pool of weights across all the experts. Second, since only a small proportion of experts are active during each inference, it significantly reduces storage and computational costs. Figure 1 : High-level illustration of the Mixture-of-Experts architecture While MoE models allow for a selective, and parsimonious activation of experts, their management remains challenging. First, in order to maintain high accuracy, the combined size of all the experts’ weights is generally larger than the total size of weights in non-MoE models [ 22 ] , leading to storage complications. LLMs are autoregressive models, meaning that the entire pipeline of all layers has to be processed for the production of each token—a word or a portion of a word in the generated text. Hence, even though only a limited number of experts are activated per layer for each token, loading their weights into memory incurs a significant cost that adds to the overall computational cost. Such issues were observed in [ 10 ] , which showed that caching certain experts weights in the memory, instead of reloading them for each layer, improved the inference time. This was achieved using a simple Least-Recently-Used (LRU) replacement policy. However, the following question arises naturally: What are the power and limitations of caching policies for MoE models of LLMs? What theoretical and experimental improvements can one obtain, especially relative to standard caching approaches suitable for much simpler environments, such as LRU? 1.1 Contribution In this work, we answer the above question by introducing and studying a new model of online caching that is tailored to the characteristics of MoE-based LLMs. The model allows us to provide rigorous theoretical bounds on the performance of both deterministic and randomized caching policies, using the framework of competitive analysis [ 5 ] . This framework has been infuential in the study of many other variants of caching (see Section 1.2 for related works) and we likewise demonstrate, for the first time, that it can be equally useful in the context of LLMs. In Section 2 we describe in detail a layered model of caching, which defines the interactions between the experts across the layers, and involves parameters such as the number of layers \ell , the number of experts n , and the cache size k . In Section 3 we give lower bounds on the competitive ratio of deterministic and randomized caching policies. These bounds show that as long as the parameters n or \ell are constant (which is typically the case in all current models), the best-possible competitive ratios cannot improve, asymptotically, upon standard policies such as LRU. While the theoretical lower bounds may seem, at first sight, quite restrictive, they provide insights about how to obtain algorithms that perform better in practice. In Section 4 we propose an extension of LRU that is adapted to the problem at hand. In Section 5 we perform an extensive experimental evaluation of our algorithm on a variety of traces from real data of MoE usage, as well as on synthetic datasets. The results demonstrate that our algorithm clearly outperforms standard LRU, and showcases the benefits of a layered-based approach in the deployment of efficient cache policies. 1.2 Related Work Online caching, also known as paging , is one of the fundamental online optimization problems, and has served as proving grounds for the introduction and the development of competitive analysis. In their seminal work, Sleator and Tarjan [ 26 ] considered the standard model with a cache size k , and showed that an optimal deterministic competitive ratio equal to k can be achieved by a variety of marking policies, to which LRU belongs. Randomization can help improve the competitive ratio to a tight bound H_{k}=\Theta(\log k) , where H_{n} is the n -th harmonic number [ 13 ] .Paging has been studied in a multitude of settings, such as weighted requests [ 7 ] , hierarchical cache systems [ 8 ] , reordering cache models [ 16 ] , and energy-efficient policies [ 1 ] . We refer to Chapters 3 and 4 in [ 5 ] as well as to the more recent survey by Karlin and Koutsoupias [ 17 ] . Caching is a critical aspect in optimizing the inference efficiency of LLMs. A common approach involves the use of Key-Value (KV) caching [ 19 ] , which stores past activations from the attention mechanism to prevent redundant computations during the autoregressive text generation. Our work, in contrast, addresses a new caching setting that is specific to MoE models within LLMs. Unlike KV caching, which focuses on reusing intermediate attention outputs, we investigate caching policies aimed at efficiently managing the dynamic loading and unloading of expert weights across layers. This involves challenges due to the selective activation of experts and the substantial memory footprint associated with MoE architectures [ 10 ] , making our approach complementary to existing KV caching solutions. 2 Layered Paging: a Model for MoE Caching in LLMs In this section, we formulate the problem we will study, and which serves as a model of LLM caching. We first discuss, in Section 2.1 , the pertinent structure and properties of MoE architectures, then in Section 2.2 we define the problem of layered paging. 2.1 Caching in MoE Architectures Text generation with LLMs involves producing a sequence of tokens , which are units of text that can represent words, subwords, or punctuation marks. To generate a single token, the model processes information through \ell layers sequentially. Once the last layer is processed, the token is produced and then fed back into the first layer to begin the computation for the next token. This cycle repeats until an “End of Text” token is generated or the maximum number of tokens is reached. In modern LLMs, the number of layers \ell typically ranges from 10 to 100, depending on the model’s size and complexity. In the MoE paradigm, in particular, each layer involves n experts, which are specialized neural network modules that enhance model efficiency and performance. In current models, n generally varies between 8 and 256. We denote by E_{i}^{(j)} the i th expert in layer j , where i\in[1,n] and j\in[1,\ell] . In a MoE module, only a few experts, among the n total, are typically required. For simplicity, we consider here that a single expert per layer is requested. That is, in order to produce a single token, the required (ordered) series of experts is of the form E_{i_{1}}^{(1)},E_{i_{2}}^{(2)},\ldots,E_{i_{\ell}}^{(\ell)} , for some i_{1},...,i_{\ell} . Hence, the total series of experts that we have to process to produce all tokens is of the form E_{i_{1}^{1}}^{(1)},E_{i_{2}^{1}}^{(2)},\ldots,E_{i_{\ell}^{1}}^{(\ell)},E_{i_{1}^{2}}^{(1)},E_{i_{2}^{2}}^{(2)},\ldots,E_{i_{\ell}^{2}}^{(\ell)},\ldots Computing an expert requires its data (i.e., the weights of the neural network) to be loaded in the memory. Thus, to speed up computation, it is important to ensure that frequently reused expert data are kept in the fast cache memory which is of limited size k (we assume that all experts produce data of the same size). Figure 2 provides an illustration. L_{1} L_{2} L_{3} L_{4} E_{1}^{(1)} E_{2}^{(1)} E_{3}^{(1)} E_{4}^{(1)} E_{1}^{(2)} E_{2}^{(2)} E_{3}^{(2)} E_{4}^{(2)} E_{1}^{(3)} E_{2}^{(3)} E_{3}^{(3)} E_{4}^{(3)} E_{1}^{(4)} E_{2}^{(4)} E_{3}^{(4)} E_{4}^{(4)} Experts per layer ( n=4 ) Number of layers (\ell=4) S=(\overbrace{E_{1}^{(1)},E_{1}^{(2)},E_{2}^{(3)},E_{3}^{(4)}}^{{\color[rgb]{1,0,0}\text{Token 1}}},\overbrace{E_{2}^{(1)},E_{2}^{(2)},E_{2}^{(3)},E_{1}^{(4)}}^{{\color[rgb]{0,0,1}\text{Token 2}}},\overbrace{E_{2}^{(1)},E_{3}^{(2)},E_{4}^{(3)},E_{2}^{(4)}}^{{\color[rgb]{0,0.4,0}\text{Token 3}}}) reused First eviction E_{1}^{(1)} E_{1}^{(2)} E_{2}^{(3)} E_{3}^{(4)} E_{2}^{(1)} E_{2}^{(2)} E_{1}^{(4)} E_{3}^{(2)} Memory Max k=8 experts loaded at once Figure 2 : Example of experts used in the production of three tokens. The models has \ell=4 layers, each with n=4 experts. The experts used for each token are represented by a different color. Expert E_{2}^{(3)} is used for token 1 and reused for 2, hence resulting in a cache hit. The figure on the right depicts the state of the cache when processing the third layer for token 3: Expert E_{4}^{(3)} is requested, but the memory is already full, hence some other expert needs to be evicted. 2.2 Layered Paging We now proceed with the formal definition of our problem, which captures the setting discussed in the previous section. We say that the data produced by each expert corresponds to a page , and recall that the cache has a capacity k , in that it can store k pages. There are n\ell possible pages in total, given that each of the n experts may produce a page in each of the \ell layers. The set of pages P can be thus decomposed in \ell disjoint sets L_{1},\ldots L_{\ell} , each of cardinality n . We denote the pages inside each set L_{i} as \{p_{1}^{(i)},p_{2}^{(i)},\dots,p_{n}^{(i)}\} . The input \sigma to our problem is a sequence of pages \sigma=p_{1},p_{2},\ldots , with the constraint that p_{i}\in L_{(i-1\bmod\ell)+1} , modeling the layered structure of experts in the MoE architecture. For the purpose of analysis, a round in \sigma is defined as a consecutive block of pages of the form p_{j},\ldots,p_{j+\ell-1} where p_{i} with i\in[j,j+\ell-1] belongs to layer L_{i-j+1} , so \ell divides j-1 . For an illustration, each round is depicted in Figure 2 by its proper color. Having defined the set of pages and the structure of an input sequence, the optimization objective is as in the standard online paging. Namely, if a requested page is present in the cache, which corresponds to a cache hit , then the page is served at zero cost. In contrast, if a requested page is not in the cache, which corresponds to a cache miss , then the algorithm must determine which page to evict from the cache, in order to bring in the requested page. In this case, the page is served at cost equal to 1. Note that any paging algorithm can be fully described as a cache eviction policy, which determines the page to be evicted in the event of a cache miss. We will refer to the above problem as the \ell -layer paging problem, or layered paging , for simplicity. Note that this problem is a generalization of standard online paging, since the latter is equivalent to 1 -layered paging. To analyze the performance of algorithms for the problem, we will rely on the canonical framework of competitive analysis. Let A denote an online paging algorithm, and A(\sigma) its cost on input \sigma , i.e., the total number of cache misses it incurs on \sigma . Let also Opt denote an optimal offline algorithm that has foreknowledge of \sigma . It is known that an optimal offline algorithm is the one that, upon each request that results in a cache miss, evicts a page that will be requested the furthest in the future [ 3 ] . Definition 1 (Competitive Ratio) A deterministic algorithm A is r -competitive if there is a constant c\in\mathbb{R} such that for any request sequence \sigma , it holds that A(\sigma)\leqslant r\cdot{\textsc{Opt}}(\sigma)+c. Similarly, a randomized algorithm A is r -competitive if for every request \sigma \mathds{E}(A(\sigma))\leqslant r\cdot{\textsc{Opt}}(\sigma)+c, where the expectation is over the random choices of A . We will denote by \CR(A) the competitive ratio of an algorithm A . The paging problem was often studied in the more general setting of the k -server problem [ 21 , 28 ] . The book "Randomized Algorithms" by Motwani & Raghavan [ 23 ] conveys a lot of the intuition behind the study of randomized algorithms, with a section focusing on the paging problem, proving some previously mentioned results. 3 Competitive Analysis of Layered Paging In this section, we present theoretical results on the competitive ratio of deterministic and randomized algorithms for layered paging. 3.1 Deterministic Algorithms A first approach is to consider an online algorithm that devotes a predetermined portion of the cache to requests of each layer; e.g. , a portion of size approximately equal to k/\ell to each layer. While such simple approaches are used in practical implementations [ 10 ] , we show that they result in poor theoretical performance. Fixed cache partitions lead to inefficiencies, aligning with prior results on parallel paging [ 2 ] . Theorem 3.1 Any deterministic algorithm that allocates a fixed portion of the cache to a requests of a given layer has unbounded competitive ratio, as long as n\geqslant 2 and \ell\geqslant 2 . Proof We consider a layered paging instance and an algorithm A with a fixed cache allocation per layer. Let the total cache size k be such that n+\ell-1\leqslant kn+\ell , can store all requested pages, ensuring no cache miss after initially filling the cache. Thus, A has an unbounded competitive ratio. ∎ The following theorem provides a lower bound on the competitive ratio of any deterministic algorithm. The result shows that the best competitive ratio cannot be much smaller than that of standard online paging, namely k . Theorem 3.2 For every value of \ell , every deterministic layered paging algorithm has a competitive ratio at least k-\ell+1 . Proof Consider a deterministic layered paging algorithm A , and let k=n\ell-1 . We define a sequence \sigma such that two consecutive rounds differ in exactly one request: the page p_{i}^{(j)} missing from A ’s cache at the start of the round is requested and the other requests are repeated from the previous round. The first round contains arbitrary valid requests. The algorithm A suffers one cache miss at every round by construction. Consider a round i where an optimal solution Opt suffers a cache miss. Opt evicts the page which is requested the latest. There are \ell pages requested during round i , so at most k pages requested between rounds i and i+k-\ell , included. The next cache miss of Opt is at round i+k-\ell+1 at the earliest, so Opt suffers at most one cache miss every k-\ell+1 rounds. Therefore, A(\sigma)\geqslant(k-\ell+1)\textsc{Opt}(\sigma) , so \CR(A)\geqslant k-\ell+1 . ∎ LRU is k -competitive for layered paging, since it is k -competitive in standard paging, but does it achieve a better competitive ratio for \ell -layered paging? The following theorem answers in the negative, for any \ell . Theorem 3.3 For any \ell and k such that \ell divides k+1 , \CR(\textsc{LRU})\geqslant k . Proof Let n=(k+1)/\ell . We build a sequence \sigma that cycles through all n\ell=k+1 pages, respecting the layer constraints, achieving the worst case for LRU compared to Opt . \begin{array}[c]{ccc}\sigma=(&p_{1}^{(1)},p_{1}^{(2)},\ldots,p_{1}^{(\ell)}&\\ &p_{2}^{(1)},p_{2}^{(2)},\ldots,p_{2}^{(\ell)}&\\ &\ldots&\\ &p_{n}^{(1)},p_{n}^{(2)},\ldots,p_{n}^{(\ell)}&\\ &p_{1}^{(1)},p_{1}^{(2)},\ldots,p_{1}^{(\ell)}&\\ &\ldots&).\end{array} L_{1} L_{2} L_{3} L_{4} L_{5} L_{6} Token 1 Token 2 Token 3 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 Illustration with n=2 and \ell=6 . We construct a request sequence \sigma such that the i -th round subsequence equals (p_{i^{\prime}}^{(1)},p_{i^{\prime}}^{(2)},\dots,p_{i^{\prime}}^{(\ell)}) with i^{\prime}=i\mod n . That is, the request repeats itself cyclically with a period of n rounds. We analyze the sequence in chunks of n rounds, meaning that within each such chunk, we observe n\ell total requests. Since there are k+1 distinct pages, the LRU policy will always evict a page just before it is needed again. This means that every request results in a cache miss. Opt evicts the last page requested at each cache miss, so suffers a cache miss every k requests. Therefore, \CR(\textsc{LRU})\geqslant k . ∎ 3.2 Randomized Algorithms In this section we turn our attention to randomized algorithms. Recall that in standard online paging, randomization can help improving the competitive ratio to H_{k}=\Theta(\log k) , which is tight, as discussed in Section 1.2 . The following theorem is the main result of this section, which establishes a lower bound on the competitive ratio for the layered paging problem. Theorem 3.4 Every randomized algorithm for \ell -layered paging with n experts has competitive ratio at least \max(H_{n},\frac{\log(\ell)}{6n}) . Before we present the proof of Theorem 3.4 , let us discuss its significance. First, note that layered paging becomes trivial from the point of view of competitive analysis if k\geqslant n\ell : this is because the algorithm can store all pages in the cache, and thus achieve a competitive ratio equal to 1. We can thus assume that k\leqslant n\ell . Hence, if n\in O(1) , then Theorem 3.4 shows a lower bound \Omega(\log\ell)=\Omega(\log k) . Similarly, if \ell\in O(1) , then the theorem shows a lower bound of \Omega(\log n)=\Omega(\log k) . Therefore, the result shows that if either n or \ell is constant (as typically in practice), then any randomized algorithm has competitive ratio at least \Omega(\log k) , which is tight. To prove Theorem 3.4 , we will rely on a variant of the coupon collector problem known as the parallel coupon collector problem [ 12 ] . In this problem, there are N different types of coupons, and C agents (collectors). In each round, each of the C agents selects one of the N coupon types uniformly at random. Agents are not allowed to exchange or share their coupons. Define T(N,C) as the number of rounds after which each agent has collected all N coupons. Note that this problem is a generalization of the well-known vanilla coupon collector problem in which C=1 [ 4 ] , which is a key part in the analysis of the standard online paging problem [ 23 ] . We are interested in bounding from below the cover time , namely the quantity \mathbb{E}(T(N,C)) . We accomplish this in the following theorem, as previous work did not establish usable bounds [ 12 ] . Theorem 3.5 For the parallel coupon collector with N\geqslant 2 coupons and C agents, its cover time is such that \mathbb{E}(T(N,C))\geqslant\max\{N\cdot H_{N},\frac{\log C}{6}\}. Proof We prove the lower bounds separately, starting by \mathbb{E}(T(N,C))\geqslant N\cdot H_{N} . We focus of the first collector, corresponding to the first layer. We know from the traditional coupon collector problem that it will finish on average after NH_{N} rounds. By definition, all the collectors finish collecting their coupons after the first collector finishes its collection, hence the first bound: \mathbb{E}(T(N,C))\geqslant\mathbb{E}(T(N,1))=NH_{N}. We now show that \mathbb{E}(T(N,C))\geqslant\frac{\log(C)}{6} for N\geqslant 2 . We first compute the probability of the expected time to complete all collections to be larger than t . By definition: \mathbb{P}(T(N,C)\geqslant t)=1-\mathbb{P}(T(N,C)