What is Conditional Program?

It is a compressed format for conditional-memory lookup tables. Each row is stored as a short code and a scale, and one shared trellis decoder rebuilds a row only when an input requests it. At two bits per value the paper reports the DeepSeek table shrinking from 203 GB to 51 GB.

Why can't an ordinary weight quantizer compress a lookup table?

It can shrink the table, but dense-weight schemes often encode values together, so reading one row means decoding neighbouring data. A lookup table is read one row at a time at unpredictable addresses, so the format must keep each row independently decodable.

What does norm restoration do?

It sets each row's scale so the decoded vector has the same length as the original, instead of the length that minimizes squared error. The least-squares choice shrinks vectors whose decoded direction is off, and the model reads length as well as direction.

How does this relate to KV-cache or weight quantization?

It uses the same ingredients, low-bit codes and trellis decoding, but for a different access pattern. Weights are read in bulk and KV entries are appended and re-read; lookup rows are read sparsely by hash address, which is why per-row records matter.

LLM· 2026-10-20

N-Gram Memories at Two Bits — Row-addressable lookup-table quantization — What does it mean?

TL;DR

What is it: The N-Gram Memories at Two Bits paper (arXiv 2610.21810, posted October 15, 2026) introduces Conditional Program, a way to store the huge n-gram lookup tables of conditional-memory LLMs at 2 bits per value while keeping every row independently readable.
Why it’s needed: These tables add model capacity without adding per-token compute, but the whole table must sit in memory for every possible input; for the DeepSeek model the paper studies it is 203 GB, which crowds out batch size and context length on the same GPUs.
vs previous: Ordinary weight quantization encodes values together, and the QTIP tiled layout the authors adapted as a baseline spreads one row across several code fragments, which makes a single-row lookup costly; Conditional Program gives each row its own short code plus one scale, decoded by one shared trellis, so a lookup touches only the rows it needs.

Jargon

Conditional memory: A lookup table added to a model so each input retrieves a few learned rows instead of running more computation. Capacity grows with table size, while per-token compute barely changes.
N-gram lookup table: A table whose row addresses come from hashing the last few tokens (an n-gram). Different n-grams can hash to the same row, so a row mixes several training signals.
RTN (round-to-nearest): The simplest quantizer: round every value independently to the closest allowed level. It is the 2-bit baseline the paper's accuracy numbers are measured against.
TCQ (trellis-coded quantization): Storing a short code per value and decoding it through a small state machine, so neighbouring values are quantized jointly. See XOR-Trellis for the weight-quantization version.
Norm: The length of a row vector. Two vectors can point nearly the same way and still differ in length, and the model reads both direction and length.
KL divergence (output KL): A measure of how far the compressed model's next-token probabilities drift from the original model's. Lower is better; it tracks what the model actually says, not just how close the numbers are.
Pinned host DRAM over PCIe: Ordinary CPU memory locked in place so the GPU can read it across the PCIe link. Much roomier than GPU memory, but each access is slower.
QTIP: A trellis-based weight quantizer for dense matrices. The paper adapts its tiled layout to lookup tables as a comparison baseline.

The news. On October 15, 2026, researchers at Dnotitia and KAIST posted N-Gram Memories at Two Bits: Quantizing Lookup Tables in Large Language Models. They compress the n-gram lookup tables used by DeepSeek, Qwen and LongCat to about two bits per value, cutting the DeepSeek table from 203 GB to 51 GB, and report that this lets the same GPUs run larger batches and longer prompts. Read the paper →

A menu with millions of dishes

A conditional-memory model keeps a very large table beside its normal layers. For each token, the last few tokens are hashed into a handful of row addresses, and only those rows are fetched and mixed into the hidden state. Think of a restaurant whose menu lists millions of dishes: each customer's order names a few, and the kitchen cooks only those. That is why the idea is attractive: capacity grows with the menu, but the work per customer stays small.

The cost is the pantry. The kitchen must be able to cook any dish on the menu, so every recipe has to be stored, even though one order touches only a tiny part. In the paper's DeepSeek setup each token requests 48 rows across two Engram layers, out of a table that takes 203 GB at FP8. Moving the table to CPU memory only moves the bill: it avoids GPU memory but makes every lookup cross the PCIe link.

Smaller storage is not the same as cheaper lookup

The obvious fix is to quantize the table like model weights. The paper argues this misses a difference in how the data is used. Dense weights are read in bulk by a matrix multiply, so encoding many values together is fine. A lookup table is read one row at a time, at unpredictable addresses. If a compression scheme ties rows into a larger decoding unit, reading one row means fetching and decoding its neighbours too. A smaller table does not imply a cheap sparse lookup. The paper's comparison baseline shows the problem: QTIP's tiled layout, which the authors adapted to lookup tables, spreads each row across several code fragments, so they had to build a tile-window decoder just to read the needed bit windows.

