# Condensation-Controlled Hierarchical Routing

- ID: 1040
- Canonical URL: https://synthcore.org/idea/1040/condensation-controlled-hierarchical-routing
- API JSON: https://synthcore.org/api/idea/1040.json
- API Markdown: https://synthcore.org/api/idea/1040.md
- Verification status: unverified
- Source: [arXiv:2607.16971](https://arxiv.org/abs/2607.16971)
- Category: dynamics
- Solves: scalability, sample-efficiency, stability
- ML areas: moe-routing, training-dynamics, optimizer
- Math tags: statistical-mechanics, dynamical-systems, probability, graph-theory
- Ratings: usefulness 6/10; difficulty 5/10; novelty 7/10

## Idea description

Replace purely instantaneous routing in a balanced hierarchical MoE or adaptive-computation tree with a sublinear visit-count reinforcement term. Small reinforcement produces broad exploration of experts, whereas reinforcement above the condensation threshold deliberately creates a persistent core of frequently used experts while retaining slow discovery of new experts.

## Mathematical statement

For a vertex or expert \(v\), let \(n_v(t)\) be its number of assignments up to routing step \(t\), let \(a\in(0,1)\) be the memory exponent, and let \(\beta\geq0\) be the reinforcement strength. The paper assigns weight \(w_v(t)=1+\beta n_v(t)^a\) and, from a node \(v\), selects a neighboring child \(u\) with probability proportional to \(w_u(t)\). For a neural router with child set \(C(v)\), use \(p(u\mid v,t)=\exp(s_u(x_t)/\tau)w_u(t)/\sum_{j\in C(v)}\exp(s_j(x_t)/\tau)w_j(t)\), where \(s_u\) is the learned routing logit and \(\tau\) is temperature. On a regular tree with branching factor \(b\), the paper reports a condensation boundary \(\beta_c(a,b)\propto b-1\): below the boundary the occupation is spread over a growing range, while above it the maximum occupation fraction \(M_T=\max_v n_v(T)/T\) remains O(1), the active range grows approximately logarithmically rather than as a power, and near the transition the occupation is bimodal and non-self-averaging. These signatures should be tested in the learned-logit router, while the proportionality constant must be calibrated empirically.

## Key formulas

- $$w_v(t)=1+\beta n_v(t)^a,\qquad 0<a<1,$$
- $$p(u\mid v,t)=\frac{w_u(t)}{\sum_{j\in C(v)}w_j(t)}\quad\text{(paper)},\qquad p_\theta(u\mid v,x_t,t)=\frac{e^{s_u(x_t)/\tau}w_u(t)}{\sum_{j\in C(v)}e^{s_j(x_t)/\tau}w_j(t)}\quad\text{(neural adaptation)},$$
- $$\beta_c(a,b)\approx C(a)(b-1),\qquad M_T=\max_v\frac{n_v(T)}{T}=\begin{cases}o(1),&\beta<\beta_c,\\O(1),&\beta>\beta_c,\end{cases}$$
- $$R(T)\sim T^\gamma\ \text{below the transition},\qquad R(T)\approx A\log T\ \text{above it},$$

## Implementation notes

1. Integration point: implement this mechanism in a balanced b-ary hierarchical MoE. At every internal router, compute ordinary logits \(s_u(x)\), maintain an integer or exponential-moving-average visit count \(n_u\) for every child, multiply each child probability by \(1+\beta n_u^a\), and use the resulting distribution for soft or hard routing. Keep counts separate for each router; optionally reset them at epoch boundaries to prevent a single global frequency statistic from dominating. Use straight-through Gumbel sampling if hard expert execution is required. 2. Pseudocode: for each input \(x\) at node \(v\), compute \(q=\operatorname{softmax}(s_\theta(x)/\tau)\), compute \(w_u=1+\beta(n_u+\epsilon)^a\), set \(p_u=q_uw_u/(\sum_jq_jw_j)\), sample or select child \(u\), execute that child, and update \(n_u\leftarrow n_u+1\). 3. Taken from the paper: the sublinear reinforcement law, the exploration-versus-condensation mechanism, and the predicted dependence on \(b-1\). Estimated empirically: the constant \(C(a)\), the effect of learned logits, and whether raw or EMA counts work better. 4. First cheap experiment: use CIFAR-10 with a two-level b-ary MLP-MoE, initially with frozen random logits and then with trainable routers. Compare \(\beta=0\), standard load balancing, and a beta sweep for \(b=2,3,4\) at fixed \(a=0.5\), using at least 20 seeds. Measure maximum occupation \(M_T\), active-expert count \(R(T)\), entropy, validation accuracy, and run-to-run variance. The quantitative prediction is a sharp crossover: below \(\beta_c\), \(M_T\) decreases with time and \(R(T)\) follows approximate power growth; above \(\beta_c\), \(M_T\) plateaus and \(R(T)\) is closer to logarithmic growth. Estimate \(\beta_c\) independently for each \(b\); successful transfer predicts \(\beta_c/(b-1)\) collapse within roughly 20%. Near the threshold, the distribution of \(M_T\) across seeds should become bimodal and non-self-averaging.

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.