PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Donghoon Han, Minseop Jung, Dong Woo Kwak, SeungJae Lee, Junhoo Lee

arXiv:2610.21810v1cs.LGcs.CL

TL;DR

Conditional memory expands language-model capacity through selective lookup, but its full tables remain costly to store and dense-weight compression does not address their sparse access pattern. This paper introduces Conditional Program, which stores short row codes and local scales for reconstruction by a shared decoder. At two bits, CP reduces output KL relative to round-to-nearest quantization, while its smaller tables can support larger workloads under GPU memory pressure.

  • Problem

    Conditional memory expands model capacity through selective lookup, but full tables remain costly to store and dense-weight compression leaves its sparse access pattern unaddressed.

    Source: §1 · p. 1

  • Method

    Conditional Program stores short row codes and local scales, using a shared decoder to reconstruct the entries selected by each input.

    Source: §1 · pp. 1–2

  • Results

    At two bits, CP reduces output KL divergence by 41 to 63% compared with RTN and by a further 3 to 9% over QTIP.

    Source: §4.2 · p. 5

  • Takeaways & Limitations

    Under GPU memory pressure, smaller tables allow larger workloads and reduce prefill time.

    Source: §7 · p. 8

    The conclusions cover post-training compression of three models with hashed lookup tables and need not extend to other memory architectures, including token-indexed tables.

    Source: Limitations · p. 8

Abstract

from arXiv · show

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 203GB to 51GB, leaving room for larger workloads when the table is kept on GPU.

1 Introduction

Conditional memory offers language models additional capacity through selective lookup, but its full embedding tables still impose substantial storage costs. Conditional Program (CP) compresses those tables while reconstructing only requested rows, using a shared decoder and row-specific codes and scales.

1 Introduction

  • Conditional memory increases model capacity without proportional per-token computation, but its tables remain costly to store even when moved to host memory.Moving tables changes where storage costs are paid without reducing them.Source: §1 · p. 1
  • Each row uses a short code and local scale with a shared Gaussian trellis decoder, and independently stored records retain selective access.At two bits, the cited overview reports roughly four- to eightfold table compression.Source: §1 · pp. 1–2, Figure 1 · p. 2
  • CP exchanges storage across the full table for reconstruction work on the few entries selected by each input.The input determines which entries are reconstructed, preserving conditional memory’s selective use.Source: §1 · pp. 1–2
  • The paper evaluates downstream performance, compression fidelity, lookup costs, and workload capacity under GPU and host-memory placement.The introduction frames these evaluations as tests of CP’s practical trade-offs.Source: §1 · p. 2

2 Preliminaries

Conditional memory retrieves learned rows selected from input tokens, rather than computing over the full table. Compressing it therefore requires both reducing table storage and preserving efficient independent access and the information that retrieved embeddings contribute to model predictions.

2.1 Conditional Memory as Selective Lookup

  • N-gram conditional memory hashes input n-grams to row addresses, so retrieval can avoid scanning or computing over the whole table.Each token retrieves a fixed number of rows.Source: §2.1 · p. 2

2.2 Compressing Conditional Memory

  • A smaller compressed table may still be inefficient for sparse lookup if accessing one row requires fetching or decoding a larger block.The storage footprint and the cost of accessing an individual row are distinct quantities.Source: §2.2 · p. 2
  • Compression must reduce the full table’s footprint while reconstructing each requested row without decoding unrelated rows.The address function and remaining model parameters stay fixed.Source: §2.2 · p. 3
  • The objective is to minimize expected output divergence under a storage budget because reconstruction error alone may not predict changes in model outputs.Retrieved embeddings pass through the readout and later network layers, where errors of similar magnitude can have different effects.Source: §2.2 · p. 3

3 Conditional Programs

Conditional Program (CP) stores a short code and local scale for each row, then reconstructs requested rows with a shared function. Its implementation uses a Gaussian source model and trellis coding, restores row norms, and stores records independently for selective execution.

3.1 Conditional Program Representation

  • CP represents each row with a code and local scale, reconstructed by a function shared across the table.Only requested rows are reconstructed, exchanging storage across the table for computation on a small subset.Source: §3.1 · p. 3

