Browse by kind · Close Enough

Experiments 8

Numerical experiments on real embeddings. Each leads a section: shown first, explained, shown again.

Six books are cut into passages, and each passage becomes a list of 384 numbers. Nobody tells the model which book a passage came from. Do passages from the same book still land near each other?

first look1.5 What the geometry means6-step recipe
second look1.5 What the geometry means › Back to the map4 guided steps
another look1.6 The shape of the cloud › Back to the map, one last time2 guided steps

Experiment 1.5BNearest passages

Take one passage. Of eighty thousand others, which point most nearly the same way? Are they about the same thing?

first look1.5 What the geometry means › Similarity is angle6-step recipe
second look1.5 What the geometry means › Similarity is angle6 guided steps

Experiment 1.5CTwo dials

Is there a direction in the space that means “good versus bad”, and another that means “past versus present”? Can simple averaging find them?

first look1.5 What the geometry means › Directions carry attributes6-step recipe
second look1.5 What the geometry means › Directions carry attributes4 guided steps

Experiment 1.5DHot and cold

Which sentence does the model place closer to “The soup is hot.”: “The soup is cold.”, or “The broth is scalding.”?

first look1.5 What the geometry means › “Similar” means what the training said5-step recipe
second look1.5 What the geometry means › “Similar” means what the training said3 guided steps

Experiment 1.6AThe lopsided cloud

Pick two passages from two different books at random. If the arrows pointed every which way, they would be nearly perpendicular, with cosine close to 0. Are they?

first look1.6 The shape of the cloud › The cloud sits off to one side5-step recipe
second look1.6 The shape of the cloud › The cloud sits off to one side5 guided steps

Experiment 1.6BHow many directions are used?

Each passage has 384 numbers. Does the cloud spread equally in all 384 directions, or mostly in a few?

first look1.6 The shape of the cloud › Fewer real directions than dimensions5-step recipe
second look1.6 The shape of the cloud › Fewer real directions than dimensions4 guided steps

Experiment 1.6CA walk through Alice

Read a book passage by passage. Does the embedding jump around at random, or walk?

first look1.6 The shape of the cloud › A text is a path6-step recipe
second look1.6 The shape of the cloud › A text is a path4 guided steps
another look3.3 Know your data › Neighbours in the text are neighbours in space2 guided steps

Experiment 9.2AThe measured V spectrum

How much variation survives when we keep only the strongest directions?

first look9.2 The shape of cached values › A small dimension number can hide a long tail3-step recipe

Interactive figures 57

Charts and playgrounds you can hover, drag and adjust.

