# Leveraging Expert Usage to Speed up LLM Inference with Expert Parallelism

Olivier Beaumont, Raphaël Bourgouin, Maxime Darrin, Loris Marchal, Pablo Piantanida

<figure><img src="image_1.png" /></figure>

## To cite this version:

Olivier Beaumont, Raphaël Bourgouin, Maxime Darrin, Loris Marchal, Pablo Piantanida. Leveraging Expert Usage to Speed up LLM Inference with Expert Parallelism. Euro-Par 2025: Parallel Processing, Aug 2025, Dresden, Germany. hal-04994839v2

HAL Id: hal-04994839

https://hal.science/hal-04994839v2

Submitted on 27 Aug 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Leveraging Expert Usage to Speed up LLM
## Inference with Expert Parallelism

Olivier Beaumont¹[0000-0003-2741-6228], Raphaël Bourgouin¹, Maxime Darrin²,
Loris Marchal²✉[0000-0002-5519-9913], and Pablo
Piantanida²[0000-0002-8717-2117]

1 Inria Centre at the University of Bordeaux, Bordeaux, France
[olivier.beaumont, raphael.bourgouin]@inria.fr

2 International Laboratory on Learning Systems, Montreal, Canada,
CNRS, Centrale-Supélec, Université Paris-Saclay and MILA - Québec AI Institute
[loris.marchal, pablo.piantanida]@cnrs.fr, maxime.darrin@centralesupelec.fr

**Abstract** Large language models have become essential for text-processing applications, yet their inference remains time-consuming, as tokens must be generated sequentially. While model sparsification techniques, such as Mixture of Experts (MoE) models, help mitigate computational costs, they introduce new challenges. In MoE models, only a subset of experts is activated at each layer. Note that not all expert subsets (typically pairs) are selected with equal probability. When experts are mapped across multiple GPUs, load imbalances can arise if frequently co-activated experts are assigned to the same GPU, leading to load unbalance and inefficient execution. This paper proposes a strategy that leverages the non-uniform selection of expert subsets to optimize their mapping across GPUs. By ensuring that frequently co-activated experts are placed on separate GPUs, we improve parallel processing and reduce inference time. Despite the NP-completeness of this mapping problem, we introduce simple yet effective greedy strategies that significantly minimize sequential expert processing. Our proof-of-concept experiments on the Mixtral model demonstrate the effectiveness of our approach for reducing inference time.

**Keywords:** Large Language Models · Mixture-of-Experts · Memory Mapping · Inference Optimization.

## 1 Introduction

Large Language Models (LLMs) have become crucial in tasks such as machine translation and natural language understanding [16], enabling applications such as conversational agents and code generation tools with improved text production fluency and accuracy. However, their efficiency is closely tied to their size, often reaching billions or trillions of parameters [17], leading to substantial computational demands.

For inference tasks, fast text generation requires optimized computational strategies. One key approach is model compression, including quantization and sparsity, which reduce model size at the price of a (minimal) accuracy loss.
A particularly promising sparsification approach is the Mixture of Experts (MoE) architecture [6,14], which employs conditional computations for efficiency. MoE models are based on transformer-based architectures [19], where each block includes an attention layer and a gating function to dynamically activate experts depending on the input. This structure retains a large number of parameters while ensuring that only a small subset of experts is active per inference, thus reducing computational costs. This process can further accelerated when combined to parallel computing strategies to distribute memory requirements across multiple computational nodes and allow parallel execution of selected experts.

Optimizing inference requires leveraging multi-GPU computational power efficiently. While transformer attention layer distribution has been extensively studied [19], expert layer parallelism has received less attention. Two primary strategies address this: tensor parallelism and expert parallelism. Tensor parallelism distributes computations across devices at each layer but is less effective for expert-specific tasks. Expert parallelism, in contrast, assigns experts to specific devices based on memory availability, enhancing efficiency.

Training ensures relatively balanced expert popularity through penalization mechanisms [2]. The gating function typically selects *n* experts per transformer block, typically *n* = 2 to *n* = 8. If all selected experts are spread across different GPUs, inference fully benefits from parallel execution. Nevertheless, although individual expert selection is balanced, the selection of specific expert groups is not, thus allowing for optimized expert placement to maximize GPU utilization and minimize inference time as proposed in present paper.

