✓✓ Beats tuned baseline 2026

Boundary-Compressed Approximate Pruning

Implementation & benchmark of arXiv:2608.22815 — Convexification of mixed-integer quadratic optimization via decision diagrams

Usefulness6/10

Difficulty6/10

Novelty7/10

Memory Memory Scalability Generalization Pruning Transformer Attention Mlp Memory Graph theory Combinatorics Quadratic forms Optimization

Source paper: Convexification of mixed-integer quadratic optimization via decision diagrams arXiv:2608.22815 ⓘ · analyzed Aug 29, 2026

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

Idea description

Use an approximate decision diagram to select a structured subset of neurons, channels, attention heads, or attention edges when their quadratic interactions are sparse or inverse-sparse. Merge states that agree on a local interaction boundary and accept a tunable epsilon loss in the pruning objective, obtaining a representation whose size is linear in model width for fixed accuracy tolerance.

Formulas

$$(n+1)\cdot 2^{\delta^{\prime}\eta_{\epsilon}^{\gamma^{\prime}}},\qquad \eta_{\epsilon}=\mathcal{O}\left(\log(1/\epsilon)\right).$$

$$\omega_{G}(\eta)\leq\delta^{\prime}\eta^{\gamma^{\prime}},\qquad G=\operatorname{supp}(\bm{Q})\ \text{or}\ G=\operatorname{supp}(\bm{Q}^{-1}).$$

$$\widehat{J}(z,x)=d^{\top}x+c^{\top}z+\|F^{\top}x\|_{2}^{2},\qquad x_i=0\ \text{whenever }z_i=0,$$

$$\left|J_{\mathrm{DD},\epsilon}^{\star}-J_{\mathrm{exact}}^{\star}\right|\leq\epsilon,\qquad N_{\mathrm{states}}\leq(n+1)2^{\delta'\eta_\epsilon^{\gamma'}}.$$

Mathematical statement

Theorem 4 assumes that G = supp(Q) or G = supp(Q^{-1}) has polynomial volume growth with parameters gamma and delta, and that its eta-boundaries satisfy omega_G(eta) <= delta' eta^{gamma'} for all eta >= 1. Here Q is the quadratic interaction matrix, G is its support graph or precision-graph support, omega_G(eta) is the maximum boundary size under the selected variable ordering, and gamma', delta' describe boundary growth. The theorem concludes that for every epsilon > 0 there is an epsilon-exact decision diagram with at most (n+1) 2^{delta' eta_epsilon^{gamma'}} nodes, where eta_epsilon = O(log(1/epsilon)); epsilon-exact means that the resulting optimum differs from the exact optimum by at most epsilon. The adapted pruning objective is J(z,x) = d^T x + c^T z + ||F^T x||_2^2, where z_i indicates retaining component i, x_i is its rescaling coefficient, d_i is estimated importance, c_i is a parameter or latency cost, and Q = FF^T encodes pairwise redundancy or interaction. Boundary truncation discards interactions farther than eta graph hops from the decided/undecided cut.

Implementation notes

Apply this as a post-training structured-pruning or architecture-search module. Candidate components can be transformer heads, MLP channels, convolution channels, or fixed local attention edges; z_i = 1 means retained and x_i is a rescaling coefficient. On a calibration set, estimate d_i from first-order Taylor loss change and estimate pairwise interaction Q_ij from second-order finite differences, activation covariance, or a low-rank regression of output error. Sparsify Q by retaining its largest interactions, then construct its support graph G; if Q is dense, also test a regularized inverse precision matrix Q^{-1}. Choose an ordering using minimum-degree or reverse-Cuthill--McKee heuristics. At step ell, compute the eta-boundary consisting of decided components within graph distance eta of any undecided component. Replace each partial mask with a key containing its boundary mask and tolerance-rounded truncated residual quadratic coefficients. Initialize states with an empty boundary and zero cost; for each component, branch on z_i = 0 and z_i = 1, optimize x_i subject to 0 <= x_i <= U_i z_i, update the quadratic residual, truncate it outside eta hops, merge equal keys, and retain the cheapest state per key. Backtrack the final mask, physically prune the network, and fine-tune briefly. The theorem supplies the state-growth and epsilon dependence; Q estimation, truncation tolerance, and eta selection are empirical. First test on ViT-Tiny or a 6-layer transformer, pruning 50% of heads or MLP channels on ImageNet-100 or WikiText-2, against magnitude and Hessian-diagonal pruning at equal retained parameters. Record state count, calibration time, final accuracy or perplexity, and fine-tuning recovery. Success is near-linear state growth with lower proxy loss than magnitude pruning at the same memory footprint.