3.2 Gaussian Source Modeling

  • CP models normalized row coordinates as a standard Gaussian source, giving different rows a common statistical basis for shared reconstruction.Row-specific codes capture each row’s individual contents.Source: §3.2 · p. 3

3.3 Encoding and Norm Restoration

  • Trellis coding selects a low-error path for each row, while norm restoration scales the decoded vector to match the original row’s norm.Restoring the norm can increase coordinate reconstruction error.Source: §3.3 · pp. 3–4

3.4 Independent Storage and Selective Execution

  • Each row’s code and scale form an independently addressable record that can be fetched and reconstructed without decoding unrelated rows.At inference, CP processes requested rows in the original lookup order and leaves the address function and downstream computation unchanged.Source: §3.4 · p. 4

4 Experiments

The experiments evaluate lookup-table compression across three n-gram memory models and 40 tasks, then examine output-distribution fidelity and CP design choices. CP reduces storage while largely preserving benchmark performance, and the analyses favor a shared trellis with norm restoration.

4.1 Experimental Setup

  • The evaluation compresses lookup tables only, holding other model components fixed, and spans 40 tasks across five categories, including GSM8K and HumanEval.Baselines include original tables, table removal, RTN, NVFP4, MXFP4, and a trellis variant with within-row rotation and a global scale.Source: §4.1 · p. 4

4.2 Results

  • Approximately 4–8× table compression retains most benchmark performance; CP largely preserves knowledge-task performance and outperforms RTN on Qwen and LongCat knowledge benchmarks while matching QTIP in paired evaluations.At 1.5 bits, storage falls further, although some tasks lose more performance.Source: §4.2 · pp. 4–5, Table 1 · p. 5
  • 41–63% lower output KL than 2-bit RTN; CP also reduces KL 3–9% versus QTIP, with an additional bf16 scale per row required for the latter improvement.At 2.5 bits, CP approaches RTN 3-bit fidelity with less storage; at higher rates, it has lower KL than four-bit floating-point formats while using less storage.Source: §4.2 · p. 5, Figure 2 · p. 6

4.3 Analysis

  • Across three models, CP achieves lower row reconstruction error than fitted VQ and better output fidelity at matched storage, despite shared structure among frequently accessed rows.Explicit mean and principal-component representations offer limited improvement relative to their storage cost.Source: §4.3 · pp. 5–6, Table 2 · p. 5, Table 3 · p. 6
  • Norm restoration consistently yields lower output KL than global or row-wise least-squares scaling across all three models; rotation shows no statistically resolved benefit, and frequency-based bit allocation does not consistently generalize across domains.The scale comparison uses identical trellis codes and storage budgets for the two row-wise alternatives.Source: §4.3 · p. 6, Table 4 · p. 6

5 Serving Efficiency

Serving tests measure selective lookup and the workload capacity unlocked by smaller GPU-resident tables. CP improves lookup latency and, under memory pressure, reduces prefill time and supports larger workloads.

5.1 Selective Lookup

  • 0.190 ms versus 0.221 ms on HBM and 6.54 ms versus 10.78 ms over PCIe: CP’s row-wise decoder is faster than tile-window decoding for the tested lookups.Each token requests 48 rows across two Engram layers; the PCIe comparison uses pinned host DRAM.Source: §5.1 · p. 7

5.2 Workload Capacity

  • 64.66 s to 13.27 s: on four GPUs, CP reduces representative-workload prefill latency and enables larger workloads that otherwise run out of memory.The FP8 tables occupy 50.7 GB per GPU versus 12.7 GB for CP; against NVFP4, CP reduces 64k-token prefill time from 59.81 s to 18.23 s, while decode times remain similar.Source: §5.2 · p. 7, Table 5 · p. 7
  • At eight GPUs, CP frees 19.0 GB per GPU; the largest tested successful decode batch rises from 1,024 to at least 2,048 sequences, and prefill capacity rises from 96k to at least 128k tokens.For smaller workloads, where memory pressure is limited, step times differ by at most 2.4%.Source: §5.2 · pp. 7–8

5 Serving Efficiency

  • CP’s row-wise representation supports selective lookup, while compact storage reduces GPU memory pressure, improving performance for memory-intensive serving and supporting larger workloads.The serving evaluation measures selective row reconstruction and the effects of reduced memory use on serving performance and workload capacity.Source: §5 · p. 6, §5.2 · p. 8

