Binary Quadratic Quantization: Beyond First-Order Quantization for Real-Valued Matrix Compression

AI summary

Overview

• Research area: Model compression and matrix quantization, with applications to computer vision (Vision Transformers) and general real-valued matrix compression. Submitted under cs.CV (arXiv:2510.18650v1, 21 Oct 2025).
• Technical level: Advanced. The paper builds on polynomial unconstrained binary optimization (PUBO), quadratic unconstrained binary optimization (QUBO), mean-field annealing, and convex quadratic programming, alongside standard deep learning quantization practice.
• Scope (one sentence): The paper introduces a matrix quantizer that replaces the usual linear combination of binary bases with a quadratic (product) combination of binary matrices, and evaluates it on a matrix compression benchmark and on post-training quantization (PTQ) of pretrained Vision Transformer models.

What This Paper Is About

Conventional quantization methods such as Uniform Quantization (UQ) and Binary Coding Quantization (BCQ) approximate a real-valued matrix as a linear sum of binary matrices with scaling factors (plus, for UQ, a bias). At extremely low bit widths — 1 or 2 bits — each element can take only two or four values, which limits how accurately the original matrix can be reconstructed. The goal of this work is to keep the storage format essentially binary while gaining far more expressive power, by representing a matrix as a sum of products of binary matrices with their own scaling factors and bias terms. The authors then test whether this richer form pays off both on generic matrix data and on compressing the weights of pretrained ViTs.

Key Contributions

1. A new quantization framework (BQQ). The paper proposes Binary Quadratic Quantization, which approximates a real-valued matrix as a sum over p terms of r_i Y_i Z_i + s_i Y_i 1_Z + t_i 1_Y Z_i, plus a global bias u 1, where Y_i and Z_i are binary matrices and r_i, s_i, t_i, u are real scalar coefficients. The paper notes this formulation subsumes BCQ as a special case (when l = max(m, n) and one factor is set to the identity).
2. An efficient optimizer for an NP-hard problem. Minimizing the BQQ squared error is a mixed-integer problem the paper describes as NP-hard (optimizing 3p + 1 real coefficients and the elements of 2p binary matrices). The authors solve it by decoupling the two variable types: greedy, per-index optimization over a residual matrix; PUBO for the binary variables via an extension of Annealed Mean Field Descent (AMFD) to general PUBO; and closed-form convex quadratic programming for the coefficients.
3. Matrix compression benchmark. BQQ is compared against nine methods on five kinds of real-valued matrices, and is reported to consistently achieve a better trade-off between memory size and reconstruction error.
4. Post-training quantization of ViTs. BQQ is applied to weight-only PTQ of DeiT and Swin Transformer models, and the paper states it is the first work to reach practical accuracy — such as 72% ImageNet top-1 accuracy on DeiT-base — using data-free PTQ for ViTs at a model size equivalent to 2-bit quantization.

Main Findings

