acceptodds
Under review as a conference paper at ICLR 2027

BRANCH-MoE: Balance-Aware Tree Routing for Large Embedding Models

Abstract

Mixture-of-experts (MoE) layers increase model capacity without a proportional increase in per-example computation. However, conventional flat routers can yield imbalanced expert utilization and treat experts as an unstructured collection, whose indices carry no topological meaning. We introduce BRANCH-MoE, a routing architecture that places \(E\) experts at the leaves of a binary decision tree of depth . At each internal node the branching probability is centered on the arrival-weighted mean score of the traffic reaching that node. This mean is estimated using an exponential moving average, which promotes utilization of both child subtrees without an auxiliary load-balancing loss. We show that this moving-average estimate admits an explicit noise–lag trade-off. We prove that for linear node maps and log-concave arrival distributions, this mechanism prevents routing-mass collapse. We further establish that, under a frozen router, an expert’s execution frequency controls its stochastic-gradient convergence rate, and that confident decisions near the root bound cross-device communication when experts are assigned to devices by tree prefix. We evaluate BRANCH-MoE against Switch softmax, DeepSeek-V3 dynamic-bias, Skywork logit-normalized, and deterministic hash routing on Criteo click-through-rate prediction, Forest Covertype, HIGGS, and YearPredictionMSD, using \(E=16\), top-\(4\) routing, and five random seeds. BRANCH-MoE matches the predictive performance of the strongest baselines, attaining the lowest mean held-out loss on Forest Covertype and showing no statistically significant difference from the best-performing methods on Criteo, HIGGS, or YearPredictionMSD across random seeds. It also maintains balanced expert load without an auxiliary penalty. Unlike flat routers, BRANCH-MoE induces input-conditional co-routing locality: for each input token, the experts selected together tend to lie closer to one another in the routing tree. On all three UCI benchmarks, linear node maps yield a normalized tree distance of \(0.710\)–\(0.718\) between co-selected experts, compared with \(0.817\) for random expert pairs—a reduction of \(12\)–\(13%\). Every flat-routing baseline remains within \(3.5%\) of the random-pair distance. Together, these results show that hierarchical routing can preserve task quality and balanced utilization while inducing a topology that supports localized expert co-activation and reduced communication.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Mixture of Experts, Hierarchical Tree Routing, Conditional Computation, Auxiliary-Loss-Free Load Balancing, Routing Locality

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_F8mMOpenReview ↗
Rating
1(−1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes BRANCH-MoE, a hierarchical MoE router that places experts at the leaves of a binary tree and uses arrival-weighted EMA anchors to center each internal routing decision. The goal is to obtain balanced expert utilization without an auxiliary load-balancing loss while simultaneously giving expert indices a meaningful tree topology that can support communication locality.

Critical strengths
  • Coherent routing design that jointly addresses balance and topology. BRANCH-MoE does more than replace one balancing heuristic with another: the tree structure, arrival-weighted EMA anchoring, and prefix-based expert addresses are coupled in a single routing mechanism. This is consequential because the method maintains competitive predictive quality and reasonably balanced utilization without an auxiliary balancing loss, while also producing locality that flat routers do not exhibit on the three UCI benchmarks.

  • The paper provides theoretical support for the routing mechanism. The analysis connects EMA anchoring to a noise lag trade-off, establishes a positive soft routing-mass bound under stated assumptions, relates expert execution frequency to SGD convergence, and derives explicit communication-locality bounds under tree-aligned placement. This strengthens the contribution beyond an empirical routing heuristic and provides useful insight into why the proposed architecture may avoid starvation and induce structured expert assignments.

Critical weaknesses
  • The empirical evaluation is too small-scale to substantiate the paper’s systems-oriented motivation. All experiments use a single MoE layer with only 16 experts on tabular benchmarks, and the paper does not evaluate a multilayer language/embedding model or an actual distributed, topology-aware implementation. The claimed communication benefit is assessed through tree-distance proxies rather than measured cross-device traffic, throughput, or end-to-end latency. The authors themselves note that multilayer interactions and large-scale topology-aware implementations remain future work. This is important because reduced communication and suitability for large embedding/MoE models are central motivations of the method, yet they are not directly demonstrated in the setting where they would matter most.

  • The strongest theoretical guarantee does not directly cover the actual sparse routing behavior, and the locality effect is not robust across datasets. The anti-collapse result concerns soft routing mass for linear routing under log-concave arrival distributions, the paper explicitly notes that this does not guarantee positive execution probability after deterministic top-K selection. Moreover, the proposed locality disappears on Criteo: the linear BRANCH-MoE tree distance is statistically indistinguishable from random, and the authors have not isolated the cause. This weakens the connection between the theoretical motivation and the behavior of the actual sparse router, particularly because locality is one of the paper’s principal claimed advantages.

Questions for authors
  1. Can the authors provide experiments on a multilayer MoE model with substantially more experts, ideally including an actual multi-device setup? In particular, how much do the observed tree-distance improvements translate into reductions in communication volume and end-to-end latency?

  2. Can the authors empirically quantify how well the theoretical soft leaf-mass bound correlates with actual expert execution frequency after top-K truncation? Are there settings where a leaf has non-negligible soft mass but is nevertheless rarely or never executed?

  3. Why does training remove the locality that is already present in the untrained BRANCH-MoE tree on Criteo?

  4. The paper observes that changing the node map can affect predictive loss more strongly than changing the routing rule itself, and nonlinear node maps can also weaken BRANCH-MoE locality. How sensitive are the claimed benefits to this architectural choice, and is there a principled way to choose the node-map complexity?

4 comments
AuthorsOpenReview ↗

Question 1 and Question 2

We thank Reviewer F8mM for the positive assessment of our coherent balance-and-topology design, and four insightful technical questions. Below we address all three weaknesses and questions. We have also uploaded a revised 10-page manuscript (all revisions highlighted in blue) to reflect these changes.

Q1. Multilayer MoE, Larger Expert Counts (E>16E > 16), and Reductions in Communication Volume / Latency

We added three sets of experiments in Section 5.3 and Appendix G.5 (Figures 3–4, Tables 10–11):

  1. Scaling to E∈2,4,8,16,32,64E \in \\{2,4,8,16,32,64\\} (D∈1,…,6D \in \\{1,\dots,6\\}, K=min⁡(4,E/2)K = \min(4, E/2), Table 10): Locality strengthens monotonically with depth (L/DL/D drops from 0.7700.770 vs. 0.8330.833 at E=4E=4 and 0.7710.771 vs. 0.8100.810 at E=8E=8 down to 0.6830.683 vs. 0.8490.849 at E=64E=64, −19.6-19.6\\%), with 00 dead experts and task loss matching Switch and Flat-Centered baselines at every scale.
  2. Multilayer Causal Transformer LM (Table 11, Figure 4a): On a 2-layer causal Transformer LM with token embeddings, multi-head self-attention, and two stacked E=16,K=4E=16, K=4 SwiGLU MoE blocks on Shakespeare (5 seeds), linear BRANCH-MoE achieves 12.6512.65 validation perplexity (matching Switch 12.6612.66 and DeepSeek-V3 12.7512.75, and tying h=8h=8 MLP BRANCH-MoE at 12.5512.55, Welch p=0.68p = 0.68), maintains balanced utilization across both layers without auxiliary loss (CV=0.273\mathrm{CV} = 0.273 and 0.3560.356, whereas unanchored trees degrade from 0.8250.825 to 1.1761.176), and lowers group fanout N2(x)N_2(x) (G=4G=4) by 2121\\% in both Layer 0 (2.372.37 vs. 3.003.00) and Layer 1 (2.422.42 vs. 3.073.07). We also updated the paper title to "BRANCH-MoE: Balance-Aware Hierarchical Tree Routing for Mixture-of-Experts" to reflect the evaluated scope accurately.
  3. Translation to communication volume and dispatch latency: Defining group fanout Nr(x):=∑g=02r−11SK(x)∩Lg≠∅N_r(x) := \sum_{g=0}^{2^r-1}\mathbf{1}\\{\mathcal{S}_K(x)\cap\mathcal{L}_g \neq \emptyset\\} as the number of distinct prefix-aligned hardware groups (G=2rG=2^r) contacted by token xx (and spillover fanout Nr(x)−1N_r(x)-1 beyond the primary subtree), at E=64,K=4E=64, K=4 BRANCH-MoE lowers N2(x)N_2(x) (G=4G=4) from 2.792.79 to 1.981.98 (−29.0-29.0\\%) and N3(x)N_3(x) (G=8G=8) from 3.383.38 to 2.482.48 (−26.6-26.6\\% group fanout, −37.8-37.8\\% spillover fanout). Evaluating those 5 trained E=64E=64 routers in a single-host CPU in-memory group-deduplicated gather/scatter microbenchmark (32,76832{,}768 tokens, d=256d=256, float32, G=8,K=4G=8, K=4, median of 25 trials after warmup per seed; distinct from distributed multi-node GPU/TPU network collectives, which remain future systems work) reduces gathered/scattered payload volume from 113.5 MB113.5\,\mathrm{MB} to 83.1 MB83.1\,\mathrm{MB} (−26.8-26.8\\%) and CPU gather/scatter latency from 77.5 ms77.5\,\mathrm{ms} to 59.5 ms59.5\,\mathrm{ms} (−23.2-23.2\\%).

Q2. Correlation Between Soft Leaf Mass qeq_e and Sparse Top-KK Execution pep_e (and When qe>0q_e > 0 Rarely Executes)

We address both parts via new Proposition 4.4 (Section 4.3) and empirical measurements (Table 10, Figure 4b):

  • Mathematical bridge & exact failure regime: Because any leaf e∉SK(x)e \notin \mathcal{S}_K(x) is exceeded by at least KK other entries of m(D)(x)∈ΔE−1m^{(D)}(x) \in \Delta^{E-1}, me(D)(x)≤1K+1m_e^{(D)}(x) \le \frac{1}{K+1} on e∉SK(x)\\{e \notin \mathcal{S}_K(x)\\}. Taking expectations gives

    pe≥qe−δe,tail≥(K+1)qe−1K,δe,tail:=E![me(D)(X) 1e∉SK(X)].p_e \ge q_e - \delta_{e,\mathrm{tail}} \ge \frac{(K+1)q_e - 1}{K}, \qquad \delta_{e,\mathrm{tail}} := \mathbb{E}\\!\big[m_e^{(D)}(X)\,\mathbf{1}\\{e \notin \mathcal{S}_K(X)\\}\big].

    In the sharp-split limit (router weight norms β:=∣Wj(d)∥2→∞\beta := \\|W_j^{(d)}\\\|_2 \to \infty at exact anchors on log-concave inputs), halfspace indicators preserve log-concavity at every depth, δe,tail→0\delta_{e,\mathrm{tail}} \to 0, and Grünbaum's inequality yields pe=qe≥e−Dp_e = q_e \ge \mathrm{e}^{-D} for every K≥1K \ge 1. Conversely, qe>0q_e > 0 can coexist with pe=0p_e = 0 only if me(D)(X)≤1K+1m_e^{(D)}(X) \le \frac{1}{K+1} almost surely—i.e., in the near-zero weight-norm regime (β=∣Wj(d)∥2≈0\beta = \\|W_j^{(d)}\\\|_2 \approx 0) where all branch splits hover near 1/21/2 (me(D)(x)≈1/E<1K+1m_e^{(D)}(x) \approx 1/E < \frac{1}{K+1}) and small static offsets rank KK leaves ahead.

  • Empirical quantification: In trained BRANCH-MoE models, qeq_e and pe/Kp_e/K correlate strongly (Pearson r=0.972r = 0.972 at E=16E=16, 0.8590.859 at E=32E=32, with 00 dead experts across all depths and seeds). Scaling the router weight norm Wj(d)=βWˉj(d)W_j^{(d)} = \beta \bar{W}_j^{(d)} (∣Wˉj(d)∥2=1\\|\bar{W}_j^{(d)}\\\|_2 = 1) across β∈[0.02,4.0]\beta \in [0.02, 4.0] at E=16,K=4E=16, K=4 (Figure 4b) confirms Proposition 4.4: for β∈[0.25,4.0]\beta \in [0.25, 4.0], min⁡epe∈[0.19,0.24]\min_e p_e \in [0.19, 0.24] (near uniform K/E=0.25K/E = 0.25), and min⁡epe\min_e p_e drops near zero (0.00060.0006 despite min⁡eqe=0.060\min_e q_e = 0.060) only when β\beta is compressed to 0.020.02 so that every split hovers near 1/21/2 (1−E[RK]=0.7431 - \mathbb{E}[R_K] = 0.743).

AuthorsOpenReview ↗

Question 3 and Question 4

Q3. Why Does Training Remove Initial Untrained Locality (0.725→0.8130.725 \to 0.813) on Criteo?

  1. Why untrained BRANCH-MoE starts at 0.7250.725: At random Glorot initialization, unit-variance centered logits produce moderate depth-33 splits (σ(z)∈[0.25,0.75]\sigma(z) \in [0.25, 0.75]). Sibling leaves (2j,2j+1)(2j, 2j+1) share identical ancestor probabilities up to depth 33, so whenever their parent has large arrival mass, both siblings enter S4(x)\mathcal{S}_4(x) together (L=1L = 1), yielding initial L/D≈0.72L/D \approx 0.72.
  2. Plausible mechanisms behind the training shift on Criteo: While we did not vary batch size or training passes independently on Criteo, two diagnostics shed light on this shift: first, in a 25-seed single-expert dense control (base, Appendix G.5) directly on Criteo, one SwiGLU expert (0.44650.4465 logloss, 0.80600.8060 AUC) already matches or slightly exceeds all 17 MoE arms on AUC (0.80560.8056–0.80600.8060) and comes within 6×10−46\times 10^{-4} in logloss (0.44600.4460–0.44620.4462), whereas on Covertype 16-expert MoE beats single-expert base by +6.78%+6.78\% accuracy. Second, Criteo concatenates 39 anonymized categorical fields whose effects combine additively; in a controlled synthetic comparison of cluster-partitioned vs. 4-block additive targets from identical initial trees (L/D=0.721L/D = 0.721, Appendix G.5), additive multi-field tasks suppress root margins relative to leaf margins (E∣z(0)∣=0.87\mathbb{E}|z^{(0)}| = 0.87 vs. E∣z(3)∣=1.21\mathbb{E}|z^{(3)}| = 1.21, ratio 1.391.39), causing tokens to select specialists across distinct subtrees in accordance with Theorem 4.5.

Q4. Sensitivity to Node-Map Complexity & Principled Selection Guideline

We added both theoretical intuition and a direct linear vs. h=8h=8 MLP ablation in our 2-layer causal Transformer LM in Section 5.2 ("Node maps", Pages 9–10) and Appendix G.5 (Table 11):

  • Why MLPs loosen balance and locality (Section 5.2): Anchoring enforces zero mean score (EDj[zj(X)]=0\mathbb{E}_{\mathcal{D}_j}[z_j(X)] = 0) for any node map, whereas balanced mass splitting depends on the median. Linear maps link mean and median via Grünbaum's halfspace inequality; curved MLP level sets permit skewed tails. Even so, on UCI moving from linear to h=8h=8 shifts L/DL/D only modestly from 0.7100.710–0.7180.718 to 0.7360.736–0.7490.749, still 88–10%10\% below random (0.8170.817) and every flat router (0.8000.800–0.8190.819).
  • New multilayer Transformer linear-vs.-MLP comparison (Appendix G.5, Table 11): Comparing BRANCH-MoE (linear) against BRANCH-MoE (MLP, h=8) across 5 seeds on the 2-layer Shakespeare Transformer LM shows statistically indistinguishable task quality (2.5377±0.02092.5377 \pm 0.0209 vs. 2.5295±0.03692.5295 \pm 0.0369 Val CE, Welch p=0.68p = 0.68), while h=8h=8 MLPs widen Layer 0 Load CV (0.273→0.3500.273 \to 0.350), loosen Layer 0/1 L/DL/D (0.725/0.722→0.782/0.7630.725/0.722 \to 0.782/0.763), raise group fanout N2N_2 (2.37/2.42→2.64/2.572.37/2.42 \to 2.64/2.57), and add 17×17\times more router parameters.
  • Principled selection rule (Section 5.2 & Appendix G.5): Per-node MLPs improve task loss only when the MoE sits directly on raw standardized features with no upstream hidden layer (Covertype, MSD). Whenever an upstream learned representation layer precedes the MoE—such as Criteo's Dense(256)->SiLU->LN (p=0.19p = 0.19) or self-attention blocks in multilayer Transformers (p=0.68p = 0.68, Table 11)—use linear node maps, which match MLP quality while preserving exact Grünbaum guarantees, tighter Load CV, strongest prefix locality, and minimal router cost. (Where nonlinear router features are needed on raw inputs, applying linear node maps after a shared projection ϕ(x)\phi(x) also preserves halfspace splits in ϕ(x)\phi(x)-space; Appendix C.2.)
AuthorsOpenReview ↗

A gentle reminder as the deadline is approaching

Thank you again for your constructive feedback, which has meaningfully strengthened our work.

As the discussion phase closes soon, we wanted to let you know that we have addressed all the points raised in your review with new experiments and analyses. If any of your concerns remain, please let us know so we can discuss them further.

If our response has resolved your questions, we would be grateful if you would consider updating your score to reflect these improvements. Thank you for your time and guidance!

Reviewer_F8mMOpenReview ↗

Response to authors

Dear Authors,

Thank you for your effort. However, you response haven't addressed my concern.

Q1. The author report 23.2% latency reduction, but this is CPU gather/scatter time without routing computation, expert execution and real communication with GPUs. Need to evaluate end-to-end inference and training (because your motivation is system oriented method)

Moreover, the author need to compare communication savings with scenario that flat router place frequently co-selected experts on the same device. If this work, then your contribution (hiearachial routing) is not necessary.

Finally, the 2-layer character-level Transformer experiment is too small to demonstrate the method's effectiveness on realistic large-scale MoE language models.

Q2. The lower bound in Proposition 4.4 is useless when qe≤1/(K+1)q_e \leq 1/(K+1), which includes balanced soft routing for E=16E=16, K=4K=4. Moreover, the condition me(X)≤1/(K+1)m_e(X) \leq 1/(K+1) does not establish that top-K starvation occurs only when the router weight norms approach zero. This misleading and overstates what Proposition 4.4 actually guarantees.

The authors need to clarify whether non-negligible weight norms can also lead to expert starvation, and why the reported correlation decreases from 0.972 at E=16E=16 to 0.696 at E=64E=64.

Q3. The single-expert results do not explain why training removes locality, and the synthetic additive-task experiment does not establish that the same mechanism occurs on Criteo. Moreover, Theorem 4.5 provides a sufficient condition for locality, not a causal explanation for its disappearance. The authors need to provide direct evidence from Criteo, such as root/leaf margin evolution and tree distance throughout training, to substantiate the proposed explanation.

Q4. The proposed node-map selection guideline remains empirical rather than principled. Moreover, applying linear routing after a nonlinear learned representation ϕ(x)\phi(x) does not necessarily preserve log-concavity, which is required by Corollary 4.2. Therefore, the claimed preservation of theoretical guarantees is not justified.

I believe this work still requires substantial improvements to meet the acceptance bar for ICLR.

Reviewer_sdU4OpenReview ↗
Rating
2(+1)
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper proposes BRANCH-MoE, a hierarchical MoE router that combines binary-tree routing with EMA-based score anchoring to balance expert utilization without auxiliary losses. The paper provides theoretical analyses of routing balance and communication locality. Experiments on four tabular datasets show competitive predictive performance and improved routing locality on three datasets.

Critical strengths
  1. The method is simple and combines hierarchical routing with load balancing without an auxiliary loss.

  2. The paper provides theoretical analyses of routing-mass bounds, anchor estimation, and communication locality.

  3. The experiments include several representative MoE baselines and different node-map configurations.

Critical weaknesses
  1. Hierarchical routing and score centering are established techniques. The paper lacks critical ablations against an unanchored tree router and an equivalently centered flat router to justify the novelty and necessity of the proposed design.

  2. The claimed communication efficiency improvement is not supported by actual system measurements. The paper only reports tree-distance metrics and fails to show improved locality on Criteo.

  3. The experimental results show limited advantages over existing routers. BRANCH-MoE achieves competitive predictive performance but does not consistently outperform the baselines, while DeepSeek-V3 shows better load balancing on several datasets. Moreover, all experiments use a single MoE layer with only 16 experts, providing limited evidence of scalability.

Questions for authors
  1. Can the authors provide ablations against an unanchored tree router and a flat router with equivalent score centering?

  2. Does the improved tree locality translate into measurable communication or inference efficiency gains?

  3. How does BRANCH-MoE perform with more experts and multiple MoE layers?

4 comments
AuthorsOpenReview ↗

(Weakness 1 & Question 1), (Weakness 2 & Question 2)

We thank Reviewer sdU4 for noting the simplicity of our auxiliary-loss-free hierarchical router, our theoretical guarantees, and our baseline comparisons. Below we address all three weaknesses and questions. We have also uploaded a revised 10-page manuscript (all revisions highlighted in blue) to reflect these changes.

1. Ablations Against an Unanchored Tree Router and an Equivalently Centered Flat Router (Weakness 1 & Question 1)

We added both a theoretical proof (Proposition 4.3) and a 2×22 \times 2 empirical ablation (Section 5.3, Figure 3a–b, Table 8) comparing Flat Unanchored, Flat Score-Centered (ze(x)=fe(x)−ν^ez_e(x) = f_e(x) - \widehat{\nu}_e), Unanchored Tree, and BRANCH-MoE:

  • Theory: Proposition 4.3 proves that for E≥3E \ge 3 on X∼N(0,Idin)X \sim \mathcal{N}(0, I_{d_{\mathrm{in}}}), a flat score-centered softmax router at exact population anchors (νe⋆=0\nu_e^\star = 0) still suffers O(1/R)\mathcal{O}(1/R) routing-mass collapse under logit scale asymmetry and yields random expected tree distance (0.8170.817), whereas an unanchored tree starves E/2E/2-expert subtrees whenever upstream activations carry a nonzero offset.
  • Empirical 2×22 \times 2 results (5 seeds, E=16,K=4E=16, K=4, capacity factor 1.251.25):
    • Unanchored Tree: CV=0.970\mathrm{CV} = 0.970 (UCI Digits) and 1.0021.002 (Hierarchical), dropping 32.4%32.4\%–33.0%33.0\% of dispatches and leaving 1.01.0–3.43.4 experts dead.
    • Flat Score-Centered: 00 dead experts, but higher CV\mathrm{CV} (0.3660.366 / 0.1910.191) and zero locality (L/D=0.820L/D = 0.820 / 0.8180.818; N2(x)=2.94N_2(x) = 2.94 / 2.922.92 out of G=4G=4 groups vs. 2.912.91 random).
    • BRANCH-MoE: 00 dead experts, low CV\mathrm{CV} (0.2720.272 / 0.1640.164; 3.3%3.3\% / 0.9%0.9\% drops), competitive loss, and L/D=0.727L/D = 0.727 / 0.7300.730 (N2(x)=2.46N_2(x) = 2.46, −16.3%-16.3\% fewer contacted groups and −24.7%-24.7\% fewer secondary cross-group transfers).

2. Measurable Communication / Dispatch Efficiency Gains & Criteo Locality (Weakness 2 & Question 2)

  • Concrete communication volume and scatter-gather latency (Section 4.4, Section 5.3, Figure 3c, Table 10): Partitioning E=2DE = 2^D experts by their length-rr prefix into G=2rG = 2^r hardware groups {Lg}g=0G−1\{\mathcal{L}_g\}_{g=0}^{G-1}, each token's payload (stoks_{\mathrm{tok}} bytes) is sent once per contacted group, so communication cost Commr(x)=stokcrNr(x)\mathrm{Comm}_r(x) = s_{\mathrm{tok}}c_r N_r(x) is proportional to group fanout Nr(x):=∑g=0G−11(SK(x)∩Lg≠∅)N_r(x) := \sum_{g=0}^{G-1}\mathbf{1}(\mathcal{S}_K(x)\cap\mathcal{L}_g \neq \emptyset) (with spillover fanout Nr(x)−1N_r(x)-1 beyond the primary group bounded by Theorem 4.5). At E=64,K=4E=64, K=4, BRANCH-MoE lowers N2(x)N_2(x) (G=4G=4) from 2.792.79 to 1.981.98 (−29.0%-29.0\%) and N3(x)N_3(x) (G=8G=8) from 3.383.38 to 2.482.48 (−26.6%-26.6\% group fanout, −37.8%-37.8\% spillover fanout). Evaluating those 5 trained E=64E=64 routers in a single-host CPU in-memory group-deduplicated gather/scatter microbenchmark on N=32,768N = 32{,}768 tokens (d=256d = 256, float32, G=8,K=4G=8, K=4; median wall-clock time across 25 trials after warmup per seed, measuring contiguous per-group buffer gather/copy and scatter-accumulate on host memory rather than distributed multi-node GPU/TPU network collectives) cuts gathered/scattered payload volume from 113.5113.5,MB to 83.183.1,MB (−26.8%-26.8\%) and CPU gather/scatter latency from 77.577.5,ms to 59.559.5,ms (−23.2%-23.2\%). In addition, on Covertype at K=2K=2 (Table 9), BRANCH-MoE achieves both the best validation loss (0.25240.2524) and −17.1%-17.1\% tree distance (0.6770.677).
  • Why Criteo shows no locality (0.8130.813): While we did not vary batch size or training passes independently on Criteo, two diagnostics point to plausible mechanisms consistent with this shift: (i) a 25-seed single-expert dense control (base, Appendix G.5) directly on Criteo attains 0.44650.4465 logloss and 0.80600.8060 AUC—matching or slightly exceeding all 17 MoE arms on AUC (0.80560.8056–0.80600.8060) and coming within 6×10−46\times 10^{-4} in logloss (0.44600.4460–0.44620.4462), whereas on Covertype 16-expert MoE beats single-expert base by +6.78%+6.78\% accuracy (0.23720.2372 vs. 0.38730.3873 CE); and (ii) in a controlled synthetic multi-field diagnostic, orthogonal additive feature blocks sharpen leaf margins over root margins (E∣z(3)∣/E∣z(0)∣=1.39\mathbb{E}|z^{(3)}|/\mathbb{E}|z^{(0)}| = 1.39), driving co-selection across distinct subtrees.
AuthorsOpenReview ↗

Weakness 3 & Question 3

3. Scalability (E≤64E \le 64, Multilayer MoE) & Comparison with DeepSeek-V3 (Weakness 3 & Question 3)

  • Scaling to E=64E=64 and multiple MoE layers (Tables 10–11): Across E∈{2,4,8,16,32,64}E \in \{2,4,8,16,32,64\} (D=1…6D = 1\dots 6, K=min⁡(4,E/2)K = \min(4, E/2)), BRANCH-MoE maintains 00 dead experts while its group-fanout savings increase monotonically with depth (on G=4G=4, ΔN2\Delta N_2: −9.8%-9.8\% at E=8→−14.7%E=8 \to -14.7\% at E=16→−23.5%E=16 \to -23.5\% at E=32→−29.0%E=32 \to \mathbf{-29.0\%} at E=64E=64; on G=8G=8, ΔN3\Delta N_3: −9.9%→−20.8%→−26.6%-9.9\% \to -20.8\% \to \mathbf{-26.6\%}). In a 2-layer causal Transformer LM with self-attention on Shakespeare (Table 11), BRANCH-MoE matches Switch and DeepSeek-V3 in perplexity (12.6512.65 vs. 12.6612.66, 12.7512.75) while reducing group fanout N2(x)N_2(x) by 21%21\% in both MoE layers.
  • Advantage over DeepSeek-V3: DeepSeek-V3 drives Load CV near zero (≈0.002\approx 0.002) via per-expert load feedback, but its flat indices carry zero topological locality (L/D=0.813L/D = 0.813–0.8300.830; N3(x)=3.38N_3(x) = 3.38 at E=64E=64). At standard capacity factor 1.251.25, BRANCH-MoE's Load CV (0.090.09–0.230.23) already yields near-zero token drops (0.08%0.08\% on Criteo, 0.18%0.18\% on Covertype), so driving CV from 0.100.10 to 0.0020.002 saves virtually zero compute while forfeiting 21%21\%–29%29\% reductions in cross-group communication.
  • Presentation: We added Algorithm 1, motivating intuitive explanations before Propositions 4.3–4.4, simplified equation layouts in Sections 3–4, and expanded Section 5 using the 10 page limit for clarity.
AuthorsOpenReview ↗

A gentle reminder as the deadline is approaching

Thank you again for your constructive feedback, which has meaningfully strengthened our work.

As the discussion phase closes soon, we wanted to let you know that we have addressed all the points raised in your review with new experiments and analyses. If any of your concerns remain, please let us know so we can discuss them further.

If our response has resolved your questions, we would be grateful if you would consider updating your score to reflect these improvements. Thank you for your time and guidance!

Thank you for the detailed response and additional experiments.

The new ablations largely address my first concern, and the scaling experiments provide useful additional evidence. However, the practical communication benefits remain insufficiently validated, as the CPU benchmark does not demonstrate end-to-end efficiency gains. A comparison with flat routers using optimized expert placement is also missing.

Given the improvements, I will raise my rating from 1 to 2.

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

This paper proposes a routing method for MoE models for the natural emergence of expert diversity and the locality of token-wise expert coactivation during training, so that load-balancing and low hardware communication overhead can be achieved. Specifically, the paper introduces a tree-based hierarchical routing with a batch-wise anchoring method to achieve the goal. Theoretical bounds are provided to justify the design, and empirical results are provided for verification.

Critical strengths
  1. The proposed approach is novel, interesting, and intuitive

  2. Theoretical results are nontrivial and promising

Critical weaknesses
  1. The paper lacks theoretical comparison and/or empirical ablation studies to establish the individual necessities and separate the contributions of the tree-based architecture and the anchor mechanism to achieve the desired results. I am wondering whether we can establish similar bounds by adding only the anchor in a flat router (i.e., the tree depth is equal to one). Empirically, a sweep over tree depth is missing.

  2. Although the title suggests that the paper's focus is on embedding models, I still believe that the evaluated MoE models are too simple, i.e., only one input stage, one MoE block, and no attention block, without evaluation on LLM tasks. Adding some version of these results would greatly benefit the broader audience.

Questions for authors

Please see the weaknesses.

3 comments
AuthorsOpenReview ↗

Separating Tree Architecture vs. Score Anchoring (Theory and Empirical Results)

We thank Reviewer xCio for highlighting the novelty and intuitiveness of our routing architecture and the nontriviality of our theoretical analysis. Below we address both weaknesses and manuscript presentation. We have uploaded a revised 10-page manuscript (all revisions highlighted in blue) to reflect these changes.

1. Separating Tree Architecture vs. Score Anchoring: Theory (D=1D=1 vs. E≥3E \ge 3) & Empirical Depth Sweep (Weakness 1)

Can we establish similar anti-collapse bounds by adding only the anchor in a flat router (D=1D=1)?

At D=1D=1 (E=2E=2), yes: a flat softmax router whose logits s0(x),s1(x)s_0(x), s_1(x) are centered by their population means sˉe=E[se(X)]\bar{s}_e = \mathbb{E}[s_e(X)] has right-expert probability

G1(x)=exp⁡(s1(x)−sˉ1)exp⁡(s0(x)−sˉ0)+exp⁡(s1(x)−sˉ1)=σ!((s1(x)−s0(x))−(sˉ1−sˉ0)),G_1(x) = \frac{\exp(s_1(x)-\bar{s}_1)}{\exp(s_0(x)-\bar{s}_0)+\exp(s_1(x)-\bar{s}_1)} = \sigma\\!\big((s_1(x)-s_0(x)) - (\bar{s}_1-\bar{s}_0)\big),

which coincides with a depth-11 BRANCH-MoE tree and satisfies min⁡E[G0],E[G1]≥12e\min\\{\mathbb{E}[G_0], \mathbb{E}[G_1]\\} \ge \frac{1}{2\mathrm{e}} under log-concave arrivals.

For E≥3E \ge 3, however, flat score anchoring cannot provide a scale-free anti-collapse bound. We prove this in new Proposition 4.3 (Section 4.2, verified numerically in Figure 3a):

  • Let X∼N(0,Idin)X \sim \mathcal{N}(0, I_{d_{\mathrm{in}}}) (log-concave, E[X]=0\mathbb{E}[X]=0), so every linear score fe(x)=we⊤xf_e(x) = w_e^\top x has exact population anchor νe⋆=E[fe(X)]=0\nu_e^\star = \mathbb{E}[f_e(X)] = 0. Setting w1=Ruw_1 = R u, w2=−Ruw_2 = -R u, and we=rvew_e = r v_e (0<r<R0 < r < R, ∣u∣2=∣ve∣2=1\\|u\\|_2 = \\|v_e\\|_2 = 1) for e∈3,…,Ee \in \\{3,\dots,E\\} keeps every expert exactly centered, yet ∑e′ewe′⊤x≥eR∣u⊤x∣\sum_{e'} \mathrm{e}^{w_{e'}^\top x} \ge \mathrm{e}^{R\lvert u^\top x\rvert}, forcing

    E[Ge(X)]≤2π er2/2R−r→R→∞0∀ e∈3,…,E.\mathbb{E}[G_e(X)] \le \sqrt{\frac{2}{\pi}}\,\frac{\mathrm{e}^{r^2/2}}{R - r} \xrightarrow{R \to \infty} 0 \qquad \forall\, e \in \\{3,\dots,E\\}.

    Moreover, when E≥2K+1E \ge 2K+1 with w1=⋯=wK=Ruw_1=\dots=w_K=Ru and wK+1=⋯=w2K=−Ruw_{K+1}=\dots=w_{2K}=-Ru, experts e>2Ke > 2K have zero top-KK execution probability (pe=0p_e = 0) under both flat softmax and independent sigmoids σ(we⊤x−νe⋆)\sigma(w_e^\top x - \nu_e^\star).

  • Why both hierarchy and anchoring are required: Flat EE-way competition is vulnerable to variance asymmetry across logits even when means are zero. BRANCH-MoE decomposes routing into binary splits pj=σ(zj)p_j = \sigma(z_j) where zj≥0  ⟹  σ(zj)≥1/2\\{z_j \ge 0\\} \implies \sigma(z_j) \ge 1/2 independently of ∣Wj∣2\\|W_j\\|_2, while arrival-weighted cascading centers each split on the conditional subpopulation reaching that node. In addition, flat score-centered routers are permutation-equivariant in expert indices and therefore give zero locality (L/D=0.817L/D = 0.817 at E=16E=16). Conversely, an unanchored tree has no lower bound even at D=1D=1: shifting root bias b0→−∞b_0 \to -\infty starves E/2E/2 experts simultaneously.

