N-Gram Memories at Two Bits Quantizing Lookup Tables in Large Language Models

Abstract

Conditional memory expands language-model capacity through selective lookup, but the full embedding table must remain available for every possible input. We introduce Conditional Program (CP), a compressed representation that reconstructs only the rows an input requests. CP represents each row by a short code and a local scale, with a reconstruction program shared across the table. We instantiate this representation with a Gaussian trellis, norm restoration and independently decodable row records. CP's two-bit code lowers output KL by 41–63% relative to 2-bit round-to-nearest. Analysis across three trained n-gram memory families shows that Gaussian-like coordinate statistics coexist with learned relationships among rows; at matched storage budgets, the shared trellis outperforms the fitted codebooks and low-rank residual variants we test. For DeepSeek, it reduces table storage from 203 GB to 51 GB, leaving room for larger workloads when the table is kept on GPU.

Key numbers

1. The problem: a huge table, read a few rows at a time

Conditional memory adds capacity without a proportional increase in per-token compute: a model hashes input n-grams into row addresses and reads only those rows from a large embedding table. DeepSeek-V4.1-Flash, Qwen3.8-Flash-Next and LongCat-Flash-Lite all carry such tables — 202.7 GB, 102.4 GB and 62.8 GB respectively. Moving them from GPU to host memory changes where that cost is paid without reducing it.

Weight quantization methods are built for dense matrices. A lookup table is different: storage must shrink across the whole table, but each request touches only a handful of rows. A format that couples rows inside larger tiles saves bytes yet forces the runtime to fetch and decode unrelated data on every lookup.

2. Conditional Program

CP stores each row e_i as a short code c_i and a local scale α_i, and reconstructs it with a decoder shared by the whole table: ê_i = α_i · f(c_i). Three design choices follow from the access pattern and the row statistics.

• Shared Gaussian trellis. Normalized rows accumulate many small, weakly dependent training contributions, so their coordinates look approximately Gaussian. CP encodes them in their stored coordinates with a Gaussian HYB bitshift trellis (tail-biting), without an extra rotation.
• Norm restoration. Instead of the least-squares scale, which shrinks rows whose direction is imperfectly decoded, CP sets α_i = ‖e_i‖ / ‖f(c_i)‖, preserving the magnitude the model consumes.
• Independent row records. Each code and its bf16 scale form one addressable record. A fused kernel fetches and decodes only the requested rows and hands them to the unchanged readout in the original lookup order.

3. Downstream quality at two bits

We compress only the lookup tables and evaluate 40 tasks across commonsense, knowledge, reading comprehension, multilingual understanding, and math and code. Removing the table shows how much each model relies on it; CP keeps most of that benefit at roughly a quarter to an eighth of the storage.

Selected columns from Table 1 of the paper (scores 0–100; Overall equally weights five task-group means). Table GB includes scales and offsets. The paper also reports RTN 3-bit, QTIP and CP at 1.5 bits, and all 40 tasks in the appendix.

4. Output fidelity across storage budgets

Task scores can hide behavioral drift, so we also measure per-token KL(p_orig ‖ p_quant) over six text domains. At two bits CP lowers KL by 41–63% relative to RTN and by a further 3–9% relative to a QTIP-style trellis with one scale per table. CP at 2.5 bits approaches RTN 3-bit with less storage, and at higher rates it beats NVFP4 and MXFP4 while using less memory.

5. What matters in the design

A shared trellis beats fitted codebooks. Frequently read rows do share structure — 16 fitted directions capture 10–33% of their energy against a 6–10% Gaussian reference. Yet at a matched 2.10 bpp on Qwen, the shared trellis (KL 0.0198) outperforms vector quantizers fitted to the table (0.0226–0.0238), and explicit mean or principal-component terms buy little for the storage they cost.

Restore the norm, not the least-squares fit. With identical codes and storage, the norm-restoring scale gives lower output KL than the least-squares scale on all three models (e.g. 0.0327 vs. 0.0349 on Qwen, 0.0426 vs. 0.0462 on LongCat). Minimizing reconstruction error is not the same as preserving model behavior. Within-row rotation shows no resolved benefit.

6. Serving

Selective lookup. Replaying 4,096-token DeepSeek lookups on one H200, CP's row records complete in 0.190 ms from HBM versus 0.221 ms for a tile-window decoder over QTIP's tiled layout, and in 6.54 ms versus 10.78 ms from pinned host DRAM over PCIe.

Workload capacity. On four H200s, the DeepSeek table drops from 50.7 GB to 12.7 GB per GPU. Prefill for 8 × 4k tokens falls from 64.66 s to 13.27 s, and a 512-sequence decode batch and a 64k-token prefill that run out of memory with FP8 tables now fit. On eight GPUs, CP frees 19.0 GB per GPU, raising the largest tested decode batch from 1,024 to at least 2,048 and prefill from 96k to at least 128k tokens.

Scope. Results cover post-training compression of three models with hashed lookup tables and may not extend to other memory architectures. When GPU memory is already sufficient, complete inference steps show little speed improvement in our implementation.

Citation

@article{han2026ngram,
  title   = {N-Gram Memories at Two Bits: Quantizing Lookup Tables in Large Language Models},
  author  = {Han, Donghoon and Jung, Minseop and Kwak, Dong Woo and Lee, SeungJae and Lee, Junhoo},
  journal = {arXiv preprint arXiv:2610.21810},
  year    = {2026}
}