Fig 1Nearest neighbours of a drifting queryThe whole field in one picture
A query (the star) drifts through a cloud of embedded items, always linked to its six nearest neighbours. Part 1 is about where the points come from, Part 2 about finding the neighbours quickly, and Parts 3 to 6 about …
Close Enough
Fig 1.2.1A toy word spaceDrag the star, or tap a word
A hand-placed two-dimensional toy, not a real model. Real embeddings have hundreds of dimensions but the logic is the same: similar items cluster, and consistent offsets (gender, royalty, age) act like directions you …
1.2 Meaning from context › word2vec: predict instead of count
Fig 1.7.1Distances in high dimensionsSlide d from 2 to 1,024
In high dimensions almost every random point sits at distance √2 from the query, which is to say at a right angle to it. The nearest point is barely nearer than the farthest.
1.7 What does "close" mean? › The villain: distances concentrate
Fig 1.8.1Seventy years of vector searchFilter by thread
Representations is the story of Part 1. Search algorithms is Parts 2 to 5. Industry is Part 7.
1.8 Interlude: seventy years in one page
Fig 2.4.1Four indexes on one mapTap the map to move the query
Switch between brute force, LSH, IVF and a graph. In every mode the yellow dots are what the index returned, the rings are the true ten nearest, and blue marks what the index had to examine.
2.4 The index lab
Fig 2.5.1Napkin math for a vector indexSlide the numbers yourself
The vertical ticks are a 16 GB laptop, an 80 GB GPU, 1 TB of server RAM and a 100 TB cluster, on a log scale: each step to the right is ten times more. HNSW adds roughly 2 × M × 4 bytes of links per vector on top (about …
2.5 Napkin math › Orders of magnitude
Fig 3.2.1From a book to vectorsThe pipeline
48-word windows with a stride of 24, so each window shares half its words with the next. Each coloured column on the right is one real embedding (the first 24 of its 384 coordinates; colour shows sign and size). …
3.2 The running example › From a book to a sequence of vectors
Fig 3.3.1Variance per principal directionHover the bars
The first 8 directions (yellow) hold 24% of the variance, the first 64 hold 61%, and the first 128 hold 80%.
3.3 Know your data › Variance is concentrated in a few directions
Fig 3.4.1Reverse water-fillingDrag the budget
This is the real spectrum of the embeddings. The lime part of each bar is what gets described; the faded red part is the error that remains. At 8 bytes, how many directions get anything at all?
3.4 From spectrum to bit budget › The rule
Fig 3.4.2Error against bits, measuredMeasured, from 4 bytes to 384 bytes
Each dot is a full train-and-evaluate run on held-out books. The dashed line is the Gaussian bound from water-filling. Switch to recall to see what the error means for search.
3.4 From spectrum to bit budget › So why does anyone use vector quantization?
Fig 3.5.1Scalar quantization: bits and clippingSlide the bits, then the clip range
With few bits you must choose: a wide range wastes levels on values that almost never occur, a narrow one clips the tails (red). Press best c to see the compromise move outward as bits are added.
3.5 Scalar quantization › Rounding with a step
Fig 4.1.1One codebook: bits against errorSlide the bits
Each extra bit doubles $K$ . On the right, error on a log scale. In two dimensions each bit roughly halves the error once $K$ is large; the dashed line is that slope.
4.1 One codebook, and the wall › Replace each vector by its nearest representative
Fig 4.2.1Three codebooks that add upDrag the yellow point
Three codebooks of four arrows each: big, medium, small. Pick one arrow from each and chain them. Only 12 arrows are stored, yet 4 × 4 × 4 = 64 grey points are reachable.
4.2 Codebooks that add up › The sum trick
Fig 4.2.2Sums of codewordsDrag the arrow tips
Each mint dot is Aᵢ + Bⱼ, so moving one arrow moves four dots at once. Then switch to the product constraint and press Fit: the sums are forced onto an axis-aligned grid, which wastes points on a tilted cloud.
4.2 Codebooks that add up › The sum trick
Fig 4.3.1Greedy residual quantizationDrag the target
The dashed gold path is greedy; the solid mint path is the best of all 64 combinations. Greedy commits to the closest first arrow even when a slightly worse first arrow would let the smaller arrows land closer.
4.3 Be greedy › Quantize what is left
Fig 4.4.2Beam search over codebooksTry B = 1, then raise it
One test vector from an 8-dimensional problem with $M = 4$ codebooks of $K = 16$ . Each column is a stage; each dot is a candidate partial code, at a height equal to its error. Mint dots survive, faint ones are …
4.4 Encoding is the hard part › Beam search: greedy, but hedge your bets
Fig 4.5.1ICM, one step at a timeStep through it
Each row is a codebook; each cell shows how good that entry would be given the current choice in every other row. Brighter is better; the yellow outline is the current choice. Each update moves the outline to the …
4.5 Fix all but one › Iterated conditional modes
Fig 4.5.2Encoders against the optimumMove the overlap slider
The x axis is compute in table lookups per vector (log scale); the y axis is how far above the optimum each encoder lands on average. Hover the points.
4.5 Fix all but one › The encoder lab
Fig 4.7.1Asymmetric distance computationADC
The pink cells are the entries the code picks. The search cost is the same $M$ lookups for PQ, RQ and additive codes.
4.7 Searching without decoding › Asymmetric distance computation
Fig 4.8.1Every method at 64 bitsRead it left to right
Each step down in error costs a step right in encode time. Hover for details. The pink points use the order of the windows, explained below.
4.8 Measured on real embeddings › The setup
Fig 5.1.1Random hyperplanes in the planeDrag the two arrows
Red lines are hyperplanes that separate the query from the document. In the plane a random line through the origin has a random angle, and it separates the arrows exactly when it falls inside the yellow angle between …
5.1 Hash functions that like their neighbours › SimHash: one hyperplane, one bit
Fig 5.1.2Collision probability, measuredMeasured
Dots: the fraction of 2,048 random hyperplanes on which real query–passage pairs agree, grouped by their true angle. Line: $1-\theta/\pi$ . The two dashed markers are the angles that matter for search on this data.
5.1 Hash functions that like their neighbours › Does it hold on real embeddings?
Fig 5.2.1The LSH S-curveSet k and L
The faint dotted line is a single bit. The dashed markers are a true 10th neighbour and a random pair on Marginalia’s data. Where a marker meets the curve is, roughly, your recall (green) and the share of the database …
5.2 Turning a gentle slope into a cliff › OR: give neighbours more chances
Fig 5.3.1LSH recall against workUp and to the left is better
Each blue curve is LSH with a fixed number of bits per table, running from 1 table to 64. Pink is multi-probe LSH. Green is IVF, the k-means partition of 2.2 Cut the space into pieces, with its nprobe raised from 1 to …
5.3 Random cuts against learned cuts › The measurement
Fig 5.4.1Angle estimates from bit sketchesChoose the number of bits
Each dot is a real pair of passages. With 64 bits the estimate is a blur; with 1,024 it hugs the diagonal.
5.4 Bits as a compressed sketch › From collision probability to an estimator
Fig 5.4.2Re-ranking a sketch shortlistPick the shortlist size
Recall of the true top 10 after re-ranking, against the size of the sketch. All three lines use the same number of stored bits per vector; they differ in which hyperplanes are used and in how the query is treated.
5.4 Bits as a compressed sketch › How good is the shortlist?
Fig 6.1.2The lossless ladder, measuredMeasured
Bits per vector for an int8-exact copy of four held-out books, with an ideal entropy coder (a real one lands within a tenth of a percent, 6.6 The entropy-coder zoo).
6.1 Every bit must come back › Where this part ends up
Fig 6.2.1Probability models for a coordinateChoose what is being coded and how it is modelled
Bars are the measured histogram, pooled over every coordinate of every held-out vector. The line is the model. The readout compares what this model charges with the entropy of the histogram itself; the difference is the …
6.2 Everything is a probability model › Look at the actual distribution
Fig 6.3.1The bits of a float32Where the bits go
Top: six real values from the first window of Alice in Wonderland, bit by bit: sign, exponent, mantissa. Bottom: the entropy of each bit position over the whole dataset. A bar at full height is a fair coin.
6.3 Floats are stubborn › Where the bits go
Fig 6.4.1Rotating the coding axesRotate the coding axes
Each axis is coded with its own bell curve, costing about $\log_2 \sigma$ bits. The panel shows the total relative to the original axes. Snap to the principal axes: that is the lowest a rotation can go. Then read the last …
6.4 The transform zoo › What correlation costs
Fig 6.4.3Spread explained by earlier coordinatesWhat the earlier coordinates explain
Blue: each coordinate’s spread on its own. Orange: its spread once the coordinates before it are known. The gap, on a log scale, is the saving.
6.4 The transform zoo › The lossless twin of a rotation
Fig 6.5.1What a known neighbour savesSlide ρ
The wide curve is a coordinate on its own; the narrow one is the same coordinate once a correlated value is known. The saving in bits is the log of the ratio of widths.
6.5 The prediction zoo › Prediction is conditioning
Fig 6.5.2Quantizing prediction errorsThe lossy case, in two dimensions
The same 4 bits per step either way: a 16-entry codebook for the vectors themselves, or for the prediction errors. Yellow: the true path. Mint: the reconstruction. Red: the error. Diamonds are keyframes, coded …
6.5 The prediction zoo › The rule that changes: open or closed loop
Fig 6.6.1Four entropy coders against the entropySlide the spread
Average bits per value for four coders on a residual of spread σ, against the entropy. Start at σ ≈ 15, where Marginalia’s residuals live. Then slide left, below σ = 1. Switch to Laplace to see why audio codecs choose …
6.6 The entropy-coder zoo › The job
Fig 6.7.2Lossless size against predictor stagesHover the chart
Bits per vector to store the database books exactly, against the number of RQ stages $m$ used as the predictor. Pink band: the code, 8 bits per stage. Dashed lime: the residual alone. Solid lime: the total. The …
6.7 Where should the bits go? › Dial 1: how many RQ stages?
Fig 6.7.3Two kinds of side informationTwo kinds of side information on one axis
x: bits spent on the side information. y: total bits, zoomed. Both curves are shallow bowls with a minimum.
6.7 Where should the bits go? › Dial 2: how fine a step for the side information?
Fig 6.8.1Bits per index, per RQ stageBits per index, per RQ stage
Grey outline: the flat 8 bits. Blue: an ideal coder that knows how often each codeword is used. Orange: one that also knows the same stage’s index in the previous window.
6.8 Squeezing the codes themselves › The indices are not uniform
Fig 6.9.1Compressing a search responseA search response, measured
300 queries, the top 50 vectors of each. General-purpose compression against a model that both ends hold.
6.9 Two codecs › The wire codec
Fig 7.3.1Attention as soft nearest neighbourDrag the query arrow, then lower the temperature
Arrow thickness is attention weight. At low temperature one key takes nearly all the weight: hard nearest-neighbour retrieval. When the weight is concentrated in a few keys you only need to find those few, which is an …
7.3 The same math in other places › Attention is a soft nearest-neighbour lookup
Fig 7.4.1Compression methods by encode and decode workA qualitative map
Horizontal: work to encode one vector. Vertical: work to decode or score one. Dot size: error at a tight budget (bigger is worse). A ring means the method needs the vectors in sequence order. Positions are judgement …
7.4 The big picture › Encoder-heavy against decoder-heavy
Fig 8.2.1TopK against samplingPick a scenario, then draw samples
Red sticks are the ones TopK reads. The red arrow is how far its answer misses. Each purple dot uses as many draws as TopK reads tokens; repeated draws need only one value load.
8.2 MagicPIG: don't pick the tallest › Picking the tallest
Fig 8.2.2Importance samplingSlide the guess from uniform to exact
The purple bars are where we can afford to sample; the grey sticks are where we should. Red dots average the draws as they come; green dots re-weight them by w / u.
8.2 MagicPIG: don't pick the tallest › The catch: you cannot sample without looking
Fig 8.2.3Two cones and a sinkSwitch between the views
Every key and query of Qwen2.5-1.5B-Instruct reading the first 16,384 tokens of Emma. One head: how keys and queries spread around the mean key direction. One query: its cosine with every key, before and after …
8.2 MagicPIG: don't pick the tallest › Where the keys live
Fig 8.2.4Hashing a coneToggle between raw and centred keys, and drag the query
Grey lines are random hyperplanes, and they cut the plane into buckets. The shaded wedge is the query’s bucket. Ringed keys share it. Dot size is attention weight.
8.2 MagicPIG: don't pick the tallest › A hash that knows its odds
Fig 8.2.5The sampling curve on real keysSet K and L, and compare requiring one collision with requiring two
The curve is the probability that a key is sampled, given its cosine with the query. Grey: how many of this query’s centred keys sit at each cosine. Green: where its attention weight sits; the spike is the sink.
8.2 MagicPIG: don't pick the tallest › A hash that knows its odds
Fig 8.2.6The memory billSlide K and L
Bytes per key, per layer, per head. The paper’s settings put $L$ between 75 and 150.
8.2 MagicPIG: don't pick the tallest › The bill
Fig 8.2.7Estimators at a budgetTurn centring and the exact sink and local tokens on and off
Lines: the oracles at budgets from 0.1% to 20% of the keys. Diamonds: MagicPIG at the paper’s three settings. Square: the sink and the 64 most recent tokens alone.
8.2 MagicPIG: don't pick the tallest › Did it work? We checked
Fig 9.2.1Walk into one V tensorChoose a thread, layer and head.
The grid is a schematic, not a heatmap: each square stands for coordinates, with no tensor values plotted. The counts and prompt boundary come from the dataset metadata.
9.2 The shape of cached values › One token, one vector
Fig 9.2.2Keep a line, lose the distance to itRotate the kept direction.
Points are synthetic tokens, green marks their reconstructions, and red segments show the error. The cross is the mean. The same points are reused as you move the controls; units are arbitrary.
9.2 The shape of cached values › Try a smaller world
Fig 9.2.3Concentration is not a truncation rankSwitch spectra, then move the rank.
The exact-rank and flat presets spread variance equally over 32 or 256 directions. The long tail uses variance proportional to $i^{-1.2}$ ; it is a toy, not a fit to V. Blue bars are retained, red bars discarded. …
9.2 The shape of cached values › A small dimension number can hide a long tail
Fig 9.2.4Borrowing PCA directionsChoose the target thread, layer and head.
“All” averages selected target blocks equally. The dashed reference is a randomly oriented subspace’s expected share, $k/256$ . Other-thread fits exclude the target; next-layer fits use the next cached layer, with 23 …
9.2 The shape of cached values › Could we learn the directions once?
Fig 9.2.5Equal fit sizes, past to futureCompare each pair of bars.
Blue uses the thread’s own past; purple uses other threads. Each value averages 12 layer × head blocks and three random draws. Past and future are separated in time, though residual dependence may remain.
9.2 The shape of cached values › Give both bases 160 fitting tokens
Fig 9.2.6What pooling does to dimensionCompare the scopes.
Bars show split-half-corrected PR, averaged over all 60 seed blocks. Hover also gives naive PR at matched token counts. Other threads raise dimension less than other heads or layers in their stored coordinates.
9.2 The shape of cached values › Give both bases 160 fitting tokens
Fig 9.2.7Shape, mean and norm across depthSwitch the quantity.
Every point averages threads and heads at one cached layer. Centred effective dimension changes mildly; the norm grows about sixfold from layer 3 to 23, and the mean’s energy share rises sharply at layer 23.
9.2 The shape of cached values › What if most of the vector is an offset?
Fig 9.2.8Sample size and apparent dimensionSwitch between synthetic data and real windows.
The synthetic Gaussian has the measured layer-11 V covariance and token autocorrelation $\rho=0.55$ ; the dotted line is its true PR. Real contiguous windows come from thread 104, layer 11, head 0; their reference is the …
9.2 The shape of cached values › Are short sequences fooling us?
Fig 9.2.9Short threads gain more from correctionCompare the linked dots.
Blue is naive PR, purple is corrected PR, averaged over layers and heads. Labels identify threads. The horizontal axis is sequence length on a log scale.
9.2 The shape of cached values › Are short sequences fooling us?
Fig 9.2.10An ideal rate, not a demonstrated codecRead toward stricter error on the right.
Solid blue is the ideal Gaussian rate from the measured spectra, taking the median over 12 layer × head covariances. The dashed reference spreads the same total variance equally over 256 directions. Both omit mean/basis …
9.2 The shape of cached values › So where might the savings come from?

Diagrams 9

Static pictures of a mechanism.

Fig 1.3.1Inside a text embedding modelThe pipeline
A text embedding model reuses an LLM-style backbone end to end, not just its first layer. The blue box is where word2vec-era vectors live; the yellow box is what an embedding API returns.
1.3 Context arrives › From token vectors to one embedding
Fig 1.4.1Contrastive trainingContrastive training
The query pulls its positive closer and pushes negatives away. The woodworking passage is a hard negative: it shares the word “router” but answers a different question.
1.4 The secret ingredient › Pull together, push apart
Fig 3.2.2Encode once, compare oftenThe asymmetry
A vector is encoded once, when it enters the index. It is decoded or compared every time a query touches it. This is why it can be worth making encoding very expensive.
3.2 The running example › Two jobs, two budgets
Fig 4.4.1Four methods as graphsOne picture, four methods
Nodes are codebooks, edges are non-zero pairwise terms. PQ deletes the edges by construction. Tree quantization lets codebooks overlap only in a tree pattern, so exact encoding is dynamic programming. Unconstrained …
4.4 Encoding is the hard part › The energy and its graph
Fig 6.1.1The lossless codecThe codec
A model looks at the context (whatever the decoder will also have) and outputs a guess and an uncertainty. The entropy coder turns the actual value into about −log₂ q bits. The decoder runs the same model on the same …
6.1 Every bit must come back › One machine
Fig 6.4.2Rotations break the integer gridThe grid does not survive
Left: the int8 values sit on a square grid. Right: after a rotation the same points sit on a tilted grid. Rounding the rotated coordinates to integers moves each point, and nothing guarantees it can be moved back.
6.4 The transform zoo › Why you cannot just rotate
Fig 6.7.1A quantizer as side informationA quantizer as side information
The stored file is the code plus the entropy-coded residual. The decoder recomputes the prediction from the code, so adding the residual restores every bit.
6.7 Where should the bits go? › The two-part code
Fig 6.9.2One product, three compressorsOne product, three compressors
The RAM tier is encoder-heavy and lossy. The SSD tier is cheap both ways. The archive is lossless and sequential, and is what lets Marginalia retrain codebooks or change quantizers later without paying to re-embed.
6.9 Two codecs › What Marginalia ships
Fig 7.2.1The retrieval funnelThe funnel
Cheap methods narrow billions of items to thousands; expensive methods order the thousands. ANN lives in the first stage.
7.2 The funnel › Cheap narrows, expensive orders

Key ideas 19

The one idea a section hangs on.

The modern recipe
Start from a strong pretrained LLM, then fine-tune it contrastively into an embedder.
1.4 The secret ingredient › What the big labs ship today
Why APIs return unit vectors
Once vectors are normalized, cosine, dot product and Euclidean distance give the same ranking. You can use whichever your index computes fastest, and you can measure compression error as plain squared distance.
1.7 What does "close" mean? › On unit vectors they are one measure
The one trick
Look at a small, well-chosen fraction of the data and hope the true neighbours are in it.
2.1 Finding neighbours without checking everyone › Not a lookup
The quarter-bit tax
A scalar quantizer followed by an entropy coder is about ¼ bit per dimension (1.53 dB) worse than the best possible quantizer, at any rate. It is the price of rounding each coordinate into a cube-shaped cell when a rounder cell would pack space better.
3.4 From spectrum to bit budget › How good can transform + scalar get?
Six decibels per bit
One more bit halves $\Delta$ , which quarters the squared error. In signal-processing units a factor of 4 is 6.02 dB. This single fact reappears on almost every later page.
3.5 Scalar quantization › Rounding with a step
The theme of the next three pages
Every method from here is an answer to “how do you encode?” There are three broad answers: Restrict the codebooks so that the search falls apart into small pieces: product quantization, below. Search greedily: residual quantization, 4.3 Be greedy. Search …
4.2 Codebooks that add up › Two things to take from playing with it
The progressive property
Any prefix of an RQ code is itself a valid, coarser code. Truncate 8 bytes to 4 and you still get a reasonable $\hat x$ .
4.3 Be greedy › A side effect worth remembering
Why the expensive encoder is worth it
At query time PQ, RQ and LSQ codes all cost exactly $M$ lookups. The encoder’s extra effort is free forever after.
4.7 Searching without decoding › Asymmetric distance computation
What ρ really says
LSH is fast when neighbours are much closer than typical points: near-duplicates, where $p_1 \approx 1$ and $\rho \approx 0$ . It is slow when “near” means cosine 0.3 against a background of 0.1, which is the normal situation for semantic search.
5.2 Turning a gentle slope into a cliff › How to choose k and L
The only equation in this part that matters
An ideal entropy coder spends $\kbits{\ell(x)} \;=\; -\log_2 \kbits{q}(\kvec{x} \mid \text{context}) \ \text{bits}$ on the value $x$ , where $q$ is the model’s probability for it. Everything else is the question of how to make $q$ large on the data you actually see.
6.1 Every bit must come back › One machine
Bits for a Gaussian coordinate on a grid
$\kbits{\text{bits}} \;\approx\; \log_2\frac{\kres{\sigma}}{\kbook{\Delta}} \;+\; 2.05$ Halve the spread $\sigma$ and you save one bit. Halve the step $\Delta$ and you pay one more.
6.2 Everything is a probability model › From a density to bits
Why prediction cannot help
Suppose a model predicts a coordinate to within ±16 int8 steps, which is about ±0.035. A float32 of that size has a resolution near $2^{-28}$ . The number of bits still unknown is $\log_2 \frac{0.035}{2^{-28}} \;\approx\; 23 \ \text{bits}$ Those bits are numerical noise from the model’s arithmetic. No …
6.3 Floats are stubborn › Where the bits go
Prediction is worth little until ρ is large
$\rho = 0.5$ saves 0.21 bits per coordinate. $\rho = 0.9$ saves 1.2. $\rho = 0.99$ saves 2.8. This is why video compresses a hundredfold (consecutive frames are nearly identical) and embeddings do not.
6.5 The prediction zoo › Prediction is conditioning
The pick
A static quantized-Gaussian model per coordinate, coded with rANS or a range coder. Fractional bits, no per-context tables, and the same code path for every row of the ladder.
6.6 The entropy-coder zoo › Choosing for embeddings
Halve the error, save a bit per dimension
Quartering $D$ (halving the RMS error) saves $d$ bits. So a stage that costs 8 bits is worth adding only if it shrinks $D$ by more than a factor of $2^{-16/d} \qquad\text{which for } d = 384 \text{ is a cut of } 2.8%$
6.7 Where should the bits go? › The exchange rate
The largest saving in this part
Going from exact to ±1 step saves 604 bits per vector. That one decision is worth more than the previous-window predictor and the triangular predictor combined. Precision is the dial that matters; everything else is tuning.
6.9 Two codecs › The dial: near-lossless
TopK misses by a fixed amount
Call the weight TopK keeps $M$ , the balance point of the kept sticks $\kdec{a}$ and of the skipped ones $\kdec{b}$ . Then the truth is $o = M a + (1-M)\, b$ , TopK answers $a$ , and $\kres{o - \hat o_{\text{TopK}}} \;=\; (1 - M)\,(\kdec{b} - \kdec{a}).$ The weight it skipped, times how different the skipped tokens are. That …
8.2 MagicPIG: don't pick the tallest › Picking the tallest
Dumb turns out to be the point
Part 5 called LSH’s obliviousness its weakness: it ignores the data, so learned indexes beat it. But obliviousness is exactly what makes $u_i$ computable from one arccos. A learned index may find better neighbours, but its ordinary retrieval rule does not …
8.2 MagicPIG: don't pick the tallest › A hash that knows its odds
Share within a layer and head, then test new sequences
These five sequences suggest a reusable basis is worth trying. They don’t settle transfer across tasks. Fit the mean, basis and quantizer without using the evaluation sequence.
9.2 The shape of cached values › Give both bases 160 fitting tokens

Measured results 21

Numbers measured on this book's data, with what they mean.

The primer’s running dataset
The primer’s running measurements use 88,942 passages from 18 public-domain books, embedded with the open model all-MiniLM-L6-v2 into 384 dimensions. Codebooks and probability models are always fitted on some books (63,120 passages) and scored on other books …
Close Enough › Where the numbers come from
Random cuts versus learned cuts
On this book’s 23,490 database passages, comparing about 7% of the database with each query: LSH with 16 tables of 8 bits finds 29% of the true top 10. IVF with 256 lists finds 66%. Random hyperplanes ignore where the data is. k-means does not. The full …
2.2 Cut the space into pieces › Family 3 · Clustering: learn where the data is
The same 64 bits, two shapes
Top 8 directions × 8 bits: relative error 0.77, recall 0.05. Water-filled over 58 directions, 1 to 3 bits each: relative error 0.60, recall 0.12. Same transform, same total bits, same trivial encoder. Only the allocation changed.
3.4 From spectrum to bit budget › “Keep the top 8 dimensions” is a crude version of this
On Marginalia’s vectors
Per-coordinate quantizers fitted on the training books, scored on held-out books, without re-ranking: Bits per coordinate Vector size Relative squared error 10-recall@10 1 48 B 0.359 0.42 2 96 B 0.116 0.67 4 192 B 0.0133 0.88 8 384 B 0.00008 0.99
3.5 Scalar quantization › The three you will meet
How much the rotation is worth
At 64 bits on held-out books: PQ leaves a relative error of 0.71; OPQ, the same quantizer after a learned rotation, 0.56. That is 22% less error from layer 1 of the stack alone.
4.2 Codebooks that add up › Restrict: product quantization
Freeing the codebooks
At 64 bits on held-out books: Relative error Recall@10 Encode PQ, 8 blocks 0.713 0.108 5 µs OPQ 0.556 0.158 9 µs RQ, greedy 0.538 0.194 26 µs From PQ to greedy RQ the error falls by 25%. That is the grid-versus-free picture of the previous page, measured.
4.3 Be greedy › Measured
Wider is not always better
On Marginalia’s vectors, a beam of 4 cuts the error from 0.538 to 0.525 at 3.7× the encode time. A beam of 16 costs 15× and lands at 0.529: no better on held-out books. The wider beam fits the training books more tightly, and that does not transfer.
4.4 Encoding is the hard part › Beam search: greedy, but hedge your bets
On Marginalia’s data
Eight codebooks of 256 × 384 have 786,432 free parameters. Trained on 63,120 windows, LSQ reaches a relative error of 0.34 on the training books and 0.48 on the database books. The gap is overfitting. A strong encoder plus free codebooks will happily memorise …
4.6 Learning the codebooks › The overfitting trap
The gap LSH has to work with
After centring, a query’s true 10th neighbour is at cosine 0.34 and a random passage at 0.07. In collision probabilities: $p_1$ = 0.611 for a true neighbour, $p_2$ = 0.521 for a random point. One bit agrees 61% of the time for a neighbour and 52% of …
5.1 Hash functions that like their neighbours › Does it hold on real embeddings?
ρ on Marginalia’s embeddings
With $p_1 = 0.611$ and $p_2 = 0.521$ : $\rho = \frac{\ln(1/0.611)}{\ln(1/0.521)} = 0.75$ Sublinear, but only just. For a million vectors $N^{\rho}$ is about 33,867; for the 23,490 vectors here it is about 1,995 candidates per query, 8% of the database.
5.2 Turning a gentle slope into a cliff › How to choose k and L
The formula holds
Typical angle error on real pairs: 0.198 rad with 64 bits, 0.098 with 256, 0.050 with 1,024. The formula predicts 0.194, 0.097 and 0.048.
5.4 Bits as a compressed sketch › From collision probability to an estimator
The prize
On Marginalia’s int8 vectors the coding gain is 260 bits per vector, about 220 of which survive on held-out books. That is the second-largest item on the ladder.
6.4 The transform zoo › What correlation costs
Rotate, quantize, and code the leftover
PCA coefficients quantized with step $s$ , plus the exact integer difference: $s = 6$ (best): 2,367 bits, split 1,278 for coefficients + 1,089 for the leftover; $s = 1$ (as fine as the data): 2,447 bits, barely better than no transform at all …
6.4 The transform zoo › Why you cannot just rotate
The triangular predictor
Per-coordinate model: 2,477 bits. With triangular prediction: 2,257 bits, a further 220 bits per vector, and within a rounding error of the ideal joint-Gaussian bound (2,256). The cost is one triangular solve: 73,536 multiply-adds per vector, about 2 µs in …
6.4 The transform zoo › The lossless twin of a rotation
Both together
$2,477 \;\xrightarrow{\ \text{previous window}\ }\; 2,344 \;\xrightarrow{\ \text{earlier coordinates}\ }\; \mathbf{ 2,171 }\ \text{bits}$ That is 29% below raw int8, and it is the best archive model in this book.
6.5 The prediction zoo › The two free predictors stack
A real coder on 4,000 held-out vectors
Bits per vector Ideal: $-\sum\log_2 q$ 2,335.6 Range coder output (constriction library) 2,335.6 Overhead 0.000% Decoded output identical to the input. Encoding took 10 µs per vector and decoding 32 µs, called once per vector from Python; a batched or SIMD …
6.6 The entropy-coder zoo › Does a real coder match the “ideal” numbers?
The same 64 bits of RQ code, against two residual models
Residual model Without RQ With RQ-8 (code included) RQ’s net effect A bell curve per coordinate 2,477 2,397 saves 79 bits Triangular prediction 2,257 2,274 costs 17 bits Triangular + previous window 2,171 2,220 costs 49 bits
6.7 Where should the bits go? › When side information pays, and when it does not
Three findings that held up
Keys crowd into a narrow cone. Average cosine with the mean key: 0.67. Unrelated random directions would average near 0. This is anisotropy, the same lean as sentence embeddings. Queries point away from it. Their cosine with the mean key averages −0.24. For …
8.2 MagicPIG: don't pick the tallest › Where the keys live
What we found
The budgets reproduce. (8, 75), (9, 120) and (10, 150) read 5.1%, 3.9% and 2.1% of the keys; the paper says 5%, 4% and 2%. Sampling beats TopK, as an oracle. At a 2% budget TopK misses by 12.1%, sampling by about 6%, the hybrid by 4.5%. MagicPIG trails the …
8.2 MagicPIG: don't pick the tallest › Did it work? We checked
Fitting the cloud is easier than predicting it
Across the 60 individual blocks, the top 32 directions capture about 70% in-sample, but 56% on held-out chunks. Keeping 8 / 32 / 64 directions captures 29% / 56% / 71% of held-out centred variance, with each block weighted equally. The median …
9.2 The shape of cached values › A small dimension number can hide a long tail
Layer 23’s large mean
The within-sequence mean accounts for 91% of raw energy, averaged across five threads and two heads. Each sequence supplied its own mean. Whether a mean learned elsewhere transfers is still untested.
9.2 The shape of cached values › What if most of the vector is an offset?

Pitfalls 7

Ways this goes wrong in practice.

Embeddings find topic, not truth
A vector search for “the treatment works” will happily return “the treatment does not work”. If your application needs to tell a claim from its opposite (fact checking, contradiction detection, sentiment), check what your model was trained on, or rerank the …
1.5 What the geometry means › “Similar” means what the training said
The curse of dimensionality
Any index that works by cutting space into boxes relies on most boxes being far from the query. When everything is about equally far, no box can be ruled out, and the index degenerates into looking at everything.
1.7 What does "close" mean? › The villain: distances concentrate
Held-out, always
A compressor that is fitted and scored on the same vectors flatters itself. Every error, recall and bit count in this book is on books the compressor never saw.
3.2 The running example › The data used in this book
The bill: random access
Predictive codes depend on the previous reconstruction, so: To score window $t$ you need $\hat x_{t-1}$ , which needs $\hat x_{t-2}$ , back to a keyframe. IVF scans lists in cluster order, not reading order, so predictive codes do not fit an IVF index. A sequential …
4.8 Measured on real embeddings › A cheap trick that beats the expensive ones
Check that the target is good enough
Rounding to int8 moves each coordinate by at most half a step. On this data that leaves recall@10 at 0.99 against exact search (3.5 Scalar quantization). If you re-rank against the int8 copy, that is your ceiling; decide whether it is acceptable before making …
6.3 Floats are stubborn › The lesson
Closed loop, or drift
Predict from $\hat x_{t-1}$ , never from $x_{t-1}$ . If the encoder predicts from the original and the decoder from its approximation, they disagree a little at every step and the disagreement accumulates. That failure is called drift.
6.5 The prediction zoo › The rule that changes: open or closed loop
Determinism is part of the format
The decoder must compute exactly the same prediction as the encoder, on any machine. Floating-point sums in a different order, a different BLAS, or float32 against float64 can flip one rounding and corrupt everything after it. Fix the arithmetic: store the …
6.5 The prediction zoo › The rule that changes: open or closed loop

Exercises 8

Things to try yourself.

Four experiments
IVF, nprobe = 1. Move the query near a cell boundary. Recall drops: the missing neighbours are just across the line. Raise nprobe until they come back. LSH, 1 table. Raise bits per table to 10. The bucket shrinks, the work drops and the neighbours vanish. Now …
2.4 The index lab
What to look for
Overlap 0. Every method hits the optimum: no edges, so greedy is exact. Raise it. Greedy lands far above. ICM from greedy improves a little and then sticks; perturbing helps more. Beam search buys the most per lookup here, and its curve flattens: the last few …
4.5 Fix all but one › The encoder lab
Find a good index
Set k = 12, L = 1. Almost nothing collides, neighbours included. Raise L to 64. Recall climbs. So does the red dot: you are scanning more. Now try k = 8, L = 64. More recall, far more scanning. Try to get the green dot above 0.9 with the red dot below 0.01. …
5.2 Turning a gentle slope into a cliff › OR: give neighbours more chances
Things to try
Gaussian, width 1.00. The waste is a few thousandths of a bit. The curve fits. Laplace. The peak is too sharp and the tails too heavy: you pay for it at every value. Flat 8 bits. This is raw int8: the model says every value from −128 to 127 is equally likely. …
6.2 Everything is a probability model › Look at the actual distribution
Three situations
One needle. A single token holds 92% of the weight. TopK with one token is within 0.02 of the truth. This is the world TopK was designed for. A loud few, a quiet crowd. Six tokens score high and say one thing; thirty-four score lower and say another. TopK …
8.2 MagicPIG: don't pick the tallest › Picking the tallest
Break the guess
Slide the guess all the way to uniform. The plain average (red) now answers a different question entirely: the unweighted mean of all tokens. The correction pulls the green estimates toward the truth, but with few draws their average can still miss it. Slide …
8.2 MagicPIG: don't pick the tallest › The catch: you cannot sample without looking
A line through the cloud
Set thickness to 25% and click Align with the cloud. Most variation survives along that line. Turn the line to 120°. It now runs across the cloud; the residuals grow. Align again, then add a constant offset. Raw energy in the mean rises, while centred …
9.2 The shape of cached values › Try a smaller world
Count what is left behind
Choose Exactly 32 and retain 32 directions. All variance survives. Choose Long tail, still keeping 32. A small effective dimension coexists with substantial discarded variance. Choose Equal in 256. Keeping 32 now retains only one eighth; there is no preferred …
9.2 The shape of cached values › A small dimension number can hide a long tail

Code sketches 26

Short numpy versions of the ideas.

numpyThe naive version of all three stages
# Stage 1: the same model embeds the corpus and the query X = embed (documents) # N texts -> (N, d) matrix, each row has length 1 q = embed ([ query ])[ 0 ] # …
1.1 The whole map › The entire pipeline in nine lines
numpySkip-gram with negative sampling, the whole idea
# Two tables of shape (vocab_size, d), random at the start. # For every (center, context) pair in real text, plus k random "negative" words: pos = sigmoid …
1.2 Meaning from context › word2vec: predict instead of count
numpyInfoNCE, the loss behind nearly every modern embedding model
# q, p: (B, d) normalized embeddings of B queries and their matching passages logits = (q @ p. T) / 0.05 # B x B similarity matrix, sharpened by a temperature …
1.4 The secret ingredient › The loss, in four lines
numpyThree measures, one ranking
a, b = a / np. linalg. norm (a), b / np. linalg. norm (b) cos = a @ b l2sq = ((a - b) ** 2). sum () # equals 2 - 2*cos for unit vectors
1.7 What does "close" mean? › On unit vectors they are one measure
numpyBrute force
X = embed (corpus) # (N, d), rows normalized q = embed ([ "how do I reset my router" ])[ 0 ] scores = X @ q # N*d multiply-adds: one matrix-vector product …
1.7 What does "close" mean? › Exact search is fine, for a while
numpySimHash in three lines
R = np. random. randn (d, 16) # 16 random hyperplanes through the origin signature = lambda v: tuple (v @ R > 0) # 16 bits # For vectors at angle theta, each …
2.2 Cut the space into pieces › Family 2 · Hashing: make collisions mean closeness
numpyScalar and binary quantization
x = X. astype (np. float32) # 768 dims: 3,072 bytes each int8 = np. round (x / np. abs (x). max (0) * 127). astype (np. int8) # 768 bytes, 4x smaller bits = …
2.5 Napkin math › The cheap tricks, in three lines
sentence-transformersEmbed a book
from sentence_transformers import SentenceTransformer import numpy as np def windows (words, size = 48, stride = 24): for s in range (0, max (1, len (words) - …
3.2 The running example › From a book to a sequence of vectors
numpyMeasure it yourself
Xc = X - X. mean (0) ev = np. linalg. svd (Xc, compute_uv = False) ** 2 ev /= ev. sum () print ("variance in the top 64 directions:", ev [: 64 ]. sum ()) # …
3.3 Know your data › Variance is concentrated in a few directions
numpyVQ in numpy: encode = nearest neighbour, decode = lookup
def nearest (X, C): # ||x-c||² = ||x||² - 2x·c + ||c||²; drop ||x||², it doesn't move the argmin return (- 2 * X @ C. T + (C ** 2). sum (1)). argmin (1) codes …
4.1 One codebook, and the wall › Replace each vector by its nearest representative
numpyProduct quantization
def pq_encode (X, codebooks): # M arrays of shape (K, d/M) blocks = np. split (X, len (codebooks), axis = 1) return np. stack ([ nearest (B, C) for B, C in zip …
4.2 Codebooks that add up › Restrict: product quantization
numpyResidual quantization
def rq_encode (X, codebooks): # M arrays of shape (K, d) R, codes = X. copy (), [] for C in codebooks: i = nearest (R, C) codes. append (i) R -= C [ i ] # the …
4.3 Be greedy › Quantize what is left
numpyBeam search
def beam_encode (x, codebooks, B = 8): beam = [((), x)] # (partial code, residual) for C in codebooks: cand = [] for code, r in beam: err = ((r - C) ** 2). sum …
4.4 Encoding is the hard part › Beam search: greedy, but hedge your bets
numpyICM, and LSQ's perturb-and-retry around it
def icm_encode (x, codebooks, codes, n_iter = 4): codes, M = codes. copy (), len (codebooks) for _ in range (n_iter): for m, C in enumerate (codebooks): rest = …
4.5 Fix all but one › Iterated conditional modes
numpyAlternate: encode, then solve for the codebooks
def update_codebooks (X, codes, K): N, M = codes. shape B = np. zeros ((N, M * K)) # sparse in practice B [ np. arange (N)[:, None ], np. arange (M) * K + …
4.6 Learning the codebooks › The decoder update is least squares
numpyADC search
def adc_search (q, codes, codebooks, norms_sq, topk = 10): M = codes. shape [ 1 ] luts = np. stack ([ C @ q for C in codebooks ]) # (M, K), once per query ip = …
4.7 Searching without decoding › Asymmetric distance computation
faissIn practice: Faiss index-factory strings
import faiss d = 384 index = faiss. index_factory (d, "IVF4096,RQ16x8_Nqint8") # 16 B code + 1 B norm faiss. extract_index_ivf (index). rq. max_beam_size = 4 # …
4.7 Searching without decoding › Three tricks production systems stack on top
numpySimHash
R = np. random. randn (n_bits, d) # one random hyperplane per bit bits = (X @ R. T) > 0 # (N, n_bits) booleans # two rows differ in about n_bits * angle / pi …
5.1 Hash functions that like their neighbours › SimHash: one hyperplane, one bit
numpyBinary sketches and Hamming search
bits = np. packbits ((X - mean) @ R. T > 0, axis = 1) # N x (b/8) bytes qbit = np. packbits ((q - mean) @ R. T > 0) ham = np. unpackbits (bits ^ qbit, axis = …
5.4 Bits as a compressed sketch › From collision probability to an estimator
numpy + scipyTriangular prediction: the lossless decorrelator
from scipy.linalg import solve_triangular m = X_train. mean (0) L = np. linalg. cholesky (np. cov ((X_train - m). T) + np. eye (d) / 12) # fit once def …
6.4 The transform zoo › The lossless twin of a rotation
numpyIdeal code length of the stored indices
def code_entropy_bits (codes_train, codes_test, K = 256): total = 0.0 for m in range (codes_train. shape [ 1 ]): p = np. bincount (codes_train [:, m ], …
6.8 Squeezing the codes themselves › The indices are not uniform
numpyAttention
scores = K @ q / np. sqrt (d) # similarity of the query to every stored key (MIPS!) w = softmax (scores) # a soft version of "pick the nearest" out = w @ V # …
7.3 The same math in other places › Attention is a soft nearest-neighbour lookup
after Algorithm 1MagicPIG's estimate for one query
s = (K_S @ q) / np. sqrt (d) # scores of the sampled keys only p = 1 - np. arccos (cos (q, K_S - mu)) / np. pi # SimHash: chance one bit agrees u = 1 - (1 - p …
8.2 MagicPIG: don't pick the tallest › A hash that knows its odds
kvdiffOpen the experiment
uv run marimo edit notebooks/03_v_spectrum.py
9.2 The shape of cached values › Reproduce and trace the results
kvdiffRebuild the original overview
uv run python overview_src/build.py 03_v_spectrum
9.2 The shape of cached values › Reproduce and trace the results
Close EnoughImport the measurements
uv run experiments/import_kvdiff.py /attic/d/kvdiff/overviews/03_v_spectrum.html uv run build.py
9.2 The shape of cached values › Reproduce and trace the results

Checkpoints 48

The end-of-page summary of each page: the fastest way to review.

After 1.1 The whole map
Stage 1 makes vectors, stage 2 finds near ones, stage 3 uses them. A term is easier to learn once you know which stage it belongs to. Compression is a stack of four layers that sits inside stage 2.
1.1 The whole map › A fourth box hiding inside the second
After 1.2 Meaning from context
Sparse keyword vectors cannot see that two different words mean the same thing. The distributional hypothesis turns “meaning” into something countable: shared contexts. LSA and word2vec both compress co-occurrence statistics into a few hundred dimensions. A …
1.2 Meaning from context › Where it runs out
After 1.3 Context arrives
Transformers produce contextual vectors: one per token, per sentence. An embedding is the pooled, normalized last layer of the whole model, not its first layer. A model trained to predict tokens does not automatically produce vectors where distance means …
1.3 Context arrives › Why the raw states are not enough
After 1.4 The secret ingredient
Contrastive training makes distance mean relevance, by classifying the right partner among a batch. Batch size, temperature and hard negatives are the levers. Modern embedders are LLM backbones fine-tuned this way; a bi-encoder is what makes indexing possible.
1.4 The secret ingredient › Four terms from every model card
After 1.5 What the geometry means
Embeddings are directions; closeness is the angle between them, and it only means something relative to everything else. Attributes such as sentiment and tense are directions, found by averaging differences, and no single coordinate carries them. “Similar” …
1.5 What the geometry means › What the experiments showed
After 1.6 The shape of the cloud
The cloud leans one way: random pairs have cosine 0.16, not 0. Subtract the mean first. A few passages become everyone’s neighbour (hubs). Centring removes the part caused by the lean; crowded regions keep the rest. About 68 directions out of 384 are …
1.6 The shape of the cloud › Why this matters for the rest of the book
After 1.7 What does "close" mean?
kNN: find the k most similar stored vectors. Cosine, dot product and L2 agree on unit vectors. Brute force is one matrix product and is fine up to roughly a million vectors. In high dimensions random points are all nearly equidistant; indexes survive only …
1.7 What does "close" mean? › The villain: distances concentrate
After 1.8 Interlude: seventy years in one page
Two threads: how to make vectors that carry meaning, and how to search and store vectors. They merged when pretrained transformers made dense retrieval beat keyword search.
1.8 Interlude: seventy years in one page › Three things to notice
After 2.1 Finding neighbours without checking everyone
ANN trades a little recall for a lot of speed by examining a small fraction of the data. Recall@k is measured against exact brute-force results. Trees, hashing, clustering and graphs are four ways of choosing the fraction.
2.1 Finding neighbours without checking everyone › Four families
After 2.2 Cut the space into pieces
Trees cut along coordinates and stop pruning in high dimensions. LSH cuts at random: no training, provable, but blind to the data. IVF cuts where k-means says the data is. nprobe trades speed for recall.
2.2 Cut the space into pieces › The cluster id is already compression
After 2.3 Walk toward the query
A graph index walks greedily toward the query, keeping the best efSearch candidates. HNSW’s layers make the first long stretch take only a few hops. The cost is RAM for links, hard deletes and awkward filtering.
2.3 Walk toward the query › Relatives
After 2.4 The index lab
Every index has one knob that buys recall with work. Flat is exact and simple; IVF and PQ scale by partitioning and compressing; HNSW is fastest when RAM is plentiful. FAISS is a library of these pieces; a vector database is a product built around them.
2.4 The index lab › Two things every real system adds
After 2.5 Napkin math
Size = vectors × dimensions × bytes per number. Compute it before anything else. The redundancy is in precision, in correlation between coordinates, and in correlation between vectors. Generic compressors cannot see any of the three.
2.5 Napkin math › The standard production pattern
After 3.1 Compression is a stack
Transform, quantize, predict, entropy-code: four layers, four kinds of structure. PCA is a layer-1 tool, VQ a layer-2 tool; they are combined, not compared. Lossless compression reuses the stack with the quantizer demoted to a predictor.
3.1 Compression is a stack › What each family is good at
After 3.2 The running example
Marginalia turns books into a sequence of unit vectors, 300 million of them. Two jobs: a lossy search index at about 16 bytes per vector, and a lossless archive. Encoding happens once; searching happens on every query.
3.2 The running example › The five-number scorecard
After 3.3 Know your data
Centre the vectors: the mean has length 0.44 and carries no information about any one passage. The spectrum is lopsided: 82 directions hold two thirds of the variance; the effective dimension is about 68. Consecutive windows have cosine 0.70: the data is a …
3.3 Know your data › And the numbers themselves
After 3.4 From spectrum to bit budget
Water-filling: direction $i$ gets $\tfrac12\log_2(\lambda_i/\theta)$ bits; directions below the water level get none. Transform + scalar is within ¼ bit per dimension of optimal, which is excellent at high rates and fatal at very low ones. Vector quantizers win below roughly one …
3.4 From spectrum to bit budget › What to read for the theory
After 3.5 Scalar quantization
Uniform rounding with step Δ has error Δ²/12; each extra bit quarters it. int8 costs almost nothing in recall; 1 bit per coordinate needs re-ranking. Scalar quantizers cannot go below 1 bit per dimension and cannot see correlations.
3.5 Scalar quantization › Where it stops
After 4.1 One codebook, and the wall
VQ: k-means centroids as a codebook, the nearest centroid’s index as the code. Distortion falls like $2^{-2R/d}$ : high dimension needs astronomically many codewords. A huge codebook breaks storage, training and encoding all at once.
4.1 One codebook, and the wall › The wall: bits per dimension
After 4.2 Codebooks that add up
M codebooks × K entries give $K^M$ reachable points from $MK$ stored vectors. Decoding is M lookups. Encoding is a search over $K^M$ combinations. PQ makes the search trivial by forcing the codebooks into separate blocks, at the cost of a …
4.2 Codebooks that add up › Restrict: product quantization
After 4.3 Be greedy
RQ quantizes the residual of the previous stage; every codebook is free to point anywhere. Greedy encoding is cheap and suboptimal: early stages cannot see what later ones could fix. Any prefix of the code is a coarser code.
4.3 Be greedy › Measured
After 4.4 Encoding is the hard part
Encoding minimises unary + pairwise energy; the pairwise graph’s shape sets the difficulty. PQ has no edges, trees are exactly solvable, free additive codebooks are fully connected. Beam search keeps B partial codes per stage; gains flatten quickly.
4.4 Encoding is the hard part › Beam search: greedy, but hedge your bets
After 4.5 Fix all but one
ICM re-optimises one codebook’s choice at a time and stops at a local minimum; random perturbations (LSQ) escape it. With no overlap between codebooks every encoder is exact; the harder the overlap, the more search pays. An ILP gives the exact optimum and is …
4.5 Fix all but one › Exact answers: integer linear programming
After 4.6 Learning the codebooks
Training alternates: encode (hard, combinatorial) ↔ codebook update (least squares). Training therefore costs as much as encoding the training set, many times over. Free codebooks have hundreds of thousands of parameters; measure on held-out data.
4.6 Learning the codebooks › The overfitting trap
After 4.7 Searching without decoding
ADC scores a query against a code with M table lookups, the same for PQ, RQ and additive codes. Additive codes need $\lVert\hat x\rVert^2$ for L2 search: one extra byte. Not for inner product. Fast-scan, IVF and re-ranking are what turn a quantizer into a search system.
4.7 Searching without decoding › Three tricks production systems stack on top
After 4.8 Measured on real embeddings
At 64 bits: PQ 0.71, OPQ 0.56, greedy RQ 0.54, LSQ 0.48 relative error. The big steps are freeing the codebooks and adding bytes; heavier encoders add a few percent. Using the order of the data beats heavier search, but costs random access.
4.8 Measured on real embeddings › What Priya takes away
After 4.9 Bells and whistles
Centre, rotate and partition before quantizing; re-rank and compress ids after. Mixed families (product of additive, 4-bit fast-scan) trade a little accuracy for encoding or scanning speed. Neural codebooks have the lowest error and the most expensive decoder.
4.9 Bells and whistles › Same idea, other fields
After 5.1 Hash functions that like their neighbours
An LSH family makes close points collide with probability at least $p_1$ and far points at most $p_2$ . SimHash: one random hyperplane per bit; two vectors at angle θ disagree with probability θ/π. On real embeddings $p_1$ and $p_2$ are close …
5.1 Hash functions that like their neighbours › Two ways to use the bits
After 5.2 Turning a gentle slope into a cliff
AND over k bits: collision probability $p^k$ , which makes buckets selective. OR over L tables: $1-(1-p^k)^L$ , which rescues recall. With $k = \ln N/\ln(1/p_2)$ and $L = N^{\rho}$ , query time is about $N^{\rho}$ , where $\rho = \ln(1/p_1)/\ln(1/p_2)$ . On real embeddings ρ is about 0.75: the gap …
5.2 Turning a gentle slope into a cliff › The memory bill
After 5.3 Random cuts against learned cuts
On real embeddings, IVF finds roughly twice the neighbours of LSH for the same work. Multi-probe trades tables for extra bucket probes; data-dependent hashing turns into quantization. LSH remains the tool for near-duplicates, streaming inserts and settings …
5.3 Random cuts against learned cuts › Where hashing is still the right tool
After 5.4 Bits as a compressed sketch
Hamming distance over b random sign bits estimates the angle with error proportional to $1/\sqrt b$ . Binary quantization is SimHash with axis-aligned hyperplanes; rotate first so that every bit matters. Keep the query in floats: the asymmetric score roughly …
5.4 Bits as a compressed sketch › Bits against codebooks
After 6.1 Every bit must come back
Two jobs: an archive (sequential, slow encode allowed) and the wire (random access, fast decode). “Exact” needs a target; int8 is the practical one. A lossless codec is a probability model plus an entropy coder, and code length is $-\log_2 q$ .
6.1 Every bit must come back › Where this part ends up
After 6.2 Everything is a probability model
Cost = entropy + KL divergence. The model’s fit is the only thing you control. A Gaussian coordinate on a grid costs about $\log_2(\sigma/\Delta) + 2.05$ bits. For embeddings, one bell curve per coordinate removes 19% of raw int8 and no fancier marginal model does better.
6.2 Everything is a probability model › What is still on the table
After 6.3 Floats are stubborn
A float32 embedding coordinate has about 27 bits of entropy, nearly all of it mantissa noise. Byte-shuffling plus zstd is the practical limit for bit-exact floats; predictors do not help. Pick the precision you trust (int8 or 16-bit fixed point) and be exact …
6.3 Floats are stubborn › The lesson
After 6.4 The transform zoo
Decorrelation is worth $\tfrac12\sum\log_2(\sigma_i^2/\lambda_i)$ bits: 260 per vector here. A rotation breaks the integer grid, so it cannot be used directly for lossless coding. Predicting each coordinate from the earlier ones (a triangular transform) captures the same gain and is exactly …
6.4 The transform zoo › The lossless twin of a rotation
After 6.5 The prediction zoo
A predictor narrows the bell curve by $\sqrt{1-\rho^2}$ , saving $\tfrac12\log_2\frac{1}{1-\rho^2}$ bits per coordinate. The previous window saves 133 bits per vector with one parameter; a full matrix adds almost nothing. Previous-window and earlier-coordinate prediction stack to 2,171 bits. …
6.5 The prediction zoo › Predict only when it helps
After 6.6 The entropy-coder zoo
Fixed width, Rice, Huffman, arithmetic/ANS: in that order they get closer to the entropy and need more machinery. For wide, per-coordinate bell curves with moving centres, a static Gaussian model with rANS or range coding is the natural fit. A real coder …
6.6 The entropy-coder zoo › Practicalities that decide a format
After 6.7 Where should the bits go?
Two-part code: total = side information + residual. Halving the error saves one bit per dimension. Add an 8-bit stage only if it cuts the error by more than $2^{-16/d}$ (2.8% at $d$ = 384). Every dial is set where a bit spent saves exactly a bit …
6.7 Where should the bits go? › The hyperparameter sheet
After 6.8 Squeezing the codes themselves
RQ indices carry about 59 bits of information in 64 stored bits; conditioning on the previous window gets to 55. The coarse first stage is the most predictable; the model must match the data it is used on. Entropy-coded indices and delta-coded ids are for …
6.8 Squeezing the codes themselves › The ids deserve the same treatment
After 6.9 Two codecs
Archive: int8 → mean → previous window → earlier coordinates → rANS, chunked at keyframes. 1.41× smaller than raw int8. Wire: the same minus the previous window; a model on both ends beats zstd by a wide margin. A format needs deterministic arithmetic, …
6.9 Two codecs › What Marginalia ships
After 7.1 Where you see this in practice
Search, RAG, recommendations, multimodal search and dedup all reduce to “embed, then find neighbours”. Keyword and vector search coexist; hybrid plus re-ranking is the norm. Tools differ mainly in whether they are a library, an engine or a database.
7.1 Where you see this in practice › The tool landscape
After 7.2 The funnel
Large systems retrieve cheaply with an indexable model, then rank expensively. Two-tower models are restricted to a dot product precisely so that item vectors can be indexed. The right index depends mostly on how many vectors you have.
7.2 The funnel › What bites, in the order teams discover it
After 7.3 The same math in other places
Attention is a soft nearest-neighbour lookup over keys, with the KV cache as its datastore. LSH, clustering and quantization are being applied inside transformers for long contexts and smaller caches. Quantization, low-rank factorization and sketching recur …
7.3 The same math in other places › Where the two worlds have merged
After 7.4 The big picture
Place a compressor by where it spends compute (encode or decode) and by how much order it needs. Additive codebooks are the encoder-heavy, decode-cheap tool for static, memory-bound indexes. A real product mixes tiers: compact codes in RAM, finer vectors for …
7.4 The big picture › A decision guide
After 8.1 Paper club
Each chapter restates one paper in this book’s language and connects it to earlier pages. Measured boxes are our own re-runs, not the paper’s numbers. Doubts are listed explicitly and argued, not implied.
8.1 Paper club › The papers
After 8.2 MagicPIG: don't pick the tallest
Attention’s output is an average. TopK misses it by (skipped weight) × (how different the skipped values are), every time; direct sampling from the true weights is unbiased. Sampling from a cheap guess needs known, positive probabilities and …
8.2 MagicPIG: don't pick the tallest › What it suggests
After 9.1 Our experiments
The figures distinguish synthetic toys from measured model data. A low reconstruction error still needs a model-output check. A promising ideal rate still needs an actual codec, with all storage counted.
9.1 Our experiments › What comes next
After 9.2 The shape of cached values
A concentrated spectrum does not make its tail cheap to delete: 32 directions leave about 44% of held-out variation behind. Bases transfer best between these sequences at a fixed layer and head, with exceptions that need wider testing. Large means and uneven …
9.2 The shape of cached values › Reproduce and trace the results