Sparse routing and gating networks: Exercises

This page tests your grip on Sparse routing and gating networks. Work each problem before opening its solution. Every problem is graded by cognitive level: L1 Recognition (do you know the pieces?), L2 Application (can you compute?), L3 Analysis (can you compare and diagnose?), L4 Synthesis (can you combine ideas into a design?), L5 Mastery (can you reason at the edges — zero, limits, degenerate cases?).

Before we start, a symbol reminder so nothing appears un-earned:

Definition Symbols used on this page

$x$ — one input token, a list of $d$ numbers (a vector in $R^{d}$ ).
$N$ — total number of experts (independent sub-networks).
$E_{i} (x)$ — the output of expert $i$ when it processes token $x$ (each $E_{i}$ is a small feed-forward network).
$k$ — how many experts each token is actually sent through ( $k ≪ N$ ).
$G (x)_{i}$ — the gate probability that token $x$ goes to expert $i$ ; all $N$ of them add to $1$ .
$logits_{i}$ — the raw score for expert $i$ before softmax turns it into a probability.
$W_{g}, b_{g}$ — the gate's learned weight matrix ( $W_{g} \in R^{N \times d}$ ) and bias ( $b_{g} \in R^{N}$ ); the raw scores are $logits = W_{g} x + b_{g}$ .
$I$ — the index set of the kept experts: the $k$ experts selected by top- $k$ for this token (e.g. $I = {1, 2}$ if experts 1 and 2 win).
$d_{ffn}$ — the hidden width of one expert (each expert is a feed-forward network).
$B$ — number of tokens in a batch.
$α$ — a small positive constant weighting the load-balancing auxiliary loss against the main task loss.

L1 — Recognition

Problem 1.1

An MoE layer has $N = 64$ experts and uses top- $k$ routing with $k = 2$ . For a single token, how many experts are (a) available in the parameter store and (b) actually run (compute happens) during one forward pass?

Recall Solution 1.1

(a) All $64$ experts sit in memory — the full parameter store is always present. (b) Only $k = 2$ experts actually run. "Sparse" means available $\neq =$ active. Answer: 64 available, 2 active.

Problem 1.2

The gating function has three stages: raw scores, then softmax, then top- $k$ . Match each stage to what it guarantees: (i) values sum to 1, (ii) only a handful of experts are kept, (iii) turns the input vector into $N$ numbers.

Recall Solution 1.2

Raw scores ( $logits = W_{g} x + b_{g}$ ) → (iii) turns $x$ into $N$ numbers.
Softmax → (i) forces the numbers to be positive and sum to 1 (a probability distribution).
Top- $k$ → (ii) keeps only the largest few, zeros the rest.

Problem 1.3

True/False: In the conditional-computation picture, growing $N$ from 8 to 128 (with $k$ fixed) roughly multiplies the per-token active compute by 16.

Recall Solution 1.3

False. Active compute is $O (k \cdot d \cdot d_{ffn})$ — it depends on $k$ , not $N$ . Going $8 \to 128$ leaves $k$ fixed, so per-token active compute is essentially unchanged (only the tiny gating cost $O (N d)$ grows). That is the whole point of sparse routing.

L2 — Application

Problem 2.1

A gate produces logits $[2, 1, 0, - 1]$ for $N = 4$ experts. Compute the full softmax $G (x)$ (4 dp). Then with $k = 2$ , list the selected experts and the renormalized weights.

Recall Solution 2.1

Exponentiate: $e^{2} = 7.3891, e^{1} = 2.7183, e^{0} = 1, e^{- 1} = 0.3679$ . Sum $= 11.4752$ . $G = [0.6439, 0.2369, 0.0871, 0.0321]$ Top-2 experts: expert 1 and expert 2 (weights $0.6439, 0.2369$ ). Why renormalize? Once top- $k$ drops experts 3 and 4, their probabilities $0.0871 + 0.0321 = 0.1192$ vanish — the two surviving weights no longer add to 1, so $y = \sum_{i \in I} G (x)_{i} E_{i} (x)$ would be a shrunken blend, not a proper average. Dividing by the kept-sum restores a valid convex combination (weights positive and summing to 1), keeping the output's scale correct. Renormalize over the kept two: divide by $0.6439 + 0.2369 = 0.8808$ : $G^{'} = [0.7311, 0.2689]$

Problem 2.2

A dense feed-forward sublayer costs $O (d \cdot d_{ffn})$ per token. An MoE layer with $k = 1$ has the same per-expert width. By what factor does the active per-token compute of the expert FFNs change when we replace the dense layer by this MoE, ignoring gating cost?

Recall Solution 2.2

Dense active work $\propto d d_{ffn}$ . MoE with $k = 1$ runs one expert of the same width $\Rightarrow$ also $\propto d d_{ffn}$ . Factor $= 1$ (unchanged), yet the model now holds $N$ experts' worth of parameters. This is the Switch Transformer bargain: same FLOPs, far more capacity.

