Structured Transforms for Low-Overhead Quantization of Language Models

Daria Cherniuk; Alexander Rudikov; Boris Kashin; Ivan Oseledets

Source-linked AI summary

Structured Transforms for Low-Overhead Quantization of Language Models

Daria Cherniuk, Alexander Rudikov, Boris Kashin, Ivan Oseledets

arXiv:2609.11687v1Sep 10, 2026cs.CL

TL;DR

Low-bit LLM quantization needs methods that reduce weight cost without the practical bottlenecks of prior Kashin and codebook approaches. The paper combines alternating greedy Kashin updates, randomized DCT transforms, and analytic clustering initialization; its pipeline is competitive across several model families and remains stable in stress tests.

Problem
Prior Kashin quantization suffered from convergence failures, inconsistent four-peak structure, and costly multi-restart clustering, while low-bit PTQ must avoid substantial deployment overhead.
Method
The method uses vector-level alternating greedy Kashin decomposition with a sign-randomized DCT, closed-form cluster centers, and OPTQ- or QuIP-style integration.
Results
The resulting JAX pipeline is competitive with OPTQ, QuIP, QuIP-RG, and a fine-tuning- and vector-quantization-free QuIP# variant at 4-bit per channel, while Kashin-DCT remains robust where other pipelines diverge or produce NaNs.
Takeaways & Limitations
Bounded-infinity-norm factorization provides a structured route to two 2-bit factor codes per channel with favorable computational scaling and numerical robustness.
Takeaways & Limitations
The evaluation does not cover activation-aware baselines or alternative learned and residual-stream rotations, which are left for future work.

Abstract

from arXiv · show

We revisit Kashin-decomposition-based weight quantization for large language models and propose an improved algorithm with stronger convergence properties and structured, efficient orthogonal transforms. The method retains the core factorization of each weight into two components -- one with bounded infinity norm and the other with bounded infinity norm after an orthogonal transformation -- but replaces the dense random orthogonal matrix with a sign-randomized Discrete Cosine Transform (DCT), reducing the per-iteration cost from $\mathcal{O}(N^2)$ to $\mathcal{O}(N \log N)$. The proposed greedy algorithm with alternating updates guarantees the four-peak distribution required for stable 2-bit clustering of each factor and admits closed-form initialization of cluster centers, removing the multi-restart k-means bottleneck of prior work. Composed with OPTQ-style sequential error compensation and QuIP-style incoherence preprocessing, the resulting JAX pipeline is competitive with OPTQ, QuIP, QuIP-RG and a fine-tuning- and vector-quantization-free variant of QuIP# at 4-bit per channel on OPT, Llama-2 and Pythia, with favorable wall-clock scaling. The bounded-$\ell_\infty$ factorization is also notably robust: on stress configurations where QuIP variants diverge to four-digit perplexity (Pythia-6.9B) or abort with NaNs in LDL back-substitution (Mistral-7B), Kashin-DCT remains numerically stable and stays close to FP16 baseline. At inference time, each weight decomposes into two 2-bit factor codes per channel that are structurally suited to native-2-bit hardware.

1 Introduction

The paper revisits Kashin-decomposition quantization to address convergence, four-peak structure, and clustering bottlenecks while retaining rigorous vector-level analysis. It introduces alternating greedy updates, structured DCT transforms, and closed-form clustering initialization.

The method addresses prior Kashin quantization's convergence failures, inconsistent four-peak distributions, and slow multi-restart clustering.
The alternating greedy algorithm fixes update order in blocks of four, guaranteeing four-peak factor distributions and enabling 2-bit clustering.
A sign-randomized DCT replaces dense random orthogonal matrices, reducing transform cost to O(N log N) with no stored matrix.
Analytic centroid locations initialize clustering and eliminate multi-restart k-means, reducing quantization overhead.

2 Related Work

Related work spans practical PTQ baselines, second-order error-compensation methods, randomized rotations, and vector-codebook approaches. These methods improve compression or accuracy but introduce trade-offs in fine-tuning, codebook storage, kernel compatibility, or runtime.

