Pith. sign in

REVIEW 2 major objections 7 minor 28 references

High-Rate Nested-Lattice Quantized Matrix Multiplication with Small Lookup Tables

T0 review · 2 major / 7 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Hierarchical nested-lattice quantizers cut the inner-product lookup table from $2^{2dR}$ to $2^{2dR/M}$ entries while nearly matching the distortion of a same-rate Voronoi code.

desk verdict A genuinely useful hierarchical lattice quantizer that cuts LUT size by a factor of M at a small, mostly numerical, distortion cost; the retry overhead in the rate accounting is the one thing I'd ask the authors to nail down. read the letter →

arxiv 2505.13164 v1 pith:V4TWZTSC submitted 2025-05-19 cs.IT math.IT

Iris Kaplan , Or Ordentlich This is my paper · ORCID
classification cs.ITmath.IT MSC 94A3494A2911H06
keywords nestedlatticecodesVoronoivectorquantizationlookuptabledecodingmatrixmultiplicationsuccessiverefinementrate-distortiontheory
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to prove that the lookup-table bottleneck in quantized matrix multiplication can be removed without sacrificing quantization rate. Standard nested-lattice schemes decode an inner product by querying a table with $2^{2dR}$ entries, which only fits in fast cache when the rate-dimension product $dR$ is small. The authors' hierarchical scheme quantizes each vector into $M$ nested-lattice layers and decodes via $M^2$ queries to one table of $2^{2dR/M}$ entries, so a high-rate quantizer can be decoded with a small, cache-sized table. They prove bounds that relate the hierarchical codebook to Voronoi codebooks of nearly the same rate, and report simulations showing the distortion loss is negligible. If the claim holds, fast software inner-product decoding becomes practical for high-rate quantization in memory-bound neural-network inference.

What carries the argument

The load-bearing object is the hierarchical nested-lattice quantizer built from a base lattice $L\subset\mathbb{R}^d$, a nesting ratio $q$, and depth $M$: the encoder computes $\tilde{g}_m = Q_L(\tilde{g}_{m-1}/q)$ and transmits each layer as a coset label $b_m\in[q]^d$, and the decoder assembles $\hat{x}=\sum_{m=0}^{M-1} q^m x_m$. Lemma 1 is the identity $\hat{x}=Q_L(x)$ iff the $M$-fold composition $Q^{\circ M}(x)=0$, which identifies the codebook $C_{L,q,M}=L\cap P_{q,M}$ for a fundamental cell $P_{q,M}$; Lemma 2 sandwiches this codebook between scaled Voronoi codebooks and thereby transfers known overload-probability bounds to the hierarchical scheme. Equation (15) is the algorithmic payoff: $\hat{x}^\top\hat{y}=\sum_{i,j}q^{i+j}L(b_i(x),b_j(y))$, which reduces the lookup table from size $2^{2dR}$ to $2^{2dR/M}$ at the price of $M^2$ lookups.

What would settle it

Run the $D_4$ hierarchical encoder on standard Gaussian vectors at $q=4$ with $M=2,3,4$, record the retry count $T$ under the overload-avoidance rule, estimate the entropy-coded bit cost $H(T)$, add $H(T)/d$ to the rate, and compare the adjusted distortion-rate curve with the same-rate Voronoi reference; if the curve moves more than a small fraction of a bit from the reference, the negligible-loss claim fails.

Watch

Extended reading notes

Core claim

At its core, the paper claims that quantizing each $d$-dimensional vector as $M$ layers of a nested lattice lets an inner product be decoded from a single lookup table of $2^{2dR/M}$ entries rather than $2^{2dR}$, while staying near the distortion-rate performance of a standard rate-$R$ Voronoi code. Encoding runs the nearest-neighbor lattice quantizer $Q_L$ repeatedly on scaled residuals and writes each layer as a label in $\{0,\ldots,q-1\}^d$; decoding reconstructs $\hat{x}$ as $\sum_{m=0}^{M-1} q^m x_m$, and the inner product of two reconstructed vectors is $\sum_{i,j} q^{i+j} L(b_i(x), b_j(y))$ for a precomputed table $L$. Lemma 2 bounds the hierarchical codebook between scaled Voronoi codebooks, $A_{q^M(1-r_{q,M})}\subset C_{L,q,M}\subset A_{q^M(1+r_{q,M})}$, with $r_{q,M}=(1-q^{1-M})/(q-1)$, so the overload behavior is close to that of a code of nearly the same rate. The experiments show the loss relative to a same-rate Voronoi code is small, and both schemes sit about half a bit from the Shannon limit.