6 Related Work

Related work spans dense-weight quantization, embedding-table compression, and memory architecture or placement. CP instead numerically compresses existing hashed-table rows with a shared decoder while retaining independent row access.

LLM weight quantization

  • Unlike dense-weight quantization methods, CP applies Gaussian trellis coding to frozen lookup rows without rotation, restores each row’s norm, and stores rows independently for selective access.The passage contrasts CP with calibration-guided rounding or scaling, coordinate transformations, additive codebooks, trellis coding, and Gaussian-optimal grids.Source: §6 · p. 8

Embedding-table compression

  • Unlike embedding methods that train low-precision representations or model-specific corrective components, CP compresses already trained hashed tables using row values, a shared decoder, and no retraining or frequency-based bit allocation.The passage also distinguishes CP from CARVQ’s grouped residual vector quantization and per-model corrective MLP.Source: §6 · p. 8

Conditional-memory structure and placement

  • CP numerically compresses rows of an existing table, unlike methods that replace table structure during pretraining, address placement, share hash slots, or compute embeddings off-accelerator.The passage also distinguishes learned-key retrieval memories from the hashed-token tables studied here.Source: §6 · p. 8

7 Conclusion

The conclusion presents CP as a way to compress lookup tables while preserving independent access, with serving benefits when GPU memory is pressured. It also notes that complete inference steps show little speed improvement when memory is sufficient.

7 Conclusion

  • Two-bit CP codes reduce table storage roughly four- to eightfold across three hashed-memory models, with most reported task scores close to the originals despite task- and model-dependent losses.Under GPU memory pressure, smaller tables allow larger workloads and reduce prefill time.Source: §7 · p. 8
  • When memory is sufficient, complete inference steps show little speed improvement in the authors’ implementation.This qualifies the serving benefit of reduced table storage.Source: §7 · p. 8

Limitations

The paper bounds its conclusions by model and deployment coverage, and qualifies the generality of some analyses and serving measurements.

Coverage

  • The conclusions cover post-training compression of three models with hashed lookup tables and need not extend to other memory architectures, including token-indexed tables.Most downstream comparisons use two primary code rates; higher rates have less task coverage, and small task-score differences do not establish equivalence.Source: Limitations · p. 8

Analysis

  • Fitted-codebook and structured-residual output-KL comparisons use Qwen only; some equal-budget interpolations lack uncertainty estimates, and the Gaussian approximation does not explain how training produces the observed row statistics..Source: Limitations · p. 8

Deployment

  • Serving measurements use a single node and eager inference, so optimized engines may devote a different fraction of time to lookup; some configurations have one run and workload limits are not exact capacity thresholds.Access counts come from English web text, so frequency-based allocation and caching results may change with deployment distribution.Source: Limitations · p. 8

A.1 Models and task evaluation

The appendices specify the evaluation and quantization protocols, then report absolute and paired task comparisons. They also caution that benefit retained measures preservation of the table-removal gap, not accuracy relative to the original model.

A.1 Models and task evaluation

  • The 40 tasks span five groups, and every model sees the same frozen items; evaluation uses raw-text log-likelihood scoring and greedy generation.The groups are commonsense, knowledge, reading comprehension, multilingual, and math and code.Source: §A.1 · p. 11, Table 7 · p. 12

A.3 Quantizers and encoding

  • The appendix lists trellis settings and baseline quantizer formats, including four-bit NVFP4 and MXFP4 and groupwise RTN metadata.Qwen RTN’s scale and minimum remain fp32 although the reported rate counts them as bf16.Source: §A.3 · p. 11

B.1 Absolute scores and removal controls

  • Across 40 DeepSeek tasks, pooled accuracy changes by −0.07 points with CP, −0.34 with RTN 2-bit, and −12.0 with the table removed.Table 9 splits PopQA accuracy by entity-popularity bin, with bin 1 containing the rarest entities.Source: §B.1 · p. 11, Table 9 · p. 13