Empirical 2×22 \times 2 ablation and sweep over tree depth D∈1,2,3,4,5,6D \in \\{1,2,3,4,5,6\\}:

  • 2×22 \times 2 Ablation (Section 5.3, Figure 3b, Appendix Table 8): Across 5 seeds on UCI Optical Digits (post-SiLU features) and Log-Concave Hierarchical Regression (E=16,K=4E=16, K=4, capacity factor 1.251.25):
    • Unanchored Tree suffers severe subtree starvation (CV=0.970\mathrm{CV} = 0.970 / 1.0021.002; 32.432.4\\% / 33.033.0\\% dropped dispatches; 3.43.4 / 1.01.0 dead experts).
    • Flat Score-Centered removes dead experts at E=16E=16 but yields higher CV\mathrm{CV} (0.3660.366 / 0.1910.191) and zero locality (L/D=0.820L/D = 0.820 / 0.8180.818; N2(x)=2.94N_2(x) = 2.94 / 2.922.92 out of G=4G=4 groups vs. 2.912.91 random).
    • BRANCH-MoE uniquely achieves 00 dead experts, low CV\mathrm{CV} (0.2720.272 / 0.1640.164; 3.33.3\\% / 0.90.9\\% drops), competitive loss, and strong locality (L/D=0.727L/D = 0.727 / 0.7300.730; N2(x)=2.46N_2(x) = 2.46, −16.3-16.3\\% fewer contacted groups).
    • On Forest Covertype (Table 9), O(1)O(1) scalar anchoring also improves over O(din)O(d_{\mathrm{in}}) centroid EMA (CV\mathrm{CV} 0.0950.095 vs. 0.1260.126; drops 0.180.18\\% vs. 0.390.39\\%).
  • Sweep over tree depth D=log⁡2E∈1,…,6D = \log_2 E \in \\{1,\dots,6\\} (E∈2,4,8,16,32,64E \in \\{2,4,8,16,32,64\\}, K=min⁡(4,E/2)K = \min(4, E/2); Figure 3c, Table 10): At D=1D=1 (E=2,K=1E=2, K=1), BRANCH-MoE and flat score centering coincide (0.20200.2020 vs. 0.20240.2024 MSE). Defining group fanout Nr(x):=∑g=02r−11SK(x)∩Lg≠∅N_r(x) := \sum_{g=0}^{2^r-1}\mathbf{1}\\{\mathcal{S}_K(x)\cap\mathcal{L}_g \neq \emptyset\\} as the number of distinct prefix-aligned hardware groups (G=2rG = 2^r) contacted by token xx (so per-token communication volume is stokcrNr(x)s_{\mathrm{tok}}c_r N_r(x), with spillover fanout Nr(x)−1N_r(x)-1 beyond the primary subtree), BRANCH-MoE maintains 00 dead experts across D=2…6D=2\dots 6, matches Switch/Flat-Centered MSE, and strengthens locality monotonically from L/D=0.770L/D = 0.770 vs. 0.8330.833 at E=4E=4 (K=2K=2) to L/D=0.683L/D = 0.683 vs. 0.8490.849 (−19.6-19.6\\%) at E=64E=64 (K=4K=4), lowering group fanout N2(x)N_2(x) (G=4G=4) from 2.792.79 to 1.981.98 (−29.0-29.0\\%) and N3(x)N_3(x) (G=8G=8) from 3.383.38 to 2.482.48 (−26.6-26.6\\% group fanout, −37.8-37.8\\% spillover fanout).
