MiSTiQ: MicroScaling Trellis Quantization for Extreme KV Cache Compression

Ofir Gordon, Lior Dikstein, Paul Balanca, Idan Achituve, Douglas Orr, Hai Victor HabiarXiv 2026 · arXiv

TL;DR

MiSTiQ is a novel quantization framework that achieves extreme KV cache compression—down to ~1.25 bits per element—without sacrificing the speed of hardware-accelerated low-precision math. By combining trellis-coded quantization with MicroScaling (MX) formats, it outperforms state-of-the-art baselines in both perplexity and reasoning accuracy on models like Llama-3 and Qwen-3.

What Problem Does This Paper Address?

As Large Language Models (LLMs) handle increasingly massive contexts (think 100k+ tokens), the "KV cache"—the memory used to store previous keys and values during inference—becomes a massive bottleneck. It eats up GPU memory, limits how many requests a server can handle simultaneously, and slows down generation.

Existing solutions often face a "speed vs. precision" trade-off. Vector Quantization (VQ) can reach very low bit-widths but requires massive codebooks that hardware cannot store efficiently. Furthermore, most methods dequantize data back into high-precision floating-point (like FP16) to perform attention math, which negates the computational benefits of using low-precision hardware.

Methods

The authors introduce MiSTiQ (MicroScaling Trellis Quantization), which acts as a drop-in replacement for standard vector quantizers. Its architecture rests on three pillars:

  1. Trellis-Coded Storage: Instead of using an explicit, giant lookup table (codebook), MiSTiQ uses a trellis structure. This allows the model to represent a massive space of possible reconstructions using a small, stateful bitshift rule. To find the best path through this trellis, they employ an approximate beam search during encoding.
  2. Direct MX-Format Reconstruction: MiSTiQ is designed to reconstruct values directly into MicroScaling (MX) formats. MX formats use a shared scale for a block of elements, allowing hardware to perform dot products in extremely low precision (like 4-bit or even 2-bit) without dequantizing to higher precision first.
  3. MX-Hash Functions: To bridge the gap between the trellis and MX formats, the authors derived "MX-Hash" functions. These functions map trellis states to reconstruction values by accounting for the specific "MX-Gaussian" distribution that emerges when data is block-normalized.
Figure 1. MicroScaling trellis quantization overview. (a) Inputs are scaled blockwise before beam search on the bitshift trellis. (b) Trellis-state bits are mixed and mapped through the scale-dependent inverse CDF to form MX-Gaussian reconstruction values. The distribution diagrams are schematic.

Datasets

The researchers evaluated MiSTiQ across several rigorous benchmarks:

  • WikiText-2: Used to measure language modeling perplexity.
  • LongBench: A suite of seven tasks (QA, summarization, etc.) designed to test long-context understanding.
  • GSM8K: A benchmark for mathematical reasoning, tested in a "decode-heavy" chain-of-thought setting.
  • Models: Evaluations were performed on Llama-3.1-8B-Instruct and Qwen3-8B.

Key Insights and Ideas

  • The "MX-Gaussian" Shift: Standard quantization assumes a Gaussian distribution. However, the authors discovered that once you apply block-scaling (as required by MX formats), the marginal distribution of the elements changes significantly. MiSTiQ's hash functions are specifically tuned to this new distribution.
Figure 3. Comparison between the standard Gaussian distribution and the MX-Gaussian marginal distribution for a block size of 32 with E2M1 scaling.
  • Joint Optimization: Rather than picking a scale and then quantizing, MiSTiQ performs a "Relaxed Joint Scale Search." It refits the block scales during the beam search, ensuring the scale and the trellis path are perfectly optimized for each other.
  • Mixed Precision Sensitivity: The paper confirms that "Keys" are generally more sensitive to quantization than "Values." MiSTiQ leverages the flexibility of the trellis to allocate more bits to keys while keeping the overall average bit-rate extremely low.

Key Results

MiSTiQ consistently outperformed existing vector quantization methods like NSNQuant and VecInfer, especially in the "extreme" compression regime:

  • Extreme Compression: At roughly 1.25 bits per element, MiSTiQ achieved significantly lower perplexity on WikiText-2 and higher accuracy on GSM8K compared to baselines.
  • Long-Context Superiority: On LongBench, MiSTiQ (using the NVFP4 format) achieved the highest average scores across both Llama-3 and Qwen-3 models.
  • Scaling Efficiency: As shown in the results, MiSTiQ's advantage becomes even more pronounced as the bit-rate drops below 1.5 bits per element.
Perplexity comparison showing MiSTiQ maintaining much higher accuracy than NSNQuant as the bit rate decreases.

Limitations and Future Work

While MiSTiQ is powerful, the authors note a few areas for growth:

  • Gaussian Assumption: The current hash functions assume the input data is Gaussian. While this is often true for LLM activations after certain transformations, real-world data can be "peakier" or have outliers. Future work could involve adapting the hash functions to empirical data distributions.
  • Encoding Complexity: Beam search is more computationally expensive than simple rounding during the encoding phase (when the KV cache is first written). While decoding is very fast, reducing the encoding overhead remains a goal.
  • Beyond KV Caches: The authors suggest that this combination of trellis quantization and MX formats could be highly effective for weight quantization, where the encoding happens offline and can afford even more intensive search.

Summary updated

Abstract

Modern large language models (LLMs) increasingly support longer contexts and serve more concurrent requests, increasing both sequence lengths and batch sizes. Both trends increase KV-cache size and memory traffic during inference. KV-cache quantization reduces these costs, with recent approaches using codebook-based vector quantization to achieve extremely low bit widths. However, hardware constraints limit codebook size, and most methods reconstruct the cache in higher-precision floating-point formats for attention, limiting the computational benefits of quantization. To address these limitations, we introduce MiSTiQ, a drop-in replacement for codebook-based vector quantizers that combines trellis-coded storage with microscaling (MX) formats for low-precision computation. We combine trellis quantization with beam search to encode the KV cache over large reconstruction spaces without large codebooks. To support MX computation, we derive MX-Hash functions that generate reconstruction values directly in the target MX element format. These functions use the scale-conditioned marginal distribution of block-normalized Gaussian inputs. On Llama3 and Qwen3, MiSTiQ achieves lower WikiText perplexity and higher GSM8K accuracy than the evaluated baselines across several block-scale formats at approximately 1.25 effective bits per element. With NVFP4, it also achieves the highest LongBench average on both models.
BibTeX
@misc{gordon2026mistiq,
  author = {Ofir Gordon and Lior Dikstein and Paul Balanca and Idan Achituve and Douglas Orr and Hai Victor Habi},
  title = {{MiSTiQ: MicroScaling Trellis Quantization for Extreme KV Cache Compression}},
  year = {2026},
  eprint = {2611.21216},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.21216},
}
Figure