A.2 Output fidelity and statistics

  • Paired task differences use 10,000 item-bootstrap replicates, and intervals containing zero do not establish equivalence.Task scores and benefit retained use 2,000 item-bootstrap replicates; KL uses 2,000 chunk-bootstrap replicates.Source: §A.2 · p. 11, §B.2 · p. 12

B.2 Paired comparisons

  • Qwen improves over RTN 2-bit by 0.67 [0.27, 1.06] points and LongCat by 0.82 [0.23, 1.41] on the seven-task knowledge group; DeepSeek’s 0.40 [−0.04, 0.84] comparison includes zero.Paired comparisons with QTIP include zero, as do PopQA and combined GSM8K/HumanEval comparisons in every model.Source: §B.2 · p. 12

B.3 Benefit retained as a secondary measure

  • Benefit retained measures preservation of the table-removal score gap, not accuracy relative to the original model; it can exceed one and becomes unstable when original and removed scores are close.The main comparison therefore uses absolute scores and paired differences.Source: §B.3 · p. 12

C Full Rate–Distortion Results

The full rate–distortion results compare CP with quantization baselines on storage and output fidelity. The accompanying row analysis finds Gaussian-like coordinate statistics alongside shared directions and access-frequency skew.

C Full Rate–Distortion Results

D.1 Row statistics and access counts

  • Normalized within-row kurtosis differs from its Gaussian control by at most .02 for uniform and read-weighted samples, while 16 fitted directions explain 19%, 21%, 33%, and 10% of top-row squared norm across the listed settings.The dimension-based references are 6.25% for 256-dimensional rows and 10% for Qwen’s 160-dimensional rows.Source: §D.1 · p. 18, Table 15 · p. 18
  • The top 1% of rows receive 35%, 48%, and 33% of reads in DeepSeek, Qwen, and LongCat, while read-count correlations with coordinate magnitude vary by model and n-gram order.LongCat correlations are .53 for 2-grams, −.16 for 3-grams, and −.04 for 4-grams.Source: §D.1 · p. 18

D.2 Fitted codes and synthetic rank sweeps

The section tests trellis, fitted-code, and structured-code performance on trained and synthetic tables, then describes comparisons with published codes and scale variants. Results favor the shared trellis over fitted codebooks on trained tables, while synthetic low-rank structure can favor PCA codes.

D.2 Fitted codes and synthetic rank sweeps

  • Across frequency bins and hashed families, the shared trellis has relative row MSE .0724–.0728, versus .098–.099 for the 256 × 4 codebook and .091 for the 65,536 × 8 codebook.For Qwen, the mean-and-PC representation improves on the 2-bit trellis only with more storage; at its rate, an interpolated trellis-only curve predicts lower KL.Source: §D.2 · pp. 18–19, Table 16 · p. 19
  • At d = 256, rank-k synthetic tables pass the Gaussian-coordinate test for k ≥16, yet a PCA-basis code reaches .013 of trellis MSE for k = 64 at 2.06 bpp.For spiked full-rank tables, the structured-code/trellis MSE ratio is 1.19 at one-third spike energy and .94 at one-half; crossover is near .45–.5.Source: §D.2 · p. 19

D.3 Other published codes

  • With norm restoration on every code, the trellis has lower KL than E8P, AQLM, and HIGGS, with paired ratios .877, .875, and .836.The comparison is on Qwen in the shared benchmark at about 2 bpp.Source: §D.3 · p. 19, Table 17 · p. 19

E.1 Scale ablation across rates

  • The scale ablation compares removing rotation at global scale, adding a row-wise least-squares gain, then changing only the gain to restore each row’s original norm.The passage describes the comparison sequence and reports additional gain comparisons at other rates.Source: §E.1 · p. 19

E.2 Held-out gain test

The held-out tests show where norm restoration and allocation choices help, while analyses connect embedding error to downstream KL. Systems measurements show that two-bit CP reduces DeepSeek table storage, with cache and lookup benefits depending on placement and workload.

E.2 Held-out gain test

  • Norm restoration lowers held-out KL relative to LS by ratios of .904–.940 on LongCat and .944–.983 on Qwen web and code; Qwen multilingual and all DeepSeek intervals include 1.Test-curve optima fall at t = .92–1.30, while the primary predictor often misses them; the secondary predictor has the right sign in all five cells resolving an effect.Source: §E.2 · p. 20, Table 19 · p. 20