Load-bearing premise

The claim that the hierarchical scheme loses negligibly to a same-rate Voronoi code rests on the overload-avoidance retry loop, where the encoder keeps rescaling $\beta$ until no overload occurs and sends the retry count $T$ at entropy-coded cost $H(T)$; the paper does not bound $H(T)$ or prove the rescaled codebook preserves near-Voronoi distortion, relying instead on simulations.

Editorial extensions

If this is right

  • LUT-based inner-product decoding is no longer limited to low rates: any rate $R=M\log_2 q$ can be decoded from a table of $2^{2dR/M}$ entries.
  • Each inner product costs $M^2$ table lookups plus $M^2$ scalar multiplications by powers of $q$, implementable as bit-shifts when $q$ is a power of two.
  • One-sided inner products, where a fixed vector is compared with many quantized vectors, need only a table of $2^{dR/M}$ entries.
  • For vectors of arbitrary dimension, product codes over $d$-dimensional chunks decode the full inner product chunkwise with the same small table.
  • Simulations on the $D_4$ lattice place the scheme within about half a bit of the Shannon distortion-rate limit, close to a same-rate Voronoi code.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A natural follow-up is to bound the entropy $H(T)$ of the overload-avoidance retry count for Gaussian sources; until that is done, the effective rate of the scheme is not fully pinned down.
  • The same layered decomposition could be tuned non-uniformly, using different nesting ratios per layer, to optimize LUT size against distortion for a fixed total rate.
  • The one-sided lookup table of size $2^{dR/M}$ suggests a role for hierarchical quantizers in approximate nearest-neighbor search where the query stays full-resolution, though the paper only sketches this setting.
  • Because decoding to $t<M$ layers already yields a coarse reconstruction, the scheme has a built-in progressive-precision mode that could support early-exit or adaptive inference.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 7 minor

Summary. The paper proposes a hierarchical nested-lattice quantizer for the matrix-multiplication quantization problem. A d-dimensional vector is encoded into M layers, each represented by d log2(q) bits, and an inner product is reconstructed from M^2 lookups into a single lookup table of size q^{2d} = 2^{2dR/M}, instead of the 2^{2dR} table needed by a standard Voronoi code of the same nominal rate. The paper proves Lemma 1, a clean telescoping identity showing that the hierarchical reconstruction equals the nearest lattice point exactly when the final residual is zero, and Lemma 2, which bounds the hierarchical codebook between two scaled Voronoi codebooks. The paper then reports D4-lattice simulations showing that the hierarchical scheme is very close to a Voronoi code of the same nominal rate and roughly half a bit from the Shannon limit, and it provides code links for the implementation.

Significance. If the rate accounting is correct, this is a practical contribution: it offers a way to use L1-resident lookup tables for high-rate quantized matrix multiplication at the cost of M^2 table accesses per inner product. The algebraic core is elegant, the proof of Lemma 1 is a genuine telescoping argument, Lemma 2 is proved correctly using convexity of the Voronoi region, and the paper ships reproducible Python and C implementations. These are clear strengths. The significance is conditional, however, on whether the reported rate is the true communication rate; the overload-avoidance retry overhead is not accounted for in the headline numbers.

