Priced Routing: One Assignment Rule for Training and Generation in Mixture-of-Experts

A mixture-of-experts model splits a layer into many small sub-networks, called experts, and uses a learned router to send each token to one or a few of them. Two problems recur. First, the router collapses: a few experts attract most tokens and the rest go unused. Second, the choice of expert is a discrete jump, so the router gets almost no gradient about the experts it did not pick. The cleanest fix for collapse treats routing as a balanced assignment problem: match tokens to experts so total affinity is maximized while every expert receives its fair share. This is what BASE Layers and Sinkhorn-based routing do. It fails exactly where language models are used, though. When text is generated one token at a time there is no batch to balance over, so these models fall back to plain greedy routing at test time. The model is then trained under one decision rule and deployed under another.

We propose to remove that mismatch with a fact from optimization duality. The solution of a balanced assignment can be written as each token independently picking the expert that maximizes its affinity minus an expert-specific price, where the prices are the dual variables of the capacity constraints. If the router learns population-level prices, the same per-token rule, "pick the expert with the best affinity minus price", is a balanced assignment during training and a valid greedy rule during one-token-at-a-time generation. We then make this rule a proper differentiable combinatorial layer. We use black-box solver differentiation, which estimates a useful gradient by re-running a discrete solver on perturbed inputs, so the router learns from cheaply estimated counterfactuals: what the loss would have been had a token gone to a different expert. The question is whether exact, capacity-respecting discrete decisions with decision-aware gradients beat both smooth relaxations and heuristic balancing when the evaluation is honest about how the model is actually run.

Core Claim

Routing is a linear assignment problem with objective $\sum_{i,e} s_{ie} y_{ie}$, where $s_{ie}$ is the router's affinity between token $i$ and expert $e$ and $y_{ie}\in\{0,1\}$ indicates assignment. Each expert $e$ is subject to a capacity $C_e$. For a large pool of tokens, the optimal capacity-constrained assignment is, up to ties, given by

