# Entropy-constrained unbiased block quantization

- ID: 2501
- Canonical URL: https://synthcore.org/idea/2501/entropy-constrained-unbiased-block-quantization
- API JSON: https://synthcore.org/api/idea/2501.json
- API Markdown: https://synthcore.org/api/idea/2501.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2608.18147](https://arxiv.org/abs/2608.18147)
- Category: memory
- Solves: memory, speedup, accuracy
- ML areas: quantization, transformer, kv-cache, inference-speedup
- Math tags: information-theory, optimization, probability, dynamic-programming
- Ratings: usefulness 8/10; difficulty 6/10; novelty 6/10

## Idea description

Replace fixed-grid stochastic quantization of each tensor block with an adaptive ordered codebook selected under both an entropy budget and a maximum number of codepoints. Within every interval between adjacent codepoints, use unbiased stochastic interpolation, so the quantized block remains unbiased while the emitted symbol distribution becomes easier for arithmetic or Huffman coding to compress. The representation should reduce actual compressed bytes at fixed MSE, or reduce MSE at fixed compressed size.

## Mathematical statement

The paper defines ECASQ for a real vector X, permissible alphabet P, maximum codebook size s, and average entropy budget b as minimizing MSE(Q,X) subject to |Q|<=s, H(hat X)<=b, and E[hat X]=X. Here Q is the selected scalar codebook, hat X is the random quantized vector, and H is Shannon entropy in bits per entry. For ordered codepoints q_1<...<q_k, an input x in [q_i,q_{i+1}] is mapped to q_i with probability (q_{i+1}-x)/(q_{i+1}-q_i) and to q_{i+1} with probability (x-q_i)/(q_{i+1}-q_i). This gives E[hat x|x]=x and conditional MSE E[(hat x-x)^2|x]=(q_{i+1}-x)(x-q_i). If pi_j is the empirical probability that output symbol q_j is emitted, the rate is H(hat X)=-sum_j pi_j log_2(pi_j). The constrained problem can be searched through the Lagrangian D(Q)+lambda*d*H(Q), where D is total MSE, d is block length, and lambda>=0 is a rate multiplier. The paper reports an approximate dynamic program using O(s d^2) time and O(d) space, with MSE no larger than the optimum using one fewer entropy bit per entry, followed by iterative refinement.

## Key formulas

- $$\min_{Q\subseteq P} MSE(Q,X)\quad\text{subject to}\quad |Q|\le s,\;H(\widehat X)\le b,\;\mathbb{E}[\widehat X]=X.$$
- $$\Pr(\widehat x=q_i\mid x)=\frac{q_{i+1}-x}{q_{i+1}-q_i},\qquad \Pr(\widehat x=q_{i+1}\mid x)=\frac{x-q_i}{q_{i+1}-q_i},\quad x\in[q_i,q_{i+1}].$$
- $$\mathbb{E}[\widehat x\mid x]=x,\qquad \mathbb{E}[(\widehat x-x)^2\mid x]=(q_{i+1}-x)(x-q_i).$$
- $$\mathcal{L}(Q;\lambda)=\sum_{t=1}^{d}(\widehat x_t-x_t)^2+\lambda d\left[-\sum_{j=1}^{k}\pi_j\log_2\pi_j\right],\qquad H(\widehat X)=-\sum_{j=1}^{k}\pi_j\log_2\pi_j.$$

## Implementation notes

Integrate this at the tensor-block quantization boundary, initially for 1D blocks of gradients, weights, activations, or KV-cache rows. Use blocks of d=64 or 128 values and retain the original block's scale/range normalization if needed. For each block: (1) sort or histogram values and construct a candidate alphabet P from uniformly spaced points, percentile points, or observed values plus endpoints; (2) for a candidate ordered codebook Q={q_1,...,q_k}, assign each x_t to its bracketing interval and compute stochastic probabilities from the interpolation formula; (3) estimate output probabilities by expected emissions, pi_j=(1/d) sum_t Pr(hat x_t=q_j|x_t), rather than from one random sample; (4) compute distortion D=sum_t(q_{i(t)+1}-x_t)(x_t-q_{i(t)}) and rate R=-sum_j pi_j log2 pi_j; (5) select Q minimizing D+lambda*d*R among k<=s. An MVP can approximate the paper's dynamic program with states dp[k,j], the minimum objective for using k codepoints through candidate index j, and transitions over previous cutpoints; interval distortion and symbol probabilities should be computed with prefix sums. Binary-search lambda until R is near target b, then run 2-5 local refinement passes that move codepoints to nearby candidates and accept reductions in D+lambda*d*R. During compression, sample symbols once and entropy-code the integer stream with arithmetic coding; transmit codebook and block metadata. The mathematical quantities are unbiased interpolation, conditional MSE, entropy, and the Lagrangian; candidate alphabets and lambda search are engineering choices. First test on GPT-2-small or a 6-layer decoder, quantizing weights or activations at 3-8 symbols and comparing uniform stochastic quantization plus arithmetic coding. Measure perplexity, realized bits per value, MSE, and encode/decode throughput. Success is at least 15% fewer post-coded bytes at equal perplexity, or lower perplexity at equal bytes, without material quantization-latency growth.

## Verification

- Status: mech_ok_no_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: no_effect
- Verdict: Built an entropy-constrained unbiased block quantizer with ordered stochastic interpolation, expected-emission entropy, exhaustive small-codebook Lagrangian search, and sampling. The core MSE identity matched to 6.1e-17; 5,000-sample unbiasedness checks had maximum empirical bias 0.0122, consistent with finite-sample error, and selected entropy was monotone as lambda increased. On the skewed toy block, adaptive codebooks reduced MSE by 20.7% at a nearby 1.88-bit/value rate and by 54.8% at a low-rate comparison, but actual arithmetic-coded bytes and neural-model quality were not tested.

### Mechanism check

- Verdict: Built an entropy-constrained unbiased block quantizer with ordered stochastic interpolation, expected-emission entropy, exhaustive small-codebook Lagrangian search, and sampling. The core MSE identity matched to 6.1e-17; 5,000-sample unbiasedness checks had maximum empirical bias 0.0122, consistent with finite-sample error, and selected entropy was monotone as lambda increased. On the skewed toy block, adaptive codebooks reduced MSE by 20.7% at a nearby 1.88-bit/value rate and by 54.8% at a low-rate comparison, but actual arithmetic-coded bytes and neural-model quality were not tested.
- Confidence: 8/10
- Limitations: The candidate search is exhaustive and intended only for small toy blocks; no dynamic-programming optimization, local refinement, arithmetic/Huffman coder, metadata overhead, throughput measurement, tensor integration, or neural-network perplexity/accuracy experiment was performed.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.5494
- Paired wins: 5/8
- Benchmark verdict: no significant win

## Artifacts

- [bench_exp.py](https://synthcore.org/code/896/bench_exp.py)
- [bench_report.json](https://synthcore.org/code/896/bench_report.json)
- [ecuq.py](https://synthcore.org/code/896/ecuq.py)
- [report.md](https://synthcore.org/code/896/report.md)
- [report_bench_2026-09-01T144450.md](https://synthcore.org/code/896/report_bench_2026-09-01T144450.md)
- [results.json](https://synthcore.org/code/896/results.json)
- [run_experiment.py](https://synthcore.org/code/896/run_experiment.py)
- [Download all files as ZIP](https://synthcore.org/download/896)

## Disclaimer

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