Glossary

Embeddings

anisotropyanisotropic

Embeddings crowding into a narrow cone, so even unrelated pairs have a clearly positive cosine. Subtracting the mean vector removes most of it.

Explained in 1.5 What the geometry means

bi-encoderbi-encoders

A model that embeds the query and the document separately, so document vectors can be computed once and indexed.

Explained in 1.4 The secret ingredient

BM25

The classic keyword-ranking formula (term frequency, rarity, document length). Each vocabulary word is its own dimension, so synonyms do not match.

Explained in 1.2 Meaning from context

contrastive trainingcontrastive learning, contrastive objective, contrastively

Train on pairs that should match. Pull each pair's vectors together and push every other pairing in the batch apart.

Explained in 1.4 The secret ingredient

cross-encodercross-encoders

A model that reads query and document together and outputs one score. Accurate, but nothing can be precomputed, so it only re-ranks a shortlist.

Explained in 1.4 The secret ingredient

distributional hypothesis

Words that appear in similar contexts have similar meanings. The founding idea behind every embedding method.

Explained in 1.2 Meaning from context

embeddingembeddings, dense embedding, embedding vector

A list of a few hundred to a few thousand numbers that places an item (text, image, user) in a space where nearby points mean similar things.

Explained in 1.1 The whole map

hard negativehard negatives

A training example that looks relevant but is not. It teaches the model the fine distinctions that random negatives never test.

Explained in 1.4 The secret ingredient

hubness

In high dimensions a few points become a nearest neighbour of very many others.

Explained in 1.5 What the geometry means

InfoNCE

The loss behind most embedding models. A cross-entropy over a batch that asks "which of these B passages belongs to my query?"

Explained in 1.4 The secret ingredient

intrinsic dimension

How many numbers you really need to locate a point on the surface the data lies near. Far fewer than the embedding's nominal dimension.

Explained in 1.5 What the geometry means

LSALatent Semantic Analysis

Latent Semantic Analysis (1990). Compress the word–document count matrix with SVD; the first dense semantic vectors.

Explained in 1.2 Meaning from context

Matryoshka embeddingsMatryoshka

Embeddings trained so that the first k coordinates are already a usable embedding, which lets you truncate to save space.

Explained in 1.4 The secret ingredient

MTEB

The Massive Text Embedding Benchmark. The standard leaderboard for comparing embedding models.

Explained in 1.4 The secret ingredient

poolingmean-pooling, mean pooling

Turning one vector per token into one vector per text, usually by averaging them or taking a special token's state.

Explained in 1.3 Context arrives

superposition

A network packing more concepts than it has dimensions by letting them overlap as almost-orthogonal directions.

Explained in 1.5 What the geometry means

word2vec

A table with one learned vector per word, trained (2013) to tell a word's real neighbours in text from random words.

Explained in 1.2 Meaning from context

Search

ADCasymmetric distance computation

Asymmetric distance computation. Keep the query exact, compress the database, and score each code with M table lookups.

Explained in 4.7 Searching without decoding

ANNapproximate nearest neighbour

Approximate nearest-neighbour search. Look at a small, well-chosen fraction of the data and accept missing a few true neighbours.

Explained in 2.1 Finding neighbours without checking everyone

cosine similaritycosine

The cosine of the angle between two vectors, $a\cdot b / (\lVert a\rVert\lVert b\rVert)$. For unit vectors it equals the dot product.

Explained in 1.7 What does "close" mean?

curse of dimensionality

In hundreds of dimensions, distances between random points concentrate around one value, so space-splitting tricks stop pruning.

Explained in 1.7 What does "close" mean?

DiskANNVamana

A graph index (Vamana) laid out to be read from SSD, with only compressed vectors in RAM. Billion-scale search on one machine.

Explained in 2.3 Walk toward the query

dot productinner product

$a \cdot b = \sum_i a_i b_i$. Cares about angle and length. On unit vectors it ranks exactly like cosine and like Euclidean distance.

Explained in 1.7 What does "close" mean?

efSearch

The width of the candidate list a graph search keeps. Larger means more distance computations and higher recall.

Explained in 2.3 Walk toward the query

HNSW

Hierarchical Navigable Small World. A layered neighbour graph searched by greedy hops; the default index in most vector databases.

Explained in 2.3 Walk toward the query

IVFinverted file index

Inverted file index. Cluster the vectors with k-means, keep one list per cluster, and scan only the few lists nearest the query.

Explained in 2.2 Cut the space into pieces

k-d treek-d trees

A tree that splits space one coordinate at a time. Excellent in 2 to 10 dimensions, useless at 768.

