Repository navigation
TurboQuant: A Paper Crashes Storage Stock Prices? MNN Runs It on Mobile #4351
wangzhaode
announced in
Technical Blog
Replies: 0 comments
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Uh oh!
There was an error while loading. Please reload this page.
I. Problem Background
Over the past few days, a quantization paper from Google called TurboQuant (posted on arXiv in April 2025, accepted by ICLR 2026) has suddenly gone viral in the community. No earnings miss, no supply chain disruption—yet the stock prices of two memory chip giants, Micron and Western Digital, plummeted in response. A mere hint of "we don't need that much GPU memory" was enough to rattle the market (though some suspect it was used as a pretext for shorting storage stocks). Soon after, someone filed issue #4321 on MNN's GitHub, asking us to support this quantization method. MNN has always focused on on-device inference, where phone memory is at a premium, and we ourselves urgently need to optimize KV Cache memory usage. So I read the paper carefully and adapted and optimized the implementation to match on-device compute characteristics.
Why has this paper drawn so much attention? Because it hits the core pain point of large model inference: KV Cache memory usage.
During LLM inference, each generated token must attend to the Key/Value vectors of all previous tokens. These vectors are cached in the KV Cache, and memory usage grows linearly with context length. For Qwen3-4B with 8K context, the KV Cache alone consumes about 2 GB. If we can compress fp16 KV Cache down to 3~4 bits, memory savings reach 30%~60%.
The question is: how do we compress further without breaking the model?
TurboQuant offers a mathematically elegant and engineeringly simple solution: first use an orthogonal rotation to transform the statistical distribution of vectors into a "known shape," then quantize using an optimal codebook pre-computed for that distribution. No training data needed, no calibration set needed, codebooks directly hard-coded—the entire quantization process is purely online computation, zero data dependency.
This article breaks down the scheme from three dimensions: algorithm principles, MNN engineering implementation, and on-device experiments.
II. Paper Analysis
2.1 The Full Flow in One Diagram
The figure below shows the complete TurboQuant quantization process for a 32-dimensional block:
The entire process can be summarized in three lines of pseudocode:
De-quantization reverses the process: look up codebook → inverse rotation → multiply by norm.
Each step has a clear purpose:
Key insight: Step ② is the core. The rotation not only "scatters outliers" (which QuaRot also does), but more importantly makes the statistical distribution of each post-rotation coordinate precisely known—enabling us to pre-compute information-theoretically optimal quantization codebooks rather than using suboptimal uniform quantization.
2.2 Why Rotation Makes the Distribution Known
This is the most crucial insight of the entire algorithm.
Globe analogy: You mark a point on a globe (the direction of the original vector after normalization), then randomly spin the globe (multiply by an orthogonal matrix). No matter where you originally marked, after spinning, the point's position on the sphere is completely random—equivalent to picking a point uniformly on the sphere.
Mathematically: the normalized vector lies on a unit sphere, and multiplying by a random orthogonal matrix is equivalent to a uniform random rotation on that sphere. After rotation, each coordinate's distribution is determined by pure geometry:
This is the Beta distribution, whose shape depends only on the dimensionality d and is completely independent of the input vector.
Intuitive understanding: On a d-dimensional unit sphere, points satisfying "j-th coordinate = t" form a (d-2)-dimensional lower-dimensional sphere with radius √(1-t²), whose "area" is proportional to (1-t²)^((d-2)/2). The closer t is to 0, the larger the lower-dimensional sphere and the higher the probability; as t approaches ±1, the lower-dimensional sphere shrinks to a point and the probability tends to zero. This is the geometric origin of the Beta distribution.
The figure below shows the shape of the Beta distribution at different dimensionalities, along with the Lloyd-Max optimal codebooks designed on top of it:
High-dimensional effect: the higher the dimensionality, the more concentrated the distribution is around 0. When d=128 (typical head_dim), each coordinate's standard deviation is only ≈ 1/√128 ≈ 0.088, and the Beta distribution essentially degenerates to a Gaussian N(0, 1/d).
Key corollary:
2.3 Lloyd-Max Optimal Codebook: 1D k-means
Once we know the exact distribution of each coordinate, we can compute the information-theoretically optimal codebook using the classic Lloyd-Max algorithm.
Lloyd-Max is essentially 1D continuous k-means:
From the codebook figure above, an important characteristic is visible: dense at the center, sparse at the edges. This is exactly Lloyd-Max's advantage over uniform quantization—allocating more codebook resources to regions with higher probability density.
Since the distribution formula is known, we can compute precisely via numerical integration—no training data needed, no calibration set needed. Codebooks can be directly hard-coded:
The paper proves a theoretical upper bound on MSE: MSE ≤ 2.7 / 4^b, with the information-theoretic lower bound being 1/4^b—only a 2.7x constant gap—close to theoretically optimal.
2.4 Biased Inner Product and QJL Correction
In Attention, what we truly care about is not vector reconstruction error (MSE), but the accuracy of Q·K inner products. An MSE-optimal quantizer is biased when estimating inner products—the inner product is systematically shrunk:
As shown, at 3-bit the bias is only 4%, and at 4-bit it is nearly unbiased (1%). For practical 3~4 bit quantization, this bias is small enough that no additional correction is needed.
For extremely low bit (1~2 bit), the paper proposes a two-stage method: use (b-1) bits for MSE quantization, and the remaining 1 bit for QJL (Quantized Johnson-Lindenstrauss) unbiased inner product correction. QJL is a 1-bit scheme based on random projection sign-taking—it does not pursue reconstruction accuracy, but guarantees unbiased expectation of inner product estimates.
III. MNN Engineering Implementation
The MNN implementation code is in this commit, which includes TQ3 (3-bit) and TQ4 (4-bit) KV Cache quantization modes, with core code in
TurboQuant.hpp(approximately 780 lines).This implementation was completed with assistance from Claude. Initially I asked Claude whether this approach would be valuable for MNN, and it judged directly from the paper—concluding that the random orthogonal matrix and QJL would significantly slow down inference, making it not cost-effective on-device. At my suggestion, we made two key adjustments: replacing the random matrix with a Hadamard transform, and implementing only 3/4-bit to completely sidestep QJL. Final measurements showed minimal performance impact, and decode speed even improved slightly.
Below I analyze several key engineering decisions.
3.1 Hadamard Replaces Random Orthogonal Matrix
The paper uses a random orthogonal matrix Π for rotation, requiring O(d²) storage and O(d²) multiply-add operations—prohibitively expensive in practice.
MNN draws on QuaRot's approach, using a Walsh-Hadamard Transform (WHT) instead. Why can a Hadamard matrix replace a random orthogonal matrix? Because a Hadamard matrix is itself an orthogonal matrix with only ±1 elements (rows and columns are pairwise orthogonal after normalization), satisfying the orthogonality conditions required by TurboQuant. Combined with sign flipping (a deterministic ±1 sequence generated via golden-ratio hashing, applied per-coordinate), this introduces sufficient pseudo-randomness to scatter the input structure.
This substitution is extremely friendly to on-device compute:
The butterfly structure of the WHT is shown below (8-point example; actual implementation uses 32-point = 5 stages):
Choice of block_size = 32: rather than applying WHT to the entire head_dim (e.g., 128), we split into 32-dimensional blocks processed independently. Each block has its own norm (L2), which partially compensates for approximation errors from the lower block dimensionality. A 32-dimensional WHT requires only 5 butterfly stages (log₂32 = 5), making it extremely fast and memory-friendly.
3.2 First Stage Only (MSE Quantization)
The paper's full scheme is two-stage (MSE + QJL), but MNN implements only the first stage:
Rationale: 3-bit bias is only 4%, 4-bit only 1%—negligible in practice; eliminates QJL random projection matrix storage and extra computation; with the same b-bit budget allocated entirely to MSE, reconstruction precision is higher.
3.3 Memory Layout and Attention Fusion Optimization
Compact bit-packed storage
Storage format per 32-dimensional block:
The 3-bit index packing packs 8 three-bit values into 3 bytes (24 bits) via bit shifts and mask operations for compact storage. For 4-bit, two indices simply share one byte.
Compression ratios: TQ3 ≈ 4.6x, TQ4 ≈ 3.6x.
Key path: rotated-domain dot product (skip inverse WHT)
When computing Q·K, using the orthogonal matrix property
⟨Q, Π^T·y⟩ = ⟨Π·Q, y⟩, we pre-rotate Q into the WHT domain, then directly compute dot products with quantized K in the rotated domain. K does not need inverse WHT—each KV token only needs to unpack indices, look up the codebook, and do multiply-add. The WHT transform of Q is done once per head at the start of computation and reused for all KV tokens of that head.Value path: rotated-domain accumulation (N inverse WHT → 1)
When computing Softmax(QK)·V, we first accumulate the weighted sum of all V in the rotated domain (each V only needs codebook lookup multiplied by attention weight), then perform the inverse WHT just once at the end. Reduced from N inverse WHTs (N = KV sequence length, up to thousands) to 1, with significant performance benefit.
Quantization write path
The KV Cache is quantized in-place during each Attention write—reading 32 values from fp16/fp32 source into a float buffer, computing the L2 norm and normalizing, applying the forward WHT, searching the codebook for indices, and packing into compact format for cache write. No separate fp16 buffer is needed.
3.4 NEON SIMD Acceleration
On aarch64 platforms, MNN applies NEON vectorization optimizations to three hot paths:
vqtbl1q_u8(vector table lookup instruction) to convert 8 three-bit indices into 8 fp16 codebook values at once, avoiding scalar lookups one by onevshlq_u32(variable shift) combined with masks, extracting 4 three-bit indices per SIMD instructionvcgtq_f32(vector comparison) for 7 boundary comparisons, accumulating comparison results to obtain the index, processing 4 values in parallelIn practice, NEON optimizations yield limited prefill improvement (+1~5%), because the prefill bottleneck lies in upstream GEMM computation rather than quantization itself.
IV. Experimental Results and Analysis
We tested two models on macOS ARM64 (Apple Silicon): Qwen3-4B (2.34 GiB) and Qwen3-0.6B (355 MiB), using FlashAttention + ChunkPrefill (chunk=256), 4 threads.
4.1 Accuracy: PPL (Perplexity)
4.2 Speed and Memory
Qwen3-4B detailed data:
Key conclusions:
24% at 4K, 3336% at 8K—the longer the context, the greater the advantage34x slower: bottleneck is in quantization computation (WHT + codebook search), an inherent overhead of online quantization4.3 Output Quality
Question: "What is the capital of China?" (greedy decoding, max_new_tokens=100)
4.4 Why Did the Small Model Collapse?
The mathematical guarantees of TurboQuant still hold on the 0.6B model, but the paper implicitly assumes a prerequisite: the model has sufficient redundancy to absorb quantization noise.
The root cause was discovered by measuring the actual KV Cache value distribution:
Triple reasons for small model collapse:
4.5 Memory Savings on the 0.6B
Although accuracy collapses on the 0.6B, the memory compression itself is effective—TQ3 saves 62% memory at 8K context (3343→1278 MB), more than the 36% savings on the 4B, because KV Cache accounts for a higher proportion of total memory in smaller models.
Interestingly, the 0.6B TQ3 decode speed actually exceeds baseline (217.64 vs 170.99 tok/s), because the compressed KV Cache substantially reduces memory bandwidth requirements.
4.6 Comprehensive Comparison of Approaches
Across accuracy, memory, and speed:
4.7 Experimental Conclusions
Usage recommendations:
V. Summary
TurboQuant is indeed an effective KV Cache quantization scheme—elegant theory, simple implementation, no calibration data dependency, and it achieves a reasonable memory-accuracy balance on models of 4B and above. It shares similarities with QuaRot and other rotation-based quantization methods (both use orthogonal transforms to scatter outliers), but TurboQuant goes further: leveraging the known post-rotation distribution to design information-theoretically optimal codebooks.
But objectively, it is no silver bullet. AI's demand for storage and compute remains enormous and continues to grow—models are getting larger, contexts are getting longer, and multimodal is becoming mainstream. TurboQuant provides an effective compression method at the specific point of KV Cache, but compared to other quantization methods, it does not constitute a breakthrough generational gap. True relief of storage bottlenecks still requires joint progress across model architecture, quantization algorithms, and hardware co-design.
References
All reactions