major comments (2)
  1. [Section II-A, Eq. (15), Fig. 2] The abstract, Eq. (15), and the LUT-size discussion identify the rate as R = M log2(q), but Section II-A states that the expected rate is M log2(q) + H(T)/d, where T is the overload-avoidance retry count. The simulation section does not state whether the plotted rate includes H(T)/d. If it does not, every plotted point is shifted to a lower rate than the true rate, and the comparison with a Voronoi code 'of the same rate' is not on equal footing. Because the distribution of T depends on the scheme, the scaling schedule, and beta0, this overhead cannot be assumed to cancel in the comparison. The authors should either provide an analysis or a measured value of H(T)/d, explicitly state whether the plotted rates include it, and, if not, replot with the total rate.
  2. [Section II-B, Lemma 2] Lemma 2 establishes the inclusion A_{q^M(1-r)} subset C_{L,q,M} subset A_{q^M(1+r)} with r = (1 - q^{1-M})/(q-1). This implies that the hierarchical codebook's overload probability is bracketed by two Voronoi codes whose rates differ by log2((1+r)/(1-r)) bits; for q=4 and M=2 this difference is about 0.737 bits and it approaches 1 bit as M grows. The gap does not shrink with M. Consequently, Lemma 2 by itself does not provide an analytic bound on distortion loss, and the abstract's phrase 'analytic bounds on the loss' overstates what is proved. The numerical simulations are the actual support for the negligible-loss claim, so those simulations must use the total rate as discussed in the first major comment.
minor comments (7)
  1. [Abstract and Introduction] The phrase 'Recent work have shown' is ungrammatical and should be 'Recent work has shown'.
  2. [Related Work] 'chucks' should be 'chunks', and 'Loyd's algorithm' should be 'Lloyd's algorithm'.
  3. [Section II-A, Algorithm 1] The sentence defining the overload error uses 'OverloadError' as both a variable and a concept; it would be clearer to state explicitly that the decoder output equals Q_L(x) if and only if this flag is zero, which is already the content of Lemma 1.
  4. [Section III] The sentence 'It therefore follows that for if our goal is to quantize x,y...' contains a redundant 'for' and should be reworded.
  5. [Section III, Simulation results] The typo 'overlaod' should be 'overload'.
  6. [References [15] and [16]] The repository descriptions contain the typo 'neseted-lattice' and should read 'nested-lattice'.
  7. [Fig. 2] The text refers to Figures 2a and 2b but does not describe the axis labels; please ensure the figures explicitly state whether the horizontal axis is nominal rate or total rate including H(T)/d.

Circularity Check

0 steps flagged · score 2.0 of 10

No construction-level circularity: the LUT-size reduction and Lemma 2 are derived in-paper, with only a minor, non-load-bearing self-citation to [12] for the overload-avoidance mechanism and benchmark.

full rationale

The central derivation is self-contained. Algorithm 1/2 define the hierarchical code, Lemma 1 proves that reconstruction equals Q_L(x) iff Q^{◦M}(x)=0, and Lemma 2 gives an explicit geometric sandwich A_{q^M(1-r)} ⊂ C_{L,q,M} ⊂ A_{q^M(1+r)}, so the comparison to Voronoi codes is a genuine bound rather than an imported conclusion. The LUT-size statement 2^{2dR/M} follows by counting pairs of q-ary d-dimensional layer codewords and is an algebraic consequence of the construction, not a fitted prediction. The only caveats are (a) a minor self-citation: the overload-avoidance retry mechanism and the Γ(R) fundamental limit are taken from [12], which shares an author, but these are not load-bearing for the paper's new LUT-size or Lemma 2 results; and (b) a rate-accounting gap: Section II-A states "In total, the expected rate of this scheme is M log_2(q) + H(T)/d", but Section III and the abstract use R = M log_2(q) as "the rate", and the paper never analyzes H(T) nor states whether the plotted rates include it. This missing H(T) term is an omitted support for the "same total rate" comparison, but it is not a circular reduction: no equation in the paper forces the distortion result from the rate definition. Accordingly, no circular step is present; the appropriate finding is a low score reflecting minor self-citation and a caveat, not built-in circularity.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

The central claim rests only on standard lattice geometry plus the inherited overload-avoidance mechanism from [12]. The two free parameters are simulation-level choices, not fitted to force the LUT-size result. No new physical or mathematical entities are postulated.