Problem 2.3

Expert Choice routing: batch $B = 1024$ tokens, $N = 8$ experts, target $k = 2$ experts per token on average. What capacity $C$ (tokens per expert) does each expert receive?

Recall Solution 2.3

$C = \frac{k \cdot B}{N} = \frac{2 \cdot 1024}{8} = 256 tokens per expert.$ Total slots $= N \cdot C = 8 \cdot 256 = 2048 = B \cdot k$ . Every expert processes exactly $C$ tokens — balance is structural.

L3 — Analysis

Problem 3.1

A batch of $∣ batch ∣ = 100$ tokens is routed over $N = 4$ experts with the loads $Load = [70, 20, 8, 2]$ . Compute the coefficient of variation $CV = σ / μ$ . Is this balanced?

Recall Solution 3.1

Mean $μ = (70 + 20 + 8 + 2) /4 = 25$ . Deviations: $45, - 5, - 17, - 23$ . Squares: $2025, 25, 289, 529$ ; sum $= 2868$ . Population variance $σ^{2} = 2868/4 = 717$ ; $σ = 717 = 26.7769$ . $CV = 26.7769/25 = 1.0711.$ A perfectly balanced load would give $CV = 0$ . A value $> 1$ signals severe imbalance — one expert is doing 70% of the work. (See Long-tail Distribution — this collapse is exactly a long-tailed usage pattern.)

Problem 3.2

For the same batch, the mean gate probabilities are $P = [0.60, 0.25, 0.10, 0.05]$ and the dispatch fractions are $f = Load /100 = [0.70, 0.20, 0.08, 0.02]$ . Compute the Switch auxiliary loss $L_{aux} = α N \sum_{i} f_{i} P_{i}$ with $α = 1$ , $N = 4$ . Compare it to the loss under perfect balance.

Recall Solution 3.2

$\sum_{i} f_{i} P_{i} = (0.70) (0.60) + (0.20) (0.25) + (0.08) (0.10) + (0.02) (0.05)$ $= 0.42 + 0.05 + 0.008 + 0.001 = 0.479$ . $L_{aux} = 1 \cdot 4 \cdot 0.479 = 1.916.$ Perfect balance ( $f_{i} = P_{i} = 1/4$ ) gives $\sum_{i} (1/4) (1/4) = 4 \cdot 1/16 = 1/4$ , so $L_{aux} = 4 \cdot 1/4 = 1$ . Our imbalanced batch scores 1.916 vs the ideal 1.0 — the loss is nearly double, pushing the gate to spread probability mass away from expert 1.

Problem 3.3

Explain, using the gradient argument, why the auxiliary loss uses the product $f_{i} P_{i}$ rather than $f_{i}^{2}$ or $P_{i}^{2}$ alone.

Recall Solution 3.3

$f_{i}$ (the hard top- $k$ count fraction) is non-differentiable — you cannot backprop through an $ar g$ -selection. It is treated as a detached constant. The gradient of $L_{aux}$ therefore flows only through $P_{i}$ . In the product $f_{i} P_{i}$ , $f_{i}$ acts as a weight: experts that are already overloaded (large $f_{i}$ ) get a large gradient pushing their $P_{i}$ down; underloaded experts get little push. Using $P_{i}^{2}$ alone would ignore the actual observed load; using $f_{i}^{2}$ alone would have zero gradient. The product marries "what actually happened" (measured by $f$ ) to "what we can steer" (the differentiable $P$ ).

L4 — Synthesis

Problem 4.1

You must design an MoE feed-forward block for a Transformer Architecture with model dim $d = 512$ , expert width $d_{ffn} = 2048$ , and a per-token active-FLOP budget equal to one dense FFN. You want the largest possible parameter store. Pick $k$ and justify the largest sensible $N$ given a capacity factor constraint that each expert can hold at most $C = 1.25 \cdot B / N$ tokens with $B = 4096$ .

Recall Solution 4.1

Budget → $k$ : one dense FFN's active work equals one expert's work. To stay at that budget you can run $k = 1$ expert per token (Switch-style). This maximizes how large $N$ can be for a fixed active cost. $N$ is limited by the capacity floor, not FLOPs: active FLOPs are $N$ -independent, so in principle $N \to \infty$ . The real limit is that each expert's capacity $C = 1.25 B / N$ must be at least $\sim 1$ token, else experts sit empty. Setting $C \geq 1$ : $1.25 \cdot 4096/ N \geq 1 \Rightarrow N \leq 5120$ . Practically you'd pick $N$ so $C$ is a few dozen (e.g. $N = 128 \Rightarrow C = 1.25 \cdot 4096/128 = 40$ tokens) to avoid tiny, high-variance loads. Report: $k = 1$ , $N = 128$ , $C = 40$ , giving $128 \times$ the FFN parameters at $1 \times$ the FFN compute.

Problem 4.2

