# Boundary-Compressed Approximate Pruning

- ID: 77
- Canonical URL: https://synthcore.org/idea/77/boundary-compressed-approximate-pruning
- API JSON: https://synthcore.org/api/idea/77.json
- API Markdown: https://synthcore.org/api/idea/77.md
- Verification status: beats_baseline
- Source: [arXiv:2608.22815](https://arxiv.org/abs/2608.22815)
- Category: memory
- Solves: memory, scalability, generalization
- ML areas: pruning, transformer, attention, mlp, memory
- Math tags: graph-theory, combinatorics, quadratic-forms, optimization, approximation-theory
- Ratings: usefulness 6/10; difficulty 6/10; novelty 7/10

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

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

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

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

- Status: beats_baseline
- Mechanism evidence: yes
- Mechanism confirmed: no
- Practical verdict: helps
- Verdict: 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.

### Mechanism check

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

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

- [bench_report.json](https://synthcore.org/code/702/bench_report.json)
- [boundary_bench.py](https://synthcore.org/code/702/boundary_bench.py)
- [boundary_pruning.py](https://synthcore.org/code/702/boundary_pruning.py)
- [report.md](https://synthcore.org/code/702/report.md)
- [report_bench_2026-08-31T223642.md](https://synthcore.org/code/702/report_bench_2026-08-31T223642.md)
- [results.json](https://synthcore.org/code/702/results.json)
- [Download all files as ZIP](https://synthcore.org/download/702)

## Disclaimer

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