Every Bit Counts: A Theoretical Study of Precision-Expressivity Tradeoffs in Quantized Transformers
This work addresses the problem of optimizing quantization for practitioners in machine learning, providing a theoretical basis for choosing precision levels in tasks sensitive to exact comparisons, though it is incremental in building on existing quantization research.
The study tackles the problem of how quantization affects Transformer expressivity by demonstrating a theoretical tradeoff: for each precision level p, a one-layer softmax Transformer can compute a specific function with p bits but not with p-1 bits, concretely explaining empirical losses in tasks like equality comparisons.
Quantization reduces the numerical precision of Transformer computations and is widely used to accelerate inference, yet its effect on expressivity remains poorly characterized. We demonstrate a fine-grained theoretical tradeoff between expressivity and precision: For every p we exhibit a function Γ, inspired by the equality function, and prove that a one-layer softmax Transformer can compute Γ, with p bits of precision, but not with p-1 bits of precision. This result concretely explains the widely observed phenomenon of empirical loss of expressivity when quantization is used. Practically, it suggests that tasks requiring equality-like comparisons (exact match, membership, etc.) are especially sensitive to quantization. Dropping even one bit can cross a threshold where the model cannot represent the needed comparison reliably. Thus, it paves the way for developing heuristics that will help practitioners choose how much quantization is possible: the precision should be chosen as a function of the length of equality to be checked for the specific task. Our proofs combine explicit finite-precision Transformer constructions with communication-complexity lower bounds, yielding a tight "one-bit" threshold.