🤖 machine learning

Hurwitz Quaternion Multiplicative Quantization for KV Cache Compression

The paper introduces Hurwitz Quaternion Multiplicative Quantization (HQMQ), a calibration-free method that compresses KV caches by representing 4-element chunks as quaternions quantized via a product of a fixed Hurwitz group and random secondary codebooks, achieving near-fp16 accuracy with up to 5.05× compression across diverse modern LLMs while eliminating the need for calibration.

Original authors: Kabir Swain, Sijie Han, Daniel Karl I. Weidele, Mauro Martino, David Cox, Antonio Torralba

Published 2026-05-28

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Kabir Swain, Sijie Han, Daniel Karl I. Weidele, Mauro Martino, David Cox, Antonio Torralba

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: The "Memory Hoarder"

Imagine a Large Language Model (LLM) like a brilliant but forgetful librarian. When you ask it a long question, it has to remember every word you've said so far to answer correctly. In computer terms, this memory is called the KV Cache.

For very long conversations, this memory cache gets huge. If the librarian tries to remember every detail in high-definition (like a 4K movie), it fills up the computer's RAM instantly. This forces the computer to use slower storage or crash, making the conversation stop.

To fix this, engineers try to "compress" the memory, like turning a 4K movie into a smaller MP4 file. However, previous methods of compression were like using a blunt knife: if you cut the file size too much (below 4 bits), the movie becomes unwatchable (the AI starts making nonsense). If the AI model has "outliers" (weird, extreme numbers in its data), standard compression breaks completely, causing the AI to hallucinate wildly.

The Solution: HQMQ (The "Smart Compass" System)

The authors propose a new method called HQMQ. Instead of just shrinking the numbers, they treat groups of data as quaternions (a type of 4D mathematical compass).

Here is how it works, broken down into three simple steps:

1. The "24-Point Star" (The Primary Codebook)

Imagine the direction a piece of data is pointing is like a compass needle. Instead of trying to store the exact angle (which takes too much space), the authors use a special, pre-made "star" with 24 points (called the Hurwitz group).

The Analogy: Think of this as a standard set of 24 fixed directions (North, Northeast, etc., but in 4D). No matter where the data points, you just snap it to the nearest of these 24 "perfect" directions.
The Magic: Because these 24 points are mathematically perfect and evenly spaced, you don't need to train the AI to learn them. They are just "hard-coded" rules, like the letters on a keyboard.

2. The "Random Spin" (The Secondary Codebook)

The 24 points aren't enough to cover every possible nuance. So, the authors add a second layer: a small, random "spin" for each specific part of the AI.

The Analogy: Imagine you have a globe with the 24 points painted on it. Now, imagine you can spin the globe randomly for every single sentence the AI processes.
The Result: When you combine the fixed 24 points with a random spin, you get thousands of unique directions ( $24 \times \text{random spins}$ ).
Why it's cool: The paper claims you don't need to train this random spin. Because of the math behind it, any random spin works almost as well as a trained one. It's like saying, "You don't need to practice throwing darts; just throw them randomly, and the math guarantees you'll hit the board." This saves time and data.

3. The "Outlier Safety Net" (Med3×)

Some AI models (like Qwen) have "outliers"—data points that are 100x or 200x larger than normal. Standard compression tries to squash these huge numbers down to fit, which destroys the data.

The Analogy: Imagine you are packing a suitcase. Most clothes are normal size, but you have one giant, awkwardly shaped teddy bear. If you try to force the bear into a small box, it rips the box.
The Fix: HQMQ has a rule: "If a number is too big (more than 3 times the average), don't squeeze it. Just keep it in its original, high-quality form (fp16) and mark it with a tiny flag."
The Result: Only about 1–3% of the data gets this special treatment, so the memory savings are still massive, but the "giant teddy bears" don't break the system.

What Did They Prove?

The authors tested this on five different modern AI models (Mistral, Llama, Qwen, etc.). Here are their main findings:

It Works Without Training: Unlike other methods that need a "calibration" phase (where the AI studies data to learn how to compress), HQMQ works immediately with random settings.
It Saves Massive Space: They managed to shrink the memory cache by 5 times. For example, a 128k-context cache for a 70-billion-parameter model (which usually takes 43 GB) was shrunk to 8.5 GB. This means you could run a massive AI on a single consumer graphics card instead of a supercomputer.
It Handles "Bad" Data: On models with extreme outliers (like Qwen), standard compression failed completely (the AI's error rate exploded). HQMQ + the "Safety Net" fixed this, bringing the AI's performance back to near-perfect levels.
Speed: They built a special "fused" engine that reads the compressed data and decodes it instantly while the AI is thinking. This means the AI doesn't slow down; it just uses less memory.

The Bottom Line

HQMQ is like a universal, pre-made compression kit for AI memory. It uses a clever mathematical trick (multiplying a fixed 24-point star by a random spin) to store directions efficiently without needing to learn anything first. It also has a safety switch for weird data spikes.

The result? You can run much longer, smarter conversations on much smaller computers without the AI losing its mind.

Technical Summary: Hurwitz Quaternion Multiplicative Quantization for KV Cache Compression

Problem Statement

The memory cost of the Key-Value (KV) cache during long-context inference in Large Language Models (LLMs) often dominates computational costs. Storing K and V vectors in FP16 can consume tens of gigabytes for sequence lengths exceeding 32k. While scalar quantization (e.g., int8, int4) reduces this cost, performance degrades significantly below 4 bits, and int2 typically breaks the model. Furthermore, modern architectures (specifically those with Grouped Query Attention, like Qwen2.5 and Qwen3) exhibit "outlier-heavy" attention patterns where a small fraction of K-chunks have extreme magnitudes. Standard scalar quantization fails catastrophically in these scenarios, leading to perplexity (PPL) spikes of 10,000+ points. Existing vector quantization approaches often require calibration data or fail to handle these outliers effectively.

Methodology: Hurwitz Quaternion Multiplicative Quantization (HQMQ)

The authors propose HQMQ, a calibration-free method that treats every 4-element chunk of K or V vectors as a quaternion $x \in \mathbb{H}$ . The method decomposes the vector into a radius $r = \|x\|$ and a unit direction $u = x/r$ on the 3-sphere $S^3$ .

1. Multiplicative Codebook Composition

Instead of learning a single large codebook or using additive composition, HQMQ constructs a joint codebook via the multiplicative product of two components:

Primary Codebook ( $P$ ): A fixed set of 24 unit Hurwitz quaternions, corresponding to the vertices of the 24-cell on $S^3$ (the binary tetrahedral group $2T$ ). These vertices are pairwise separated by $60^\circ$ and form a closed multiplicative group.
Secondary Codebook ( $S$ ): A set of $S$ random unit quaternions, initialized per (layer, head, role) without calibration.

The effective codebook is the set $C = \{q_p \cdot q_s \mid q_p \in P, q_s \in S\}$ . This yields $24S$ effective codewords while storing only $S$ parameters. The direction $u$ is quantized to the codeword $c \in C$ that maximizes the inner product $\langle u, c \rangle$ .

2. Theoretical Justification for Random Initialization

The paper argues that calibration is unnecessary because left-multiplication by a unit quaternion is an isometry on $S^3$ . Randomly selecting $S$ effectively rotates the fixed $2T$ group, creating $S$ disjoint isometric copies that tile $S^3$ quasi-uniformly. Proposition 3.1 establishes that this random multiplicative packing achieves an optimal covering rate of $O((24S)^{-1/3})$ on $S^3$ , matching the theoretical bound for optimal sphere packings up to constants.

3. Median-Multiplier Outlier Extraction (Med3×)

To address the "outlier-heavy" architectures where chunk norms vary by factors of 80–280×, the authors introduce a per-batch outlier extraction step:

Compute the median chunk norm $r_{med}$ across the current batch.
Identify chunks where $r > C \cdot r_{med}$ (with a fixed constant $C=3$ ).
Store these outliers in full FP16 (with a 1-bit flag) and quantize the remaining "bulk" chunks using HQMQ.
This step requires no calibration data and is stable across different architectures.

Key Contributions

New Codebook Composition Rule: A multiplicative quantization scheme based on the finite Hurwitz group $2T$ , differing from additive VQ (CommVQ) or flat learned VQ (VPTQ).
Calibration-Free Deployment: The method relies on the geometric properties of Haar-random rotations of the 24-cell, eliminating the need for per-model calibration passes. Empirical results show end-task perplexity variation of $<0.14\%$ across random seeds.
Robust Outlier Handling: The Med3× extraction mechanism enables the use of low-bit quantization on outlier-heavy models (like Qwen2.5/3) where naive int4 fails completely.
Empirical Validation: Evaluation across five diverse models (Mistral-7B, Llama-3-8B, Qwen2.5-7B, Qwen3-8B, and gpt-oss-20b) demonstrating Pareto dominance over naive integer baselines.

Experimental Results

Perplexity and Quality

Mistral-7B & Llama-3-8B: HQMQ achieves near-lossless compression at $\sim5$ bits, matching FP16 perplexity within 0.02–0.03 points. At 3.79 bits, it matches FP16 downstream zero-shot accuracy (PIQA, HellaSwag, ARC-Easy).
Qwen2.5-7B & Qwen3-8B (Outlier-Heavy): Naive int4 collapses to PPLs of 17,000–18,000. HQMQ + Med3× recovers FP16 quality (PPL $\approx$ 9.0–9.7) at $\sim5$ bits, representing a $\sim1,900\times$ quality improvement over naive int4 at fewer bits.
gpt-oss-20b (Sparse MoE): HQMQ Pareto-dominates the naive baseline by 3–3.5× at matched bits.

Comparison with Baselines

vs. Naive Int: HQMQ outperforms naive int4 by 3–1,900× in PPL across all models at matched bit rates.
vs. KIVI (Calibrated Baseline): At 3.79 bits, HQMQ matches the calibrated KIVI-4 (which uses $\sim4.5$ bits) within $\sim1$ point on CoQA and 2.3 points on GSM8K, using 16% fewer bits and zero calibration.
vs. Spherical/Vector Quantization: HQMQ outperforms spherical baselines (e.g., TurboQuant-style) and additive VQ baselines with random codebooks.

Memory and Latency

Compression: HQMQ delivers up to 5.05× KV cache compression. For a Llama-3-70B model with a 128k context, the cache shrinks from 43 GB (FP16) to 8.5 GB, enabling inference on a single 24 GB consumer GPU.
Latency: A fused Triton kernel decodes K/V directly within the attention loop. On a production decode workload, the fused kernel maintains a constant latency of $\sim0.033$ ms regardless of context length, offering a 7.4× to 82.9× speedup over a naive "fake-quant" pipeline that dequantizes the entire cache per step.

Significance and Claims

The paper claims that HQMQ provides a "clean algebraic recipe" for KV cache quantization that bridges the gap between theoretical vector quantization and practical deployment. Its primary significance lies in:

Enabling Low-Bit Quantization on Outlier-Heavy Models: It is the first method to make sub-5-bit quantization viable for architectures like Qwen2.5/3, where standard methods fail.
Eliminating Calibration Overhead: By leveraging the geometric properties of the Hurwitz group, it removes the need for data-dependent calibration, making it suitable for proprietary or rapidly deployed models.
Practical Efficiency: The combination of high compression ratios (up to 5×) and a fused kernel that avoids memory bandwidth bottlenecks makes long-context inference practical on consumer hardware.

The authors note limitations, specifically that HQMQ does not compete with trained codebooks (like CommVQ) in the sub-3-bit regime and that its performance on extremely long contexts (beyond 128k) or specific architectures like Multi-head Latent Attention (MLA) requires further investigation. However, within the 3–5 bit regime, it establishes a new state-of-the-art for calibration-free, outlier-robust KV compression.