The remainder of this paper is structured as follows. Section 2 reviews related work on MoE models and parallelization strategies. Section 3 presents the model; Section 4 formalizes the optimization problem, proves its NP-completeness while Section 5 presents a greedy heuristic. Section 6 evaluates these methods using Mixtral expert co-location statistics. Finally, Section 7 provides concluding remarks and future directions.

## 2 Related Work

Mixture of Experts models have gained significant attention [6,14,17]. They maintain strong accuracy in text generation due to their large number of parameters while reducing inference time compared to dense models, as only a subset of experts is selected at each layer. Research continues on optimizing model size, expert count, and selection strategy [17]. Various models follow the same principle but differ significantly, as highlighted in recent surveys [2].

For instance, Mixtral [14] selects 2 out of 8 experts per transformer block, DRBX [5] selects 4 out of 8, Qwen1.5-MoE [18] and DeepSeekMoE [3] select 8 out of 64. Some models, like Switch Transformers [8], use even larger expert counts, ranging from 128 per layer (Switch-Large, 26B parameters) to 2048 per layer (Switch-C, 1571B parameters).

To enhance parallelism and reduce inference time while respecting GPU memory constraints, it is crucial to develop efficient expert allocation strategies. Typ-
<figure><img src="image_3.png" /><figcaption>Figure 1: General Mixture-of-Expert architecture and detail on one MoE module</figcaption></figure>

ically, each GPU stores only a subset of experts, meaning there is no guarantee that selected experts will map to different GPUs. Expert parallelism aims to maximize the likelihood of this mapping.

Many systems [15,10] rely on static expert allocation, while others, like Tu-
tel [13], adapt parallelism dynamically based on previous iterations. Unlike these
approaches, we propose leveraging statistical data on expert selection probabil-
ities to maximize the expected matching size between experts and GPUs.

Another class of solutions [7,12] improves expert-GPU distribution through prediction techniques. By analyzing activations in earlier layers, future expert selections can be anticipated, enabling prefetching into GPU memory. This predictive approach can complement static placement, minimizing expert movement during execution and improving overall efficiency.

3 Problem Modeling

In this section, we describe the general MoE architecture in detail. We experi-
mentally study the distribution of expert pairs in the Mixtral model and show
that it is highly heterogeneous, which motivates the present study. We formalize
the optimization problem to be solved for each layer to minimize inference time
and maximize parallelism. We also show that this problem is NP-complete even
in the special case where each expert can only be stored in the memory of a
single GPU.

3.1 Mixture-of-Experts Architecture

We consider a large language model with *L* transformer layers, each containing an attention layer, a gating function selecting experts based on the attention output, and an expert mixing module (see Figure 1). Each module is defined by the total number *N* of potential experts and the number *n* of experts activated per layer. As seen in Section 2, different MoE models use various (*N*, *n*) configurations [2]. The selected experts compute outputs, which are then combined via a weighted sum determined by the gating function.

We focus on the inference phase, which has limited parallelism and poses a
greater optimization challenge. Generating each token requires sequential traver-
<figure><img src="image_4.png" /><figcaption>Figure 2: Probability of simultaneous selection in the Mixtral model, for various layers. Bright colors correspond to highly popular expert pairs. Only pairs $(i, j)$ with $i < j$ are considered.</figcaption></figure>

sal of the *L* layers, with the output of the last layer for token *i* serving as the input for token *i* + 1.

During training, penalization techniques ensure that each expert's activation probability is approximately constant and close to $\frac{n}{N}$ [2]. MoE models rely on experts being specialized for different contexts and sharing workload accordingly. This guarantees high-quality results despite using fewer experts per layer than dense models. Since expert selection depends on context, the probabilities of certain expert combinations appearing together are not uniform, as experts for similar contexts are activated more frequently together.

To test this assumption, we measured the probabilities of simultaneous selection in a Mixtral model with *n* = 2 and *N* = 8 on a representative text corpus. The results for several layers are shown in Figure 2. We observe (only values above the diagonal make sense) that the popularity of expert pairs is highly variable, even though the probability of each expert is uniform. For example, in layer 16, expert 0 appears very often with expert 1, but seldom with expert 5. This observation suggests that if two GPUs are available and each expert is present on only one, it is more appropriate to allocate experts 0 and 1 on two different GPUs to maximize parallelism, while experts 0 and 5 can be located on the same GPU.

## 3.2 Platform Model and Objective