AuthorsOpenReview ↗

Multilayer Self-Attention Language Model Evaluation & Title Alignment (Weakness 2), Presentation Improvements

2. Multilayer Self-Attention Language Model Evaluation & Title Alignment (Weakness 2)

  1. 2-Layer Causal Transformer LM on Shakespeare (Section 5.3, Figure 4a, Table 11): We trained a 2-layer causal Transformer LM (token + positional embeddings, multi-head causal self-attention, Pre-LN, and two stacked E=16E=16, top-44 SwiGLU MoE blocks) over 5 seeds on Complete Works of Shakespeare:
    • Predictive parity: BRANCH-MoE attains held-out validation perplexity 12.6512.65 (2.5377±0.02092.5377 \pm 0.0209 CE), matching Switch (12.6612.66), Flat Score-Centered (12.5712.57), and DeepSeek-V3 (12.7512.75), and outperforming Hash (13.4313.43).
    • Cross-layer stability & locality: Without score anchoring, Unanchored Tree compounds imbalance across depth (Layer 0 CV=0.825→\mathrm{CV} = 0.825 \to Layer 1 CV=1.176\mathrm{CV} = 1.176). BRANCH-MoE keeps both layers balanced without auxiliary loss (CV=0.273\mathrm{CV} = 0.273 and 0.3560.356) while lowering contacted groups N2(x)N_2(x) (G=4G=4) by 21%21\% in both Layer 0 (2.372.37 vs. 3.003.00) and Layer 1 (2.422.42 vs. 3.073.07).
  2. Title revision: We revised the title to "BRANCH-MoE: Balance-Aware Hierarchical Tree Routing for Mixture-of-Experts" so the title reflects the general routing contribution without overclaiming large-scale embedding deployment.

