# Lower-Hull Pruning for Min-Plus Experts

- ID: 151
- Canonical URL: https://synthcore.org/idea/151/lower-hull-pruning-for-min-plus-experts
- API JSON: https://synthcore.org/api/idea/151.json
- API Markdown: https://synthcore.org/api/idea/151.md
- Verification status: audited
- Source: [arXiv:2608.25034](https://arxiv.org/abs/2608.25034)
- Category: memory
- Solves: speedup, memory, stability
- ML areas: moe-routing, graph-nn, inference-speedup
- Math tags: tropical-geometry, convex-analysis, polyhedral-geometry
- Ratings: usefulness 7/10; difficulty 4/10; novelty 7/10

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

## 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}\).

## Key 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}$$

## 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

- Status: audited
- Mechanism evidence: yes
- Mechanism confirmed: no
- Verdict: 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.

### Mechanism check

- Verdict: 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.
- Confidence: 9/10
- 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.

## Artifacts

- [experiment.py](https://synthcore.org/code/68/experiment.py)
- [report.md](https://synthcore.org/code/68/report.md)
- [report_super_2026-08-30T110300.md](https://synthcore.org/code/68/report_super_2026-08-30T110300.md)
- [results.json](https://synthcore.org/code/68/results.json)
- [super_results.json](https://synthcore.org/code/68/super_results.json)
- [supercheck.py](https://synthcore.org/code/68/supercheck.py)
- [Download all files as ZIP](https://synthcore.org/download/68)

## Disclaimer

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