# Maximum-cardinality token-expert routing

- ID: 1870
- Canonical URL: https://synthcore.org/idea/1870/maximum-cardinality-token-expert-routing
- API JSON: https://synthcore.org/api/idea/1870.json
- API Markdown: https://synthcore.org/api/idea/1870.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2608.06084](https://arxiv.org/abs/2608.06084)
- Category: architecture
- Solves: stability, speedup, scalability
- ML areas: moe-routing, transformer, inference-speedup, training-dynamics
- Math tags: combinatorics, graph-theory, statistical-mechanics, dynamical-systems
- Ratings: usefulness 7/10; difficulty 6/10; novelty 4/10

## Idea description

Construct a bipartite candidate graph between tokens and experts from the router’s top-k logits, then solve a capacity-constrained maximum-cardinality matching rather than dispatching each token independently. The mechanism targets the extreme tail of routing completion: it should reduce unmatched or repeatedly reassigned tokens and lower maximum dispatch delay and expert starvation, even when average routing quality changes little.

## Mathematical statement

Let tokens be vertices i in {1,...,B}, experts be vertices j in {1,...,E}, and G=(U,V,𝓔) be a candidate bipartite graph with edge (i,j) in 𝓔 when expert j is among token i’s top-k router choices. Let x_ij in {0,1} indicate assignment, c_j be expert j’s capacity, and r_i be the required number of expert assignments per token, usually r_i=1 or 2. Maximum-cardinality matching solves max_x sum_(i,j) in 𝓔 x_ij subject to sum_j x_ij <= r_i, sum_i x_ij <= c_j, and x_ij=0 for absent edges. If all demands are feasible, the maximum cardinality is sum_i r_i; otherwise the unmatched count U=sum_i r_i-sum_ij x_ij is minimized. Router scores can be used as a secondary cost without sacrificing cardinality. The transferable signature is that completion time is an extreme tail, so high-quantile or maximum dispatch delay should improve more strongly than mean load.

## Key formulas

- $$\max_{x_{ij}}\quad M=\sum_{i=1}^{B}\sum_{j=1}^{E}x_{ij},\qquad x_{ij}\in\{0,1\}.$$
- $$\sum_{j:(i,j)\in\mathcal{E}}x_{ij}\le r_i,\qquad \sum_{i:(i,j)\in\mathcal{E}}x_{ij}\le c_j,\qquad x_{ij}=0\ \text{if }(i,j)\notin\mathcal{E}.$$
- $$U=\sum_{i=1}^{B}r_i-M,\qquad T_{\mathrm{tail}}=\max_i d_i\ \text{or}\ Q_{0.99}(d_i),$$
- $$T_c=\min\{t:N_{\mathrm{unassigned}}(t)=0\}.$$

## Implementation notes

Integrate this after router logits are computed and before all-to-all token dispatch. For a batch of B tokens, compute router probabilities p_ij=softmax_j(z_ij), retain the top-k experts per token, and create edges only for those candidates. Set capacity c_j=ceil(gamma B r/E), where r is the number of experts required per token and gamma is the capacity factor. Solve the bipartite maximum-cardinality matching using a GPU-friendly min-cost-flow, auction, or batched augmenting-path approximation; use edge cost -log p_ij as a secondary objective after maximizing cardinality. Pseudocode is: logits -> top-k candidate edges -> capacities -> maximize cardinality -> among maximum-cardinality solutions minimize score cost -> dispatch matched token-expert pairs -> combine outputs using normalized original router probabilities. Unmatched tokens should use a deterministic fallback, such as the highest-probability expert with residual capacity or a dense shared expert. The paper contributes the matching-versus-greedy mechanism and extreme-tail interpretation; the solver, logits, and capacities are computed directly, while tail latency, unmatched fraction, and expert-load distributions are measured empirically. First experiment: train a small Switch-Transformer or Mixtral-style model on WikiText-103 or C4 with identical initialization and optimizer, comparing independent top-1 routing, sequential capacity-aware greedy routing, and maximum-cardinality routing at batch sizes producing 5–30% candidate conflicts. Measure validation loss, throughput, dropped-token fraction, maximum expert load, and 99th-percentile dispatch latency. The quantitative prediction is that matching will produce nearly zero unmatched assignments whenever the candidate graph admits a full matching, whereas greedy routing will retain a positive unmatched fraction; the largest improvement should occur at intermediate candidate density, and the 99th-percentile latency should decrease substantially more than the mean latency.

## Verification

- Status: mech_ok_no_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: inconclusive
- Verdict: Built an exact capacity-constrained maximum-cardinality matcher over top-k token-expert candidate graphs and compared it with sequential greedy routing. All three toy predictions matched exactly: full candidate graphs had zero unmatched tokens when total capacity was sufficient, singleton collisions matched the analytical lower bound, and matching removed the one avoidable greedy miss in the adversarial sweep. In randomized routing at B=96,E=8,gamma=1, matching reduced mean unmatched tokens from 4.81 to 0.02 for k=2, 2.92 to 0 for k=3, and 1.83 to 0 for k=4, while reducing the proxy p99 delay modestly; the cost was 9.5–23.5x CPU runtime in the timing checks.

### Mechanism check

- Verdict: Built an exact capacity-constrained maximum-cardinality matcher over top-k token-expert candidate graphs and compared it with sequential greedy routing. All three toy predictions matched exactly: full candidate graphs had zero unmatched tokens when total capacity was sufficient, singleton collisions matched the analytical lower bound, and matching removed the one avoidable greedy miss in the adversarial sweep. In randomized routing at B=96,E=8,gamma=1, matching reduced mean unmatched tokens from 4.81 to 0.02 for k=2, 2.92 to 0 for k=3, and 1.83 to 0 for k=4, while reducing the proxy p99 delay modestly; the cost was 9.5–23.5x CPU runtime in the timing checks.
- Confidence: 9/10
- Limitations: No neural language-model training, GPU implementation, all-to-all dispatch benchmark, score-aware secondary optimization, r=2 routing, or true wall-clock distributed dispatch latency was tested. The matcher uses a simple CPU Kuhn augmenting-path solver with cloned capacity slots, so production scalability and GPU efficiency remain unverified; p99 delay is a load-based proxy rather than measured completion latency.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.6243
- Paired wins: 3/8
- Benchmark verdict: no significant win

## Artifacts

- [bench_report.json](https://synthcore.org/code/714/bench_report.json)
- [custom_moe_track.py](https://synthcore.org/code/714/custom_moe_track.py)
- [experiment.py](https://synthcore.org/code/714/experiment.py)
- [report.md](https://synthcore.org/code/714/report.md)
- [report_bench_2026-09-01T014459.md](https://synthcore.org/code/714/report_bench_2026-09-01T014459.md)
- [results.json](https://synthcore.org/code/714/results.json)
- [run_bench.py](https://synthcore.org/code/714/run_bench.py)
- [verify.py](https://synthcore.org/code/714/verify.py)
- [Download all files as ZIP](https://synthcore.org/download/714)

## Disclaimer

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