The computational platform consists of a node equipped with *k* identical GPUs, each of which has its own dedicated memory. This memory is used to store model weights and activations. Since we perform inference for a single prompt of limited size, we assume that the memory footprint of activations is negligible compared to model weights. The GPUs are connected to the main memory of the system via a PCIe bus with limited bandwidth (see Figure 3a). The weights for the tokenizer, the attention mechanisms for each layer, and those for the final stage are distributed equally among all GPUs. The remaining memory $M_r$ on
<figure><img src="image_5.png" /><figcaption>Figure 3: An example of the distribution of experts without replication and resulting processing time, depending on the co-location of selected experts</figcaption></figure>

the GPUs is used to store the weights of the experts, where each expert has a weight $M_e$, so that each GPU can store $M = \frac{M_r}{LM_e}$ experts for each layer. For the $k$ available GPUs, each expert can therefore be replicated $R_e = \frac{kM_r}{LM_e}$ times.

## 3.3 Allocating of Experts onto GPUs

We now focus on a specific transformer layer in the LLM. For an expert to run on a GPU, its weights must already be in memory. If not, they must be fetched from main memory or another GPU, causing delays. Since multiple GPUs hold different expert weights, the required weights are often already stored on one of them. In many cases, multiple copies exist across GPUs, making them viable candidates for processing the corresponding expert. Inference for a given layer involves solving both a dynamic and a static problem.

The dynamic problem involves selecting, at runtime, which GPUs should process the activated experts, given a fixed expert placement. This can be approached using matching-based algorithms. Since runtime decisions must be made quickly, pre-computing solutions is a viable strategy. The number of possible expert selection configurations is around $N^n$, which is manageable for certain models (e.g., $N \le 32$, $n \le 4$). We examine this problem in Section 4.2.

The static problem determines how to distribute the $R_e$ replicas of the $N$ experts across $k$ GPUs before the computation, in order to minimize the expected maximum load on any GPU, given the dynamic allocation strategy. The complexity of this problem is analyzed in Section 4.3.

The different challenges in expert placement for MoE models are illustrated in Figures 3 and 4. In Figure 3, a constrained scenario is considered where each expert is assigned to a single GPU without replication. Figure 3a presents the static placement of experts, while Figure 3b shows two possible execution cases: when Experts 1 and 6 are selected, both GPUs operate in parallel (total expert execution time of 1), but when Experts 1 and 4 are selected, execution must be
<figure><img src="image_6.png" /><figcaption>Figure 4: An example of the distribution of experts with replication. The choice of which expert copy is used for a given pair impacts the processing time.</figcaption></figure>

sequential (total time of 2). If only pairs (1,4) and (1,6) were possible, placing Expert 1 on GPU 1 and Experts 4 and 6 on GPU 2 would optimize parallelism. Since each expert is present only once, the dynamic scheduling problem is trivial, but the static allocation problem remains NP-complete, as shown in Section 4.3.

Figure 4 extends this to a more flexible setting with 6 experts and 4 memory slots per GPU, allowing expert replication. Figure 4a illustrates this static placement, where Experts 1 and 2 are stored on both GPUs. The dynamic problem arises when Experts 1 and 4 are selected, leading to two possible execution schedules (Figure 4b), only one of which ensures efficient parallelism. The quality of static allocation depends on dynamic scheduling, making it crucial to solve both problems jointly.

# 4 Analysis of Static and Dynamic Allocation Problems

## 4.1 Definitions

In this section, we establish the complexity of the dynamic (ALLOCDYNAMIC) and static (ALLOCSTATIC) allocation problems,

**Definition 1 (ALLOCDYNAMIC).** Let a platform consist of $k$ GPUs, let $A(i) \subset \{1, \dots, k\}$ be the subset of GPUs holding expert $i$ and let $i_1, \dots, i_n$ be the $n$ experts activated by the gating function. We are looking for an expert replica selection $s$ such that $S(i)$ is the GPU chosen to process expert $i$, so that

(a) $\forall i \in \{i_1, \dots, i_n\}, S(i) \in A(i)$ (validity),

(b) $T(i_1, \dots, i_n) = \max_u |\{i \in \{i_1, \dots, i_n\}, S(i) = u\}|$ is minimal (parallel efficiency) where $T(i_1, \dots, i_n)$ denotes the time to process all experts in parallel on the GPUs given the expert allocation.

We prove in Section 4.2 that ALLOCDYNAMIC can be solved in polynomial time using matching algorithms, so that $T(i_1, \dots, i_n)$ is the optimal parallel time for a given subset of experts and a given static allocation $a$ of experts onto GPU.
We can now define the static allocation problem `ALLOCSTATIC`, which consists in deciding how to store all experts on the different GPUs.