Rework 4.1 but the client refuses an auxiliary loss (too much tuning). Redesign the routing so load balance is structural, and state the new per-token cost relative to $k = 1$ .

Recall Solution 4.2

Switch to Expert Choice routing: experts pick their top- $C$ tokens, so every expert gets exactly $C$ tokens — balance is guaranteed by construction, no auxiliary loss. To keep the same average tokens-per-token, set the average experts-per-token to $k = 1$ , i.e. $C = 1 \cdot B / N$ . Per-token average active cost stays $\approx 1$ dense FFN (total slots $= N C = B$ ), though individual tokens may see 0, 1, or several experts. Alternatively Soft MoE with $S$ slots per expert gives fully-differentiable, perfectly balanced routing at the cost of computing $M = N \cdot S$ slot mixtures.

L5 — Mastery (edges, limits, degenerate cases)

Problem 5.1 — the $k = N$ limit

Show that top- $k$ routing with $k = N$ and renormalization reduces the MoE layer exactly to the dense weighted sum $y = \sum_{i} G (x)_{i} E_{i} (x)$ . What is lost?

Recall Solution 5.1

With $k = N$ every expert is kept, so the kept-index set $I = {1, 2, \dots, N}$ (all experts) and nothing is dropped. The renormalizer $\sum_{i \in I} G (x)_{i} = \sum_{i = 1}^{N} G (x)_{i} = 1$ (softmax already sums to 1), so renormalization does nothing and $G^{'} = G$ . Hence $y = \sum_{i = 1}^{N} G (x)_{i} E_{i} (x)$ — the dense MoE, where $E_{i} (x)$ is expert $i$ 's output on token $x$ . What is lost: all sparsity and all compute savings — you now run every expert. Sparse routing is only meaningful for $k < N$ .

Problem 5.2 — the degenerate tie

The gate outputs logits $[3, 3, 1]$ ( $N = 3$ , $k = 1$ ). Two experts tie for the top. What happens, and why is this a real training hazard?

Recall Solution 5.2

Softmax: $e^{3} = 20.0855$ twice, $e^{1} = 2.7183$ ; sum $= 42.8893$ ; $G = [0.4683, 0.4683, 0.1584]$ . The $ar g max$ is tied between experts 1 and 2. Implementations break ties deterministically (e.g. lowest index), so all tied tokens deterministically flood one expert → sudden load spike. Hazard: ties create discontinuous jumps in routing as logits wobble across each other during training; combined with zero gradient through $ar g max$ , the gate can oscillate. Tie-breaking noise (adding small random noise to logits before top- $k$ ) smooths this — the same trick that helps Neural Architecture Search escape argmax plateaus.

Problem 5.3 — the empty-expert / zero-load case

In a batch, expert $j$ receives zero tokens ( $f_{j} = 0$ ). (a) What is its contribution to $L_{aux}$ ? (b) Does the gate ever learn to send tokens to it again? Explain the mechanism.

Recall Solution 5.3

(a) Its term is $f_{j} P_{j} = 0 \cdot P_{j} = 0$ — a dead expert contributes nothing to the load loss. (b) Yes, and this is subtle. Even with $f_{j} = 0$ , the soft probability $P_{j} = \frac{1}{B} \sum_{x} G (x)_{j}$ is generally $> 0$ (softmax never outputs an exact zero). The main-task gradient still nudges $P_{j}$ ; if some token's true best answer sits in expert $j$ , the loss on that token's output pulls $G (x)_{j}$ up until $j$ eventually wins a top- $k$ slot. Because $L_{aux}$ does not penalize an empty expert, it never forces revival — recovery relies on the task loss plus the fact that overloaded experts are being pushed down, raising the relative appeal of idle ones. This is why a long warmup and noisy gating matter: they keep every expert weakly alive so none dies permanently.

Problem 5.4 — quantifying "almost free" scaling

A model has a dense backbone costing $F_{dense}$ FLOPs/token. Adding an MoE FFN with $k = 2$ , $d = 1024$ , $d_{ffn} = 4096$ adds $2 d d_{ffn}$ expert-FLOPs plus gating $N d$ FLOPs. For $N = 256$ , what fraction of the added MoE cost is the gating? (Count one multiply-add as 1 FLOP; use $2 d d_{ffn}$ for the $k = 2$ experts.)

Recall Solution 5.4

Expert FLOPs: $2 \cdot d \cdot d_{ffn} = 2 \cdot 1024 \cdot 4096 = 8, 388, 608$ . Gating FLOPs: $N \cdot d = 256 \cdot 1024 = 262, 144$ . Fraction gating $= \frac{262144}{8388608 + 262144} = \frac{262144}{8650752} = 0.0303$ . Gating is $\approx 3.0%$ of the added cost — genuinely tiny, confirming that growing $N$ is "almost free." (Even quadrupling $N$ to 1024 only lifts this to $\approx 11%$ .)

Recall One-line self-check

Active compute scales with $k$ , capacity scales with ::: $N$