# Active-Set CG Router

- ID: 1263
- Canonical URL: https://synthcore.org/idea/1263/active-set-cg-router
- API JSON: https://synthcore.org/api/idea/1263.json
- API Markdown: https://synthcore.org/api/idea/1263.md
- Verification status: beats_baseline
- Source: [arXiv:2607.22121](https://arxiv.org/abs/2607.22121)
- Category: optimization
- Solves: speedup, stability, scalability
- ML areas: moe-routing, optimizer, inference-speedup
- Math tags: optimization, linear-algebra, numerical-analysis, combinatorics
- Ratings: usefulness 7/10; difficulty 5/10; novelty 7/10

## Idea description

Train a mixture-of-experts router by solving its regularized nonnegative simplex least-squares subproblem with a matrix-free active-set conjugate-gradient method instead of projected gradient or Adam. The router coefficients remain exactly nonnegative and sum to one, while CG rapidly solves each free-set quadratic and the active-set pivots identify sparse expert assignments.

## Mathematical statement

The paper solves the strictly convex quadratic program $\min_{x\ge 0} f(x)=\tfrac12 x^{\top}Ax-b^{\top}x$ with $A\succ0$, and its equality-augmented form $\min_x \tfrac12 x^{\top}Ax-b^{\top}x$ subject to $x\ge0$ and $Bx=c$. For a router, $x\in\mathbb{R}^{E}$ is the vector of expert weights for one routing group, $E$ is the number of experts, $A=Z^{\top}Z+\lambda I$ is the regularized Gram matrix of router features $Z$, $b=Z^{\top}Y$, and $\lambda>0$ makes $A$ strictly positive definite. The simplex constraint is $B=\mathbf{1}^{\top}$ and $c=1$. The KKT conditions are $x\ge0$, $Bx=c$, reduced gradient $g=Ax-b+B^{\top}\nu\ge0$ on bound coordinates, and $x_i g_i=0$; $\nu$ is the equality multiplier. The active-set loop solves the equality-constrained system on the current free set $F$, drops a free coordinate when its computed value becomes negative, and re-admits a bound coordinate when its reduced gradient is negative. These toggles are principal pivots of the linear complementarity problem associated with $(A,-b)$. Because $A$ is SPD and hence a $P$-matrix, pivots are well-defined; a least-index Bland fallback avoids cycling under degeneracy and gives finite outer termination for the exact method. The inner CG solve has the paper's $O(\sqrt{\kappa(A)})$ convergence behavior, compared with the $O(\kappa(A))$ behavior of the projected-gradient reference. If $A=M^{\top}M$, products are computed as $Av=M^{\top}(Mv)$ without materializing $A$.

## Key formulas

- $$\min_{x\in\mathbb{R}^{n}} f(x)=\tfrac{1}{2}x^{\top}Ax-b^{\top}x\quad\text{subject to}\quad x\geq0,\qquad A\succ0.$$
- $$\min_{x}\;\tfrac{1}{2}x^{\top}Ax-b^{\top}x\quad\text{subject to}\quad x\geq0,\qquad Bx=c.$$
- $$A=M^{\top}M,\qquad b=M^{\top}d,\qquad Av=M^{\top}(Mv),$$
- $$\text{CG rate }O(\sqrt{\kappa(A)})\quad\text{versus projected-gradient rate }O(\kappa(A)),\qquad \kappa(A)=\frac{\lambda_{\max}(A)}{\lambda_{\min}(A)}.$$

## Implementation notes

1. Integration point: replace the usual softmax router-training update for a small router calibration or alternating-routing step. Given router features $Z\in\mathbb{R}^{N\times E}$ and desired routing targets $Y\in\mathbb{R}^{N\times E}$, solve for each routing group or minibatch the nonnegative simplex-constrained quadratic with $A=Z^{\top}Z+\lambda I$, $b=Z^{\top}Y$, $B=\mathbf{1}^{\top}$, and $c=1$. This can be used for a router weight matrix column-by-column, or for per-token expert mixtures when $E$ is small. 2. Pseudocode: initialize $F=\{1,\ldots,E\}$ and $x=\mathbf{1}/E$; repeat: solve $A_{FF}x_F+B_F^{\top}\nu=b_F$ and $B_Fx_F=c$ with matrix-free CG or a small direct solve; set $x_i=0$ for $i\notin F$; if any $x_i< -\tau$, remove the most-negative free index from $F$ and restart CG; compute $g=Ax-b+B^{\top}\nu$; among bound indices with $g_i< -\tau$, add the most-negative reduced-gradient index to $F$ and restart; otherwise terminate. Apply $x\leftarrow\max(x,0)$ only as numerical cleanup, not as the main update. Use least-index tie-breaking when multiple pivots are near zero. 3. Compute $Av$ by two matvecs $Zv$ and $Z^{\top}(Zv)$; estimate $\lambda_{\min}$ and $\lambda_{\max}$ with 5--10 Lanczos or power iterations to select a CG tolerance and monitor $\kappa(A)$. Stop CG when the residual norm is below $\eta$ times the smallest current primal or dual decision margin, for example $\eta=0.1$, so an inexact solve is unlikely to change a sign decision. The finite-pivot guarantee and $O(\sqrt{\kappa})$ rate come from the paper; $\tau$, ridge $\lambda$, warm starts, and the maximum pivot count are empirical choices. 4. First experiment: use a Switch-Transformer-style router with $E=16$ experts on a small language model or CIFAR-100 MLP, freeze the experts, and fit router targets generated from loss-based expert scores. Compare active-set CG against projected gradient, softmax gradient descent, and a dense QP solver at equal router FLOPs. Measure router objective, constraint violations, active expert count, outer pivots, CG matvecs, load imbalance, and downstream validation loss. Success is at least 2x fewer router-update matvecs at equal objective value, exact nonnegativity and simplex feasibility, and no increase in validation perplexity or classification error; a secondary success signal is sparse routing with lower inference cost.

## Verification

- Status: beats_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: helps
- Verdict: Built a matrix-free active-set simplex QP router solver using CG on Z_F and Z_F^T products, plus a projected-gradient baseline. Positive inactive KKT margins caused 13 active-set pivots and produced exactly 3 active experts with simplex error <=2.2e-16, nonnegativity, KKT residual <=1.7e-11, and objective gap <=1.2e-13. Conditioning sweeps showed CG work increasing 2 to 55 versus projected-gradient 2 to 3239 on the dense case; in the nondegenerate sparse case, active-set CG used 366 matvecs versus 1437 projected-gradient steps at condition number about 9990, although pivot overhead makes it slower at low condition numbers.

### Mechanism check

- Verdict: Built a matrix-free active-set simplex QP router solver using CG on Z_F and Z_F^T products, plus a projected-gradient baseline. Positive inactive KKT margins caused 13 active-set pivots and produced exactly 3 active experts with simplex error <=2.2e-16, nonnegativity, KKT residual <=1.7e-11, and objective gap <=1.2e-13. Conditioning sweeps showed CG work increasing 2 to 55 versus projected-gradient 2 to 3239 on the dense case; in the nondegenerate sparse case, active-set CG used 366 matvecs versus 1437 projected-gradient steps at condition number about 9990, although pivot overhead makes it slower at low condition numbers.
- Confidence: 8/10
- Limitations: Only a small synthetic quadratic router calibration was tested; no neural network, MoE downstream accuracy, GPU implementation, batching, warm starts, preconditioning, FLOP-normalized production router, or comparison with Adam/softmax training was evaluated. The asymptotic CG rate was probed with a small diagonal SPD sweep, not established statistically.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.0081
- Paired wins: 8/8
- Benchmark verdict: idea better (significant)

## Artifacts

- [active_set_router.py](https://synthcore.org/code/505/active_set_router.py)
- [bench_active_set_router.py](https://synthcore.org/code/505/bench_active_set_router.py)
- [bench_report.json](https://synthcore.org/code/505/bench_report.json)
- [mechanism_results.json](https://synthcore.org/code/505/mechanism_results.json)
- [report.md](https://synthcore.org/code/505/report.md)
- [report_bench_2026-08-31T162931.md](https://synthcore.org/code/505/report_bench_2026-08-31T162931.md)
- [results.json](https://synthcore.org/code/505/results.json)
- [run_experiment.py](https://synthcore.org/code/505/run_experiment.py)
- [verify_mechanism.py](https://synthcore.org/code/505/verify_mechanism.py)
- [Download all files as ZIP](https://synthcore.org/download/505)

## Disclaimer

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