• Matrix compression trade-off: Across five matrix datasets, BQQ consistently achieves a superior trade-off between compression rate and reconstruction accuracy, which the authors present as evidence of general effectiveness for matrix approximation.
• Where BQQ helps most against UQ, BCQ, and LVQ: The advantage is especially pronounced for matrices whose singular value spectrum is dominated by a few large components (concentrated spectral energy); for relatively flat spectra the gain is smaller.
• Where BQQ helps most against factorization and codebook methods: Compared with SVD, SVD + p-bit UQ, VQ, and VQ + p-bit UQ, the opposite trend is observed — BQQ's advantage is greater for matrices with more uniform singular value spectra.
• One acknowledged loss: On the ImageNet dataset, BQQ yields a less favorable trade-off between memory size and reconstruction error than JPEG (8-bit UQ + JPEG).
• Headline PTQ claim: The paper reports that BQQ outperforms the state-of-the-art PTQ method by up to 2.2% and 59.1% on the ImageNet dataset under the calibration-based and data-free scenarios, respectively, with quantization equivalent to 2 bits.
• Data-free 2-bit results (ImageNet top-1, weights only, 32-bit activations): BQQ reaches 58.25% on DeiT-S, 72.09% on DeiT-B, 57.37% on Swin-T, and 68.17% on Swin-S. For comparison, its own UQ baseline reaches 3.23 / 2.45 / 14.69 / 30.69, its own BCQ baseline reaches 10.83 / 12.99 / 18.62 / 34.84, and PSAQ-ViT (data-free, column-wise) is reported at 0.27 / 0.19 / 0.15 / 0.14.
• Calibration-based 2-bit results: c-BQQ reaches 69.41 / 77.94 / 74.03 / 78.47 (DeiT-S / DeiT-B / Swin-T / Swin-S), versus c-BCQ at 60.13 / 73.37 / 68.09 / 73.97, c-UQ at 52.21 / 60.57 / 67.49 / 74.16, and COMQ at 67.19 / 77.14 / 74.05 / 78.02.
• Higher bit widths: At 3 bits, c-BQQ reaches 77.33 / 80.81 / 79.34 / 81.86 versus COMQ at 77.47 / 80.47 / 79.31 / 81.95. At 4 bits, c-BQQ reaches 79.12 / 81.47 / 80.57 / 82.72 versus COMQ at 78.98 / 81.40 / 80.89 / 82.85. Full-precision references are 79.83 / 81.80 / 81.37 / 83.21.
• Pseudo-bit accounting: Although every BQQ weight matrix is binary, its configuration is designed to match the information content of a first-order p-bit quantized model, which the paper names "pseudo p*-bit."
• Scaling granularity: BQQ's PTQ results are obtained with group-wise scaling, whereas the strongest external baselines (COMQ, ERQ, RepQ-ViT, PSAQ-ViT) use column-wise scaling and PTQ4ViT uses layer-wise scaling.
• No PTQ-specific tricks: The paper emphasizes that its PTQ method is based mainly on minimizing weight reconstruction error, rather than explicitly minimizing activation error, and does not target state-of-the-art accuracy under tight memory constraints or rely on PTQ-specific binary matrix optimization.

Methodology in Plain English

• Representation. Instead of adding up binary matrices (the BCQ/UQ idea), BQQ multiplies two binary matrices together and adds up those products. Each product term gets its own real-valued multiplier, plus two extra scaled linear terms and one shared bias. Only the binary matrices and the scalar coefficients need to be stored; the all-ones matrices are notational.
• Parameter budget matching. To compare fairly with UQ and BCQ, the intermediate dimension is fixed at l = round(mn/(m+n)), so the total number of binary parameters equals what UQ or BCQ would use; p is called the pseudo bit width.
• Solving the optimization. The exact problem is NP-hard, so the paper solves it term by term: the residual (what is left of the target matrix after the already-computed terms) becomes the target of the next term. Within each term, the binary matrices and the real coefficients are optimized alternately.
• Binary half. With coefficients fixed, powers of binary variables are reduced using y² = y so the objective becomes a PUBO. The authors extend Annealed Mean Field Descent — originally derived for QUBO — to general PUBO, deriving a KL divergence between the mean-field distribution and the canonical distribution and approximating the entropy term with a second-order Taylor expansion around 0.5. Variables are relaxed to continuous values in [0,1], optimized with annealed gradient-like updates, and finally binarized by rounding to the higher-probability value.
• Real-valued half. With the binary matrices fixed, the four coefficients per term are obtained in closed form by inverting a 4×4 Hessian, exploiting the convexity of the squared-error objective.
• Hyperparameters. Throughout all experiments: T_init = 0.2, T_fin = 0.005, η = 0.06, ζ = 4, N_step = 50,000. UQ's scaling factor and bias are optimized by grid search (details in Appendix A.2); BCQ follows a published implementation.
• Benchmark setup. Five matrices are used: a Gaussian random matrix, a weight matrix from DeiT-S, an inter-city distance matrix from TSPLIB, a matrix of 128-dimensional SIFT feature vectors, and a red channel matrix from an ImageNet image. Each is standardized to zero mean and unit variance before quantization. Nine methods are compared: SVD, SVD + p-bit UQ, UQ, BCQ, VQ, VQ + p-bit UQ, E_8 LVQ, 8-bit UQ + JPEG, and BQQ.
• PTQ pipeline. Weights are first quantized in a data-free manner by minimizing BQQ reconstruction error, with group-wise quantization to limit the number of scaling parameters. Optionally, a lightweight correction step then refines only the bias and layer-normalization parameters — keeping everything else fixed — by minimizing the normalized squared error between the original and quantized model logits, using a small set of unlabeled calibration images. Group sizes are 384×384 for DeiTs and 96×96 for Swins, 100×96 for the final classification layer, and 384×384 (DeiT-S) or 784×784 (DeiT-B) for the linear patch embedding; Swin's convolutional patch embedding uses channel-wise UQ. Correction uses Adam at learning rate 0.001 for 15 epochs with minibatch size 16 and 2048 (DeiTs) or 1024 (Swins) calibration samples.

