acceptodds
Under review as a conference paper at ICLR 2027

Stochastic Online Linear Programming for Resource-Aware Expert Routing

Abstract

Mixture-of-experts (MoE) models decouple parameter count from per-token compute, but require a router that matches tokens to experts while balancing the load across experts. We formulate MoE routing as a stochastic online linear program (SOLP), which allows a flexible formulation of matching-quality versus expert-balance tradeoffs through linear constraints. Specifically, while our formulation easily admits the traditional cardinality constraints on experts-per-token or tokens-per-expert, it can also capture substantially more flexible aggregate constraints on expert utilization across sequences, layers or even a whole training batch. Furthermore, we provide an elegant dual update algorithm, which finds a near-optimal solution as we establish in our main theoretical guarantee. Empirically, we evaluate various instantiations of our general SOLP framework across a seven-scale ladder built on the Gemma architecture, ranging from M to B parameters ( to layers), and show that the flexibility afforded by our formulation results in better validation perplexity across this ladder, when compared with standard Top- routing approaches. We further show additional benefits of our dual update algorithm, where the dual parameters can be cheaply retrained for a new set of constraints at inference-time, yielding a powerful mechanism for inference time compute optimization, without any significant quality losses.

Primary area:
learning theory
Keywords:
large language models, mixture of experts, sparsity, linear programming, online learning, online convex optimization

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_TmABOpenReview ↗
Rating
4
Confidence
4
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper examines token routing in Mixture-of-Experts (MoE) language models through a stochastic online linear programming (SOLP) framework. The framework maximizes token-expert affinity scores with linear constraints on per-token expert counts, pooled compute budgets, and balanced expert workloads. As the authors honestly disclose in a very scholarly related works section, viewing routing through linear assignment and primal-dual updates builds on precedent in Lewis et al. (2021) for BASE Layers and Han & Zhong (2025) for ALF-LB. However, the authors push this perspective further by unifying existing and new routing rules over five degrees of design freedoms. The resulting framework covers fixed-cardinality Top-k routing, Expert Choice routing, variable-cardinality score-threshold (VarK) and nucleus (TopP) routing, per-layer and cross-layer compute budget pooling, and causal sequence- or batch-level inference routing.

In the authors' formulation, the router subtracts two learned scalar ''prices'' from each expert's score, counts how many experts have a positive adjusted score, clips that count, and routes the token to that many top-scoring experts. Updating these prices via online gradient descent over update steps gives an inverse-square-root convergence rate on both expected score suboptimality and constraint violations. Additionally, the authors provide experiments across seven Gemma-4 MoE models of varying sizes (from 183 million to 6.59 billion parameters) demonstrating that relaxing fixed per-token expert counts and pooling the compute budget across all layers monotonically lowers validation loss.

Critical strengths
  • Honest and scholarly discussion of related work surveying prior MoE routing schemes and theoretical analyses.
  • Clear theoretical formulation (SOLP) and inverse-square-root convergence guarantee covering many commonly used MoE routing paradigms.
  • Extensive experiments spanning seven Gemma-4 MoE model scales (183M to 6.59B parameters) and multiple routing methods.
Critical weaknesses

Writing is generally clear, but some places can be improved. Generally the work is already good and self-contained.

Questions for authors
  • Why is ''TopP-Layer'' missing in Figure 1? It seems to be the only one to be missing from that table?

  • Why are the 183M and 414M models excluded from the forward-compute scaling curve in Figure 1(c)?

  • For the tuning in Figure 2(a), are all parameters turned or just the dual variables?

  • Equation (1) allows raw logits, probabilities, or log-probabilities as router scores. However, it is unclear which choice was used in Corollary 1 and the experiments. Might the authors clarify?

  • Section 3 and Table 2 define the compute budget as an equality constraint, but Equations (3)–(4) formulate it as an inequality with a non-negative Lagrange multiplier. While it might turn out to be mathematically equivalent, which constraint is enforced in the experiments?

3 comments
AuthorsOpenReview ↗

Author Response to Reviewer TmAB: Clarifications on Figures, Router Scores, and Budget Constraints

