Serving AI Models

Large AI models are expensive to run, and they are run a lot. Once a model has been trained, every user request has to be served on a fleet of GPUs that is costly to buy, scarce, and shared by many requests at once. How many GPUs to provision, which requests to batch together, and where to place the pieces of a model across the hardware are all resource-allocation decisions under uncertainty — exactly the kind of problem operations research was built for.

This lecture surveys the decisions involved and then works through two placement problems in depth, taken from recent papers:

• Over time, inside a data centre: placing the experts of a Mixture-of-Experts (MoE) model on GPUs as their popularity shifts, following Huang, Lou and Xiao, Mixture-of-Experts Serving (arXiv:2607.17880, 2026), which brings competitive analysis and approximation algorithms to the problem.
• Across space, over the Internet: splitting a model's layers across servers scattered around a network and routing each request through a chain of them, following Sun, He, Ji and Parag, Optimizing Resource Allocation for Geographically-Distributed Inference by Large Language Models (arXiv:2512.21884, 2025), which formulates it as a mixed-integer program and gives a greedy algorithm with a performance guarantee.

The decisions in AI serving

Serving a language model involves several layers of decisions, each recognizable from earlier lectures.

• Capacity. How many GPUs to keep running for a given request rate and latency target. This is a staffing problem: GPUs play the role of agents, requests the role of calls, and the trade-off between utilization and waiting time is the one quantified by the Erlang C model in the call centre lecture.
• Scheduling and batching. A GPU is most efficient when it processes many requests together, so requests are grouped into batches and advanced one generated token at a time. Two features make this harder than classical scheduling: a request's output length is not known when it arrives, and the memory it needs (its key–value cache) grows as it generates. Classical scheduling theory studied batching and unknown job lengths separately; recent theoretical work studies them together with growing memory use.
• Placement. Which parts of the model live on which GPUs. For Mixture-of-Experts models, an architecture used by several prominent recent language models, the question is how many GPUs each expert gets. When no single machine can hold the model, the question becomes which servers hold which layers, and how requests are routed through them. These are the two problems studied in the rest of this lecture.

Mixture-of-Experts models

A dense language model uses every parameter for every token. A Mixture-of-Experts model instead contains many expert sub-networks and a router that sends each token to only one or a few of them. Total capacity can grow with the number of experts while the computation per token stays small. Huang, Lou and Xiao cite DeepSeek-V3 as an example: it activates 37 billion of its 671 billion parameters per token.

Sparsity makes the model cheap per token, but it reshapes the serving problem. The load is no longer spread evenly; it is routed through experts whose popularity varies across application domains and drifts over time. The paper reports that DeepSeek-V3's decoding stage places its 256 routed experts on 320 GPUs — one expert per GPU, with the remaining 64 GPUs holding redundant copies of the busiest experts — and that the deployment recomputes this placement periodically (for example every ten minutes) from recently observed load using simple heuristics.

Two costs pull in opposite directions:

• Latency. The time to finish a step is set by the most heavily loaded expert relative to the GPUs serving it. Adding copies of a busy expert reduces it.
• Reconfiguration. Moving a GPU from one expert to another means copying weights, warming caches and other overhead. Reallocating too often wastes this effort, especially if the load shifts back.

The MoE serving model

Consider $m$ experts served on $n > m$ GPUs over time steps $t = 1, \dots, T$. Every expert must always have at least one GPU, so the first $m$ GPUs are assigned one per expert and the decision concerns the remaining

extra GPUs. At each step the system observes a workload vector $r_t = (r_{t,1}, \dots, r_{t,m})$, where $r_{t,i} \ge 0$ is the volume of requests routed to expert $i$, and then chooses a configuration $x_t \in \mathbb{Z}_{\ge 0}^m$, where $x_{t,i}$ is the number of extra GPUs given to expert $i$, with

The dynamic MoE serving problem is

In the static variant, reconfiguration is forbidden: a single configuration $x$ is used throughout, and the objective is $\sum_t f_t(x)$.