Why This Matters

• Research impact: The paper reframes low-bit quantization as a bilinear/quadratic decomposition problem rather than a scalar-level assignment problem, and connects it to the combinatorial-optimization literature (PUBO, QUBO, mean-field annealing). It also advances AMFD from QUBO to general PUBO, which is of interest beyond quantization. The paper claims it is the first to achieve practical accuracy (e.g., 72% ImageNet top-1 on DeiT-base) with data-free PTQ for ViTs at a 2-bit-equivalent model size.
• Real-world applications (as the paper frames them):
  • Deploying deep neural networks on edge devices with sharply reduced storage and memory footprint.
  • Reducing memory usage in retrieval systems that rely on high-dimensional embeddings and approximate nearest neighbor search.
  • Compressing large training datasets so that large-scale learning scales better.
  • Enabling quantization when training data is unavailable due to privacy constraints or data access limitations (the data-free setting), and when only a small amount of unlabeled calibration data is available (the calibration-based setting).
• Industry relevance: Data-free and calibration-based PTQ are exactly the regimes where companies cannot ship or re-collect the original training data, and where 2-bit weight storage meaningfully cuts memory and data movement. Group-wise scaling keeps the auxiliary parameter count low, which matters for real deployment budgets. The authors do note one practical caveat: on image data, JPEG still wins on memory-versus-error, so transform-based pipelines remain competitive.

Future Directions

• Combining BQQ with transform-based compression. The paper suggests that integrating BQQ with transform-based approaches (like the discrete cosine transform used by JPEG) could improve compression efficiency, given JPEG's better trade-off on the ImageNet image matrix.
• Beyond weight-only quantization. The study deliberately quantizes weights only; extending BQQ to activations, or to joint weight-and-activation quantization, is a natural next step toward fuller inference-cost reduction.
• Alternative parameter allocations. The authors fix the intermediate dimension l to match UQ/BCQ parameter counts and note that a different route is to adjust the ratio between l and the number of stacks p; this trade-off is left unexplored in the paper.
• Stronger solvers and PTQ-specific optimization. Since the core minimization is NP-hard and the current solver is a greedy, alternating heuristic, better PUBO solvers or objectives that explicitly target activation error (rather than weight reconstruction error) are open questions for closing the remaining gap to first-order PTQ at 3 and 4 bits.
• Other application domains. The paper points to accelerating ANN-based retrieval systems and improving the scalability of large-scale learning as settings where the generality of BQQ could be tested.

Target Audience

Researchers and engineers working on model compression, low-bit quantization, and efficient inference — particularly those dealing with Vision Transformers or data-free/calibration-based PTQ, where the 2-bit regime is otherwise extremely difficult. It is also relevant to readers interested in combinatorial optimization for machine learning, since the binary subproblem is cast as PUBO and solved with an extended AMFD procedure. Readers without a background in quantization or binary optimization will find the paper dense; a working knowledge of UQ, BCQ, low-rank decomposition, and basic annealing-style optimization will make it substantially more accessible.

Authors’ abstract

This paper proposes a novel matrix quantization method, Binary Quadratic Quantization (BQQ). In contrast to conventional first-order quantization approaches, such as uniform quantization and binary coding quantization, that approximate real-valued matrices via linear combinations of binary bases, BQQ leverages the expressive power of binary quadratic expressions while maintaining an extremely compact data format. We validate our approach with two experiments: a matrix compression benchmark and post-training quantization (PTQ) on pretrained Vision Transformer-based models. Experimental results demonstrate that BQQ consistently achieves a superior trade-off between memory efficiency and reconstruction error than conventional methods for compressing diverse matrix data. It also delivers strong PTQ performance, even though we neither target state-of-the-art PTQ accuracy under tight memory constraints nor rely on PTQ-specific binary matrix optimization. For example, our proposed method outperforms the state-of-the-art PTQ method by up to 2.2\% and 59.1% on the ImageNet dataset under the calibration-based and data-free scenarios, respectively, with quantization equivalent to 2 bits. These findings highlight the surprising effectiveness of binary quadratic expressions for efficient matrix approximation and neural network compression.