$$y_{ie} = 1 \iff e = \arg\max_{e'} \left(s_{ie'} - p_{e'}\right),$$

where $p_e$ is the dual price of expert $e$'s capacity. This is the standard semi-discrete transport picture: balanced allocations over a continuous token distribution are partitions defined by affinity-minus-price. Batch-level solutions converge to it as the batch grows.

Our claim has two parts. First, a router whose prices are estimated as running population duals produces near-identical expert assignments whether it sees a 64k-token batch or a single token. That closes the training–generation gap left open by BASE and by Selective Sinkhorn Routing. Second, because the objective is linear in $y$, this layer satisfies exactly the assumption under which Differentiation of Blackbox Combinatorial Solvers derives its interpolation gradient. Supplying that gradient gives the router a signal about unchosen experts that standard top-$k$ training never provides.

Relation to Prior Work

Three lines of work cast routing as combinatorial allocation, and all three either break gradient flow through the allocation or relax it away. BASE Layers solves an exact balanced assignment with the auction algorithm and reports higher throughput than Switch-style routing (545k vs. 469k tokens/s). Gradients reach the router only through a sigmoid on the chosen expert's affinity, and inference reverts to unpriced greedy top-1. We keep BASE's exact discrete forward pass, but we carry its dual prices over to inference and differentiate through the assignment itself. Selective Sinkhorn Routing uses an entropy-smoothed transport plan on a small fraction of steps and plain softmax otherwise and at test time. Its switch between two objectives is empirically effective but unexplained. Our rule is the same at every step and at test time. DOT-MoE applies differentiable Sinkhorn with straight-through estimation to a one-time partition of neurons into experts. That is a static problem and does not address token routing. We take only its lesson that output-aware objectives beat proxy objectives.

Two balancing methods motivate the price view without implementing it. $\phi$-Balancing derives "congestion prices" from a convex dual over the population and shows that forcing balance within each noisy mini-batch suppresses specialization. Its prices, however, enter only an auxiliary loss, and it gives no hard capacity guarantee. We put the prices inside the decision rule, where they act directly. Expert Choice routing achieves balance by letting experts pick tokens, but it cannot run autoregressively. This is the incompatibility our rule is designed to avoid.

Two papers constrain the design. ReMoE shows that a fully smooth ReLU gate trains well, but it gives up per-device load guarantees. We will test whether exact discreteness is worth keeping. The predictive combinatorial optimization benchmark of Geng et al. finds that decision-focused models degrade sharply when constraints shift, for example when knapsack capacity changes from 30 to 90. A router trained against one capacity could fail the same way at a different batch size or capacity factor, so constraint shift is a required test in our design rather than an afterthought. Perturbed cosine routing fixes a slow-convergence problem in how affinities are computed. It is orthogonal to how they are allocated, and it can be composed with our layer.

Research Program

The layer has three pieces. The first piece is the forward decision. During training, we solve the capacity-constrained assignment exactly on each batch with an auction solver, warm-started from the current prices $p$. This is nearly free, because warm-started auctions with good prices need few rounds. The batch's final duals then update $p$ through an exponential moving average. At inference we apply only the affinity-minus-price argmax. The measurable quantity that ties the two together is the agreement rate: the fraction of training tokens whose exact batch assignment equals the priced-greedy assignment. If the claim is right, this rate approaches one as training proceeds and batches grow, so training and generation run the same rule.

The second piece is the backward pass. Following Differentiation of Blackbox Combinatorial Solvers, we perturb affinities as $s' = s + \lambda\, \partial L/\partial y$, re-solve to get $y_\lambda$, and pass back $-(y - y_\lambda)/\lambda$ as the gradient with respect to $s$. The obstacle specific to mixture-of-experts is that $\partial L/\partial y_{ie}$ for an unchosen expert is the inner product of the output gradient with expert $e$'s output on token $i$. That output was never computed. We estimate it on a random fraction $\rho$ of tokens by evaluating all experts on them, which costs about $\rho E$ times one expert's compute. For the remaining tokens we use only the chosen expert's term, as BASE does. The second solve is the cheap priced argmax, not a full auction. Sweeping $\rho$ (values such as 1%, 5%, and 20%) tells us how much counterfactual information the router actually needs. Sweeping $\lambda$ tests whether the original paper's finding, that large perturbations give more informative gradients, carries over.

The third piece is constraint robustness. Following the warning from Geng et al., we randomize the capacity factor during training and evaluate across capacity factors and batch sizes never seen in training. Because prices are dual variables, heterogeneous capacities $C_e$ fit into the same rule without modification. As a secondary experiment, we test experts of unequal size, which $\phi$-Balancing names as open.

Baselines

The naive reference point is standard top-1/top-2 softmax routing with a Switch-style auxiliary balancing loss. It is the configuration practitioners actually ship. We train it with the same data, token budget, expert count, and capacity factor as every other method, and we tune its auxiliary coefficient over the same grid size we give our $\lambda$ and $\rho$.

The strongest existing method on our language benchmarks is Selective Sinkhorn Routing. On enwik8 it reports 1.128 bits per character for SSR-S with noise. On WikiText-103 it reports a 1.183 perplexity reduction relative to vanilla sparse routing (Selective Sinkhorn Routing). Those numbers come from that paper's own model sizes. We therefore reimplement SSR in our codebase, tune $p$ and its temperature with the same budget, and compare under identical architectures. Beating it means lower test perplexity and bits per character under autoregressive single-sequence evaluation, with equal or lower peak expert overload. For orientation, perturbed cosine routing reports 1.197 bits per character on enwik8 in its own setup.

We also run BASE Layers with its native greedy inference, which isolates the cost of the training–generation mismatch. We run $\phi$-balancing, the strongest auxiliary-loss method. We run ReMoE on a reduced Pile setup matching its 182M-active-parameter configuration. There it reports 40.03% average zero-shot accuracy against 39.67% for the best top-$k$ baseline (ReMoE).

The decisive ablation keeps the priced decision rule but drops the black-box gradient, so the router learns only through the chosen expert's gate value. This separates the two parts of the claim. A second ablation keeps the black-box gradient but uses unpriced greedy routing at inference. Beating the field means the full method wins on quality at matched compute. Beating the ablations means each ingredient contributes measurably beyond seed variance, which we estimate with three seeds per configuration.

Why not just…?

Why not just keep BASE Layers and accept greedy inference? The mismatch may be harmless. That is an empirical question nobody has measured, and our first experiment measures it. We compare BASE's batch-assignment perplexity with its greedy-generation perplexity on the same model and report the overload and dropped-token rate under greedy decoding. If the gap is negligible, the price mechanism's value reduces to robustness under capacity shift, and we will report it that way.

Why not just use an auxiliary loss, or $\phi$-balancing's congestion prices? $\phi$-Balancing already shows that population-level prices beat batch-level penalties, raising Math500 from 64.8% to 66.2%. Its prices act only through a loss term, so balance is asymptotic and capacity is not guaranteed. Our "priced rule, no black-box gradient" ablation is very close to "move $\phi$-balancing's prices into the decision rule". This alternative is a real threat. If that ablation matches the full method, the honest conclusion is that the price mechanism, not differentiation through the solver, carries the gain.

Why not just use a smooth gate like ReMoE? Smooth gates train well, but ReMoE cannot bound per-expert load and needs a dense warm-up. Our comparison reports quality together with peak per-expert load and memory. A win for ReMoE on quality alone would show that discreteness costs accuracy. That result would bear directly on whether exact combinatorial layers are worth having in routing.

Why not just run Sinkhorn intermittently, as SSR does? SSR reports that per-step Sinkhorn adds over 70% training time, while running it on 0.1–1% of steps cuts overhead below 1%. That makes it a cheap and strong competitor. Its inference still uses unconstrained softmax, though. We will compare overhead directly: auction warm-starts plus $\rho$-fraction counterfactual evaluation, measured in wall-clock time at matched quality.

Proposed Experiments

The main runs are small-to-medium language models with 8 and 32 experts, trained on WikiText-103 and enwik8 in the regime used by SSR and perturbed cosine routing. A scale-up then follows ReMoE's Pile setup, roughly 30B tokens at 182M and about 470M active parameters, with zero-shot evaluation on ARC, BoolQ, HellaSwag, LAMBADA, PIQA, and RACE. All quality numbers are computed under true autoregressive evaluation with batch size one, as well as under batched evaluation. We also report the agreement rate, per-expert load Gini and maximum-to-mean ratio, dropped-token rate at fixed capacity, and training throughput.

Three checks decide the proposal. The first is whether the agreement rate between exact batch assignment and priced greedy routing exceeds 95% late in training. If it does not, the core equivalence fails in practice. The second is whether the full method beats the no-black-box ablation by more than seed variance at matched compute. This tells us whether differentiable combinatorial optimization adds anything beyond prices. The third is the capacity-shift test, which trains at a capacity factor of 1.0 and evaluates at 0.5, 1.5, and 2.0, at batch size one. The method should lose less perplexity than BASE and SSR, which would show that decision-focused routing escapes the constraint fragility documented by Geng et al. instead of inheriting it. A secondary vision check on ImageNet-1K tests whether the gains transfer. There SSR reports a +2.368 top-1 gain over its baseline.