One cookbook, one recipe card per dish

Conditional Program (CP) makes the restaurant analogy literal. Each row e_i is stored as a short code c_i and a scale α_i, and rebuilt as α_i · f(c_i), where the decoder f is the one cookbook shared by the whole table. Cards are filed singly, so an order pulls three cards and the other cards are never opened.

The cookbook is a Gaussian trellis. The authors reason that a row's direction is built from many small, weakly dependent training contributions, so after normalizing its coordinates look roughly Gaussian (a central-limit argument, offered as intuition; the paper also finds learned relationships between rows that a pure Gaussian view does not capture). They then use trellis-coded quantization: the encoder searches once, offline, for a low-error path through a shared state machine and stores the path's transition symbols as the code, and the decoder rebuilds the vector from those symbols with a small shared lookup table and arithmetic. Unlike QTIP, CP applies no rotation to the rows.

The portion tag: restore the length, not just the direction

One detail matters more than it looks. A least-squares scale picks the length that minimizes squared error, and when the decoded direction is slightly off, that length shrinks the vector. CP instead sets α_i = ‖e_i‖ / ‖f(c_i)‖, restoring each row's original norm even though that raises plain coordinate error. The reason is that the row passes through the model's readout, so its length changes the signal the model receives. Numerical closeness and model behaviour are different measures, which is why the paper judges compression by output KL against the original model and by absolute task scores, not by reconstruction error alone.

DeepSeek, 4 H200 GPUs	FP8 (original)	NVFP4 (4-bit)	CP 2-bit	Source
Table memory per GPU (GB)	50.7	27.6	12.7	Paper, Table 5a
Prefill, 8 sequences × 4k tokens (s)	64.66	13.26	13.27	Paper, Table 5a
Decode, batch 8 (ms/step)	795.7	788.9	792.9	Paper, Table 5a
Prefill, 64k tokens (s)	out of memory	59.81	18.23	Paper, Table 5a

Where the gigabytes and the milliseconds go

Start from the paper's DeepSeek table: 768.0M rows, each 256 values wide, stored in FP8, so 256 bytes per row. A CP record costs the code bits plus one 16-bit scale per row, so the rate is b + 16/d bits per value. With b = 2 and d = 256 that is 2 + 16/256 = 2.0625 bits per value, or 2 × 256 + 16 = 528 bits = 66 bytes per row. Then 768.0M × 66 bytes ≈ 50.7 GB, which matches the paper's 203 GB → 51 GB (its 203 GB original is the measured FP8 footprint, a little above the raw 196.6B-value count) and the 50.7 GB → 12.7 GB per GPU it reports when four GPUs share the tables. That roughly fourfold cut is what frees room for batch size and context.

Now the access side. The paper replays 4,096 tokens that each request 48 rows, so 4,096 × 48 = 196,608 row lookups per replay. From pinned host memory over PCIe, CP finishes them in 6.54 ms against 10.78 ms for the tile-window decoder, roughly 33 ns against 55 ns per row (derived arithmetic). With the table in GPU memory the gap is small, 0.190 ms against 0.221 ms, so the independent-record layout helps most when the table sits across PCIe.

What the paper does not show yet

The accuracy claim is relative: output KL falls 41–63% versus 2-bit round-to-nearest, not versus the full-precision table, and the paper says most (not all) task scores stay close to the original across 40 tasks. The serving numbers come from one model family on H200 GPUs: the four-GPU timings are means over three runs, the eight-GPU capacity result (largest decode batch 1,024 → at least 2,048; prefill 96k → at least 128k tokens) is a single run per setting, and the large FP8 prefill gap (64.66 s against 13.27 s) reflects memory pressure, since decode at batch 8 is within noise across formats. The lookup comparison also pits CP's encoded tables against a tiled baseline the authors adapted themselves, using random payloads. It is a preprint with no independent replication yet.

Goes deeper in: LLM Internals → Quantization → What to Quantize

Related explainers

XOR-Trellis — trellis-coded quantization — the same trellis idea applied to dense model weights instead of lookup rows
Qwen3.8-Flash-Next n-gram embedding offload — the other way to shrink the GPU bill for the same kind of table: move it off the GPU and prefetch
TF-Engram SSD-backed phrase memory — hiding slow-tier lookups behind decode

Frequently Asked Questions

Check what you knowMap your AI & GPU knowledge across every track — free, role-based