free parameters (2)
  • beta0 (initial scaling factor) = optimized per scheme (values not reported)
    Used in the overload-avoidance mechanism in Section II-A to set the initial constellation scale; chosen to balance granular and overload distortion. Affects the numerical comparison in Fig. 2, not the analytical LUT-size claim.
  • alpha (overload retry scale exponent) = 1/3
    Parameter of the overload-avoidance mechanism that multiplies the scaling by 2^alpha per retry. Chosen by hand, following [12]; contributes to the expected rate overhead H(T)/d.
assumptions (5)
  • standard math The Voronoi region V of a lattice is convex, so alpha V + beta V = (alpha+beta) V for positive alpha, beta.
    Used in Lemma 2's proof, Eqs. (10)-(12).
  • standard math For any lattice Lambda, the nearest-neighbor quantizer satisfies Q_Lambda(x) - x in V_Lambda for all x, and Q_Lambda(x+lambda)=Q_Lambda(x)+lambda for lambda in Lambda.
    Used to derive the recursion (5)-(6) and the inclusion chain (11)-(12).
  • standard math The set P_{q,M} = {x: Q^oM(x)=0} is a fundamental cell of q^M L, so C_{L,q,M} is a set of coset representatives of L/q^M L with exactly q^{Md} points.
    Stated in Section II-B without proof; underpins the rate R = M log_2 q and the injectivity of the layered encoding.
  • domain assumption The overload-avoidance mechanism can be implemented with entropy coding of the retry count T at rate H(T), and the dithered and scaled input model x/beta - z follows the analysis of [12].
    Inherited from prior work [12]; the paper does not analyze H(T) or the retry distribution and relies on the numerical evidence in Fig. 2.
  • domain assumption Numerical evaluation uses iid Gaussian N(0,I_d) sources; universality for arbitrary vectors is obtained via a random rotation S as in [12].
    Simulation setup in Sections II-B and III; the distortion-rate plots are for Gaussian sources only.

how reviews work

0 comments
Cite this review

Pith. "Pith review of High-Rate Nested-Lattice Quantized Matrix Multiplication with Small Lookup Tables." pith.science (2026). https://pith.science/paper/V4TWZTSC

@misc{pith2026250513164,
  author       = {Pith},
  title        = {Pith review of: High-Rate Nested-Lattice Quantized Matrix Multiplication with Small Lookup Tables},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/V4TWZTSC}},
  note         = {Machine review of arXiv:2505.13164}
}
abstract

Recent work have shown that the quantization for matrix multiplication problem can be optimally solved by quantizing each column in each matrix using a nested lattice code, and then multiplying the de-quantized matrices. It was further demonstrated that when product codes of sub-dimension $d$ and rate $R$ are used, the de-quantization and inner product operations can be implemented with querying a lookup table (LUT) of size $2^{2dR}$, but this is only useful when $dR$ is sufficiently small. This in turn limits LUT-based inner product decoding to low-rate quantizers. In this work, we develop a rate $R$ hierarchical nested lattice quantization framework, which quantizes each vector to $M$ layers, and admits LUT-based inner product decoding using an LUT of size $2^{2d\frac{R}{M}}$, allowing for high-rate quantization. We provide analytic bounds on the loss of the developed scheme compared to standard nested lattice quantizers, and also numerically illustrate that this loss is negligible. Thus, our scheme enables to use small LUTs without compromising the overall distortion.

Figures

Figures reproduced from arXiv: 2505.13164 by the authors.