Explained in 2.2 Cut the space into pieces

k-meansLloyd's algorithm

Find K centroids that minimise squared distance to their assigned points by alternating two steps: assign each point to its nearest centroid, move each centroid to the mean of its points.

Explained in 2.2 Cut the space into pieces

kNNk-nearest-neighbour

k-nearest-neighbour search. Given a query, return the k stored vectors most similar to it. Exact kNN compares against everything.

Explained in 1.7 What does "close" mean?

L2Euclidean distance

Straight-line distance $\lVert a-b\rVert$. For unit vectors, $\lVert a-b\rVert^2 = 2 - 2\,a\cdot b$.

Explained in 1.7 What does "close" mean?

MIPSmaximum inner product search

Maximum inner product search. Nearest-neighbour search when vectors are not normalised, so length matters.

Explained in 1.7 What does "close" mean?

nprobe

How many IVF lists to scan per query. The knob that trades speed for recall.

Explained in 2.2 Cut the space into pieces

re-rankingrerank, re-rank, reranking, reranker

Fetch a shortlist with a cheap, compressed index, then re-score just those candidates with exact vectors or a heavier model.

Explained in 2.5 Napkin math

recall@krecall@10, 10-recall@10

Of the true k nearest neighbours, the fraction the approximate method returned. The standard quality measure for ANN.

Explained in 2.1 Finding neighbours without checking everyone

Hashing

amplificationAND-OR construction

Combine k hash bits with AND to make buckets selective, then L tables with OR to catch misses. Turns a gentle collision curve into a steep S-curve.

Explained in 5.2 Turning a gentle slope into a cliff

binary quantizationbinary codes, binary quantisation

Keep only the sign of each coordinate (1 bit per dimension, 32× smaller than float32) and compare with Hamming distance.

Explained in 5.4 Bits as a compressed sketch

Hamming distanceHamming

The number of positions where two bit strings differ. Computed with XOR and a popcount, among the fastest operations a CPU has.

Explained in 5.4 Bits as a compressed sketch

Johnson–Lindenstrauss lemmaJohnson–Lindenstrauss

Projecting points onto a random lower-dimensional subspace approximately preserves all pairwise distances. The reason random projections work.

Explained in 5.1 Hash functions that like their neighbours

LSHlocality-sensitive hashing

Locality-sensitive hashing. Hash functions built so that close points collide with higher probability than far ones.

Explained in 5.1 Hash functions that like their neighbours

LSH exponent ρ

$\rho = \ln(1/p_1)/\ln(1/p_2)$. LSH answers a query in about $N^\rho$ work; smaller is better and it is always below 1.

Explained in 5.2 Turning a gentle slope into a cliff

MinHash

LSH for set overlap. The probability that two sets share a min-hash equals their Jaccard similarity. The workhorse of near-duplicate detection.

Explained in 5.3 Random cuts against learned cuts

multi-probe LSHmulti-probe, multiprobe

Besides the query's own bucket, also look in buckets that differ in the bits the query was least sure about. Fewer tables for the same recall.

Explained in 5.3 Random cuts against learned cuts

RaBitQ

A binary code (random rotation, then signs) paired with an unbiased distance estimator that has a proven error bound.

Explained in 5.4 Bits as a compressed sketch

SimHashrandom hyperplanes, random-hyperplane

LSH for angles. Each bit records which side of a random hyperplane a vector is on; two vectors at angle $\theta$ agree on a bit with probability $1-\theta/\pi$.

Explained in 5.1 Hash functions that like their neighbours

Quantization

additive quantizationAQ, additive codebooks

Approximate a vector by a sum of one codeword from each of M unconstrained codebooks. Finding the best combination is the hard part.

Explained in 4.4 Encoding is the hard part

beam search

A greedy search that keeps the B best partial solutions at every step instead of one.

Explained in 4.4 Encoding is the hard part

code

The integers actually stored for a vector, one index per codebook.

Explained in 4.2 Codebooks that add up

codebookcodebooks, codeword, codewords

A list of K representative vectors (codewords). The decoder is a table lookup into it.

Explained in 4.1 One codebook, and the wall

effective dimensionparticipation ratio, PR

The number of equally energetic directions with the same variance concentration, (sum of variances)² / sum of squared variances. It is not a safe truncation rank.

Explained in 9.2 The shape of cached values

eigenvalue spectrumspectrum

The variance along each principal direction, sorted from largest to smallest. It says where the information is.

Explained in 3.3 Know your data

fast-scanFastScan

4-bit codes whose lookup tables fit in a SIMD register, so one shuffle instruction performs 16 or 32 lookups at once.

