Audited (legacy) 2026

Lower-Hull Pruning for Min-Plus Experts

Implementation & benchmark of arXiv:2608.25034 — On the Representational Geometry of Dynamic Programs

Usefulness7/10

Difficulty4/10

Novelty7/10

Memory Speedup Memory Stability Moe routing Graph nn Inference speedup Tropical geometry Convex analysis Polyhedral geometry

Source paper: On the Representational Geometry of Dynamic Programs arXiv:2608.25034 ⓘ · analyzed Aug 29, 2026

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

Idea description

Represent each alternative in a min-plus router or dynamic-programming layer by an affine score $c_i+\langle\alpha_i,x\rangle$. Remove every alternative whose lifted point $(\alpha_i,c_i)$ is not on the lower convex hull, because it can never be the unique minimum for any input and its deletion preserves the exact output function.

Formulas

$$f(x)=\min_i\bigl(c_i+\langle\alpha_i,x\rangle\bigr)$$

$$N\alpha_C=\sum_i k_i\alpha_i,\qquad Nc_C\geq\sum_i k_ic_i,\qquad N=\sum_i k_i$$

$$Nf_C(x)=\langle N\alpha_C,x\rangle+Nc_C\geq\sum_i k_i f_i(x)\geq N\min_j f_j(x)$$

$$\Gamma(f)=\operatorname{conv}\bigl(\{(\alpha_i,c_i)\}_i\bigr)+\mathbb{R}_{\geq0}e_{d+1}$$

Mathematical statement

The relevant function is $f(x)=\min_i(c_i+\langle\alpha_i,x\rangle)$, where $x\in\mathbb{R}^d$ is the input, $\alpha_i\in\mathbb{R}^d$ is candidate $i$'s exponent vector, and $c_i\in\mathbb{R}$ is its intercept. A deletion certificate for candidate $C$ consists of nonnegative integers $k_i$, with $N=\sum_i k_i>0$, satisfying $N\alpha_C=\sum_i k_i\alpha_i$ and $Nc_C\geq\sum_i k_ic_i$. For every $x$, the paper proves $Nf_C(x)=\langle N\alpha_C,x\rangle+Nc_C\geq\sum_i k_i f_i(x)\geq N\min_j f_j(x)$, so candidate $C$ never strictly beats all other candidates. Equivalently, using convex weights $\lambda_i=k_i/N$, solve $\sum_i\lambda_i=1$, $\lambda_i\geq0$, $\sum_i\lambda_i\alpha_i=\alpha_C$, and $\sum_i\lambda_i c_i\leq c_C$. Geometrically, the removable point is not a lower-hull vertex of $\Gamma(f)=\operatorname{conv}(\{(\alpha_i,c_i)\}_i)+\mathbb{R}_{\geq0}e_{d+1}$.

Implementation notes

Integrate this at the candidate-selection stage of a min-plus router, tropical mixture-of-experts layer, or explicit shortest-path neural module. Each candidate exposes an exponent vector alpha_i in R^d and intercept c_i; its score for a batch tensor x with shape [B,d] is score[b,i] = c_i + dot(alpha_i, x[b]), and the layer returns the elementwise minimum. Before training, or every K optimizer steps, run a pruning pass. For each candidate C, solve the linear feasibility problem: find lambda over the other candidates with lambda_i >= 0, sum(lambda)=1, sum(lambda_i alpha_i)=alpha_C, and sum(lambda_i c_i) <= c_C. If feasible within numerical tolerance, delete C and compact the parameter tensors. Pseudocode: scores = c[None,:] + einsum('bd,nd->bn', x, alpha); output = scores.min(dim=1); periodically, for C, solve the LP and set keep[C] = false when certified. The paper supplies the exact function-preservation guarantee; the LP or convex-hull routine is the numerical implementation. Retain points with a certificate margin below epsilon. First test a 32- or 64-candidate min-plus router on synthetic subset-sum or DAG shortest-path prediction, comparing an unpruned model with identical initialization. Measure candidate count, FLOPs, memory, exact output disagreement, and validation accuracy. Success means at least 2x fewer candidates and lower inference cost with zero measurable functional disagreement.

Verification

Audited (legacy)

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Not tested

Stage 2 · Practical benchmark result: Not run

Methodology: Toy-system gate first; the benchmark stage runs only after a pass. How verification works

Stage 1 — Mechanism check agent confidence 9/10

Built an LP-based lower-hull pruner for affine min-plus candidates, with sequential deletion so every removed candidate is certified against candidates that remain. The numerical math check found certificate alpha residual below 5e-16, no intercept violations, and zero output disagreement over 10,000 random inputs. In the synthetic 64-candidate benchmark, pruning retained 16 candidates, reduced estimated score FLOPs by 75%, and improved NumPy evaluation speed by 1.47x with zero measured disagreement.

Agent confidence: 9/10

Baseline: 64 candidates; 0.0799 ms per batch evaluation
Idea: 16 candidates; 0.0545 ms per batch evaluation; 1.466x speedup; 75% candidate/FLOP reduction; max output error 0.0

Limitations: Only a synthetic affine min-plus workload was tested; no learned router, dynamic programming task, validation accuracy, GPU benchmark, repeated pruning during optimization, or large-scale hull implementation was evaluated. The LP pruning pass itself was not included in the inference timing.

How to run: python3 experiment.py

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

Super-audit (legacy) Aug 30, 2026 latest Failed ✗

Agent confidence: 10/10

Implemented and ran a CUDA super-check with a 16-expert affine-routed MoE classifier, LP lower-hull pruning, three seeds, exact-output verification, trained full-vs-hull-vs-random controls, and wall-clock inference timing. Hull pruning retained 8/16 experts with zero measured output error and preserved accuracy (full 0.9659 ± 0.0030 vs hull 0.9652 ± 0.0020), while equal-size random pruning reached only 0.6131 ± 0.0630 accuracy. However, GPU inference speedup was only 1.033 ± 0.053x, below the required 1.1x threshold, so the promised practical speedup does not survive the harder check.

Accuracy: Full baseline 0.9659 ± 0.0030; hull idea 0.9652 ± 0.0020; random equal-size pruning 0.6131 ± 0.0630
Data: 6000 training and 3000 test samples per seed; 10-dimensional Gaussian inputs; 5-class teacher-routed MoE classification with 16 experts; trained student expert heads for 25 epochs
Experts: Full 16; lower-hull 8; random control 8
Gpu timing ms batch128: Full [0.1227, 0.1573, 0.1224]; hull [0.1210, 0.1440, 0.1235]
Math: All seeds retained 8/16 experts; maximum output error 0.0 over 50,000 random inputs per seed; maximum alpha residuals 4.88e-15, 2.33e-15, and 9.81e-14; maximum intercept violation 0.0
Runtime: Completed within the 40-minute super-check budget on CUDA
Seeds: 0, 1, 2
Speedup: 1.0326 ± 0.0534x; per-seed 1.0145x, 1.0928x, and 0.9906x

Limitations:

The router parameters were fixed rather than jointly learned, so this tests trained expert heads with a nontrivial MoE routing workload rather than a fully learned router. Periodic pruning checks evaluated the fixed routing setup; the LP pruning pass itself was not included in the inference timing.

How to run: python3 supercheck.py

Artifacts

Implementation overview ⬇ Download all as ZIP 6 files · code, reports and structured results

🐍 experiment.py 4.4 KB View Raw
📄 report.md 1.3 KB View
📄 report_super_2026-08-30T110300.md 3.1 KB View
📊 results.json 0.6 KB View Raw
📊 super_results.json 1.8 KB View Raw
🐍 supercheck.py 6.8 KB View Raw