✓✓ Beats tuned baseline 2026

Active-Set CG Router

Implementation & benchmark of arXiv:2607.22121 — Non-Negative Conjugate Gradients

Usefulness7/10

Difficulty5/10

Novelty7/10

Optimization Speedup Stability Scalability Moe routing Optimizer Inference speedup Optimization Linear algebra Numerical analysis Combinatorics

Source paper: Non-Negative Conjugate Gradients arXiv:2607.22121 ⓘ · analyzed Aug 30, 2026

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

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.

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

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

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

Beats tuned baseline

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Confirmed ✓

Stage 2 · Practical benchmark result: Significant win ✓

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

Stage 1 — Mechanism check agent confidence 8/10

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.

Agent confidence: 8/10

Baseline: Projected gradient used 3239 steps at kappa about 9990 in the dense sweep, and 1437 steps at kappa about 9990 in the sparse sweep.
Idea: Active-set CG used 55 matvecs at kappa about 9990 in the dense sweep and 366 matvecs with 13 pivots at kappa about 9990 in the sparse sweep; support was 3, simplex error was <=2.2e-16, and KKT residual was <=1.7e-11. Isolated SPD CG required 1, 16, 19, 23, and 27 iterations for kappa 1, 10, 100, 1000, and 10000.

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.

How to run: python3 verify_mechanism.py && /home/maxwelhelp/main/bin/python3 run_experiment.py

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

Beats the tuned baseline by 9.7% (p=0.0081, wins 8 / 8 paired seeds; metric: lower is better).

Benchmark: Tabular regression (Friedman)
Model: mlp_tiny
Paired seeds: 8
Baseline mean: 7.8484
Idea mean: 7.0839
Effect (Δ): -0.7645 (−9.7%; negative = idea better)
Wins: 8 / 8 paired seeds
p-value: 0.0081 (permutation test, 20 000 shuffles)
Smallest detectable effect: ±5.3%
Mechanism: Confirmed ✓
Practical effect: Helps
Baseline tuning: swept over 6 configs

Limitations:

Only the tabular Friedman#1 track and mlp_tiny were tested. No vision/sequence/dynamics track, real MoE experts, GPU-vs-CPU speed/FLOP accounting, matrix-free CG implementation in the benchmark loop, Adam/softmax router alternatives beyond the implemented Adam baseline, or downstream inference-cost measurement was tested.

How to run: python3 bench_active_set_router.py

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

Stage 2 — Benchmark Aug 31, 2026 latest Worked ✓

Agent confidence: 8/10

Implemented Active-Set CG Router as an end-to-end optimizer intervention on the structurally matched tabular MLP track. Against the tuned Adam baseline, it reduced test MSE from 7.8484 to 7.0839, with paired delta -0.7645, 8/8 wins, and permutation p=0.0081. The router coefficients were feasible to numerical precision and sparse, but this is only a small tabular benchmark and does not establish MoE downstream gains or production routing speedups.

Baseline: Adam, 8-seed full test MSE 7.8483812213; sweep over lr={0.001,0.003,0.01} and weight_decay={0,0.0001}.
Idea: Active-set simplex router, 8-seed full test MSE 7.0839007497; paired delta -0.7644804716; 8/8 wins; permutation p=0.0081; mean simplex error 8.33e-17; mean support 2.875/16; mean pivots 13.625.

Benchmark result