# A Per-Step Load-Balancing Engine for Expert-Parallel MoE Serving

> Relief's all-integer per-step load-balancing for MoE serving recovers up to 37.3 points of utilization at 0.02% silicon overhead, near-optimal within 1%.

- **Source:** [arXiv](https://arxiv.org/abs/2611.11402)
- **Published:** 2026-11-14
- **Permalink:** https://picx.dev/p/evO8pJ
- **Whiteboard:** https://picx.dev/p/evO8pJ/image

## Summary

## Summary (Overview)

- **Core contribution**: Relief is a lightweight, all-integer load-balancing algorithm for expert-parallel Mixture-of-Experts (MoE) serving that determines per-layer, per-decode-step token splits across replicated experts, coming within a fraction of a percent of the theoretical optimum.

- **Key innovation**: Relief replaces expensive exact linear-program solvers with a bidirectional pairwise relaxation algorithm—a few passes of integer halving over token counts—that achieves near-optimal balance with dramatically lower latency and a working set that scales linearly (not quadratically) with group size.

- **Three deployments**: The algorithm is implemented as (1) a CUDA kernel on the serving GPU, (2) a fixed-function silicon block beside the accelerator, and (3) an FPGA over PCIe—all producing bit-identical results.

- **Results**: On real routing from three open MoE families (Qwen3-30B-A3B, OLMoE-1B-7B, Qwen1.5-MoE-A2.7B), Relief achieves 93% of the per-step optimum in software and 99.5% in silicon, recovering up to **37.3 percentage points** of effective utilization over deployed static placement schemes, while adding only **0.02%** of a modern accelerator's transistors.

- **Key insight**: A balancing split loses 62–91.6% of its gain when reused for even one additional decode step, proving that per-step decisions are essential—no coarser schedule can realize the value of dynamic balancing.

---

## Introduction and Theoretical Foundation

### Background and Problem

In expert-parallel MoE serving, each MoE layer's experts are distributed across a group of **G GPUs**. Every token's hidden state travels to the GPUs holding its experts, and the layer completes only when the **most loaded GPU** finishes. This means the entire group runs at the pace of its worst straggler—once per layer, at every decode step.

Key observations:

- Token-to-expert assignments **concentrate on few experts** and **shift from step to step**
- Published characterizations place MoE-layer compute utilization **below 11%** on GPUs
- The decode phase draws roughly **half** of serving's GPU power
- On real routing from a 128-expert model, an unbalanced 64-GPU group performs expert work during only a **quarter** of the GPU time it reserves

### Two Balancing Mechanisms

The paper identifies two distinct balancing mechanisms:

| Mechanism | What it decides | Update rate | Cost to move |
|---|---|---|---|
| **Placement** | Which experts (and how many replicas) live on which GPU | Minutes | Copies expert weights across devices |
| **Split** | What fraction of a replicated expert's tokens each replica receives | Must be per-step | Rewrites routing table only; no weight movement |

The imbalance divides the same way:
- **Slow statistical skew**: Experts that are hot on average (handled by placement)
- **Per-step residue**: Deviation of each step's counts from the average (requires per-step split decisions)

### Effective Utilization Metric

The paper introduces a joint metric that scores balance and decision latency together:

$$U_{\text{eff}} = \underbrace{\frac{\sum_{i=1}^{G} L_i}{G \max_i L_i}}_{\text{balance: spatial}} \cdot \underbrace{\frac{T_{\text{moe}}}{T_{\text{solve}} + T_{\text{moe}}}}_{\text{share of time executing}} = \frac{\text{spatial}}{1 + T_{\text{solve}} / T_{\text{moe}}}$$

where:
- $L_i$ = tokens GPU $i$ serves this step
- $T_{\text{moe}}$ = per-GPU time of the layer once the split is known
- $T_{\text{solve}}$ = latency of the balancing decision
- The first factor (spatial) is the mean-to-maximum ratio of per-rank load

### The Per-Step Optimum Problem

The optimal split is the solution to a min–max linear program. For a group of G GPUs, rank $i$ carries fixed load $f_i$ plus contributions from replicated slots:

$$L_i(x) = f_i + \sum_d w_{i,d} x_{i,d} + \sum_{(j,d'): \sigma(j,d') = i} w_{j,d'} (1 - x_{j,d'})$$

The optimization is:

$$\min_{x, z} z \quad \text{s.t.} \quad L_i(x) \leq z \ \forall i, \quad 0 \leq x_{i,d} \leq 1$$

### Failure of Existing Approaches

**Decision frequency**: Reusing a split for even one additional step forfeits 62–91.6% of its gain. Periodic re-placement collapses to the static baseline by N=2 at G=64.

**Exact solver latency**: LPLB's interior-point solver takes ~102 µs per solve—longer than many layers it would serve.

