When do lookups beat multiplies? Choosing GEMM paths for ultra-low-bit LLMs

Extreme quantization can change more than model size. Once weights come from a tiny alphabet, table lookup becomes a plausible alternative to direct arithmetic but only in the right operating regime.

Quantization is often introduced as a storage and bandwidth optimization. Fewer bits mean a smaller model, less weight traffic, and a better chance of fitting a large language model (LLM) on a power- and memory-constrained device. But at sufficiently low bit widths something more fundamental can happen. The weight alphabet becomes small enough that alternative compute primitives become plausible.

Many neural-network layers ultimately reduce to general matrix-matrix multiplication (GEMM). Instead of multiplying every activation by every weight, a kernel can precompute the possible partial sums for a small group of activations. Packed weight codes then select those values from a lookup table, and the selected values are accumulated into the output. This is the basic idea behind lookup-table GEMM, or LUT-GEMM.

The interesting question is not whether lookup is universally faster. It is not. The practical question is: when do table construction, reuse, packing, and hardware throughput line up well enough for lookup to beat a mature multiply-accumulate path?

 

Figure 1: Two execution paths for ultra-low-bit weights: classical GEMM decodes weights and performs multiply-accumulate; LUT-GEMM precomputes activation-dependent values and uses packed weight codes to look them up.

Two ways to compute the same matrix product

Consider the familiar operation Y = A x W. A has shape M x K, W has shape K x N, and Y has shape M x N. A classical GEMM kernel traverses K and accumulates products. Whether the implementation is organized around inner or outer products, the path is regular: load, multiply, accumulate, and reuse data through a carefully tiled loop nest.

That regularity is a major advantage. Modern CPU kernels have had years of optimization around dense arithmetic, including packing, cache blocking, prefetching, and high-throughput multiply-accumulate instructions.

LUT-GEMM reorganizes the work. Take a group of g activations along K. If each weight can take one of C values (alphabet cardinality), that activation group has up to C^g possible partial sums. The kernel builds those values once, then uses each grouped weight code as an index while it traverses output columns.

A useful way to remember the economics is: N amortizes the table setup, M replicates it, and K determines how many groups must be processed. In other words, LUT-GEMM is not simply 'GEMM without multiplies'. It is a setup-plus-reuse algorithm.

Figure 2: Classical GEMM and LUT-based GEMM.

Why fewer arithmetic instructions do not guarantee a faster kernel

The first cost is table construction. The table nominally grows as C^g. Increasing g can replace more arithmetic per lookup, but it also increases the number of entries to build and the amount of state the kernel must manage. A grouping choice that looks attractive from an operation count can lose once setup and movement are included.

The second cost is decoding the packed weights. Ultra-low-bit formats trade storage density against execution regularity. A simple two-bit representation wastes some code points for ternary weights {-1, 0, 1}, but its fields align naturally with byte and vector operations. Denser formats can pack three ternary weights into five bits or four constrained weights into five bits, but then sign handling, non-aligned fields, or sparsity rules become visible in the online loop.

Published implementations make this trade-off concrete. Bitnet.cpp's TL1 design groups two ternary weights in a regular 2-bits-per-weight (bpw) layout. TL2 reaches about 1.67 bpw by grouping three weights and exploiting sign table symmetry but requires separate sign processing. Sherry reaches 1.25 bpw by combining ternary weights with a 3:4 sparsity constraint. Each format saves weight traffic differently, and each creates a different decode problem.

The third cost is the lookup-and-accumulate path itself. A general-purpose CPU can provide an efficient table lookup, but the looked-up result might still need widening or sign adjustment before accumulation and storage. If these stages are fragmented across too many instructions, lookup throughput is not the limiting factor. Feeding and consuming the lookup becomes the bottleneck.

There is also a working-set issue. Every independent activation row needs its own table state. Processing more rows in parallel can therefore increase register or cache pressure. Even if the table is small, feeding several tables efficiently is still difficult.

Figure 3: Packing density versus online decode work for three ternary formats. TL1 uses 9 LUT states; TL2 reduces 27 nominal combinations to 14 effective states through symmetry; Sherry reduces 81 nominal combinations to 32 through its 3:4 sparsity constraint and to 16 effective states through symmetry.

Shape is a first-class parameter

LLM inference naturally moves through different operating regimes. During prefill, many prompt tokens are processed together. M is relatively large, dense kernels can achieve high utilization, and the classical GEMM path is a robust default. During autoregressive decode, one or a few tokens are processed at a time. The operation moves toward general matrix-vector multiplication (GEMV), parallelism is lower, and memory traffic and energy per generated token become more prominent.

That makes decode a more plausible LUT regime but not an automatic win. The output width N must still provide enough reuse to repay table construction. The packed format must decode cheaply. The lookup and accumulation path must sustain the output loop. If any of those conditions fails, direct arithmetic can remain faster even at extremely low bit widths.

Not every transformer operation is equally amenable either. Feed-forward and projection layers use static weights, and their shapes move from GEMM-like during prefill toward GEMV-like during decode. They are natural places to evaluate lookup-based kernels. Attention-score computation is different because both Q and K are data-dependent. Replacing those multiplies with a weight-code lookup requires a different formulation rather than a drop-in kernel substitution.

A practical decision rule

The decision can be reduced to four questions:

1. Is the operation in a large-M, high-utilization prefill regime? If yes, start with a classical GEMM kernel as the baseline.
2. Is reuse across N high enough to amortize LUT construction? If not, the setup cost is difficult to amortize.
3. Is the packed weight format regular enough to decode without turning the inner loop into shifts, masks, extracts, and sign fixes? If not, storage density might be working against execution efficiency.
4. Can the lookup-plus-accumulate path produce and consume enough results per cycle? If not, the surrounding online path becomes the bottleneck.

When all four conditions line up, LUT-GEMM becomes a strong candidate. Energy can move the boundary further: a lookup-based path might be attractive even when peak throughput is lower, provided it reduces energy per generated token. That choice must be measured end to end, including table construction, decode, accumulation, and data movement.

Complementary processing paths, not one universal winner

The likely outcome is not a single kernel that replaces GEMM everywhere. It is phase-aware and shape-aware selection between complementary compute paths.

Dense matrix, inner-product and outer-product engines remain the natural throughput path for large, well-utilized problems. Lookup support becomes more interesting for compressed, low-cardinality data and smaller-M regimes. Arm SME2 illustrates how these capabilities can coexist. Multi-vector and matrix instructions strengthen dense arithmetic. LUTI2 and LUTI4 use packed 2-bit and 4-bit indices to retrieve values from the architected ZT0 lookup table.

The software challenge is to keep the whole pipeline balanced. A fast lookup instruction does not by itself create a fast LUT-GEMM kernel. The same is true for a fast multiply instruction does not by itself create a fast GEMM. Packing, decode, table residency, accumulation, tiling, and dispatch all matter..

Start with the representation, then choose the compute path

At moderate quantization levels, the main deployment gains are often smaller storage, lower bandwidth, and lower-precision arithmetic. At ultra-low bit widths, the representation can go further and enable a different algorithmic compute path.

For each target layer and phase, record M, N, K, the weight alphabet cardinality C, the grouping factor g, the packed decode sequence, and the true lookup-plus-accumulate throughput of the platform. Benchmark the classical and LUT paths on representative prefill and decode shapes rather than relying on arithmetic counts alone.

The most useful question is no longer only 'how many bits per weight?' It is 'what compute path does this representation make possible, and on which shapes does it pay off?'

Further reading