Explained in 4.7 Searching without decoding

ICMiterated conditional modes

Iterated conditional modes. Re-optimise one codebook's choice exactly while holding the others fixed, and cycle until nothing changes.

Explained in 4.5 Fix all but one

ILPinteger linear program

Integer linear program. An exact formulation of the encoding problem; a measuring stick, not a production encoder.

Explained in 4.5 Fix all but one

LSQLSQ++

Local search quantization. Additive codebooks encoded with ICM plus random perturbations to escape local minima.

Explained in 4.5 Fix all but one

OPQ

Optimized product quantization. Learn a rotation before PQ so that the blocks are as independent as possible.

Explained in 4.2 Codebooks that add up

PCASVD, principal component analysis, principal directions

Rotate the axes so that the first one carries the most variance, the second the most of what remains, and so on. Computed with an SVD.

Explained in 3.3 Know your data

PQproduct quantization

Product quantization. Cut the vector into M blocks and vector-quantize each block with its own small codebook.

Explained in 4.2 Codebooks that add up

QINCoQINCo2

Residual quantization where a small neural network generates each stage's codebook from the reconstruction so far.

Explained in 4.9 Bells and whistles

quantizationquantizer, quantizers

Replacing a value (or a whole vector) by the nearest member of a finite set, so that it can be named with a few bits.

Explained in 3.1 Compression is a stack

residualresiduals

What is left after subtracting the current approximation or prediction. The part that still has to be described.

Explained in 4.3 Be greedy

reverse water-fillingwater-filling

The optimal bit allocation for Gaussian data: direction i gets $\tfrac12\log_2(\lambda_i/\theta)$ bits, and directions below the water level $\theta$ get none.

Explained in 3.4 From spectrum to bit budget

RQresidual quantization, RVQ

Residual quantization. Quantize the vector, subtract, quantize what is left, and repeat. Each stage's codebook uses all dimensions.

Explained in 4.3 Be greedy

scalar quantizationint8, SQ

Round each coordinate separately to one of $2^b$ levels. int8 uses 8 bits per coordinate, 4× smaller than float32.

Explained in 3.5 Scalar quantization

transform coding

Rotate into a basis where coordinates are uncorrelated, quantize each coordinate separately, then entropy-code. The JPEG recipe.

Explained in 3.1 Compression is a stack

vector quantizationVQ

Replace a whole vector by the index of its nearest codeword in a learned codebook. $\log_2 K$ bits for a codebook of K entries.

Explained in 4.1 One codebook, and the wall

Information theory

6 dB per bit

Each extra bit per coordinate halves the quantization step and quarters the squared error (a factor of 4 is 6.02 dB).

Explained in 3.5 Scalar quantization

ANSrANS, tANS, asymmetric numeral systems

Asymmetric numeral systems. Entropy coding with arithmetic-coding accuracy at close to Huffman speed. Used in zstd.

Explained in 6.6 The entropy-coder zoo

arithmetic codingrange coder, range coding

Encodes a whole message as one number inside an interval that shrinks by each symbol's probability. Within a fraction of a bit of the model's cross-entropy.

Explained in 6.6 The entropy-coder zoo

byte shufflebyte-shuffling, shuffle

Regroup the bytes of an array of numbers so that all first bytes sit together, then all second bytes, and so on. It makes the predictable bytes compressible.

Explained in 6.3 Floats are stubborn

closed-loop predictionclosed loop, closed-loop

Predict from the decoder's reconstruction, never from the original, so that encoder and decoder cannot drift apart.

Explained in 6.5 The prediction zoo

coding gaintransform coding gain

The bits saved by decorrelating before coding. For Gaussian data it is half the log of the ratio between the arithmetic and geometric mean of the variances.

Explained in 6.4 The transform zoo

cross-entropy

The bits you actually pay when the data follows $p$ but your coder assumes $q$. It equals the entropy plus the KL divergence.

Explained in 6.2 Everything is a probability model

differential entropy

Entropy for a continuous density, $h = -\int f \log_2 f$. Quantizing with step $\Delta$ costs about $h - \log_2 \Delta$ bits.

Explained in 6.2 Everything is a probability model

entropy

$H = -\sum_x p(x)\log_2 p(x)$, the average number of bits per symbol that an ideal code needs when symbols follow $p$.

Explained in 6.2 Everything is a probability model

entropy codingentropy coder, entropy-coded, entropy coders

Storing each symbol in about $-\log_2 q$ bits, where $q$ is its probability under a model. Frequent symbols get short codes.