3. Presentation Improvements

We added Algorithm 1 in Section 3 summarizing the forward pass and EMA anchor update in 8 step-free lines, consolidated multi-line equation displays in Sections 3–4, and structured the new ablations and depth-scaling analyses into Section 5.3 with visual summaries in Figure 3.

AuthorsOpenReview ↗

A gentle reminder as the deadline is approaching

Thank you again for your constructive feedback, which has meaningfully strengthened our work.

As the discussion phase closes soon, we wanted to let you know that we have addressed all the points raised in your review with new experiments and analyses. If any of your concerns remain, please let us know so we can discuss them further.

If our response has resolved your questions, we would be grateful if you would consider updating your score to reflect these improvements. Thank you for your time and guidance!

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Comment to the Area Chair and All Reviewers

We thank the AC and the reviewers for their constructive feedback. We are encouraged that all reviewers noted the coherence of coupling hierarchical tree routing with arrival-weighted EMA score anchoring without auxiliary balancing losses, together with our theoretical analyses of anchor tracking, anti-collapse, expert SGD convergence, and prefix locality.

Across the three reviews, the main questions converged on four themes:

  1. Separating the contributions of the tree topology and score anchoring, both theoretically and empirically (xCio, sdU4).
  2. Scaling beyond a single E=16E=16 tabular MoE block to deeper trees (D=log⁡2ED = \log_2 E up to E=64E=64) and multilayer self-attention language models (xCio, sdU4, F8mM).
  3. Connecting tree-distance reductions to concrete cross-device communication volume and dispatch latency (sdU4, F8mM).
  4. Clarifying theory-to-practice links: how soft leaf mass qeq_e relates to sparse top-KK execution pep_e, why training removes initial locality on Criteo, how to choose node-map complexity, and improving presentation (xCio, sdU4, F8mM).