PTQ reduces pretrained-model weights without retraining, while uniform scalar and NF4 quantization remain common deployment baselines.
OPTQ and QuIP use sequential or LDLQ-style error compensation, with QuIP adding incoherence preprocessing to improve theorem conditions.
QuIP# uses randomized Hadamard transforms for faster incoherence processing but relies on vector quantization and fine-tuning.
Vector-codebook methods achieve strong sub-4-bit compression but require learned codebooks and do not fuse as cleanly with standard matmul kernels.

3 Problem Setting

Kashin decomposition bounds the infinity norms of two transformed factors, making them suitable for quantization and often producing four symmetric peaks. The paper retains vector-level guarantees, replaces dense transforms with randomized DCT, and uses structured updates for analytic clustering centers.

The original greedy algorithm requires storing N^2 transform entries and performs O(N^2) operations per iteration.
Figure 2 compares residual convergence and factor distributions for the original and partitioned greedy schedules.
Kashin decomposition factorizes weights into components with bounded infinity norms, whose four symmetric peaks support clustering-based quantization.
3.1 Closed-form k-means initialization: The proposed schedule alternates update blocks so dominant factor updates land at analytic centroid locations ±c1 ± c2.
3.1 Closed-form k-means initialization: Closed-form centroid initialization removes multi-restart clustering and reduces clustering wall-clock time by roughly 10× on medium-sized models.

4 The Greedy Algorithm with Alternating Updates

The proposed partitioned greedy algorithm alternates updates between two dictionary halves in fixed four-step blocks, pairing convergence guarantees with four-peaked factor distributions and efficient DCT implementation.

4.1 Background: Replacing dense random orthogonal transforms with sign-randomized DCT-based operators reduces transform overhead while storing no dense matrix.The paper instantiates the orthogonal operator with the orthonormal DCT-II and reports O(N log N) transform cost.
4.2 Proposed Algorithm: Four-step alternating blocks preserve geometric residual decay while fixing the update schedule needed for analytic factor centroids.The partitioned method contracts each block’s residual norm by (1 − β(N))^1/2, with β(N) = α(N)^2/36, and iterating blocks yields geometric decay.
4.2 Proposed Algorithm: The algorithm applies two greedy updates from Q_N to u, followed by two from U_E,ΦQ_N to ˆv, then repeats this partitioned schedule.The reverse four-step ordering has the same residual norm at every block.
4.2 Proposed Algorithm: The fixed schedule places dominant updates at ±c_1 ± c_2, providing closed-form centroid locations for clustering the two factors.Because residual norms decrease rapidly, the first four iterations provide accurate approximations of the final peak locations.
4.3 Convergence Analysis: Unlike the matrix reformulation or original vector schedule, the proposed method produces four-peaked marginals for both u and ˆv, enabling well-separated 2-bit cluster centers.The matrix reformulation loses per-vector convergence, while the original vector method leaves the transformed factor spread out.

5 Experiments

Experiments evaluate the method across language-model families, datasets, tasks, and 4-bit baselines, showing sharper factor peaks and strong numerical robustness in stress configurations.

5.1 Factorization Experiments: Algorithm 1 reaches nearly the original greedy method’s convergence rate while producing markedly sharper peak definition on random-vector experiments.The comparison uses a vector drawn from N(0, 1).
5.1 Factorization Experiments: Figure 3 shows that only the updated algorithm yields distinctive peaks in both u and ˆv distributions, enabling stable cluster quantization.The matrix reformulation collapses the joint distribution, while the original vector algorithm leaves the transformed factor spread out.
5 Experiments: Across OPT, Llama-2, Mistral, and Pythia, evaluations use perplexity and zero-shot accuracy at 4-bit per-output-channel quantization against RTN, OPTQ, QuIP variants, and QuIP#.Results use WikiText-2, C4, HellaSwag, PiQA, and Winogrande, with three-seed means and standard deviations for most methods.
5.2 Quantization Results: On Pythia-6.9B, QuIP and QuIP-RG exceed 2000 WikiText-2 PPL, QuIP# reaches approximately 325, while Kashin-DCT+H obtains 20.6±1.6 at the same bit budget.OPTQ remains at 12.02 PPL in this stress test.
5.2 Quantization Results: On Mistral-7B, all QuIP variants abort with NaNs, whereas Kashin-DCT remains stable within approximately 0.3 Wiki-2 PPL of the FP16 reference at 8.63.The failure occurs during LDL back-substitution on the SwiGLU mlp.down_proj layer.

