Unverified 2026

Exact simplex-lattice quantization

Implementation & benchmark of arXiv:2607.10479 — A Faster Closest-Point Algorithm for the $A_n^*$ Lattices

Usefulness6/10
Difficulty5/10
Novelty7/10

Source paper: A Faster Closest-Point Algorithm for the $A_n^*$ Lattices arXiv:2607.10479 ⓘ · analyzed Aug 30, 2026

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

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.

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}).$$

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.

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.

Verification

This idea has not been verified yet.

Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.

Artifacts

Artifacts unavailable.