The model deliberately abstracts away hardware details — communication, shared experts, batching — to isolate the central tension: putting more GPUs on currently busy experts reduces latency, but frequent reallocation is itself costly.

Convex relaxation

Allowing $x_t$ to be real-valued gives a convex program. Each $f_t$ is a maximum of convex functions of $x_t$, hence convex. To linearize the reconfiguration term, introduce $y_{t,i} \ge x_{t,i} - x_{t-1,i}$, the GPUs added to expert $i$ at step $t$. Because the total is fixed at $k$, GPUs added equal GPUs removed, so $\sum_i y_{t,i}$ is half the reconfiguration cost:

(The factor of 2 is dropped, which changes constants only.) Its optimal value is a lower bound on the integer optimum, and its dual — built with Fenchel conjugates of the $f_t$ — drives the online analysis below, much as LP duality priced routes in the transportation problem.

Static expert placement

With a fixed configuration the problem is a resource allocation: split $k$ GPUs among $m$ experts to minimize total latency over a known workload history.

The integrality gap instance is simple. Take $m$ experts, $k = m - 1$ extra GPUs, one step, and equal workload $r_{1,i} = 1$. The relaxation spreads the budget evenly, $x_i = 1 - 1/m$, for latency $m/(2m - 1)$. Any integer configuration must leave some expert with no extra GPU, giving latency 1. The ratio $(2m-1)/m$ tends to 2.

The hardness reduction is also instructive. Make one expert per vertex of a graph and one time step per edge $(u, v)$, with workload 2 on experts $u$ and $v$ and 1 elsewhere. Giving extra GPUs to a set $S$ of $k$ experts makes step $(u, v)$ cost 1 if both endpoints are in $S$, and 2 otherwise. The total cost is $2|E| - |E(S)|$, so minimizing it means finding the $k$ vertices that induce the most edges.

Dynamic expert placement online

In practice the workload is not known in advance. An online algorithm sees $r_t$ and must choose $x_t$ before $r_{t+1}$ is revealed.

Two naive policies show why the problem is subtle. Never reconfiguring pays nothing to move but cannot follow lasting shifts in load. Chasing the load — each step choosing the configuration that is best for the current workload alone — follows every shift but pays to move on every short-lived spike, and pays again when the load returns. This is the same tension as in caching and paging, metrical task systems, and the ski-rental problem: commit too early and you may waste the switch, too late and you keep paying for the old state.

Regularized greedy

The algorithm of Huang, Lou and Xiao works in two stages: compute a fractional configuration online, then round it online.

The entropy penalty is the key design choice. Moving GPUs toward an expert that already has many is cheap in relative terms, while stripping an expert down to its last GPU is expensive. The update therefore behaves multiplicatively, which hedges against load that may soon swing back.

The analysis is an online primal–dual argument. The optimality conditions of each update step are used to construct a feasible solution of the dual of the convex relaxation, step by step. Since any dual feasible solution bounds OPT from below, comparing the algorithm's cost with that dual value bounds the competitive ratio. Applied directly, standard techniques of this kind give a ratio of order $\log k$. The paper improves this by exploiting two properties of the latency function: it is smooth (giving an expert $\theta$ times as many GPUs reduces its latency by at most a factor of $\theta$), and its conjugate is sublinear in a way that converts the loss into a square root.

Online rounding

The fractional schedule is converted into whole GPUs by lazy threshold rounding: draw a random threshold $\theta_i \in [0, 1)$ for each expert once at the start; at each step give expert $i$ at least $\max\{0, \lfloor x_{t,i} - \theta_i \rfloor\}$ GPUs, and otherwise keep the previous integer allocation wherever possible. Because the thresholds are fixed, an expert only gains a GPU when its fractional allocation crosses a new threshold, so the expected movement is no larger than the fractional movement. Smoothness again ensures the rounded latency is at most 3 times the fractional latency.