**Definition 2 (ALLOCSTATIC).** Given a platform consisting of *k* GPUs, let $p(i_1, \dots, i_n)$ be the probability for the gating function to select the *n*-uple of experts $(i_1, \dots, i_n)$. Let *M* the maximum number of experts a GPU can host depending on the available memory. Let us denote by $A(i)$ is the subset of GPUs holding expert *i*. We are looking for a static allocation *a* of the experts on GPUs such that (a) for each GPU *g* |{*i*, *A*(*i*) = *g*}| ≤ *M* (memory constraint) and (b) the expected time to process activated expert for this layer given by $\sum_{(i_1, \dots, i_n)} p(i_1, \dots, i_n) T(i_1, \dots, i_n)$ is minimal.

We prove in Section 4.3 that the decision problem associated with `ALLOCSTATIC` is NP-Complete, even when each expert is present on only one GPU.

## 4.2 Optimal Solution for ALLOCDYNAMIC

Let us assume we are given a solution to the `ALLOCSTATIC` problem, which defines the allocation of experts to GPUs. We show how to solve the `ALLOCDYNAMIC` problem, i.e., given the allocation of experts and the result of the activation function, how to determine which GPUs will perform which activated experts to minimize parallel processing time.

Let us denote by $A(i)$ the subset of GPUs that hold expert *i* and let $i_1, \dots, i_n$ be the *n* experts activated by the gating function. Our objective is to determine, for each expert *i*, which GPU $S(i) \in A(i)$ will process that expert, so as to minimize the maximum number of activated experts to be processed on each GPU.

Algorithm 1 summarizes how to compute *S* and the cost *T* that corresponds to the parallel time necessary to process all experts given *S*. The algorithm tries all possible values of *T*, from 1 to *n*. For *T* = 1, we start by building a bipartite graph whose vertices are the activated experts on the one hand, and the GPUs on the other. We connect an activated expert vertex to a GPU vertex if the GPU holds the corresponding expert. We look for a graph matching of cardinality *n*, i.e. one that covers all the experts in the subset. This can be done, for example, by using the Hopcroft-Karp [11] algorithm to compute a maximum bipartite matching.

If there exists a matching of cardinality *n*, this means we can select a separate GPU for each expert. Otherwise, it means that *T* > 1 and we proceed to the test for *T* = 2. We create a copy of all GPU nodes: for a GPU *g*, node (*g*, 1) corresponds to the first time slot on GPU 1, while node (*g*, 2) corresponds to its second time slot. Similarly, we search for a matching of size *n*, which would correspond to a solution with *T* = 2. If such a matching of size *n* does not exist, we continue to increase *T* and make additional copies of the GPUs corresponding to the different time slots until we find a solution, what necessarily occurs at least for *T* = *n*, since *T* = *n* corresponds to the case where all activated experts can be processed on the same GPU.
**Algorithm 1** Selecting experts for a given mapping

**Inputs:** mapping $A$, subset of experts $(i_1, \dots, i_n)$

**Output:** expert selection $S$ with its cost $T$

1: $T \leftarrow 0$

2: **repeat**

3: $T \leftarrow T + 1$

4: Let $V_1 = \{i_1, \dots, i_n\}$ and $V_2 = \{(g, j)\}$ for $g \in \{1, \dots, k\}$ and $j \in \{1, \dots, T\}$

5: Let $E = \{(i, (g, j))\}$ such that $g \in A(i)$ for $i \in \{i_1, \dots, i_n\}$ and $j \in \{1, \dots, T\}$

6: Create the bipartite graph $G = (V_1 \cup V_2, E)$

7: Find a matching $M$ with maximum cardinality in $G$

8: **until** $|M| = n$

9: **for** $i \in \{i_1, \dots, i_n\}$ **do**

10: $S(i) \leftarrow g$ such that $(i, (g, j)) \in M$ for some $j$

11: Return $S, T$

## 4.3 NP-Completeness of ALLOCSTATIC