**Launch limits**: The exact GPU solver's working set grows as $O(G^2)$: specifically $156G^2 + 160G + 40$ bytes. It stops launching at G=25 on a GPU with 99 KiB shared memory, and at G=64 exceeds every shipping architecture's capacity by 2.8×.

---

## Methodology

### The Relief Algorithm

Relief is a **bidirectional pairwise relaxation** over the placement's replica edges:

**Core mechanism**: A pass visits each transfer (edge between two ranks holding copies of the same expert) and applies a locally optimal move:
- Computes the load gap between the two ranks: $\text{gap} = L[u] - L[v]$
- Shifts half the gap: $\text{delta} = |\text{gap}| \gg 1$ (truncating integer halve)
- Caps by available tokens: $\text{delta} = \min(\text{delta}, \text{limit})$
- Updates both load entries immediately (Gauss–Seidel style)

**Algorithm 1: One Relief pass**

```
for each round R of the schedule do
    for each transfer t = (u, v) ∈ R, together do
        gap ← L[u] - L[v]
        delta ← |gap| >> 1          {truncating halve}
        limit ← gap > 0 ? mass[t] : tok[t] - mass[t]
        delta ← min(delta, limit)
        if delta > ε then
            L[u] -= sgn(gap)·delta;  L[v] += sgn(gap)·delta
            mass[t] -= sgn(gap)·delta
        end if
    end for
    commit the round; the next round reads what it wrote
end for
```

**Key properties**:
- All-integer arithmetic (fixed-point Q11.20)
- Working set: just the G-entry load table (linear in group size, vs. $G^2$ for exact solvers)
- Edge coloring of the replica graph enables parallel execution: transfers sharing no rank can issue together
- A color class forms a perfect matching of ⌊G/2⌋ transfers per round
- The schedule is computed once per placement change (minutes apart), never per step

### Pass Count Selection

The optimal number of passes follows from maximizing effective utilization:

$$I^{*} = \arg\max_{p \leq p_{\max}} \frac{s[p]}{1 + (L_{\text{if}} + (a + bp)P)/T_{\text{moe}}}$$

where $s[p]$ is the balance achieved in $p$ passes, $L_{\text{if}}$ is interface latency, $(a, b)$ is the cycle model, and $P$ is clock period.

### Three Deployments

**1. CUDA Kernel** (on serving GPU):
- Runs in one thread block; shared memory holds load table
- No atomics needed (round transfers are rank-disjoint); one barrier per round
- Outruns exact solver 3.7–7.3× per call; runs where solver cannot launch

**2. Silicon Beside the Accelerator**:
- Load table held in registers (G words of Q11.20) whose outputs are wires into arithmetic
- Round takes 2 cycles; solve: 14+8I cycles at G=8, 28+8I at G=64
- 0.14 mm² of standard cells, ~10 million transistors
- Serves every layer of the die (reads E per-expert counts regardless of batch size)

**3. FPGA Across PCIe**:
- Generated to group size; runs at 139 MHz (7.2 ns period)
- Solves once per group; host distributes split
- $T_{\text{solve}} \approx 2.9$ µs at G=64 and I=12

---

## Empirical Validation / Results

### End-to-End Results

**Table II** summarizes effective utilization ($U_{\text{eff}}$) as a percentage of the per-step optimum across schemes, families, and group sizes:

| Scheme | G=16 | G=32 | G=64 | T_solve |
|---|---|---|---|---|
| No balancing | 50–60 | 51–68 | 78–83 | — |
| EPLB (deployed) | 69–78 | 64–71 | 71–72 | — |
| LPLB (GPU LP) | 49.5–95.1 | × (no launch) | × | 102 µs |
| Grouped LP (cube-8) | 74–97 | 68–90 | 69–90 | 33 µs |
| Relief (kernel) | 87–99 | 83–99 | 83–99 | 13–28 µs |
| Relief (FPGA) | 97–99.8 | 96–99.8 | 96–99.8 | 2.8–4.1 µs |
| **Relief (silicon)** | **99.0–99.9** | **98.6–99.9** | **98.8–99.9** | **0.7–1.7 µs** |

Key findings:
- The silicon deployment attains the highest utilization at every point, within **1%** of the cost-free optimum when $T_{\text{moe}}$ exceeds a few hundred microseconds
- The GPU exact solver falls below no-balancing at short layers despite optimal balance
- At G=64, the static EPLB placement actually **underperforms no balancing** (spatial utilization 0.21 vs. 0.24), because its duplicate map presumes an adaptive split that never arrives
- The median margin over the best other deployable scheme is **19.1 pp**, maximum **31.4 pp**

### Convergence and Pass Count