The lower bound has a natural interpretation. In the dual, demand keeps arriving for a single expert for an unknown number of steps, and the algorithm must decide how much dual "budget" to commit at each step, with diminishing returns. The offline benchmark knows when the burst ends and spreads the budget evenly; the online algorithm must overcommit early to stay competitive in case the burst is short. That forced overcommitment costs a $\sqrt{\log k}$ factor.

Worked example: spikes versus shifts

The example shows each failure mode. Chasing gets the lowest latency but spends 28 on moves, most of them reacting to the one-step spike and then undoing the reaction. Myopic greedy is too timid: a move only pays off over several steps, so judged one step at a time it rarely looks worthwhile. The hindsight optimum leans toward expert 1 early, then — knowing that a long shift is coming — moves to the even split at the spike and stays there, and moves fully to expert 2 only when the lasting shift begins. An online algorithm cannot know the spike from the shift when it happens; the competitive ratio measures how much that ignorance must cost in the worst case.

Distributed inference over a network

The second placement problem arises when a model is too large for any single GPU available. A pipeline-parallel system splits the model's $L$ transformer blocks (groups of layers) across several servers; each server holds a run of consecutive blocks, and a request is processed by a chain of servers that together hold every block, in order. Sun, He, Ji and Parag study this for PETALS, a system that runs large models on low-end GPUs spread over the Internet. Their argument for the setting: the bottleneck in running such models is GPU memory rather than processing speed, and offloading parameters to slower storage is far slower than pooling memory across machines.

In PETALS the client relays all traffic: it sends the current token's embedding to the first server, receives the result, forwards it to the next server, and so on. Each server keeps an attention cache for every request it is serving, so after the first token only a few kilobytes cross the network per server per token.

Two decisions must be made:

• Block placement: which consecutive blocks each server stores.
• Request routing: which chain of servers each request uses.

They interact through GPU memory. Storing more blocks on a server shortens chains but leaves less room for attention caches, which limits how many requests that server can carry.

The model

Server $j$ stores blocks $a_j, \dots, a_j + m_j - 1$: its first block $a_j$ and the number of blocks $m_j$. The paper's performance models, validated by experiment, say:

• Time. After the first token, each token costs $t_{cj} + \tau_j k_j$ at server $j$, where $t_{cj}$ is the round-trip time between client $c$ and server $j$, $\tau_j$ is the server's per-block processing time, and $k_j$ is the number of blocks it processes for this request. Measured inference time was close to linear in the number of blocks and largely independent of how many requests ran concurrently, as long as they fit in memory.
• Memory. A server with memory $M_j$ that stores $m_j$ blocks and processes $k_j^r$ blocks for each request $r$ uses

where $s_m$ is the size of one block and $s_c$ the size of one block's attention cache for one request.

A chain is feasible if each server's blocks pick up exactly where the previous server's left off. If request $r$ goes from server $i$ to server $j$, then server $j$ processes blocks $a_i + m_i$ through $a_j + m_j - 1$, which requires

The client acts as a dummy server holding "block 0" at the start of the chain and "block $L + 1$" at the end.

Written directly, the problem has an exponential number of candidate chains, and which chains are feasible depends on the placement. The paper turns it into a mixed-integer linear program of polynomial size. Routing becomes a link variable $f^r_{ij} \in \{0, 1\}$ — does request $r$ go from $i$ to $j$? — with flow conservation from a source copy of each client to a sink copy, exactly as in a shortest-path or network-flow model. The feasibility condition becomes the constraints $a_j f^r_{ij} \le a_i + m_i$ and $(a_i + m_i) f^r_{ij} \le a_j + m_j - 1$. These are products of an integer and a binary variable, which are linearized with auxiliary variables in the standard way.

The MILP has $O(|\mathcal{R}| \cdot |E|)$ variables and constraints, where $\mathcal{R}$ is the set of requests and $E$ the links between clients and servers. That grows quadratically in the number of servers, so solving it exactly does not scale. Rounding its LP relaxation does not help either: the fractional solution need not round to a feasible placement.

Solving block placement and routing

Conservative greedy