We sincerely thank Reviewer TmAB for the generous assessment, careful reading, and insightful technical questions, which we answer individually below.

1. Omission of TopP-Layer in Figure 1

"Why is 'TopP-Layer' missing in Figure 1? It seems to be the only one to be missing from that table?"

TopP-Layer was omitted from Figure 1(a–b) solely to avoid visual crowding with five overlapping curves; all seven scales are reported in Table 6, and we will include TopP-Layer in Figure 1(b) and note this in the caption.

2. Exclusion of 183M and 414M Models From Figure 1(c)

"Why are the 183M and 414M models excluded from the forward-compute scaling curve in Figure 1(c)?"

Scales S (183M) and M (414M) hold the shared dense MLP width fixed at 512 (rather than scaling with width dd as in XL–4XL) and are dominated by the 262k-vocabulary output projection (3.2% and 8.1% routed FLOP share, Table 4), placing them outside the log-linear backbone scaling regime of 0.64B →\to 6.59B; we will clarify this in Section 6.1 and add the full 7-scale curve in Appendix E.

3. Parameter Tuning in Figure 2(a) Continuation Runs

"For the tuning in Figure 2(a), are all parameters turned or just the dual variables?"

Yes good catch here. Both model weights and the dual variables update simultaneously during continuation, though the dual threshold P=1−τP = 1 - \tau re-equilibrates to within ±0.005\pm 0.005 experts/token inside the first 100 steps; we will state this explicitly in Section 6.2.

4. Router Score Representation Used in Corollary 1 and Experiments

"Equation (1) allows raw logits, probabilities, or log-probabilities as router scores. However, it is unclear which choice was used in Corollary 1 and the experiments. Might the authors clarify?"

This is an excellent question, and we apologize for the omission. Corollary 1 assumes bounded non-negative scores (directly satisfied by probabilities qt,eq_{t,e}, or shifted bounded log-probabilities). In our experiments, VarK applies admission thresholding in centered log-probability space (log⁡softmax(zt−λl)e>τl\log \mathrm{softmax}(z_t - \lambda_l)_e > \tau_l, Footnote 3) so the threshold is invariant to logit shifts, whereas TopP uses post-price probabilities qt=softmax(zt−λl)q_t = \mathrm{softmax}(z_t - \lambda_l) in the rank-slot tail-mass objective (Appendix C); in all arms, selected expert outputs are combined using renormalized raw softmax probabilities.

5. Equality vs. Inequality Compute Budget Constraint

"Section 3 and Table 2 define the compute budget as an equality constraint, but Equations (3)–(4) formulate it as an inequality with a non-negative Lagrange multiplier. While it might turn out to be mathematically equivalent, which constraint is enforced in the experiments?"

Our experiments enforce the equality constraint (=ktar/E= k_{\mathrm{tar}} / E): in VarK, because log-probabilities are non-positive, the dual multiplier τ∈R\tau \in \mathbb{R} is updated without non-negativity clipping, and in TopP, P=1−τP = 1 - \tau remains strictly inside (0,1)(0, 1), realizing kˉ∈[3.986,4.029]\bar{k} \in [3.986, 4.029] across all runs. Equations (3)–(4) wrote ≤ktar\le k_{\mathrm{tar}} with τ≥0\tau \ge 0 under positive scores ct,e>0c_{t,e} > 0, where unconstrained demand exceeds ktark_{\mathrm{tar}} so the inequality binds at equality by complementary slackness; we will harmonize Sections 3 and 4 to make this explicit.

I appreciate the authors' careful responses and the revisions they have made.

Since I am the odd-one-out here in terms of reviewer score, I will would like to give the following clarification for the AC and my fellow reviewers:

  • This paper should be viewed as a conceptual clarification rather than an engineering contribution or realistic design proposition.
  • In particular, the main concern of the other reviewers seem to be that the authors inadequately (in terms of experiments or design) justified that their SOLP framework could lead to the design of better/realistic MoE balancing updates. I agree with the other reviewers on this point, but I feel it is beside the point.
  • Instead, the authors created a unified conceptual framework through which many of the modern already used-in-practice MoE balancing frameworks could be jointly reasoned about and analyzed. To my knowledge, does not currently have a precedent in the current literature (besides Han & Zhong (2025) which does it for ALF-LB in particular). Thus, I feel like it is worth sharing with the attendees of ICLR.