E.3 Rotation, allocation and protected rows

  • Frequency allocation benefits the read-count-matched web distribution but can hurt other domains; on DeepSeek, the top-10% tier improves geometric-mean KL by .9% while multilingual ratios rise.Qwen start-row protection improves five non-chat domains, but its chat estimate is noisy and its six-domain geometric mean is 1.008.Source: §E.3 · p. 21, Table 20 · p. 21, Table 22 · p. 23

F.1 Gaussian coordinates with a fixed Gram matrix; F.2 Fixed-shape gain and local output distortion

  • The fixed-Gram rotation argument makes Gaussian coordinates compatible with learned row geometry, while the local distortion analysis identifies conditions that can invalidate its approximation.Large distortion, expert-routing changes, or a poorly estimated metric can invalidate the local quadratic approximation; the construction does not explain how training produces Gaussian coordinates.Source: §F.1 · p. 21, §F.2 · pp. 22–23

F.3 Perturbations through the readout

  • At error energy 0.2∥e∥2, pure norm errors incur more KL than equal-energy direction errors, with a direction/norm ratio of .86 [.83, .88].Top-16 value-projection directions change the readout 1.6 times as much as bottom-16 directions, yet give slightly lower KL, ratio .92 [.88, .96].Source: §F.3 · p. 23

F.4 LongCat damage model

  • The LongCat damage model fits its 29 codec configurations to within about 10% and predicts held-out pure-direction edits, but fails on several norm-change cases.For S from 10^-5 to .3, measured KL is 0.89–1.01 times prediction; the model is fitted and checked on LongCat only.Source: §F.4 · p. 23, Figure 3 · p. 24

G.1 Records and lookup kernels

  • At 4,096 tokens, CP prefill is faster than tile windows by mean ratios of 1.160 in HBM and 1.648 from host DRAM, without a consistent HBM decode advantage.Randomized CP payloads retain similar prefill ratios, while the batch-64 ordering reverses in one of five runs with real codes.Source: §G.1 · p. 24, Table 24 · p. 25

G.2 Memory tiers and workload measurements

  • On four GPUs, two-bit compression leaves decode step time unchanged but can slow prefill when a large table otherwise leaves little HBM for activations.SSD reads pass through host memory on the test system, and the minimum read unit remains 4 KB per row.Source: §G.2 · pp. 25–26

G.3 Caching and host placement

  • At 12.9 GB, CP serves 70.7% of held-out reads from cache versus 50.6% for FP8, while compression leaves each missed row’s 4 KB read unchanged.The DeepSeek table shrinks from 202.7 to 50.7 GB, but lookup is under 1% of a forward step in the tested eager implementation, so full step time changes little.Source: §G.3 · p. 26, Figure 4 · p. 26

H Token-Indexed Tables (Gemma PLE)

Gemma’s token-indexed PLE tables have a small set of sensitive rows whose protection can substantially lower worst-domain KL. Tests also show that table statistics do not reliably predict model sensitivity, while layer-level norm adjustment has mixed effects.

Sensitive rows

  • At 2.0 bpp, keeping BOS and the top-100 token rows in bf16 costs 0.006 bpp and lowers worst-domain KL to .027 on E2B and .028 on E4B.These results are similar to QTIP with rotation on those models; on E2B-it, rotation is better, .126 against .140.Source: H Token-Indexed Tables (Gemma PLE) · p. 27, Table 26 · p. 27

Predicting model sensitivity

  • Per-layer kurtosis predicted an E4B-it rotation KL ratio of .21, but the measurement was .877; the authors report that this explanation was post hoc.For layer 10 without rotation, KL is .121 on E4B and .004 on E4B-it despite similar layer statistics.Source: H Token-Indexed Tables (Gemma PLE) · p. 27

Layer-level norm adjustment

  • Layer-mean norm adjustment raises worst-domain KL by 6.3% and 9.0% in two settings, but lowers it by 3.9–79.8% in the other five.This layer-level adjustment differs from CP’s per-row norm restoration.Source: H Token-Indexed Tables (Gemma PLE) · p. 27
Loading 2610.21810v1…