To establish the NP-completeness of ALLOCSTATIC, we assume that the memory available on the GPUs is sufficient to store exactly one copy of each expert so that ALLOCDYNAMIC is trivially solvable since there is no choice to be made at runtime. We consider a restricted version of the problem, with $k = 2$ GPUs and $N = 2M_r$ experts and $n = 2$, where $M_r$ is the memory available on each GPU. The memory of each GPU can therefore contain a maximum of $N/2$ experts, and ALLOCSTATIC is equivalent to partitioning the experts into two subsets. When a token is produced, a pair of experts is selected (since $n = 2$). If a pair of experts residing on the same GPU is required, the processing of both experts will be sequentialized. Let us denote by $p_{i,j}$ the probability that experts $i$ and $j$ (with $i < j$) are simultaneously activated by the gating function, and by $A(i) \in \{1, 2\}$ the index of the GPU holding expert $i$. Given the allocation $A$ and the probability distribution $p$, the expected processing time of the experts

$$ \text{is given by } E(a, p) = \sum_{i<j, A(i) \neq A(j)} 1 \times p_{i,j} + \sum_{i<j, A(i)=A(j)} 2 \times p_{i,j} \text{ and} $$

$$ E(a, p) = 1 + \sum_{i<j, A(i)=A(j)} p_{i,j} = 2 - \sum_{i<j, A(i) \neq A(j)} p_{i,j}, \text{ given that } \sum_{i<j} p_{i,j} = 1. $$

The objective is thus to find an allocation $A$ that maximize $\sum_{i<j, A(i) \neq A(j)} p_{i,j}$.

**Theorem 1.** *The problem ALLOCSTATIC of finding a static allocation with minimum expected computation time of the experts on two GPUs with $M_r = N/2$ is NP-hard.*

*Proof.* Given an allocation, computing the expected expert computation time with the previous formula is obviously polynomial so that ALLOCSTATIC $\in$ NP. To prove the hardness, let us consider the minimization of $\sum_{i<j, A(i) \neq A(j)} p_{i,j}$ (see the previous formula) and let us consider the decision version of the problem, which consists in finding an allocation with $\sum_{i<j, A(i) \neq A(j)} p_{i,j} \ge B$. We
now perform a reduction from the MAXIMUM BISECTION problem, which is NP-complete [9,1]. Given an edge-weighted graph (with even number of vertices), this problem consists in partitioning the vertices in two subsets of same size such that the total weight of edges going from one part to the other (i.e., the cut-weight) is smaller than $K$. Consider an instance $I_{bisect}$ of the bisection problem. We build an following instance $I_{alloc}$ of the bisection problem, where each vertex $i$ is associated to an expert $i$ and the probability of using pair $i, j$ is set to $p_{i,j} = (W - w_{i,j})/P$ where $w_{i,j}$ is the weight of edge $(i, j)$ in $G$ (or 0 if there is no such edge), $W = \max_{i,j} w_{i,j}$ and $P$ is a scaling factor so that all probabilities sum to 1 ($P = N^2 W / 4 - \sum_{i<j} w_{i,j}$). We set the bound to $B = (N^2 W / 4 - K) / P$.

Assume that $I_{alloc}$ has a valid solution $A$. We then build a bisection of the graph such that $S_1$ corresponds to the set of experts mapped on the first GPU, and $S_2$ corresponds to the set of experts mapped on the second GPU ($S_1 = A^{-1}(1)$ and $S_2 = A^{-1}(2)$). The cut-weight is then given by

$$ \sum_{\substack{(i,j) \\ A(i)=1, \\ A(j)=2}} w_{i,j} = \sum_{\substack{i<j \\ A(i) \neq A(j)}} w_{i,j} = \sum_{\substack{i<j \\ A(i) \neq A(j)}} W - P p_{i,j} = \left(\frac{N}{2}\right)^2 W - P \sum_{\substack{i<j \\ A(i) \neq A(j)}} p_{i,j} $$

as there are exactly $(N/2)^2$ edges from one part to another (each part is of size $N/2$). As $\sum_{i<j, A(i) \neq A(j)} p_{i,j} \ge B$, we get that the cut-weight is at most $K$, so that $(S_1, S_2)$ is a solution of $I_{bisec}$.

Conversely, let us assume that $I_{bisec}$ has a solution $(S_1, S_2)$. From this solution, we build an optimal allocation for $I_{alloc}$ by allocating experts corresponding to $S_1$ to the first GPU, and the others to the second GPU, i.e. $A(i) = 1$ if $i \in S_1$ and $2$ if $i \in S_2$. As previously, we can relate the cut-weight to the objective of $I_{alloc}$:

$$ \sum_{\substack{(i,j) \\ A(i)=1 \text{ and } A(j)=2}} w_{i,j} = \left(\frac{N}{2}\right)^2 W - P \sum_{\substack{i<j \\ A(i) \neq A(j)}} p_{i,j} $$

