A Faster Closest-Point Algorithm for the $A_n^*$ Lattices

arXiv:2607.10479 2026 Architecture 1 ideas extracted · analyzed Aug 30, 2026

What the math gives to ML

The paper gives an efficient exact nearest-point primitive for the projected integer lattice A_n^*, whose points lie in a zero-sum hyperplane. This can transfer to quantization layers for probability vectors, histograms, simplex-valued embeddings, and other fixed-sum representations, where independent scalar rounding violates the constraint or introduces unnecessary distortion. The key engineering asset is that the nearest-point objective depends on fractional parts through prefix counts and prefix residual sums, enabling a flat-array counting-sort-style implementation instead of a general sort or pointer-heavy structure. A practical first target is a straight-through A_n^* quantizer for simplex-valued latents, compared against scalar rounding and largest-remainder rounding.

Ideas from this paper

Unverified 2026

Exact simplex-lattice quantization

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.

Useful6/10
Difficulty5/10
Novelty7/10
Paper: A Faster Closest-Point Algorithm for the $A_n^*$ Lattices arXiv:2607.10479