The Geometry of LLM Quantization: GPTQ as Babai's Nearest Plane
  Algorithm
Authors: name: Jiale Chen, name: Torsten Hoefler, name: Dan Alistarh
Organization:  IST Austria Distributed Algorithms and Systems Lab

Quantizing the weights of large language models (LLMs) from 16-bit to lower
bitwidth is the de facto approach to deploy massive transformers onto more
affordable accelerators. GPTQ emerged as one of the standard methods for
one-shot post-training quantization at LLM scale. Yet, its inner workings are
described as a sequence of ad-hoc algebraic updates that obscure any geometric
meaning or worst-case guarantees. In this work, we show that, when executed
back-to-front (from the last to first dimension) for a linear layer, GPTQ is
mathematically identical to Babai's nearest plane algorithm for the classical
closest vector problem (CVP) on a lattice defined by the Hessian matrix of the
layer's inputs. This equivalence is based on a sophisticated mathematical
argument, and has two analytical consequences: (i) the GPTQ error propagation
step gains an intuitive geometric interpretation; (ii) GPTQ inherits the error
upper bound of Babai's algorithm under the no-clipping condition. Taken
together, these results place GPTQ on firm theoretical footing and open the
door to importing decades of progress in lattice algorithms towards the design
of future quantization algorithms for billion-parameter models.