If this paper turns out unsuccessful for ICLR, I encourage the authors to improve the writing clarity of this paper (which I agree is rather confusing and disorganized at times, but not worse than usual quality of previously accepted ICLR papers) and submitting it to a more specialized journal like Operations Research, Mathematics of Operations Research, or Mathematical Programming.

AuthorsOpenReview ↗

Final thoughts for Reviewer TmAB

We sincerely thank Reviewer TmAB for the thoughtful follow-up and for clarifying the paper's framing for the AC and fellow reviewers. We have uploaded a revised manuscript incorporating all five of your technical clarifications along with a cleaner, self-contained Section 4.

We would like to add one brief, constructive nuance to your summary: while the unified primal–dual view is indeed a core contribution, the framework does not merely analyze existing methods - - it directly yields genuinely new routing algorithms with concrete practical gains:

  1. Cross-layer budget pooling (VarK-Global / TopP-Global): Relaxing the budget constraint across depth (Bud∅\mathsf{Bud}_\varnothing) with mean-zero per-layer duals (Proposition 3) is a novel algorithm that spontaneously shifts >2×>2\times more compute from early to late layers, roughly doubling the quality gain over per-layer adaptive routing.
  2. Inference-time causal rebalancing (Sequence-OLP / Batch-OLP, Algorithm 2): Decoupling training and serving constraints yields a novel zero-retraining serving controller. Following Reviewer 5p72's helpful push, our new Expert-Parallel benchmarks on Gemma 4 26B-A4B (Appendix E.4) show this delivers 1.15x–3.5x faster prefill and 1.14x–1.45x faster decode (which Reviewer 5p72 confirmed resolved their efficiency concern).

Thank you again for your careful reading and constructive guidance!

Reviewer_MuBbOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper formulates MoE routing as an online linear program, enforcing routing constraints through dual "prices" added to router scores. This view generalizes Top-k and ALF-LB to variable per-token expert counts and a compute budget shared across layers. The authors give regret bounds and report small validation-loss gains on C4.

Critical strengths

The LP/dual-price view is a potentially useful way to unify existing routing methods. However, given the limited experiments, it is unclear whether the proposed relaxations actually yield meaningful improvements.

Critical weaknesses
  1. The writing reads as heavily LLM-generated. It is verbose and dense with notation, has few figures and hard-to-read tables, and is difficult to follow.

  2. The models are trained on far fewer tokens than a compute-optimal budget, and the reported gains are small, so the results may not hold at realistic scale.

  3. Evaluation uses only C4 validation loss, with no standard downstream benchmarks.

  4. Several theoretical results are near-trivial or largely follow from existing online LP analysis.

Questions for authors

Do the gains persist when models are trained with a compute-optimal token budget, and on standard downstream benchmarks?

1 comment
AuthorsOpenReview ↗

Author Response to Reviewer MuBb: Experimental Scope, Gain Magnitude, and Dual-Space Formulation

We thank Reviewer MuBb for reviewing our paper and noting the unifying potential of the LP/dual-price perspective. Below we respond concisely to each point.

1. Prose Style, Notation Density, and Readability

"1. The writing reads as heavily LLM-generated. It is verbose and dense with notation, has few figures and hard-to-read tables, and is difficult to follow."

While LLM tools were used for light copy-editing and formatting as transparently disclosed in our AI Use Statement, the manuscript, theory, and exposition were originally written by the authors, cleaned-up with AI support, and then heavily edited again by the authors. We appreciate the feedback on notation density: in the revision we will streamline the 5-axis index notation in Sections 2–3, replace symbol-heavy columns in Tables 1–2 with plain-English scope labels, and move compact algorithm pseudocode into the main body.

2. Sub-Compute-Optimal Token Horizon and Magnitude of Gains

"2. The models are trained on far fewer tokens than a compute-optimal budget, and the reported gains are small, so the results may not hold at realistic scale. ... Question: Do the gains persist when models are trained with a compute-optimal token budget, and on standard downstream benchmarks?"

