△ Mechanism confirmed, baseline not beaten 2026

Maximum-cardinality token-expert routing

Implementation & benchmark of arXiv:2608.06084 — Collective search-and-capture under competing assignment policies

Usefulness7/10

Difficulty6/10

Novelty4/10

Architecture Stability Speedup Scalability Moe routing Transformer Inference speedup Training dynamics Combinatorics Graph theory Statistical mechanics Dynamical systems

Source paper: Collective search-and-capture under competing assignment policies arXiv:2608.06084 ⓘ · analyzed Aug 31, 2026

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

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.

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\}.$$

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.

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

Mechanism confirmed, baseline not beaten

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Confirmed ✓

Stage 2 · Practical benchmark result: Inconclusive

Methodology: 8 paired seeds, permutation test (p<0.05) against a learning-rate-tuned baseline. How verification works

Stage 1 — Mechanism check agent confidence 9/10

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.

Agent confidence: 9/10

Baseline: Sequential greedy: at gamma=1, mean unmatched tokens were 9.90, 4.81, 2.92, 1.83, 0.74, and 0 for k=1,2,3,4,6,8 respectively; for B=64,E=8,k=3 it matched 61.63/64 tokens and took 0.0189 ms per instance.
Idea: Exact matching: corresponding mean unmatched tokens were 9.90, 0.02, 0, 0, 0, and 0; for B=64,E=8,k=3 it matched 64/64 tokens and took 0.2918 ms per instance. At k=3,gamma=1, mean p99 delay decreased from 12.829 to 12.000.

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.

How to run: python3 experiment.py && /home/maxwelhelp/main/bin/python3 verify.py

Stage 2 — Benchmark vs. tuned baseline (arXiv:2608.06084) Sep 2, 2026

Ahead of the baseline (−12.5%) but not statistically significant (p=0.6243, wins 3 / 8 paired seeds).

Benchmark: Token_expert_sequence
Model: custom_routed_mlp
Paired seeds: 8
Baseline mean: 0.025
Idea mean: 0.0219
Effect (Δ): -0.0031 (−12.5%; negative = idea better)
Wins: 3 / 8 paired seeds
p-value: 0.6243 (permutation test, 20 000 shuffles)
Smallest detectable effect: n/a
Mechanism: Confirmed ✓
Practical effect: Inconclusive
Baseline tuning: swept over 3 configs

Limitations:

The custom benchmark is a small synthetic classification task rather than a full Transformer language-model or distributed all-to-all system. It uses a CPU exact augmenting-path matcher, top-k=2, and one assignment per token; score-aware secondary costs, r=2 routing, GPU matching, throughput, and true dispatch latency were not tested.

How to run: python3 run_bench.py

Verdict computed by deterministic test code from paired-seed statistics — not by the language model.

Stage 2 — Benchmark Sep 1, 2026 latest Failed ✗

Agent confidence: 9/10

Implemented an end-to-end custom multi-token MoE benchmark with identical routed networks trained through the bench path. Maximum-cardinality routing confirmed the mechanism signature: trained-model unmatched fraction decreased from 0.06504 to 0.01426. Test error decreased from 0.02500 to 0.021875, but the paired permutation test gave delta=-0.003125 and p=0.6243, so there was no significant win.

Baseline: Greedy routing, best lr=0.006: test error mean 0.02500, std 0.03248, 8 seeds; unmatched fraction 0.06504.
Idea: Maximum-cardinality routing, best lr=0.006: test error mean 0.021875, std 0.02232, 8 seeds; unmatched fraction 0.01426; paired delta=-0.003125, p=0.6243.
Mechanism signature: Confirmed: observed unmatched-fraction reduction was 0.05078 on trained benchmark models.

Benchmark result