Score a document you never decompress.

The setup: 512 bytes → 20 bytes

Late-interaction search (ColBERT-style) stores hundreds of vectors per document. At dim 128 in float32 that's 512 bytes per token — the index dwarfs the text it indexes. nano-plaid's binary scheme keeps only the sign of each dimension:

The shape of the problem, for the rest of the class: one query of ~32 tokens, each an int8 row of 128 values, against thousands of candidate documents, each ~80 tokens of 128 bits. Per (query token, doc token) pair we need a dot product; per query token we keep the max; sum of maxes is the document's score (MaxSim).

Two quantizers, deliberately unequal

The document gets brutal 1-bit treatment because there are millions of document tokens. The query is tiny (32 rows) and scored thousands of times, so it can afford 8 bits — this asymmetry is the design (class 03, chapter 07, made the counting argument). Randomize the inputs and watch both encoders:

The identity: q · signs = 2P − T

Signs are ±1. Split the dot product into lanes where the bit is 1 (contribute +q) and lanes where it's 0 (contribute −q):

q·s = P − (T − P) = 2P − T

P = Σ q over 1-bits  ·  T = Σ q (already precomputed)

So the whole dot product collapses to one masked sum: add up the query values where the document has a 1. No decompression, no multiplies, no ±1 anywhere. Toggle the document's bits and watch the identity refuse to break:

ARM: expand to 0/1, then sdot

Class 01 showed sdot: 16 int8 products accumulated per instruction. Feed it the query on one side and the document's bits expanded to 0/1 bytes on the other, and sdot(q, bits) computes… exactly P. The identity does the rest. The only real work is unpacking 128 bits into 128 bytes — and NEON does it 16 bytes at a time:

x86: the psadbw heist

Plain AVX2 has no int8 dot-product instruction — that's an AVX-512 luxury. What it does have is psadbw: sum of absolute differences of unsigned bytes, built for video motion-search in the 1990s. Watch it get repurposed, stage by stage, on the same numbers as chapter 03:

Why this is beautiful: AND, psadbw, and paddq are all ancient, 1-µop, run-anywhere instructions. No AVX-512 required, no new silicon — just the observation that a masked sum is a sum, plus one bias trick to survive the unsigned-only diet. This is the kernel that GitHub's stock CI runners execute, measured at ~28× over the autovectorized fallback.

x86 deluxe: AVX-512 VNNI

Where it exists, vpdpbusd is sdot's x86 twin at 4× the width: 64 int8 products → 16 int32 accumulators, per instruction. A 128-dim token is 128 expanded bytes = two 512-bit registers — so one (query row × doc token) dot product is just two instructions:

acc = _mm512_dpbusd_epi32(acc, bits01_lo, q_lo);
acc = _mm512_dpbusd_epi32(acc, bits01_hi, q_hi);
// P is now spread across 16 lanes —
// horizontal-fold once at the end (class 01, ch 04)

// vpdpbusd is Unsigned × Signed:
//   first operand  = u8  → the 0/1 bits ✓
//   second operand = i8  → the query    ✓
// Swap them and negative query values
// silently corrupt the sum. The 'bus'
// in the mnemonic is load-bearing.

Same skeleton as NEON: expand bits to 0/1 bytes (here with a broadcast + byte-shuffle + mask-test dance instead of shift+AND), dpbusd for P, 2P−T, done. nano-plaid ships NEON and AVX2 and leaves VNNI as the guided exercise — it's the least universal of the three — but the production twin (next-plaid) implements all of them, and its dispatcher tries VNNI first when the CPU offers it.

The fusion: loop order wins

All three platforms share a hidden cost: expanding a doc token's bits to bytes (~17 ops) is more expensive than the dot product itself (~8 ops). So when you expand — the loop order — matters more than any instruction choice. Drag the query size:

Strategy B looks like the obvious fix — precompute the expansion into the index and skip it at query time! It loses in practice: stored planes are 128 bytes per token instead of 16, so every candidate drags 8× the data through the memory system. Measured on the M4: no faster than fused, at 8× the index size. Strategy C — expand once per doc token into registers, score it against all 32 query rows before moving on — is the fused kernel, and it's the same "keep work vertical, pay overhead once" instinct as class 01's horizontal-tax chapter, applied to a loop instead of a register.

The other family: AND + popcount

Masked sums are not the only way to score bits — and honesty requires the comparison. There's a second, better-traveled family, used by Elastic's BBQ inside Lucene/Elasticsearch and by a decade of binary neural networks before it (XNOR-Net onward): don't keep the query as int8 at all. Slice the query into bit-planes too, and every plane-product runs straight on the packed bits:

q = Σᵢ 2ⁱ·planeᵢ  ⇒  P = Σᵢ 2ⁱ · popcount(planeᵢ AND bits)

one AND + one popcount per query bit — no doc expansion, no bias heist, then the same 2P − T

The costs just move: family A pays per query bit (int4 query = 4 passes, int8 = 8 — BBQ picks int4 for exactly this reason), while our family B pays a doc-side expansion that fusion amortizes across query rows. So the winner depends on one number you already met in chapter 07 — drag it:

Neither is "the" answer — each team built the right kernel for its workload's shape. Prior art worth reading: BBQ's SIMD writeup (they explicitly chose popcount over psadbw for their layout), the bit-serial dot-product literature, and Muła's popcount collection — where the psadbw-as-byte-sum idiom itself comes from. The masked-sum lineage here follows mixedbread's binary MaxSim kernels via next-plaid.

Scoreboard

Same kernel contract — bit-identical scores to the scalar reference — measured per platform. Bars are µs per document (32-token query × 80-token doc, dim 128):

Six questions