We sincerely appreciate the reviewer's concern about the non-Chinchilla token horizons, but we need to strongly emphasize here: our fixed-horizon framework is the conventional standard across the relevant MoE routing papers, including BASE Layers, Switch Transformers (sections 3–4), Clark et al. (2022), Han & Zhong (2025), and Expert Threshold Routing (Sun et al., 2026), nearly all of which report single-seed runs on 1–2 scales. Rather than spending an 85B-token budget on a single unseeded hero run, we trained >250> 250 models across 7 scales with n=6n = 6 paired seeds per arm to resolve exact scaling laws and tt-statistics. We believe our experimental setup is indeed significantly more comprehensive than prior work. As for the magnitude of the gains: routed experts account for at most 22–25% of forward FLOPs in our models (the rest is attention, a shared dense MLP, and the 262k vocabulary head). Simply reallocating that same ktar=4k_{\mathrm{tar}} = 4 budget—with zero extra FLOPs or parameters—cuts C4 loss by nearly 0.050.05 nats (∼5\sim 5\\% perplexity reduction, t=−8.3t = -8.3) at 4.42B, recovering 37% of the entire 4.42B →\to 6.59B model scale step and roughly doubling the gain of loss-free fixed-kk balancing.

3. Evaluation on Held-Out Validation Loss vs. Downstream Benchmarks

"3. Evaluation uses only C4 validation loss, with no standard downstream benchmarks."

We understand that in modern AI labs, modelling decisions need to be measured on a range of benchmarks in order to be suitable for external release. This paper, however, has a much narrower goal, which is to show that token-expert assignment efficiency, which can be achieved by relaxing various assignment allocation constraints, does indeed lead to improved model quality, indeed even at scale. The hold-out validation framework we put forth here does, we believe, quite clearly establish this claim. Moreover, evaluating routing mechanisms via held-out validation loss is the established convention across foundational MoE routing and scaling studies—including BASE Layers (Lewis et al., 2021), "Unified Scaling Laws for Routed Language Models" (Clark et al., ICML 2022), Switch Transformers' routing ablations (Fedus et al., 2022), and Han & Zhong (2025)—and within that standard paradigm, our multi-seed, 7-scale evaluation is substantially broader than prior work.

4. Simplicity of Theoretical Results Relative to Online LP Analysis

"4. Several theoretical results are near-trivial or largely follow from existing online LP analysis."

Formulating MoE routing as a clean LP from which unified algorithms and finite-sample guarantees emerge transparently is a core merit of the framework rather than a weakness. The central technical insight is operating in the dual space: solving the multi-axis primal assignment online across tokens, layers, and steps is intractable, whereas dual OGD processes constraints incrementally over time, yields regret and violation bounds that add across constraint axes rather than multiplying across tensor dimensions, and—by using mean-zero per-layer expert prices (Propositions 3 and 6)—decouples per-layer balance from cross-layer compute pooling without requiring Slater interior slack.

Reviewer_5p72OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies how to route tokens to experts in a mixture-of-experts model while keeping the compute budget fixed on average and the load balanced across experts. Instead of selecting a fixed number of experts for every token, the authors formulate routing as a stochastic online linear program and adjust the routing scores based on the observed expert usage. The experiments show that allowing compute to vary across tokens and layers improves validation loss over fixed top-k routing. Updating the routing prices during inference also reduces peak expert load with little change in validation loss.

Critical strengths

The paper presents an interesting perspective of treating several routing constraints within a unified optimization framework. In particular, I appreciate the distinction between fixing the number of experts for each token, fixing the average within each layer, and sharing the same budget across layers. This makes it possible to study which constraint is useful to relax, rather than treating each routing method as a separate design.

Critical weaknesses

There are three primary weaknesses: (1) limited novelty and insufficient experimental evidence to establish an advantage over existing routing methods, (2) unclear inference-time overhead, and (3) difficulty following the proposed method from the main text.