- Attainment of the per-step optimum reaches **99.84%** at G=16 and **99.51%** at G=64 after 12 passes
- Optimal pass count $I^*$ spans 6–64 depending on layer duration
- The 99.84% attainment frontier rises from 9 passes to 18 passes at G=32, then saturates
- Scale fit: $18.6(1 - e^{-G/12})$

### Ablation Results (Table III)

| Variant | G=16 | G=64 |
|---|---|---|
| Relief engine reference (Q11.20) | **99.84** | **99.51** |
| Without reverse move | 98.80 | 98.43 |
| Snapshot loads, damped (Jacobi) | 95.55 | 90.35 |
| Water-filling relaxation | 86.23 | 75.22 |
| Proportional relaxation | 93.09 | 81.04 |
| Hash split (deployed) | 72.54 | 70.80 |
| Relief in FP32 instead | 99.68 | 98.74 |
| Exact LP in Q11.20 | 73.68 | 73.73 |

Key ablations show:
- Removing the reverse move loses the most (flow must be able to move both directions)
- Snapshot (Jacobi-style) computation needs 4× the passes and removes 4–9 points of attainment
- Standard water-filling and proportional relaxations land an order of magnitude further from optimal
- Fixed-point arithmetic (Q11.20) matches—and slightly beats—FP32 for Relief, while the exact LP collapses to 73% in fixed point

### Hardware Overhead (Table IV)

| Block/accelerator die | mm² | Transistors | Engine share (area) | Engine share (trans.) |
|---|---|---|---|---|
| Relief engine (ASAP7) | 0.14 | 10 M | — | — |
| A100 (7 nm) | 826 | 54 B | 0.02% | 0.02% |
| H100 (4 nm) | 814 | 80 B | 0.02% | 0.01% |
| RTX 5090 | 750 | 92 B | 0.02% | 0.01% |

The engine occupies **0.14 mm²** (0.35 mm² outline), with 37,434 flip-flops and ~10 million transistors—**0.02%** of current accelerator dies.

---

## Theoretical and Practical Implications

### Theoretical Implications

1. **Refutes a claimed impossibility**: A recent ISCA paper asserted MoE's dynamism prevents any load-balancing solution from evenly distributing activated experts. Relief directly contradicts this, showing per-step balancing is both necessary and achievable.

2. **Frequency matters more than optimality**: The decision-frequency experiment proves that a free, clairvoyant periodic solution collapses to static baseline performance, while an approximate per-step solution captures nearly all available gains.

3. **Arithmetic precision insights**: The exact LP solver's interior-point method requires floating-point range that fixed-point cannot provide, collapsing to 73% attainment in Q11.20. Relief's bounded, same-scale integer operations are exactly covered by fixed-point, making it hardware-friendly.

4. **Separability of placement and split**: The decomposed timescale model (minutes for placement, per-step for split) is validated empirically—the static placement's advantage over no-balancing actually reverses sign at G=64, proving the placement's value is contingent on per-step splitting.

### Practical Implications

1. **Deployment flexibility**: Relief runs on GPUs already deployed (kernel), can be added via PCIe (FPGA), or integrated into future accelerators (silicon) with negligible transistor overhead.

2. **Scaling to deployment sizes**: The exact solver stops launching at G=25–39 depending on the GPU. Relief's linear working set (12 bytes per rank) handles any group size.

3. **Composability**: Relief composes with faster collectives—improvements in interconnect speed actually increase the importance of low-latency balancing. It also composes with placement schemes (EPLB, CRAFT) and training-time shaping methods.

4. **Production readiness**: The FPGA deployment (16% of device LUTs) offers a field-reprogrammable solution for existing servers, while the kernel requires no additional hardware at all.

---

## Conclusion

**Main takeaways**:

- Expert-parallel MoE serving wastes most of its expert-stage GPU time on stragglers caused by per-step routing imbalance
- Recovering this time requires **one balancing decision per layer per decode step**—a rate no software solver can sustain
- Relief's bidirectional pairwise relaxation achieves near-optimal balance (within 0.2%) using only integer arithmetic and a working set linear in group size
- The algorithm runs as a CUDA kernel, an FPGA engine, and a fixed-function silicon block adding just **0.02%** of an accelerator's transistors
- Across three model families, Relief matches or exceeds every deployable scheme's effective utilization, recovering up to **37.3 percentage points** over deployed static placement

**Future directions**:

- Extending to larger expert counts (256+, 1024+ experts) with minimal impact on hardware footprint
- Integration with next-generation accelerator designs as a standard on-die block
- Exploring the interaction of Relief with emerging collective communication optimizations
- Applying the same per-step relaxation philosophy to other dynamic allocation problems in large-scale inference systems

---

_Markdown view of https://picx.dev/p/evO8pJ, served by PicX — AI-generated visual whiteboard summaries of research papers._