We have uploaded a revised 10-page manuscript (all revisions highlighted in blue) containing the following additions:

  • New Theory (Propositions 4.3 & 4.4, Section 4 & Appendix E):
    • Proposition 4.3 proves that while flat score centering coincides with BRANCH-MoE at D=1D=1 (E=2E=2), for every E≥3E \ge 3 flat score centering fails to prevent routing-mass collapse even on X∼N(0,Idin)X \sim \mathcal{N}(0, I_{d_{\mathrm{in}}}) at exact population anchors (driving under-scaled experts down at rate O(1/R)\mathcal{O}(1/R) and yielding zero top-KK execution and random tree distance), whereas unanchored trees suffer simultaneous E/2E/2-expert subtree starvation.
    • Proposition 4.4 bridges soft leaf mass qeq_e and sparse top-KK execution pep_e, proving pe≥qe−δe,tail≥(K+1)qe−1Kp_e \ge q_e - \delta_{e,\mathrm{tail}} \ge \frac{(K+1)q_e - 1}{K}, establishing pe≥e−Dp_e \ge \mathrm{e}^{-D} for all K≥1K \ge 1 in the sharp-margin tree limit, and proving that qe>0q_e > 0 can fail to execute (pe=0p_e = 0) only when me(D)(X)≤1K+1m_e^{(D)}(X) \le \frac{1}{K+1} almost surely.
  • New Experiments (Section 5.3, Figure 3, & Appendix G.5):
    1. 2×22 \times 2 Component Ablation ({Flat, Tree} ×\times {Unanchored, Score-Centered}, Table 8): Unanchored trees starve subtrees (CV=0.97\mathrm{CV}=0.97–1.001.00, >32%>32\% capacity drops); flat score-centered routers yield zero locality (L/D=0.818L/D=0.818–0.8200.820, contacting N2(x)=2.92N_2(x)=2.92–2.942.94 of G=4G=4 groups vs. 2.912.91 random); only BRANCH-MoE achieves zero dead experts, low CV\mathrm{CV} (0.1640.164–0.2720.272, 0.9%0.9\%–3.3%3.3\% drops), competitive loss, and L/D=0.727L/D=0.727–0.7300.730 (N2(x)=2.46N_2(x)=2.46, −16.3%-16.3\% fewer contacted groups). We also report Covertype K=2K=2 (0.25240.2524 best CE, −17.1%-17.1\% tree distance) and O(1)O(1) scalar vs. O(din)O(d_{\mathrm{in}}) centroid anchoring (Table 9).
    2. Tree-Depth Scaling (D∈{1,…,6}D \in \{1,\dots,6\}, E∈{2,…,64}E \in \{2,\dots,64\}, Table 10): Defining group fanout Nr(x):=∑g=02r−11{SK(x)∩Lg≠∅}N_r(x) := \sum_{g=0}^{2^r-1}\mathbf{1}\{\mathcal{S}_K(x)\cap\mathcal{L}_g \neq \emptyset\} as the number of distinct prefix-aligned hardware groups (G=2rG=2^r) contacted by token xx (and Nr(x)−1N_r(x)-1 as spillover fanout beyond the primary group), locality and communication savings grow monotonically with depth, reaching L/D=0.683L/D = 0.683 vs. 0.8490.849 random (−19.6%-19.6\%), N2(x)=1.98N_2(x) = 1.98 vs. 2.792.79 across G=4G=4 groups (−29.0%-29.0\%), and N3(x)=2.48N_3(x) = 2.48 vs. 3.383.38 across G=8G=8 groups at E=64E=64 (−26.6%-26.6\% lower group fanout, −37.8%-37.8\% lower spillover fanout).
    3. Multilayer Causal Transformer Language Model (Table 11, Figure 4a): On a 2-layer causal Transformer LM with multi-head self-attention and two stacked E=16,K=4E=16, K=4 SwiGLU MoE blocks trained on Shakespeare (5 seeds), BRANCH-MoE matches Switch and DeepSeek-V3 in held-out perplexity (12.6512.65 vs. 12.6612.66, 12.7512.75), prevents cross-layer imbalance compounding (Layer 0/1 CV\mathrm{CV} 0.27/0.360.27/0.36 vs. 0.83/1.180.83/1.18 in unanchored trees), and reduces contacted groups N2(x)N_2(x) by 21%21\% in both layers.
    4. Communication Volume & CPU Group-Dispatch Microbenchmark + Diagnostics: Evaluating the 5 trained E=64,D=6E=64, D=6 routers in a single-host CPU in-memory group-deduplicated gather/scatter microbenchmark (32,76832{,}768 float32 tokens, d=256,G=8,K=4d=256, G=8, K=4, median of 25 trials after warmup per seed; distinct from distributed multi-node GPU/TPU network collectives), BRANCH-MoE (N3=2.48N_3 = 2.48 vs. 3.383.38) lowers gathered/scattered payload volume from 113.5113.5,MB to 83.183.1,MB (−26.8%-26.8\%) and wall-clock gather/scatter latency from 77.577.5,ms to 59.559.5,ms (−23.2%-23.2\%). We also report qeq_e-vs-pep_e correlations (r=0.972r = 0.972 at E=16E=16) and Criteo's 25-seed single-expert saturation + depth-margin analysis.
  • Presentation & Title Revision (xCio, sdU4): We updated the title, added Algorithm 1 in Section 3, compacted multi-line equation displays, and expanded Section 5 using the 10-page limit.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.