Explained in 6.6 The entropy-coder zoo

Golomb–RiceRice codes, Golomb-Rice, Rice coding

A one-parameter family of codes for geometrically distributed integers. No tables; the choice inside FLAC.

Explained in 6.6 The entropy-coder zoo

Huffman codingHuffman

The optimal code that spends a whole number of bits per symbol. It wastes up to one bit per symbol when probabilities are skewed.

Explained in 6.6 The entropy-coder zoo

keyframekeyframes

A value coded without reference to its predecessors. It bounds error propagation and allows decoding to start in the middle.

Explained in 6.5 The prediction zoo

KL divergenceKL

$D(p\Vert q) = \sum p \log_2 (p/q)$. The extra bits per symbol paid for coding with the wrong model.

Explained in 6.2 Everything is a probability model

MDLminimum description length

Minimum description length: prefer the model for which model bits plus data-given-model bits is smallest.

Explained in 6.7 Where should the bits go?

near-lossless

Compression that guarantees every value comes back within $\pm\epsilon$ of the original.

Explained in 6.9 Two codecs

prediction gain

The factor by which prediction shrinks the energy to be coded. For correlation $\rho$ it is $1/(1-\rho^2)$.

Explained in 6.5 The prediction zoo

predictive codingDPCM, delta coding

Guess the next value from what the decoder already has, and spend bits only on the prediction error.

Explained in 6.5 The prediction zoo

rate–distortionrate-distortion

The theory of the best possible trade between bits spent (rate) and error accepted (distortion).

Explained in 3.4 From spectrum to bit budget

two-part codeside information

Describe the data as a model choice (side information) plus the data given that model. Lossless coding with a quantizer is exactly this.

Explained in 6.7 Where should the bits go?

zstdZstandard

A general-purpose compressor (repeated-string matching plus ANS). Great on text, weak on floats because it looks for repeated bytes.

Explained in 6.3 Floats are stubborn

Systems

attention sinkattention sinks, sink token

The first token of a sequence, which many attention heads point at when nothing else matches. Its key barely depends on the token, and its value is small. A built-in "none of the above".

Explained in 8.2 MagicPIG: don't pick the tallest

DLRM

Meta's deep learning recommendation model. The heavy ranking stage that scores a few thousand candidates after retrieval.

Explained in 7.2 The funnel

FAISS

Meta's open-source library of index types (Flat, IVF, PQ, HNSW and combinations). A toolkit, not a database.

Explained in 2.4 The index lab

hybrid search

Running keyword search and vector search side by side and merging the two ranked lists.

Explained in 7.1 Where you see this in practice

KV cache

The stored keys and values of earlier tokens that attention looks up at every step. An LLM's built-in vector datastore.

Explained in 7.3 The same math in other places

RAGretrieval-augmented generation

Retrieval-augmented generation. Retrieve relevant chunks with vector search and paste them into the LLM's prompt.

Explained in 7.1 Where you see this in practice

RoPErotary position embeddings, rotary embeddings

Rotary position embeddings. Each pair of coordinates of a query or key is rotated by an angle proportional to the token's position, so the dot product depends on relative position.

Explained in 8.2 MagicPIG: don't pick the tallest

ScaNN

Google's ANN library. Partitioning plus a quantizer that penalises errors parallel to the vector more than perpendicular ones.

Explained in 4.9 Bells and whistles

semantic IDssemantic ID, generative retrieval

Short code sequences from residual quantization of item embeddings, used as a vocabulary a transformer can generate.

Explained in 7.2 The funnel

two-towertwo-tower model

A recommender that scores user·item with one network per side, so item vectors can be precomputed and indexed.

Explained in 7.2 The funnel

vector databasevector databases, vector DB, vector DBs

A service that wraps ANN indexes in storage, an API, metadata filtering, replication and scaling.

Explained in 7.1 Where you see this in practice

Sampling

importance samplingself-normalized importance sampling

Estimate an average by sampling from a convenient distribution u instead of the true one w, and weighting each sample by w/u. The self-normalized variant divides by the sum of these weights and can be biased at finite sample sizes.

Explained in 8.2 MagicPIG: don't pick the tallest

TopK attentionsparse attention, top-k attention

Approximate attention by reading only the keys with the highest scores and renormalizing over them. Biased whenever the rest of the weight is not negligible.

Explained in 8.2 MagicPIG: don't pick the tallest

unbiasedunbiased estimator, unbiased estimate

An estimate whose average over many tries equals the true value. Its errors are noise that shrinks with more samples, not a lean in one direction.

Explained in 8.2 MagicPIG: don't pick the tallest