For the first point, although the unified perspective is interesting, it remains unclear what the proposed method offers beyond existing adaptive routing approaches. In particular, the paper discusses Expert Threshold Routing and DTop-p, which already allow the number of experts to vary across tokens, but neither is included in the experimental comparison. Table 6 compares the proposed variants with TopK+Aux and TopK-OLP, both of which use a fixed number of experts per token. As it stands, the experiments make a case for varying the number of experts per token, but give no compelling reason to use the proposed optimization framework over existing adaptive routers.

A related concern is whether the reported gains hold with longer pretraining. All seven model sizes are trained for 20000 steps on the same 327M tokens. Although Figure 3 shows that validation loss changes little during the final 5,000 steps, this is also when the learning rate approaches its minimum. The reported 99.5–99.8% refers only to the fraction of the loss reduction observed within that run. It does not establish that the models would gain little from further training. The comparison is valid at the chosen budget, but it would be helpful to see whether VarK-Global retains its advantage over TopK+Aux at a larger token budget for at least one model size, with the learning-rate schedule adjusted to the longer run, e.g. billion tokens scale.

The next point is a concern about additional computation during inference. In Algorithm 2, the experts selected for one token affect the routing prices used for the next token. This is particularly important during prompt prefill, where routing decisions at the same layer could otherwise be made in parallel across token positions. During decoding, Batch-OLP also requires aggregating expert usage across the serving batch. Although the paper reports a reduction in peak expert load, it does not report prefill latency or decoding throughput. Given this additional dependency, it remains unclear whether the improvement in load balance translates into more efficient inference in practice

Finally, I found the presentation difficult to follow because several details needed to understand the method are deferred to the appendix. For example, Table 2 lists the routing variants in terms of their constraints, but one has to refer to the appendix to understand what changes in the routing procedure from VarK to TopP, or which prices are updated when switching from training to Sequence-OLP and Batch-OLP at inference. Similarly, Equation (6) introduces the step size (ηλ\eta_\lambda) and mentions a similar update for (\tau), but it is unclear how the training step sizes were chosen.

Questions for authors
  1. It would be helpful if the authors could compare VarK with Expert Threshold Routing and TopP with DTop-p under the same training conditions and average compute budget. Does the proposed framework still improve validation loss or expert balance when the baseline can also vary the number of experts per token?
  2. Could the authors report prefill latency and decoding throughput on the same checkpoint with and without the inference-time updates? In particular, it would be useful to see how the additional routing dependency affects prefill as the prompt gets longer.
5 comments
AuthorsOpenReview ↗

Author Response to Reviewer 5p72 (Part 1/2): Relationship to ETR and DTop-p

We thank Reviewer 5p72 for the thoughtful, constructive review and for highlighting the value of studying per-token, per-layer, and cross-layer routing constraints within a unified optimization framework. Below we'll try to address your concerns (split across Parts 1/2 and 2/2).

1. Comparison With Existing Adaptive-Cardinality Routers (Expert Threshold Routing and DTop-p)

"For the first point, although the unified perspective is interesting, it remains unclear what the proposed method offers beyond existing adaptive routing approaches. In particular, the paper discusses Expert Threshold Routing and DTop-p, which already allow the number of experts to vary across tokens, but neither is included in the experimental comparison... Question 1: It would be helpful if the authors could compare VarK with Expert Threshold Routing and TopP with DTop-p under the same training conditions and average compute budget. Does the proposed framework still improve validation loss or expert balance when the baseline can also vary the number of experts per token?"