Since we know that the cut-weight is smaller than $K$, $\sum_{i<j, A(i) \neq A(j)} p_{i,j}$ is at least $B$, which proves that $A$ is a valid solution for $I_{alloc}$.

In the companion research report [4], we propose an Integer Linear Programming (ILP) formulation that solves the most general version of the problem, where the memory constraint on each GPU allows the same expert to be allocated to multiple GPUs, as illustrated in Figure 4. Due to lack of space, we refer the interested reader to [4] to find the complete formulation. In practice, due to high number of variables, experiments with state-of-the-art LP solvers show that when $N > 2$ or when the memory is large enough to allow a large replication of experts ($M > 4N/k$), the linear program does not help find an optimal solution and the solvers fail to find a solution within a few minutes.
# 5 Heuristic Algorithms

As mentioned in Section 4, the large number of variables in the previous linear program makes it impractical as soon as the number *n* of simultaneously activated experts is large or, even for a moderate number of experts, when replication allows a large number of different configurations (corresponding to a large value of *M*). Therefore, there is a strong need for a low-cost solution, i.e., an algorithm capable of finding a good allocation of experts on the GPU with limited complexity. In this section, we propose a greedy heuristic algorithm for solving the ALLOCSTATIC problem, based on the algorithm for the ALLOCDYNAMIC problem proposed earlier in Section 4.2.

<caption>**Algorithm 2 Greedy allocation of experts**</caption>

