# Low-discrepancy progressive pruning and quantization

- ID: 1716
- Canonical URL: https://synthcore.org/idea/1716/low-discrepancy-progressive-pruning-and-quantization
- API JSON: https://synthcore.org/api/idea/1716.json
- API Markdown: https://synthcore.org/api/idea/1716.md
- Verification status: unverified
- Source: [arXiv:2608.02559](https://arxiv.org/abs/2608.02559)
- Category: memory
- Solves: memory, stability, generalization
- ML areas: pruning, quantization, transformer, memory
- Math tags: combinatorics, number-theory, approximation-theory
- Ratings: usefulness 6/10; difficulty 4/10; novelty 6/10

## Idea description

Use the paper's monotone allocation viewpoint to decide which parameters receive progressively more pruning, bit reduction, or update opportunities. A van der Corput order prevents a fixed early prefix of structured groups from being systematically over-pruned, while the logarithmic comb bound quantifies worst cumulative imbalance across nested groups.

## Mathematical statement

Represent progressive pruning or quantization as a sequence x_t selecting one of D equally entitled groups at event t. For any hierarchical group S, A_S(n)=sum_{t=1}^n 1{x_t in S}; proportional allocation requires A_S(n) to track n|S|/D. The discrepancy E_S(n)=A_S(n)-n|S|/D measures deviation from ideal fractional allocation. The van der Corput order uses v_2(m)=sum_j b_j2^{-j-1}, where m=sum_j b_j2^j, and x_m=floor(Dv_2(m)). For the full binary comb, max_{S,n}|E_S(n)| is at most log(D)/(3 log 2)+1. A midpoint argument gives interval discrepancy at most the grid discrepancy plus 1/2. This gives a deterministic bound on how unevenly irreversible pruning or bit-allocation events can accumulate across nested parameter groups.

## Key formulas

- $$x_m=\left\lfloor D\sum_{j\ge 0}b_j2^{-j-1}\right\rfloor,\qquad m=\sum_{j\ge 0}b_j2^j,$$
- $$A_S(n)=\sum_{t=1}^{n}\mathbf 1\{x_t\in S\},\qquad E_S(n)=A_S(n)-\frac{n|S|}{D},$$
- $$\max_{S\in\mathcal C,n}|E_S(n)|\le \frac{\log D}{3\log 2}+1,$$
- $$\Delta_{\mathrm{all\ intervals}}\le \Delta_{\mathrm{grid}}+\frac12.$$

## Implementation notes

Apply the construction to structured pruning or mixed-precision allocation in a model with D groups, such as attention heads, transformer blocks, channels, or contiguous weight tiles. Rank groups with a learned importance score, but do not remove all low-score groups simultaneously. Instead, organize groups as leaves of a binary comb, or partition them into equal-entitlement bins, and use the van der Corput sequence to determine which bin receives the next pruning event or one-bit reduction. At event m, compute c=floor(D*v2(m)); among eligible groups in bin c, prune the lowest-importance channel or reduce its precision by one level. Optionally reject a proposed event if any post-update nested discrepancy exceeds B(D)=log(D)/(3 log 2)+1. The theorem supplies the schedule and discrepancy budget; importance scores, eligibility, group ordering, and the event size must be estimated empirically. Compare against magnitude pruning, random progressive pruning, and greedy global pruning at equal final sparsity or average bit rate. Start with a 12-layer transformer on CIFAR-100 or WikiText-2, using D=32 head or weight-tile groups and evaluating after every event. Measure validation accuracy or perplexity, memory reduction, maximum nested discrepancy, and loss spikes. Success means smoother degradation and fewer catastrophic intermediate checkpoints at the same final compression.

## Disclaimer

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