Case Study 2.3: How OpenAI and Facebook Speed Up Queries with Vector Databases

Concept. You built LSH, an approximate-nearest-neighbour (ANN) index. A vector database packages that idea for production. It runs an ANN index over embeddings, often a thousand or more numbers each, usually IVF or HNSW. It answers "find the 10 most similar" in milliseconds even when the store holds billions.

Intuition. An embedding maps meaning to coordinates, so similar text lands near in that space. An exact nearest-neighbour query computes a distance to every stored vector, O(N) per query, and OpenAI runs billions of queries. An approximate index builds once and serves many queries. It trades occasional misses for sub-millisecond lookups.

Case Study 2.3 Reading Time: 6 mins

The problem: a dot product against every row

OpenAI embeds documents into vectors of a thousand or more numbers: 1,536 on its smaller model, 3,072 on the large one. Take 1,536 as the running example below, and double every byte count for the large model. OpenAI searches billions of them. One nearest-neighbour query, done exactly, compares the query against every stored vector.

One query vector fans out to all N stored vectors, one 1,536-D dot product each. A cost panel tallies a million dot products, about 1.5 billion multiply-adds and 6 GB scanned per query, times billions of queries a day. A red bar: O(N) per query does not scale.

Figure 1. Exact scan against all N vectors. At a million vectors: a million 1,536-D L2 distances, about 1.5 billion multiply-adds and ~6 GB scanned per query. In FAISS this exact index is IndexFlatL2.

The fix: an approximate nearest-neighbour index

Approximate nearest-neighbour (ANN) search gives up the guarantee of returning the exact closest vectors for an answer that is almost always right and far cheaper. LSH, the index you built last page, is the simplest ANN method: random hyperplanes bucket similar vectors, you search one bucket. IVF and HNSW are improvements on the same idea, and what a production vector database uses. All three share one goal, look at far fewer than all N:

LSH. Random-hyperplane buckets, the one you built. Simple; lower recall per byte than the others, so production has mostly moved on, but still ANN.
IVF (inverted file). k-means the vectors into cells; a query probes only the few nearest cells and skips the rest.
HNSW (Hierarchical Navigable Small World). A hierarchy of proximity graphs: short near-neighbour links at the bottom, sparse long-range links on top. A query enters at the top and greedy-hops down toward itself. Best recall per millisecond, more memory; the common production default.

For all three the structure (the cuts, the clusters, or the graph) is built once at index time, when vectors are added. A query never rebuilds it; it just walks the small part near the query and skips the rest.

HNSW is the one to picture, and the production default. Start with the trip it imitates: you are in San Francisco and you want Stanford. You could go street by street, taking whichever turn points south. It works, and it takes all day. Instead you take the freeway, come off onto an expressway, and use local streets only at the end. Coarse and fast first, fine and slow last.

That is the whole design, and the name says it. HNSW is Hierarchical Navigable Small World. Hierarchical is the grades of road. Navigable Small World is the property that makes it work: give a graph a handful of long-range links and anything becomes reachable from anything else in a few hops. It is two ideas, and the first is the hierarchy, built once as vectors arrive.

A hierarchical near-neighbour graph. Layer 0 holds every vector with short links to its nearest neighbours; a few are promoted to layer 1 where they link much further, the expressways, and fewer still to layer 2 with the longest links of all, the freeways. Dashed verticals mark the same vector on more than one layer.

Figure 2. How the graph is built. Layer 0 holds every vector, each linked to its nearest neighbours with short local links. Layer 0 is the local streets. A few vectors are promoted to layer 1, where they link much further: the expressways. Fewer still reach layer 2, with the longest links of all: the freeways. The dashed verticals are the same vector appearing on more than one layer. This is built once, when vectors are added, never per query.

The second idea is the search, and it answers how the walk knows which way to go. A query is a vector we already hold, so at any node we can measure how far each neighbour sits from the query. The walk enters at the single top-layer node and steps to whichever neighbour is closest to the query, a long jump up top. When no neighbour is closer, it drops a layer and repeats, refining. The hierarchy is what stops a plain greedy walk from getting stuck: the upper layers cover ground fast, the bottom layer does the fine search.

Figure 3. HNSW search. The query vector defines a distance from the query to any visited node. The walk starts at a top-layer entry node, moves to the closest neighbour, then drops layers when it cannot improve. The search touches only the visited path and skips the rest of the graph.

An index here just means a structure that lets a query skip the full scan. You have already built two: the exact hash bucket (Basic Hashing) and the approximate LSH bucket. Module 3 builds the classical keyed indexes, B+Tree and LSM, for exact lookups; an ANN index is their approximate cousin, for "find similar."

import faiss
from sentence_transformers import SentenceTransformer

# Demo uses a smaller 768-D model so it runs in a notebook;
# OpenAI's are 1,536-D on the small model, 3,072-D on the large.
model = SentenceTransformer('all-mpnet-base-v2')          # 768-D
strings = [f"String {i}" for i in range(100_000)]
strings[42] = "String 42 is making me hungry"
emb = model.encode(strings).astype('float32')
d = 768
q = model.encode(["String 42 is making me hungry"]).astype('float32')

# Exact baseline: query vs all 100k vectors, O(N) per query
flat = faiss.IndexFlatL2(d)
flat.add(emb)
print(flat.search(q, 5))      # exact, scans everything

# ANN: IVF clusters; probe only a few of them
ann = faiss.IndexIVFFlat(faiss.IndexFlatL2(d), d, 256)  # 256 cells
ann.train(emb)                # learns the cluster centroids
ann.add(emb)
ann.nprobe = 8                # probe 8 of 256 cells, skip the rest
print(ann.search(q, 5))       # approximate, far fewer comparisons

Both return String 42 is making me hungry at distance ≈ 0 (it was embedded and queried) plus near neighbours. The flat index compares the query to all 100k vectors; the IVF index compares it only to the vectors in the 8 of 256 cells it probes, orders of magnitude fewer, missing a true neighbour only rarely. You can run this, and LSH, in the Hashing Colab.

Shrinking the vectors themselves so a billion of them fit in RAM is a separate lever, quantization, and the subject of Case Study 2.4.

Two panels: grey exact IndexFlatL2 compares the query to all 1M 1,536-D vectors (~1.5B multiply-adds, ~6 GB per query, O(N)); orange ANN index (IVF clusters, or an HNSW graph) looks at only the few near the query, sub-millisecond, occasionally missing a neighbour.

Figure 4. Exact scan compares the query against all million 1,536-D vectors: ~1.5 billion multiply-adds and ~6 GB scanned per query. An ANN index probes only nearby vectors, either the IVF cells it selects or the HNSW neighbours it visits, so a query touches a small fraction of the data in well under a millisecond and can miss a neighbour. Same recall target, roughly 100 to 1000x less work.

Takeaway: A vector database is approximate-nearest-neighbour indexing (LSH, or in production IVF and HNSW) over embeddings: it trades the occasional missed match for sub-millisecond search across billions of ~1,536-D vectors an exact scan could never serve. Fitting those billions in RAM is the other half, quantization, in Case Study 2.4.