Verification

Beats tuned baseline

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Not reproduced ✗

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

How to read this: The implementation beat the baseline, but the claimed mechanism did not reproduce at benchmark scale. The gain may come from another effect; treat the cause as unresolved.

Stage 1 — Mechanism check agent confidence 8/10

Built a readable boundary-compressed decision-diagram prototype for cardinality-constrained quadratic pruning, with exact subset enumeration, local-boundary truncation, backtracking, and fixed-seed sweeps. The mechanism manifested: at eta=3 the gap was 0.0315 versus 0.9886 for magnitude pruning, eta=4 reached the exact objective on the main instance, and fixed eta=3 state count scaled exactly as 4n-4 (R²=1.0). Interaction sensitivity also appeared: the gap was 0 at rho=0 and increased to 0.0366 at rho=0.9, with correlation 0.86; this supports locality-dependent approximation, though it is not a full neural-network pruning validation.

Agent confidence: 8/10

Baseline: Magnitude selection: objective 3.1511, gap 0.9886 above exact optimum 2.1625.
Idea: Boundary DP, n=20 and k=10: eta=3 objective gap 0.0315 with 76 peak states; eta=4 gap 0.0 with 144 peak states. At eta=3, peak states were 36, 52, 68, 84, 100, 116, 156, and 196 for widths 10, 14, 18, 22, 26, 30, 40, and 50 respectively, exactly matching 4n-4.

Limitations: This is a toy quadratic subset-selection experiment, not a trained neural network or physical structured-pruning benchmark. It uses binary z decisions with fixed cardinality and does not implement continuous rescaling x, learned interaction estimation, inverse-precision graphs, epsilon-rounded residual keys, fine-tuning, wall-clock comparisons, or the theorem's formal epsilon-exact guarantee. The observed eta transition was tested empirically rather than fit to a log(1/epsilon) law.

How to run: python3 boundary_pruning.py

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

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

Benchmark: Sequence modeling
Model: transformer_tiny
Paired seeds: 8
Baseline mean: 0
Idea mean: 0
Effect (Δ): -0.2312 (n/a; negative = idea better)
Wins: 8 / 8 paired seeds
p-value: 0.0081 (permutation test, 20 000 shuffles)
Smallest detectable effect: n/a
Mechanism: Not confirmed ✗
Practical effect: Helps
Baseline tuning: swept over 0 configs

Limitations:

Only the registered sequence track was tested. The implementation masks input tokens rather than physically pruning transformer heads or MLP channels, and does not implement continuous rescaling, inverse-precision graphs, epsilon-rounded residual keys, fine-tuning, or wall-clock/memory comparisons. The benchmark used 1200 training and 400 test samples with 10 epochs; the mechanism signature failed confirmation.

How to run: python3 boundary_bench.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 boundary-compressed approximate pruning as a structured 50%-token selection intervention for the registered multi-token sequence forecasting track, using matched transformer_tiny systems and the canonical train_model path. Across 8 paired seeds it significantly improved test MSE over the tuned magnitude baseline (delta_mean=-0.2312, permutation p=0.0081). The independently measured mechanism signature was not confirmed, so the gain is empirically real under the bench but should not be attributed confidently to the proposed theorem mechanism.

Baseline: Tuned magnitude baseline, best lr=0.0015, 8-seed mean test MSE=0.8053048.
Idea: Boundary-compressed DP, eta=2, lr=0.0015, 8-seed mean test MSE=0.5740982; 8/8 wins; retained fraction=0.5; peak states=64.

Benchmark result