The paper's algorithm, CG-BPRR, decomposes the problem into three subproblems solved in sequence, one per type of decision.

1. How many blocks per server. Reserve memory as if every request might pass through every block on the server:

Whatever routing comes later, no server can run out of memory. 2. Which blocks. Rank servers by their amortized inference time $\tilde t_j = \tau_j + t_{*j}/m_j$, where $t_{*j}$ is the largest round-trip time from any client to $j$. This is the worst-case time per block on server $j$ with its communication cost spread over the blocks it holds. Then place blocks greedily, fastest server first, each server taking the consecutive blocks that most need service. In effect, the fastest servers cover blocks $1, 2, \dots, L$ in turn. 3. Routing. With the placement fixed, the paper shows that routing each client's requests along a shortest path through the feasible chains is optimal.

The guarantee comes at a price. The memory reservation in step 1 is conservative, so CG-BPRR can fail to find a placement when one exists, and it can be far from optimal when replicating blocks and spreading requests across the copies would be better. The paper gives an example of each.

Online: two time scales

Requests arrive continuously, but moving blocks between servers is slow, so the online version separates the decisions by time scale:

• Placement, rarely, by robust optimization. Steps 1–2 already plan for the worst case: $|\mathcal{R}|$ concurrent requests, all from the farthest client. Run with a chosen design capacity $|\mathcal{R}|$, the same bound on average per-token time holds whenever the number of concurrent requests is at most $|\mathcal{R}|$.
• Routing, per request, by shortest path. Each arriving request takes the path minimizing waiting time plus inference time, where a link's waiting time is how long until the server will have enough memory free.

The design capacity $|\mathcal{R}|$ sets a throughput–delay trade-off. A larger value lets more requests run at once without waiting, but forces fewer blocks per server, longer chains and slower tokens. The paper suggests setting it to the mean plus one standard deviation of the number of requests arriving during one request's lifetime, capped by what the servers' memory allows. This is the same reasoning as a safety stock in the inventory lecture.

In experiments with BLOOM-176B on a real PETALS deployment, and in simulations on Internet topologies, the authors report average inference times 60–80% lower than PETALS' own heuristics. Most of the gain came from the time to the first token.

The optimum beats CG-BPRR by about 11% because it replicates blocks 3–4 and splits the load between the copies. Each copy then needs attention caches for only two requests, leaving room to store two blocks instead of one. CG-BPRR's reservation assumes every request could land on every server, which rules this out — the price it pays for a guarantee that holds under any routing and, online, under any arrival pattern within the design capacity.

Extensions and open questions

• Closing the gap. The $\sqrt{\log k}$ barrier is proved for the dual problem used in the analysis. Whether a different technique can beat it for MoE serving itself is open.
• Richer models. Real deployments add communication costs between GPUs, experts of different sizes, memory limits, and the batching and key–value cache constraints from the first section. Each breaks some structure the analysis relies on.
• Predictions. Expert load is partly predictable from recent history. Online algorithms that use predictions while remaining robust when they are wrong — learning-augmented algorithms — are a natural next step.
• Beyond pipelines. The distributed-inference model assumes pipeline parallelism and the client relaying all traffic; the authors note their formulation adapts to servers that forward directly to each other. Splitting individual layers across machines (tensor parallelism) is a harder extension, and other objectives — the cost of renting GPUs, robustness to servers failing — are left open.
• Connections. The ingredients are the same as in earlier lectures: a convex relaxation and its dual (transportation, unit commitment), rounding with a provable guarantee (facility location), a hedge between reacting and waiting (inventory, revenue management), and placement with flow-based routing (facility location, vehicle routing).

Sources: Z. Huang, Q. Lou and T. Xiao, Mixture-of-Experts Serving, arXiv:2607.17880 (2026); T. Sun, T. He, B. Ji and P. Parag, Optimizing Resource Allocation for Geographically-Distributed Inference by Large Language Models, arXiv:2512.21884 (2025). For background on competitive analysis, see Borodin and El-Yaniv, Online Computation and Competitive Analysis.