Compression

An embedding describes a text with a long list of numbers, like describing a person with hundreds of adjectives. More adjectives let you tell very similar people apart, but every adjective takes shelf space, and a search system has to keep millions of these descriptions in fast memory.

This lesson is about making the descriptions smaller without mixing people up. There are three tricks, each with an everyday twin:

• Keep fewer numbers (Matryoshka truncation): a well-written news story puts the headline first and the details later, so you can cut from the bottom and still know what happened.
• Store each number more roughly (scalar quantization): round every price to the nearest dollar. Totals barely change, and the list gets much shorter to write down.
• Keep only a yes/no per number (binary quantization): instead of "4.7 out of 10", just record "above average: yes". Crude, but amazingly good for a first sort.

And one trick that rescues the crude ones: shortlist, then check. Skim a pile of CVs fast to pick 100, then read those 100 carefully.

A dimension is one number in the vector. A 32-bit float (the usual format) takes 4 bytes. So one 1,536-dimension vector takes 1,536 × 4 = 6,144 bytes, and ten million of them take:

On the example: 10,000,000 × 1,536 × 32/8 = 61,440,000,000 bytes ≈ 61 GB. As int8 it's 15.4 GB; as bits, 1.9 GB.

In Python:

n, d = 10_000_000, 1536
# float32, int8, binary
for b in (32, 8, 1):
    # bytes = n × d × b/8
    size = n * d * b // 8
    print(b, size, round(size / 1e9, 1), "GB")  # → 32 61440000000 61.4 GB 8 15360000000 15.4 GB 1 1920000000 1.9 GB
# HNSW: 2·M ids of 4 bytes each, M = 16, in GB
n * 2 * 16 * 4 / 1e9  # → 1.28

The index adds its own overhead. An HNSW graph (primer.ml.embeddings.ann) stores about 2·M neighbour ids per vector at 4 bytes each: with M = 16 that's 10M × 32 × 4 = 1.28 GB more.

In code: storage_bytes computes n × d × b/8 exactly, and hnsw_link_bytes adds the 2·M neighbour ids an HNSW graph keeps per vector.

Why it matters fast vector indexes like HNSW want every vector in RAM, so storage is the server bill. Being able to do this sum in your head tells you in seconds whether a design fits on one machine.

Everyday picture Russian nesting dolls: a small doll inside a bigger one inside a bigger one, each complete on its own. A Matryoshka embedding is trained so its first 64 numbers are a decent embedding, its first 256 a better one, and the full vector the best.

Tiny example a vector (0.9, 0.4, 0.1, 0.05) where the numbers shrink in importance. Keep the first two, (0.9, 0.4), and rescale it to length 1 (divide by √(0.81 + 0.16) = 0.985): (0.914, 0.406). The dropped numbers were small, so the direction barely moves: its cosine with the full (normalized) vector is 0.994.

On the example: m = 2: (0.9, 0.4) / 0.985 = (0.914, 0.406).

In Python:

import math
v = [0.9, 0.4, 0.1, 0.05]
m = 2
# (v_1, ..., v_m)
prefix = v[:m]
# ‖(v_1, ..., v_m)‖
length = math.sqrt(sum(v_i ** 2 for v_i in prefix))
round(length, 3)  # → 0.985
# rescale to length 1
v_m = [v_i / length for v_i in prefix]
[round(v_i, 3) for v_i in v_m]  # → [0.914, 0.406]
full = math.sqrt(sum(v_i ** 2 for v_i in v))
# cosine with the full, normalized vector
round(sum(a * b / full for a, b in zip(v_m, v)), 3)  # → 0.994

This only works if the important numbers really come first. A real Matryoshka model is trained that way: the same contrastive loss (primer.ml.embeddings.contrastive) is applied to several prefixes at once (the first 64, 128, 256, … numbers), so each prefix must work on its own. Here we imitate it by rotating vectors onto their principal directions (the directions along which the collection varies most, found with the SVD; see primer.notation), which puts the most informative number first.

flowchart LR
  T[Text] --> E[Encoder] --> V["full vector (d numbers)"]
  V --> P64["first 64"] --> L64[loss]
  V --> P256["first 256"] --> L256[loss]
  V --> PD["all d"] --> LD[loss]
  L64 & L256 & LD --> S["sum: every prefix<br/>must work on its own"]