Figure 1
Figure 1. Codebook of the hierarchical nested lattice quantizer [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Distortion-Rate curves for nested lattice quantizers, [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

28 extracted references · 15 canonical work pages

  1. [12]

    Optimal quantization for matrix multiplication,

    O. Ordentlich and Y . Polyanskiy, “Optimal quantization for matrix multiplication,”arXiv preprint arXiv:2410.13780, 2024

    arXiv 2024

  2. [1]

    Compressing deep convolutional networks using vector quantization,

    Y . Gong, L. Liu, M. Yang, and L. Bourdev, “Compressing deep convolutional networks using vector quantization,”arXiv preprint arXiv:1412.6115, 2014

    arXiv 2014

  3. [2]

    Quantization and training of neural networks for efficient integer-arithmetic-only inference,

    B. Jacob, S. Kligys, B. Chen, M. Zhu, M. Tang, A. Howard, H. Adam, and D. Kalenichenko, “Quantization and training of neural networks for efficient integer-arithmetic-only inference,” inProceedings of the IEEE conference on computer vision and pattern recognition, 2018, pp. 2704– 2713

    2018

  4. [3]

    Gpt3. int8 (): 8-bit matrix multiplication for transformers at scale,

    T. Dettmers, M. Lewis, Y . Belkada, and L. Zettlemoyer, “Gpt3. int8 (): 8-bit matrix multiplication for transformers at scale,”Advances in Neural Information Processing Systems, vol. 35, pp. 30 318–30 332, 2022

    work page 2022

  5. [4]

    Zeroquant: Efficient and affordable post-training quantization for large- scale transformers,

    Z. Yao, R. Yazdani Aminabadi, M. Zhang, X. Wu, C. Li, and Y . He, “Zeroquant: Efficient and affordable post-training quantization for large- scale transformers,”Advances in Neural Information Processing Sys- tems, vol. 35, pp. 27 168–27 183, 2022

    work page 2022

  6. [5]

    Smoothquant: Accurate and efficient post-training quantization for large language models,

    G. Xiao, J. Lin, M. Seznec, H. Wu, J. Demouth, and S. Han, “Smoothquant: Accurate and efficient post-training quantization for large language models,” inInternational Conference on Machine Learning. PMLR, 2023, pp. 38 087–38 099

    2023

  7. [6]

    The era of 1-bit llms: All large language models are in 1.58 bits,

    S. Ma, H. Wang, L. Ma, L. Wang, W. Wang, S. Huang, L. Dong, R. Wang, J. Xue, and F. Wei, “The era of 1-bit llms: All large language models are in 1.58 bits,”arXiv preprint arXiv:2402.17764, 2024

    arXiv 2024

  8. [7]

    Quip#: Even better llm quantization with hadamard incoherence and lattice codebooks,

    A. Tseng, J. Chee, Q. Sun, V . Kuleshov, and C. De Sa, “Quip#: Even better llm quantization with hadamard incoherence and lattice codebooks,”arXiv preprint arXiv:2402.04396, 2024

    arXiv 2024

Show all 28 references
  1. [8]

    Qtip: Quantization with trellises and incoherence processing,

    A. Tseng, Q. Sun, D. Hou, and C. De Sa, “Qtip: Quantization with trellises and incoherence processing,”arXiv preprint arXiv:2406.11235, 2024

    2024 arXiv

  2. [9]

    Quarot: Outlier-free 4-bit inference in rotated llms,

    S. Ashkboos, A. Mohtashami, M. L. Croci, B. Li, M. Jaggi, D. Alistarh, T. Hoefler, and J. Hensman, “Quarot: Outlier-free 4-bit inference in rotated llms,”arXiv preprint arXiv:2404.00456, 2024

    2024 arXiv

  3. [10]

    Dynamic network surgery for efficient dnns,

    Y . Guo, A. Yao, and Y . Chen, “Dynamic network surgery for efficient dnns,”Advances in neural information processing systems, vol. 29, 2016

    2016

  4. [11]

    OPTQ: Accurate quantization for generative pre-trained transformers,

    E. Frantar, S. Ashkboos, T. Hoefler, and D. Alistarh, “OPTQ: Accurate quantization for generative pre-trained transformers,” inThe Eleventh International Conference on Learning Representations, 2023. [Online]. Available: https://openreview.net/forum?id=tcbBPnfwxS

    2023

  5. [13]

    A fast encoding method for lattice codes and quantizers,

    J. Conway and N. Sloane, “A fast encoding method for lattice codes and quantizers,”IEEE Transactions on Information Theory, vol. 29, no. 6, pp. 820–824, 1983

    1983

  6. [14]

    NestQuant: Nested lattice quantization for matrix products and LLMs,

    S. Savkin, E. Porat, O. Ordentlich, and Y . Polyanskiy, “NestQuant: Nested lattice quantization for matrix products and LLMs,”arXiv preprint arXiv:2502.09720, 2025

    2025 arXiv

  7. [15]

    A python package for neseted-lattice LUT,

    I. Kaplan, “A python package for neseted-lattice LUT,” 2025. [Online]. Available: https://github.com/iriskaplan/LatticeQuant

    2025

  8. [16]

    A C package for neseted-lattice LUT,

    O. Meir, “A C package for neseted-lattice LUT,” 2025. [Online]. Available: https://github.com/orimeirgit/NestedLatticeLut

    2025

  9. [17]

    Successive refinement of information,

    W. H. Equitz and T. M. Cover, “Successive refinement of information,” IEEE Transactions on information theory, vol. 37, no. 2, pp. 269–275, 1991

    1991

  10. [18]

    Embedded image coding using zerotrees of wavelet coefficients,

    J. M. Shapiro, “Embedded image coding using zerotrees of wavelet coefficients,”IEEE Transactions on signal processing, vol. 41, no. 12, pp. 3445–3462, 1993

    1993

  11. [19]

    A new, fast, and efficient image codec based on set partitioning in hierarchical trees,

    A. Said and W. A. Pearlman, “A new, fast, and efficient image codec based on set partitioning in hierarchical trees,”IEEE Transactions on circuits and systems for video technology, vol. 6, no. 3, pp. 243–250, 1996

    1996

  12. [20]

    Successive refinement lattice vector quantization,

    D. Mukherjee and S. K. Mitra, “Successive refinement lattice vector quantization,”IEEE Transactions on Image Processing, vol. 11, no. 12, pp. 1337–1348, 2002

    2002

  13. [21]

    Embedded voronoi codes for successive refinement lattice vector quantization,

    G. Fuchs, “Embedded voronoi codes for successive refinement lattice vector quantization,” in2013 IEEE International Conference on Acous- tics, Speech and Signal Processing. IEEE, 2013, pp. 5805–5809

    2013

  14. [22]

    Quantization,

    R. M. Gray and D. L. Neuhoff, “Quantization,”IEEE transactions on information theory, vol. 44, no. 6, pp. 2325–2383, 1998

    1998

  15. [23]

    Gersho and R

    A. Gersho and R. M. Gray,V ector quantization and signal compression. Springer Science & Business Media, 2012, vol. 159

    2012

  16. [24]

    Product quantization for nearest neighbor search,

    H. Jegou, M. Douze, and C. Schmid, “Product quantization for nearest neighbor search,”IEEE transactions on pattern analysis and machine intelligence, vol. 33, no. 1, pp. 117–128, 2010

    2010

  17. [25]

    Additive quantization for extreme vector compression,

    A. Babenko and V . Lempitsky, “Additive quantization for extreme vector compression,” inProceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2014, pp. 931–938

    2014

  18. [26]

    Bolt: Accelerated data mining with fast vector compression,

    D. W. Blalock and J. V . Guttag, “Bolt: Accelerated data mining with fast vector compression,” inProceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2017, pp. 727–735

    2017

  19. [27]

    Multiplying matrices without multiplying,

    D. Blalock and J. Guttag, “Multiplying matrices without multiplying,” inInternational Conference on Machine Learning. PMLR, 2021, pp. 992–1004

    2021

  20. [28]

    Zamir,Lattice Coding for Signals and Networks: A Structured Cod- ing Approach to Quantization, Modulation, and Multiuser Information Theory

    R. Zamir,Lattice Coding for Signals and Networks: A Structured Cod- ing Approach to Quantization, Modulation, and Multiuser Information Theory. Cambridge University Press, 2014

    2014

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.