6 Conclusion

The paper resolves prior Kashin-quantization weaknesses with alternating updates, structured DCT transforms, and closed-form clustering, while delivering competitive 4-bit results and strong stress-test robustness. Its main scope boundary is that activation-aware baselines are not evaluated, although the decomposition can compose with orthogonal preprocessing.

Conclusion: Kashin-DCT+H is competitive with OPTQ, QuIP, QuIP-RG, and a fine-tuning- and vector-quantization-free QuIP# variant at 4-bit per channel across OPT, Llama-2, and Pythia.The pipeline also decomposes each weight into two 2-bit factor codes per channel for native-2-bit hardware.
Conclusion: Replacing dense random orthogonal transforms with sign-randomized DCT reduces per-iteration cost to O(N log N), while closed-form centers remove multi-restart k-means overhead.The DCT requires no stored dense matrix.
Conclusion: Kashin-DCT+H remains robust where QuIP variants diverge or abort and where OPTQ reaches approximately 380 Wiki-2 perplexity, attributed to bounded-ℓ∞ factors and adaptive codebooks.The stress configurations include Pythia-6.9B and Mistral-7B.
Conclusion: The evaluation does not cover activation-aware baselines such as AWQ, OmniQuant, or rotation-based methods, leaving those comparisons for future work.The paper states that rotation-based preprocessing can be substituted without changing the rest of the pipeline.

A Stress Tests on Pythia-6.9B and Mistral-7B

Stress tests show that Kashin-DCT variants remain numerically stable on Pythia-6.9B and Mistral-7B configurations where competing quantizers fail catastrophically or abort. The reported mechanism links competing failures to ill-conditioned Hessian processing and Kashin stability to bounded factors and residual-scaled centroids.

Pythia-6.9B: Kashin-DCT+H stays within an order of magnitude of OPTQ on Pythia-6.9B, while the QuIP family reaches perplexities in the hundreds-to-thousands.Table 2 uses 4-bit per channel and reports WikiText-2/C4 perplexity and zero-shot accuracies.
Mistral-7B: On Mistral-7B v0.1, Kashin-DCT+K and Kashin-DCT+H remain stable at 0.32 and 0.29 Wiki-2 perplexity above FP16, respectively, while GPTQ reaches approximately 380.The FP16 reference is 8.63, and the QuIP family aborts with NaNs.
Failure mechanism: QuIP aborts because near-zero LDLQ Cholesky diagonals amplify off-diagonals during normalization and overflow during back-substitution.The failure occurs at Mistral’s mlp.down_proj layer.
Stability mechanism: Kashin-DCT remains robust because residual-scaled analytic centroids follow inflated magnitudes while bounded-ℓ∞ factors keep clustering well-conditioned.The same mechanism is reported for stressed Llama-2-7B columns.

C Inference

Inference stores each layer as two 2-bit factor matrices plus a shared sign mask, with an orthogonal operator implemented by sign-masked DCT transforms. Depending on hardware, inference either reconstructs dense weights or uses a fused decomposed computation that preserves the 2-bit footprint.

