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:

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:

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)

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)

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