In code: matryoshka_order rotates vectors onto their principal directions, most informative first, and random_order is the control. search_truncated searches with the first m numbers only; search_truncated_then_rescore shortlists that way, then re-ranks the shortlist with the full vectors.

On an example: true (1, 2, 3), found (3, 4, 1): two of the three appear, so recall@3 = 2/3 ≈ 0.67.

In Python:

true_k = {1, 2, 3}
found_k = {3, 4, 1}
k = 3
# ∩: the items in both
found_k & true_k  # → {1, 3}
# |found ∩ true| / k
round(len(found_k & true_k) / k, 2)  # → 0.67

In code: recall_at_k averages this share over every query. top_k runs the exact full-precision search that supplies trueₖ, and make_corpus builds the documents, queries and true neighbours every experiment here uses.

Everyday picture rounding prices to the nearest dollar. Here, every number is rounded to one of 256 marks on a ruler that runs from the smallest to the largest value seen in that dimension. 256 marks fit in one byte (int8), a quarter of a float's 4 bytes.

Tiny example a dimension whose values run from lo = −1 to hi = 1. The 256 marks are 2/255 = 0.00784 apart. The value 0 sits at (0 − (−1)) / 2 × 255 = 127.5 marks, rounds to mark 128, and decodes back to −1 + 128/255 × 2 = 0.00392. It's off by 0.00392, half a mark, the worst case.

On the example: x = 0, lo = −1, hi = 1: code = round(0.5 × 255) = round(127.5) = 128; x̂ = −1 + (128/255)·2 = 0.00392.

In Python:

x, lo, hi = 0, -1, 1
# round(127.5): ties go to the even mark
code = round((x - lo) / (hi - lo) * 255)
code  # → 128
# decode: walk back from the mark
x_hat = lo + code / 255 * (hi - lo)
round(x_hat, 5)  # → 0.00392

In code: scalar_quantize_int8 turns each number into its code, dequantize_int8 walks back to x̂, and search_int8 calibrates lo and hi on the documents and searches the decoded vectors.

Everyday picture a yes/no questionnaire. For each number, record only "positive: yes or no". Two texts are compared by counting how many answers differ, the Hamming distance.

Tiny example the eight values (0.3, −0.2, 0.0, 5, −1, 2, −3, 0.1) become the bits 1 0 0 1 0 1 0 1, packed into one byte: 0b10010101 = 149. Compare with 0b00010100: they differ in the first and last positions, so the Hamming distance is 2.

On the example: 149 = 10010101 vs 20 = 00010100: positions 1 and 8 differ, so the distance is 2. Computers do this with one XOR (mark the differing bits) and one popcount (count them), which is why binary search is extremely fast.

In Python:

x = [0.3, -0.2, 0.0, 5, -1, 2, -3, 0.1]
# bit_i = [x_i > 0]
a = [int(x_i > 0) for x_i in x]
a  # → [1, 0, 0, 1, 0, 1, 0, 1]
# packed into one byte
int("".join(map(str, a)), 2)  # → 149
# 0b00010100 = 20
b = [0, 0, 0, 1, 0, 1, 0, 0]
# hamming(a, b) = Σ [a_i ≠ b_i]
sum(a_i != b_i for a_i, b_i in zip(a, b))  # → 2
# the computer's way: XOR, then count the 1s
bin(149 ^ 20).count("1")  # → 2

flowchart LR
  Q[Query] --> B["Stage 1: bits + Hamming<br/>scan all 5,000 docs<br/>(32× smaller, very fast)"]
  B --> S[Shortlist of 100]
  S --> F["Stage 2: full float vectors<br/>exact dot product on 100 only"]
  F --> T[Top 10]
  STORE[("bits for every doc (RAM)<br/>floats for every doc (disk or RAM)")] --> B
  STORE --> F

In code: binary_quantize keeps each number's sign and packs 8 bits per byte, and hamming_distances counts differing bits with XOR and a popcount table. search_binary ranks by bits alone; search_binary_then_rescore re-ranks the bit-based shortlist with the full float vectors.

Why it matters these knobs move real money. Many vector databases ship int8 and binary quantization with re-scoring built in, and embedding providers increasingly ship Matryoshka-trained models so you can pick your dimension. The cost is always measured the same way: recall@k on your own queries.

Answer each one out loud or on paper before you open it. If you can explain it, you know it.