**Inputs:** usage probabilities of expert subsets *p*
**Output:** expert allocation *A*(*i*) for each expert *i*
**for** *i* = 1, ..., *N* **do**
    *A*(*i*) ← ∅
    **for** *g* = 1, ..., *k* **do**
        load(*g*) ← 0
    **while** load(*g*) < *M* for some *g* **do**
        **for each** GPU *g* such that load(*g*) < *M* **do**
            **for each** expert *i* such that *g* ∉ *A*(*i*) **do**
                *a'* ← *a*, *a*'(*i*) ← *A*(*i*) ∪ {*g*}
                gain(*i*, *g*) ← cost(*a*) − cost(*a*')
                Select (*i*, *g*) with highest gain(*i*, *g*)
                *A*(*i*) ← *A*(*i*) ∪ {*g*}
                load(*g*) ← load(*g*) + 1
    **return** *A*

<caption>**Algorithm 3 Randomized round-robin allocation of experts**</caption>

**Inputs:** usage probabilities *p*
**Output:** expert allocation *A*(*i*) for each expert *i*
**for** *i* = 1, ..., *N* **do**
    *A*(*i*) ← ∅
    *next* ← 0
    **for** *it* = 1, ..., *M* **do**
        *L* ← list of all GPUs in randomized order
        **for each** GPU *g* in *L* **do**
            *A*(*next*) ← *A*(*next*) ∪ {*g*}
            *next* ← *next* + 1
    **return** *A*

The proposed algorithm, detailed in Algorithm 2, starts with an empty allocation (no expert assigned to GPUs) and iteratively computes the (expert, GPU) pair maximizing the gain in a cost function. To do this, we define the
cost of using an expert that is not yet assigned to any GPU; we set this cost to a high value (fixed at 10 times the time needed to compute an expert in our experiments). We then define the cost of an allocation as the expected parallel computation time of the experts, given the probability distribution for expert subsets. The overall cost of an allocation is computed using Algorithm 1.

To assess the performance of Algorithm 2, we also consider a Randomized Round Robin allocation of experts (Algorithm 3). Figure 5 (left) shows the respective allocation costs of greedy Algorithm 2 (in red) and Randomized algorithm 3, for increasing memory size. For the random mapping, we plot the average and standard deviation for 10 trials. These results are obtained in the particular case of the 16th layer of the DRBX model [5], with $k = 4$ GPUs and $n = 4$ experts activated by the gating function out of $N = 16$ possible experts, on a text corpus representative of the training base $^3$. These results show that when the memory is limited and does not allow for a full replication of all experts to GPUs, there is a high incentive to choose the allocation of experts based on their respective usage, as done by our algorithm. For example, as soon as only 2 copies of all experts can be allocated on the whole platform (which corresponds to a memory per GPU of 8), the greedy heuristic can reach an almost parallel computation of experts for all possible subsets (expected cost very close to 1), whereas the random allocation has a cost 30% larger on average, and can reach a parallel processing of experts only for full replication (memory of 16).

<figure><img src="image_7.png" /><figcaption>Figure 5: Expected cost of mappings (left) and runtime on Mixtral (right)</figcaption></figure>

# 6 Experimental Evaluation

To assess the performance of our proposed expert allocation, we rely on a simplified version of the Mixtral model [14] and measure the time it requires for inference for various expert mapping strategies. We instantiate a two layers model

<footnote n="3">³ We obtained very similar results on the other DRBX layers and on the Mixtral [14] model, with $n = 2$ and $N = 8$</footnote>
with 8 large experts (hidden size of 4096 and intermediary size of 140000). We use the PyTorch tracer to record the time spent on each expert computation and the time spent on the communication between the GPUs. We perform experiments on the inference time using allocations produced by both Algorithm 2 (greedy) and Algorithm 3 (randomized round-robin). We compare the inference time of the two strategies with different expert frequencies and replication factors. We measure the inference time for 150 tokens, and run each experiment 3 times.

## 6.1 Experimental Setting

<figure><img src="image_8.png" /><figcaption>Figure 6: Impact of the peakiness of the expert pair distribution on the inference time for the synthetic distributions. Low temperature corresponds to very peak distributions, high temperature to quasi-homogeneous distributions.</figcaption></figure>

We run two types of experiments relying either on synthetic distributions, which allows us to test our allocation algorithms on a wide range of parameters, or on real distributions measured from an actual inference on an existing dataset. In both cases, based on the Mixtral model, the gating function activates $n = 2$ experts among the $N = 8$ available ones.

*Synthetic Distribution of Pairs* To assess the performance of Algorithm 2 and Algorithm 3 on distributions with a large range of variance, we first randomly generate a probability distribution of the usage of the pairs and rescaled it, using a temperature parameter to control the entropy of the distribution. This setting allows us to arbitrarily tune the entropy of the distribution and to evaluate the impact of this parameter on the performance gains with Algorithm 2. The initial sampled distribution is the same for a given experiment and is simply rescaled differently to ensure fair comparison between the two strategies.

*Mixtral-like Distribution* We perform inference with 1000 prompts from VMWare Open Instruct dataset <fnref n="4" /> on the Mixtral model and compute the frequency of each pair of experts for all layers over 10⁵ tokens. This gives us 32 distributions (one per layer), which we also used as input for our experiments.

<footnote n="4">⁴ https://huggingface.co/datasets/VMware/open-instruct</footnote>
## 6.2 Results

*Synthetic Experiments* Figure 6 illustrates how the expert pair distribution temperature affects Mixtral inference time. Lower temperatures create “peaky distributions” with dominant expert pairs, while higher temperatures lead to near-uniform distributions. The greedy algorithm consistently outperforms random allocation by leveraging expert distribution and replication, achieving gains even with nearly uniform distributions. Random allocation matches greedy performance only in fully homogeneous cases, which rarely occur in practice.

*Simulations with Real Distributions* Figure 5 (right) shows the effect of expert replication on Mixtral inference time across all 32 layers. We report the average computation time and standard deviation. Again, the greedy algorithm effectively exploits expert usage distribution and reduce execution time. Despite improved expert allocation and parallelism, the overall inference performance gain remains limited. This is because the targeted optimization affects only a fraction of the pipeline, while other costly operations (e.g., Attention computations, routing) dominate execution time. Our measurements show that expert computations, even with parallelism, represent just 14% of total inference time. Optimizing these operations is beyond this study’s scope, as existing solutions are either proprietary or complex. However, we expect our method’s impact to be more significant in optimized frameworks. This work serves as a proof-of-concept for smarter expert allocation, encouraging its integration into high-performance inference systems.

## 7 Conclusion and Perspectives

We optimize inference for Mixture of Experts models, where expert selection occurs dynamically based on prior attention layers and a gating function. Despite penalization mechanisms enforcing uniform expert selection during training, we show this uniformity does not hold for *n*-tuples of experts (*n* = 2, 4, up to 256 in some MoE models). This opens the door to optimized allocations, both in expert storage on GPUs and runtime expert selection. We demonstrate that dynamic allocation can be solved in polynomial time using maximal matchings, while the static problem is NP-complete. Two allocation algorithms are proposed and evaluated on the Mixtral model by HuggingFace, showing that leveraging *n*-tuple distributions enhances expert parallelism during inference. Future work includes learning expert usage distribution dynamically for adaptive reallocation, optimizing memory allocation per layer based on variance in expert selection, and exploring theoretical combinatorial questions on distributing *N* experts over *k* GPUs to maximize diversity in *n*-expert groupings.

**Disclosure of Interests.** The authors have no competing interests to declare that are relevant to the content of this article.
References

1. Bui, T.N., Jones, C.: Finding good approximate vertex and edge partitions is np-hard. Information Processing Letters **42**(3), 153–159 (1992)

2. Cai, W., Jiang, J., Wang, F., Tang, J., Kim, S., Huang, J.: A survey on mixture of experts. arXiv preprint arXiv:2407.06204 (2024)

3. Dai, D., Deng, C., Zhao, C., Xu, R., Gao, H., Chen, D., Li, J., Zeng, W., Yu, X., Wu, Y., et al.: Deepseekmoe: Towards ultimate expert specialization in mixture-of-experts language models. arXiv preprint arXiv:2401.06066 (2024)

4. Darrin, M., Beaumont, O., Bourgouin, R., Marchal, L., Piantanida, P.: Leveraging expert usage to speed up llm inference with expert parallelism – extended version. https://hal.science/hal-04994839 (2025)

5. Introducing dbrx: A new state-of-the-art open llm. https://www.databricks.com/blog/introducing-dbrx-new-state-art-open-llm (mar 2024)

6. Du, N., Huang, Y., Dai, A.M., Tong, S., Lepikhin, D., Xu, Y., Krikun, M., et al.: Glam: Efficient scaling of language models with mixture-of-experts. In: ICML 2022 (2022)

7. Eliseev, A., Mazur, D.: Fast inference of mixture-of-experts language models with offloading (2023), https://arxiv.org/abs/2312.17238

8. Fedus, W., Zoph, B., Shazeer, N.: Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity. J. Mach. Learn. Res. **23** (2022)

9. Garey, M.R., Johnson, D.S.: Computers and Intractability, a Guide to the Theory of NP-Completeness. W. H. Freeman and Company (1979)

10. He, J., Zhai, J., Antunes, T., Wang, H., Luo, F., Shi, S., Li, Q.: Fastermoe: modeling and optimizing training of large-scale dynamic pre-trained models. In: Proceedings of the 27th ACM SIGPLAN Symposium on PPoPP. pp. 120–134 (2022)

11. Hopcroft, J.E., Karp, R.M.: An $n^{5/2}$ algorithm for maximum matchings in bipartite graphs. SIAM Journal on computing **2**(4), 225–231 (1973)

12. Huang, H., Ardalani, N., Sun, A., Ke, L., Lee, H.H.S., Sridhar, A., Bhosale, S., Wu, C.J., Lee, B.: Towards moe deployment: Mitigating inefficiencies in mixture-of-expert (moe) inference (2023), https://arxiv.org/abs/2303.06182

13. Hwang, C., Cui, W., Xiong, Y., Yang, Z., Liu, Z., Hu, H., Wang, Z., Salas, R., Jose, J., Ram, P., et al.: Tutel: Adaptive mixture-of-experts at scale. Proceedings of Machine Learning and Systems **5**, 269–287 (2023)

14. Jiang, A.Q., Sablayrolles, A., Roux, A., Mensch, A., Savary, B., Bamford, C., Chaplot, D.S., Casas, D.d.l., Hanna, E.B., Bressand, F., et al.: Mixtral of experts. arXiv preprint arXiv:2401.04088 (2024)

15. Lepikhin, D., Lee, H., Xu, Y., Chen, D., Firat, O., Huang, Y., Krikun, M., Shazeer, N., Chen, Z.: Gshard: Scaling giant models with conditional computation and automatic sharding. arXiv preprint arXiv:2006.16668 (2020)

16. Min, B., Ross, H., Sulem, E., Veyseh, A.P.B., Nguyen, T.H., Sainz, O., Agirre, E., Heintz, I., Roth, D.: Recent advances in natural language processing via large pre-trained language models: A survey. ACM Computing Surveys **56**(2), 1–40 (2023)

17. Minaee, S., Mikolov, T., Nikzad, N., Chenaghlu, M., Socher, R., Amatriain, X., Gao, J.: Large language models: A survey. arXiv preprint arXiv:2402.06196 (2024)

18. Team, Q.: Qwen1.5-moe: Matching 7b model performance with 1/3 activated parameters (2024), https://qwenlm.github.io/blog/qwen-moe/

19. Vaswani, A.: Attention is all you need. Advances in Neural Information Processing Systems (2017)