# Exact simplex-lattice quantization

- ID: 689
- Canonical URL: https://synthcore.org/idea/689/exact-simplex-lattice-quantization
- API JSON: https://synthcore.org/api/idea/689.json
- API Markdown: https://synthcore.org/api/idea/689.md
- Verification status: unverified
- Source: [arXiv:2607.10479](https://arxiv.org/abs/2607.10479)
- Category: architecture
- Solves: accuracy, memory, stability
- ML areas: quantization, embedding
- Math tags: geometry, linear-algebra, optimization, number-theory
- Ratings: usefulness 6/10; difficulty 5/10; novelty 7/10

## Idea description

Replace independent coordinate rounding of a fixed-sum vector with nearest-point quantization in the projected integer lattice A_n^*. The quantized vector preserves the zero-sum constraint exactly, while the globally optimal rounding correction accounts for the aggregate residual induced by projection.

## Mathematical statement

Let N=n+1, let 1 be the all-ones vector in R^N, let H={x in R^N:1^T x=0}, and let Q=I-11^T/N be the orthogonal projector onto H. The lattice is A_n^*={Qz:z in Z^N}. For a query y in H, nearest-point quantization minimizes ||y-Qz||^2=||y-z||^2-(1^T z)^2/N. Define a_i=floor(y_i), f_i=y_i-a_i in [0,1), and A=sum_i a_i. If f_(1)>=...>=f_(N) are the sorted fractional parts and R_m=sum_{j=1}^m f_(j), then the candidate obtained by incrementing the m coordinates with largest fractional parts has objective F(m)=sum_i f_i^2+m-2R_m-(A+m)^2/N. The optimal correction size is m*=argmin_m F(m), and the output is x*=Q(a+b*), where b* has ones at the selected coordinates. The paper's algorithmic contribution is that R_m can be computed from bucket counts and bucket residual sums, without storing or traversing every element in sorted order.

## Key formulas

- $$Q=I-\frac{\mathbf{1}\mathbf{1}^{T}}{N},\qquad A_n^*=\{Q\mathbf{z}:\mathbf{z}\in\mathbb{Z}^{N}\},\qquad H=\{\mathbf{x}\in\mathbb{R}^{N}:\mathbf{1}^{T}\mathbf{x}=0\}.$$
- $$\mathbf{x}^{*}=\arg\min_{\mathbf{x}\in A_n^*}\|\mathbf{y}-\mathbf{x}\|^2=\arg\min_{\mathbf{z}\in\mathbb{Z}^{N}}\left[\|\mathbf{y}-\mathbf{z}\|^2-\frac{(\mathbf{1}^{T}\mathbf{z})^2}{N}\right].$$
- $$F(m)=\sum_{i=1}^{N}f_i^2+m-2\sum_{j=1}^{m}f_{(j)}-\frac{(A+m)^2}{N},\qquad m^{*}=\arg\min_m F(m),\qquad \mathbf{x}^{*}=Q(\mathbf{a}+\mathbf{b}^{*}).$$
- $$\widehat{\mathbf{p}}=\frac{1}{N}\mathbf{1}+\Delta Q\mathbf{z}^{*},\qquad \mathbf{y}=\frac{\mathbf{p}-\frac{1}{N}\mathbf{1}}{\Delta},\qquad \mathbf{z}^{*}=\operatorname{CVP}_{A_n^*}(\mathbf{y}).$$

## Implementation notes

Integrate this module immediately before an embedding or MLP consumes a simplex-valued latent or histogram. Given a probability vector p of length N, select a quantization step Delta, center the input as y=(p-1/N)/Delta, and run the lattice quantizer. Compute a_i=floor(y_i), f_i=y_i-a_i, A=sum_i a_i, and S2=sum_i f_i^2. For a GPU-friendly MVP, assign each f_i to one of B uniform buckets and accumulate two arrays: C[b], the number of coordinates in bucket b, and S[b], the sum of their fractional parts. Scan buckets from largest to smallest, maintaining the prefix count m and prefix residual sum R. At each candidate m, evaluate F(m)=S2+m-2R-(A+m)^2/N. If a bucket contains multiple coordinates and exact selection is needed, sort only that boundary bucket or use a deterministic threshold plus a local scan. Set b_i=1 for the selected m* coordinates and zero elsewhere, then return q=Q(a+b) and p_hat=1/N+Delta*q. During training use the straight-through estimator p_st=p+stopgrad(p_hat-p), so the forward pass is quantized while gradients pass through p. The paper's mathematics determines the projector, candidate objective, and prefix scan; Delta and B are engineering choices estimated from calibration data. For rational inputs with common denominator D, encode residuals as integer numerators and evaluate a scaled objective with integer arithmetic. Start with a small CIFAR-10 classifier receiving normalized histogram features, or a Dirichlet-vector autoencoder. Compare scalar rounding, largest-remainder rounding, and A_n^* quantization at 4, 6, and 8 bits. Measure reconstruction MSE or KL, downstream accuracy, exact sum preservation, invalid-coordinate frequency, and latency. Success is lower distortion or higher accuracy at equal bit rate, exact constraint preservation, and throughput within 2x of scalar rounding; benchmark the bucket kernel against full sorting as N increases.

## Disclaimer

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