Representation: The decomposed representation stores U and V̂ as two 2-bit factor matrices with a layer-shared sign mask defining P = IDCT ◦ Tε ◦ DCT.With orthonormal DCT-II, P is a symmetric involution.
Inference paths: Without native 2-bit GEMM, the system reconstructs W = U + P V̂ at load time and uses standard fp16 or 4-bit-dequantized matrix multiplication.This path avoids requiring specialized 2-bit kernels at inference.
Inference paths: With native 2-bit GEMM, the fused computation XU + (XP)V̂ keeps both factors in 2-bit storage and avoids fp16 weight expansion.The DCT cost is O(KN log N), below the O(KNM) matmul cost.
Hardware implications: Native 2-bit hardware aligns codebook lookup and 2-bit codes with addressing, register-packing, and shared-memory granularity.The decomposed form avoids some cross-lane shuffles associated with 4-bit dequantization.
Memory bandwidth: At 4 bits per channel, metadata contributes an effective rate of 4 + 64/N bits per weight, with the sign vector recoverable from a seed.Each factor contributes 2NM stored bits, and metadata uses 4M fp16 values per layer.

D Quantization Runtime

Quantization runtime scales more favorably for Kashin-DCT+H than for OPTQ or QuIP# as model size increases from Llama-2-7B to 13B. The comparison is measured on one H100 GPU at 4 bits per channel, excluding Hessian estimation.

Experimental setup: The measurements use a single NVIDIA H100 GPU, average three random seeds, and exclude Hessian estimation.The comparison covers OPTQ, QuIP#, and Kashin-DCT+H.
Scaling: Kashin-DCT+H runtime grows 1.18× from Llama-2-7B to 13B, versus 1.90× for OPTQ and 1.70× for QuIP#.The reported times are 1313.6 → 1544.9 seconds for Kashin-DCT+H, 229.9 → 437.1 for OPTQ, and 763.0 → 1298.0 for QuIP#.

E Proof of Proposition 1

The proof analyzes one four-step block of the partitioned greedy algorithm and shows that alternating updates reduce the residual under either of two conditions. Non-expansive later steps preserve the reduction, establishing the stated proposition.

Block structure: The four-step block alternates two atoms from QN with two from UE,ΦQN, reducing the convergence analysis to a single block.The residual starts at ρ0 = x and ends at r1 = ρ4.
Case 1: If condition (9) holds, the first greedy step contracts the residual, while the remaining three orthogonal projections are non-expansive.This yields the bound on ρ1 and carries it through the block.
Case 2: If condition (9) fails, condition (10) holds, so an analogous contraction follows using atoms from UE,ΦQN.The transformed inner-product identity permits the same greedy estimate for the second dictionary half.
Conclusion: The remaining projection and triangle-inequality estimates preserve the contraction, so the proposition's residual bound holds in all cases.The proof concludes by combining the case analysis with non-expansiveness.

F Proof of Theorem 2

The theorem proof iterates the block contraction to obtain geometric residual decay and then bounds the accumulated coefficients using normalized atoms and Cauchy–Schwarz.

Residual decay: Inductively, each four-step block contracts the residual by the factor established in Proposition 1, proving the theorem's first bound.The induction starts from ∥r0∥2 = ∥x∥2 ⩽ 1 and applies the block estimate to rk+1.
Coefficient bound: Each block contributes two atoms from QN and two from UE,ΦQN to the factors u and v.This decomposition organizes the coefficient bound over the four atomic steps.
Coefficient bound: Because every selected atom has norm √N and λ = ⟨ρ,w⟩/N, Cauchy–Schwarz bounds each coefficient using the entering residual norm.Atomic non-expansiveness and the residual decay from part 1 then control these coefficients block by block.
Coefficient bound: Summing the coefficients uses the uniform bound ∥w∥∞ = 1 for atoms in QN and the corresponding transformed-atom bound.The transformation preserves the relevant infinity-norm control in the stated setting.
Rate: The contraction parameter is β(N) = α2(N)/36 = R4(N)/(144 K4 N 2), with the displayed logarithmic specialization derived afterward.The proof substitutes the stated expression for β(N) into the resulting bound.