Both methods correspond closely to the per-layer adaptive variants already evaluated in Table 6, which lets Table 6 isolate what our broader LP framework adds beyond varying kk per token. But let us address two key points.

  1. We thank the reviewer for recommending a closer comparison with two related methods (ETR and DTop-p). However, upon closer inspection of each update procedure, we have realized that Expert Threshold Routing (ETR) and DTop-p are actually much closer to SOLP than we originally appreciated - both are essentially special cases of our framework with minor algorithmic variations:
    • Same LP objectives: Both methods target the exact two LP objectives in our paper: ETR corresponds to our linear token/expert affinity LP (VarK, (3)), while DTop-p corresponds to our rank-slot tail-coverage LP (TopP, Appendix C, (10)), where the compute budget dual directly parameterizes P=1−τP = 1 - \tau.
    • ETR's update rule: ETR tracks each expert's threshold via an Exponential Moving Average (EMA) of batch quantiles. Because the Hessian of our pinball-loss dual (Appendix B) is the "score density" at the threshold, stepping toward the batch quantile is effectively a damped Online Newton step (step size 1−β1 - \beta) on our exact dual objective.
    • ETR's constraint limits: Batch-quantile EMA only works when the experts decouple completely, so ETR requires vacuous per-token bounds (kmin⁡=0k_{\min} = 0, kmax⁡=Ek_{\max} = E) and fixed per-layer targets. It cannot enforce the "token guardrails" [kmin⁡,kmax⁡][k_{\min}, k_{\max}] (this also avoids ETR's non-causal Expert Choice warmup), nor can it move expert compute across layers.
    • DTop-p's update rule: DTop-p updates its threshold via a PI controller, pn+1=p0+Kint∑i≤nei+Kproenp_{n+1} = p_0 + K_{\mathrm{int}} \sum_{i \le n} e_i + K_{\mathrm{pro}} e_n, where ene_n is the batch sparsity error. Since ene_n is proportional to the dual subgradient of our TopP LP, this is equivalent to our OGD update plus a one-step optimistic term KproenK_{\mathrm{pro}} e_n (Optimistic OGD on the same dual, with the exact same equilibrium fixed points).
    • Balancing and cross-layer control in DTop-p: DTop-p still relies on an auxiliary load-balancing loss for expert balance and a learned "Dynamic Routing Normalization" layer to share a threshold across depth. SOLP handles both directly inside the LP via mean-zero per-layer expert prices (Proposition 3), without auxiliary losses or extra learned parameters.
  2. On whether our framework still improves validation loss and balance when the baseline can also vary kk per token: because ETR and DTop-p map so closely onto our per-layer variants (VarK-Layer and TopP-Layer), Table 6 already tests what the broader LP adds beyond per-token adaptivity. Relaxing to cross-layer pooling yields consistent further gains across scales—for example, moving from VarK-Layer to VarK-Global improves C4 loss from −0.0380-0.0380 to −0.0497-0.0497 nats at 4.42B (and −0.0327-0.0327 to −0.0418-0.0418 nats at 6.59B), while TopP-Global improves over TopP-Layer by up to −0.012-0.012 nats across 6 of 7 scales. We think it will be very valuable to spell out these connections explicitly in the revision (and fix our imprecise summary of ETR in Table 1). That said, if there is a specific detail separating ETR or DTop-p from VarK-Layer / TopP-Layer (such as ETR's unguarded [0,E][0, E] range vs. our [2,8][2, 8] guardrails, or another adaptive baseline) that the reviewer would find particularly informative to see ablated directly, we would be happy to run a targeted comparison during the discussion window.

(Continued in Part 2/2.)

AuthorsOpenReview ↗

Author Response to Reviewer 5p72 (Part 2/2): Token Horizon, Serving Latency, and Presentation

(Continued from Part 1/2.)

2. Pretraining Token Budget and Cosine LR Schedule Tail

"All seven model sizes are trained for 20000 steps on the same 327M tokens. Although Figure 3 shows that validation loss changes little during the final 5,000 steps, this is also when the learning rate approaches its minimum... it would be helpful to see whether VarK-Global retains its advantage over TopK+Aux at a larger token budget for at least one model size, with the learning-rate schedule adjusted to the longer run, e.g. billion tokens scale."

While we understand and appreciate the reviewer's instinct to focus on a compute-optimal regime for the experimental setup, we chose to follow what has arguably become the convention in this literature: a fixed horizon scaling ladder, as followed by Switch Transformers, BASE Layers, and Clark et al. ("Unified Scaling Laws for Routed Language Models," ICML 2022). We believe our experimental comparisons are indeed quite comprehensive in this framework, as we were able to compare across n=6n = 6 paired seeds, 6 routing method variants, and 7 different model scales. We are crossing a wide range of token-to-parameter ratios across these scales. If the various benefits of SOLP were a short-horizon artifact, it would shrink on the much more token-rich smaller scales or narrow across steps, whereas we're actually able to show that the gain holds across every scale and remains steady throughout training (see Figure 3).

3. Inference-Time Latency, Prefill Parallelism, and Decoding Throughput

"In Algorithm 2, the experts selected for one token affect the routing prices used for the next token. This is particularly important during prompt prefill, where routing decisions at the same layer could otherwise be made in parallel across token positions... Question 2: Could the authors report prefill latency and decoding throughput on the same checkpoint with and without the inference-time updates? In particular, it would be useful to see how the additional routing dependency affects prefill as the prompt gets longer."

This is an important practical point. We are currently running pipeline-prefill latency and serving throughput experiments across prompt lengths on the same checkpoint, and will post those concrete measurements and plots here within the next few days. We also note that prefill and decoding do not require the same update frequency. Corollary 1 (U=H/KU = H / K) directly supports updating λseq\lambda_{\mathrm{seq}} in coarse token blocks during prefill (or running prefill fully in parallel with ηseq=0\eta_{\mathrm{seq}} = 0), while applying step-by-step Batch-OLP during autoregressive decoding where tokens already arrive sequentially one step at a time.

4. Main-Text Self-Containedness (TopP, Inference Duals, and Step Sizes)

"Finally, I found the presentation difficult to follow because several details needed to understand the method are deferred to the appendix. For example, Table 2 lists the routing variants in terms of their constraints, but one has to refer to the appendix to understand what changes in the routing procedure from VarK to TopP, or which prices are updated when switching from training to Sequence-OLP and Batch-OLP at inference. Similarly, Equation (6) introduces the step size (ηλ\eta_\lambda) and mentions a similar update for (τ\tau), but it is unclear how the training step sizes were chosen."

Thank you for pinpointing these omissions; we will make Section 4 self-contained in the revised manuscript by: (1) adding an Objective column to Table 2 and stating the 2-line TopP tail-mass rule (Ct,j−1<1−τ=:PC_{t,j-1} < 1 - \tau =: P) directly alongside Eq. (5); (2) writing out the inference adjusted score st=ct−(λtrain+λseq)−τtrains_t = c_t - (\lambda_{\mathrm{train}} + \lambda_{\mathrm{seq}}) - \tau_{\mathrm{train}} in Section 4 to make clear that (λtrain,τtrain)(\lambda_{\mathrm{train}}, \tau_{\mathrm{train}}) are frozen while only λseq\lambda_{\mathrm{seq}} updates online; and (3) reporting the exact dual step sizes (ηλ=0.03\eta_\lambda = 0.03 in normalized log-prob gap units across all arms; ητ=0.05\eta_\tau = 0.05 for VarK and 0.010.01–0.020.02 for TopP), which were tuned once at 183M and transferred unchanged up to 6.59B. Thanks for catching this omission!

AuthorsOpenReview ↗

Follow-Up on Section 3: Prefill Latency Across Prompt Lengths, Batch-OLP Sync Cost, and Decode Throughput

Following up on Part 2/2 (Section 3), we ran compiled JAX serving benchmarks measuring prefill latency across prompt lengths TT and KV-cache decode throughput on the same frozen checkpoint with vs. without Algorithm 2 updates. Below are the four main takeaways, followed by three reference tables.

Key Takeaways

  1. Our main training models (Algorithm 1, Table 6) have zero inference overhead. Algorithm 1 freezes its learned prices (λ,τ)(\lambda, \tau) after training, so at inference (η=0\eta = 0) routing runs in parallel just like standard Top-k. No token-to-token dependency or cross-batch sync. Algorithm 2 (Sequence-OLP / Batch-OLP) is an optional serving controller used only when tighter serving balance is needed.

  2. Prefill does not slow down on longer prompts once prices update in chunks (K=128K = 128 tokens) instead of every token (K=1K = 1). The reviewer is right that updating prices after every token (K=1K = 1) serializes routing and significantly slows prefill (on the 4.4B model this is 583.9 vs. 203.8 ms, Table 1). If we instead update in blocks (typically, block size K=128K = 128 tokens) we reduce $ > 99\%$ of that cost. In this block mode, the sequential OLP scan adds only +0.5% to +1.4% to wall-clock time, as we range prefill chunk sizes from T=512T = 512 to 40964096. The cost to decode is even smaller, only an additional 0.2%.

  3. Batch-OLP's cross-batch communication costs only ~1%–2%, and Sequence-OLP requires 0%. Under expert sharding, Batch-OLP sums 128 expert counts across chips (512 bytes per all_reduce), whereas overloaded experts ship tens to hundreds of MBs of token activations in extra all_to_all passes. Comparing Batch-OLP against Sequence-OLP (no cross-batch sync) across 32 devices shows Batch-OLP's all_reduce adds just 5–10 ms (1%–2%) in prefill and 0.14 ms/step (1.3%) in decode.

  4. When experts are sharded across chips, the savings from load-balance well-surpasses the ~1% cost. On an unsharded pool (Table 1), balancing saves no FLOPs, so η=0\eta = 0 is ~1% faster. Under 8- and 32-device Expert Parallelism on Gemma 4 26B-A4B (E=128E = 128, top-88, 37.537.5\\% routed FLOPs), cutting peak load from 6.95x toward 1.5x removes overflow rounds and speeds up both prefill (1.15x–3.5x across T=1024→4096T = 1024 \to 4096) and decode (1.14x–1.45x) (Table 2), while in single-pass mode η∈[1,3]\eta \in [1, 3] improves both latency and C4 loss by preventing dropped tokens (Table 3).

We want to sincerely thank the reviewer for pushing on this point: the prefill+decode results significantly strengthen the paper, and we will incorporate these in the final version.

Reference Tables

Table 1: Pure Router Overhead Without Sharding (4.42B VarK-Global, B=4B = 4 Prefill)

Routing ModeT=512T = 512T=1024T = 1024T=2048T = 2048T=4096T = 4096Decode (B=32B = 32)
No updates (η=0\eta = 0)57.3 ms76.5 ms104.7 ms203.8 ms973 tok/s
Every token (K=1K = 1)106.0 ms172.1 ms293.5 ms583.9 ms—
Batch-OLP (K=128K = 128)58.0 ms76.9 ms105.9 ms206.7 ms971 tok/s
Sequence-OLP (K=128K = 128)58.7 ms77.9 ms106.8 ms207.0 ms970 tok/s

Table 2: Dropless Expert-Parallel Serving (Gemma 4 26B-A4B, 0% Drop)

Sharded SetupT=1024T = 1024T=2048T = 2048T=4096T = 4096Decode (B=64B = 64)
32-Dev Ragged A2A — No updates327 ms669 ms1,348 ms4,790 tok/s
32-Dev Ragged A2A — Batch-OLP290 ms589 ms1,185 ms5,326 tok/s
32-Dev Ragged A2A — Sequence-OLP285 ms583 ms1,175 ms5,472 tok/s
8-Dev CapLoop — No updates520 ms877 ms1,582 ms2,382 tok/s
8-Dev CapLoop — Batch-OLP244 ms445 ms839 ms3,457 tok/s
8-Dev CapLoop — Sequence-OLP235 ms430 ms823 ms3,378 tok/s

(Prefill & 8-dev decode: 1.25x buffer; 32-dev decode: 2.0x buffer; K=128K = 128–256256.)

Table 3: Batch-OLP Latency vs. C4 Loss Across η\eta (26B-A4B, 32-Dev, 2.0x Buffer, T=2048,K=128T = 2048, K = 128)

η\etaPeak LoadDropless LatencyDropless LossSingle-Pass LatencyDroppedSingle-Pass Loss
06.95x364.4 ms2.451266.1 ms3.5%2.470
1.03.96x321.2 ms2.456274.3 ms0.7%2.459
2.03.05x293.2 ms2.462268.0 ms0.2%2.463
3.02.60x280.2 ms2.468263.9 ms0.05%2.468
6.01.99x260.4 ms2.485255.4 ms0.0%2.485
16.01.53x250.9 ms2.527245.9 ms0.0%2.527

(Sequence-OLP is 9–11 ms faster per row—264.5 ms at 2.465 loss for η=1\eta = 1, 240.4 ms dropless at η=16\eta = 16—cutting single-prompt skew 8.20x -> 1.61x.)

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.