AI servingDive 05 of 06

Vector databases, from a question to a dot product

Follow one search for a laptop that will not charge: learned geometry, graph navigation, compressed codes, filtered retrieval, and the memory traffic behind every similarity score.

Levels
9
Reading
45 min
Depth
Idea to Machine
Published
One question · seven passages“My laptop won’t charge”
C: Buying a longer laptop power cable; cosine distance 0.0001A: Battery not charging: inspect the adapter; cosine distance 0.0007B: USB-C power delivery troubleshooting; cosine distance 0.0222E: Enable two-factor authentication; cosine distance 1.3652EF: Fix intermittent Wi-Fi disconnects; cosine distance 1.4805FD: Reset a forgotten account password; cosine distance 1.6787DG: Restart a wireless router; cosine distance 1.8052GC · A · Bq‖v‖ = 1Cosine neighborhood
Nearest passages1 − cos(q, v)
  1. CBuying a longer laptop power cable0.0001
  2. ABattery not charging: inspect the adapter0.0007
  3. BUSB-C power delivery troubleshooting0.0222

Nearness retrieves candidates. The source still needs checking.

The semantic map’s toy vectors, normalized to unit length. The dashed ring marks the third neighbor’s cosine distance: ‖q − v‖² = 2(1 − cos(q, v)). No embedding model.

Level 01/09Idea

Find the answer without its words

You type “my laptop won’t charge” into a support site. The answer lives in a passage titled “Troubleshoot battery power delivery.” An exact phrase search finds nothing. A keyword engine with stemming, synonyms and a good ranking function might recover it, but somebody has to bridge the vocabulary gap. A model trained to place related questions and passages near one another offers another bridge: compare representations of the texts instead of requiring their words to overlap.

An An ordered list of numbers produced by a model, used as a representation for comparison or prediction. is that representation. A text encoder maps each passage to an ordered list of numbers, perhaps 768 coordinates. You encode the question into the same space and ask which stored vectors are closest. The individual coordinates need not have names like “battery” or “laptop.” Meaning is distributed across the pattern. It is the relationship between vectors, under a chosen scoring rule, that does useful work.

A vector database stores these representations, associates them with IDs and other data, and provides similarity queries. Its distinguishing machinery is usually an index that avoids comparing the question with every passage. The surrounding database still matters: persistence, concurrent writes, metadata filters, backups and access control turn an index into something an application can use. PostgreSQL with the pgvector extension stores ordinary rows and vector columns together, within the same service.

Retrieval is a candidate generator

Suppose our support system has ten million passages. We want ten useful pieces of evidence, restricted to the customer’s organization and product. The retrieval step returns IDs, scores and perhaps passage text. A second model can rank those candidates more carefully. A language model can then receive the selected passages alongside the question and generate an answer with citations. This arrangement is retrieval-augmented generation, or RAG. Retrieval supplies external evidence; generation turns that evidence into a response.

The same structure supports recommendations. Encode a product, an image or a user’s recent activity; find nearby candidates; apply inventory, policy and business rules; then rank. The representation must be trained for the relationship you want. Two products can be similar in appearance without being good substitutes. An accessory can be a good recommendation even when it is unlike the main product. A nearest-neighbor engine cannot decide which of these meanings of “related” your application intended.

Hand-authored toy geometry · no embedding model

Rank using

    Toy 2-D coordinates; letters identify passages, rings the top three, and the cross the query.

    Passage C nearly shares the query’s direction but sits farther away. Switch between cosine and L2, then normalize to make their rankings agree.

    In a real model the space has far more than two dimensions. A scatterplot would project that space onto a plane, distorting at least some neighborhoods. Check rankings in the original space, where retrieval actually happens. This map keeps two coordinates throughout, so you can compare the plotted positions directly with the scores.

    There are two separate questions to evaluate. Does the representation rank genuinely useful passages highly? And does the index recover the nearest vectors under that representation? A perfect answer to the second can coexist with a terrible answer to the first. Our charging query might retrieve a beautifully similar passage for a different laptop generation. Keep a set of real questions and judged relevant passages; do not use the index’s own scores as the only measure of success.

    The model defines what “nearby” means. The database spends resources finding nearby things.

    Level 02/09Interface

    A vector, a filter and a top k

    The first interface is the encoder. You send one or more strings and receive one vector per input. Actual APIs differ: some distinguish query and passage inputs, require prefixes, expose an output dimension, or return usage information. The following service-neutral TypeScript shape shows that boundary using a three-coordinate toy encoder.

    The boundary between encoding and storage
    // Service-neutral types, not a vendor endpoint.
    type EmbeddingRequest = {
      model: string;
      input: string[];
    };
    
    type EmbeddingResult = {
      modelRevision: string;
      dimensions: number;
      vectors: number[][]; // input order
    };
    
    // Illustrative output from a three-dimensional toy encoder:
    const result: EmbeddingResult = {
      modelRevision: "toy-charging-v1",
      dimensions: 3,
      vectors: [[0.8, 0.1, 0.2]],
    };

    Persist the model revision and preprocessing policy with the collection. Matching dimensions are necessary but insufficient: two 768-dimensional models can use completely incompatible coordinate systems. Changing chunk boundaries, prompts, normalization or model weights can change rankings. A migration often requires a second collection, re-embedding the corpus and switching queries only when both sides use the new representation. Treat a vector as typed data whose type includes its encoder, not merely its length.

    Chunking is part of this contract too. A whole troubleshooting manual can dilute a short adapter answer into a broad representation; a sentence alone can lose the product and safety context that makes it interpretable. Keep enough surrounding text to answer the question, and retain document ID, section, source version and chunk offsets. Overlapping chunks improve boundary coverage but create duplicates. There is no universally correct chunk size: evaluate the units you actually plan to return.

    Three common scoring rules

    For vectors q and x, the dot product sums coordinate-wise products. Euclidean distance, also called L2, measures the length of their difference. Cosine similarity divides the dot product by both lengths, keeping angle and discarding magnitude. An engine may return cosine distance, one minus cosine similarity, so smaller is better. Check that convention before sorting results or setting a threshold.

    dot(q, x) = Σ qᵢxᵢ

    L2(q, x)² = Σ (qᵢ − xᵢ)²

    cos(q, x) = dot(q, x) / (‖q‖ ‖x‖)

    If ‖q‖ = ‖x‖ = 1: L2² = 2 − 2 dot = 2 × cosine distance

    For nonzero vectors, these identities connect angle, length and dot product. Unit vectors give the same ranking under all three rules.

    When every vector is normalized to unit length, maximizing dot product, maximizing cosine and minimizing L2 give the same ranking. Their numeric scores are still different. Without normalization, a large norm can dominate dot product, while L2 penalizes a point for being far away even if it points in exactly the right direction. Squared L2 gives the same ordering as L2 and avoids square roots; it is not itself a metric satisfying the triangle inequality.

    The second interface is storage and retrieval. An upsert says “this ID now has this vector and metadata.” A query supplies a vector, a top-k limit and perhaps a predicate such as organization 7 and product family X. Results need stable IDs so that you can fetch source text, deduplicate overlapping chunks and trace an answer. Metadata belongs beside the vector even if its storage lives elsewhere. The predicate’s semantics must survive whichever index executes the query.

    Runnable toy data · PostgreSQL + pgvector 0.8.0
    -- PostgreSQL with pgvector 0.8.0 installed.
    CREATE EXTENSION IF NOT EXISTS vector;
    
    CREATE TABLE passages (
      id bigint PRIMARY KEY,
      tenant_id bigint NOT NULL,
      content text NOT NULL,
      embedding vector(3) NOT NULL
    );
    
    -- Toy coordinates keep this example runnable.
    -- Use the actual model dimension in production.
    INSERT INTO passages (id, tenant_id, content, embedding)
    VALUES
      (1, 7, 'Inspect the USB-C adapter', '[0.8,0.1,0.2]'),
      (2, 7, 'Reset your account password', '[-0.7,0.6,0.1]')
    ON CONFLICT (id) DO UPDATE
    SET content = EXCLUDED.content,
        embedding = EXCLUDED.embedding;
    
    CREATE INDEX passages_embedding_hnsw ON passages
    USING hnsw (embedding vector_cosine_ops)
    WITH (m = 16, ef_construction = 64);
    
    BEGIN;
    SET LOCAL hnsw.ef_search = 100;
    SELECT id, content,
           embedding <=> '[0.9,0.1,0.2]'::vector AS distance
    FROM passages
    WHERE tenant_id = 7
    ORDER BY embedding <=> '[0.9,0.1,0.2]'::vector
    LIMIT 10;
    COMMIT;

    The SQL syntax is pinned to pgvector 0.8.0. The operator class selects cosine indexing; the query orders by the matching distance operator. For a tiny table, the planner may choose a cheaper sequential scan. A real 768-dimensional model needs vector(768) and 768 actual coordinates, on both insert and query.

    Pgvector also supports halfvec for half-precision coordinates and sparsevec for vectors stored as nonzero entries; both arrived in 0.7.0. That release added similarity indexing for PostgreSQL’s existing bit type, including Hamming and Jaccard distance. The 0.7.0 changelog records these additions.

    pgvector operatorReturned valueAscending order finds
    <=>Cosine distanceHighest cosine
    <->L2 distanceSmallest L2
    <#>Negative inner productLargest dot product
    Check yourselfThe starting metric is cosine distance, and all vectors have unit length. Which change preserves the nearest-neighbor ordering?

    Level 03/09Runtime

    Where the geometry comes from

    Why should a battery passage end up near a charging question? Because training rewards that relationship. A common setup uses a An encoder that processes a query and a passage separately, so passage representations can be precomputed.. The query and passage are independently encoded into vectors. Their similarity becomes a training score. A positive pair might come from a question and its accepted answer, or from a query and a human-judged relevant passage. Other passages provide negatives.

    One contrastive objective applies a softmax over the positive passage and a set of negatives. Its loss is −log(exp(s(q, p+)/τ) / Σⱼ exp(s(q, pⱼ)/τ)), where s is the similarity and τ is a temperature controlling score sharpness. Lowering the loss raises the positive score relative to competing scores. Other items in a training batch can provide cheap negatives. Hard negatives, such as a convincing answer for the wrong laptop model, teach distinctions that random unrelated text does not.

    Training questionMy laptop won’t charge
    Positive passageInspect the USB-C adapter
    Hard negativeAdapter advice for a different model
    OptimizationIncrease the positive score relative to the negatives
    1. Encode the question using the query-side input convention.
    2. Encode a relevant passage independently, with shared or paired encoder weights.
    3. Score a set of competing passages; their relative scores define the contrastive loss.
    4. Backpropagate through the encoder. Repeat over many examples, then freeze a revision for indexing.
    1 / 4
    Contrastive training raises a relevant passage’s score relative to competing passages. The resulting encoder supplies the vectors stored in the index.

    The encoder often contains a transformer. It tokenizes text, creates contextual token representations, pools or selects a sequence representation, and may project it into a smaller output space. The LLM inference dive opens tokens, attention and GPU execution in detail. The crucial difference here is the training task: a useful hidden state for predicting the next token is not automatically a useful sentence vector for nearest-neighbor retrieval. Sentence-BERT is an influential example of explicitly training independently computed sentence representations for comparison.

    Normalization, if the model’s usage contract requires it, happens after producing the representation. It removes length as a degree of freedom. Model compatibility and score calibration still depend on training. Follow the encoder’s documented conventions: for example, the E5-small-v2 model card specifies query and passage prefixes and demonstrates normalized embeddings. Omitting a required prefix changes the model input rather than merely cleaning up presentation.

    Dimensions are a budget

    More coordinates give a model more representational capacity, but they also increase storage and distance work. You cannot normally take the first 128 entries of an arbitrary 768-dimensional embedding and assume most information survives. Information may be spread across all coordinates. A learned projection can reduce dimensions, but it creates a new representation that needs its own validation and consistent application to queries and passages.

    Matryoshka Representation Learning deliberately trains nested prefixes to remain useful at several lengths. A model trained this way can offer a coarse, short representation and a richer, longer one. After truncation, renormalize if the chosen similarity requires unit vectors. The trade is measurable quality against bytes and arithmetic; there is no universal dimension that is enough for all corpora. A short vector can retrieve candidates cheaply, followed by rescoring with longer originals.

    Geometry has failure modes

    Real embedding clouds are rarely uniform spheres. Anisotropy means representations occupy some directions much more strongly than others. A large common component can make unrelated texts appear similar. Research on sentence embeddings from pretrained language models studies this problem. Centering or whitening may help a particular model, but blindly transforming a production space can also damage the relationships it was trained to preserve.

    Hubness is a different symptom: a small set of points appears in many queries’ nearest-neighbor lists. High-dimensional geometry and the data distribution can both contribute. A generic “contact support” passage may become an unhelpful frequent candidate. Inspect per-document retrieval frequency as well as average relevance. Neither a larger graph-search beam nor a faster dot-product kernel repairs a representation that makes the wrong passages nearest.

    Distances mean something because training made certain comparisons useful. That promise is specific to a model, a task and a data distribution.

    Level 04/09Runtime

    Compare everything, then stop doing that

    Start with the algorithm that cannot miss a neighbor: compare the query with every stored vector, keep the best ten, return their IDs. For N vectors of dimension d, dot-product scoring needs N × d products and roughly as many additions. A small top-k heap adds bookkeeping, but reading coordinates and accumulating scores usually dominate at large d. You do not need a sophisticated index to establish this baseline.

    At ten million 768-dimensional vectors, one query evaluates 7.68 billion coordinate products. Float32 payload alone occupies 30.72 GB. At a hypothetical sustained read bandwidth of 100 GB/s, streaming that payload once takes at least 0.3072 seconds, before ranking overhead. That bandwidth bound assumes one cold read of the corpus. A batch of queries can reuse the same loaded vectors and turn many independent dot products into matrix multiplication; a single interactive query has less reuse available.

    Exact search remains an excellent choice when N is small, filters reduce the eligible set to a few hundred rows, the corpus fits in cache, or a GPU serves large batches. It is also how we measure the quality of approximate search. Choose an index when the exact scan exceeds your latency or cost budget.

    Why spatial shortcuts become harder

    In two dimensions a grid can exclude distant regions cheaply. In many dimensions, simple partitions often give weak pruning. Random high-dimensional points tend to sit at surprisingly similar distances from a query. For independent uniform coordinates, each squared coordinate difference has mean 1/6. Summing d such terms gives expected squared distance d/6, while the standard deviation of the sum grows only as √d. Relative variation shrinks as dimension rises.

    Nearest distance
    …
    Farthest distance
    …
    Max / min
    …

    256 seeded uniform points in [0, 1)ᵈ; fixed histogram bins plot distance / √d.

    Raise dimension from 2 to 256 and watch the distance distribution narrow. The max/min ratio approaches one as relative variation shrinks.

    The histogram rescales distances by √d so that you see concentration rather than just increasing length. Its max/min ratio moves toward one under this synthetic distribution with a fixed sample count. Learned vectors often have clusters, unequal variances and a much lower intrinsic dimension than their coordinate count. Those structures are exactly what useful approximate indexes exploit.

    Nearest-neighbor retrieval that trades guaranteed exact results for less search work., or ANN, spends less work by considering a promising subset. One family navigates proximity graphs. Another routes the query to a few partitions and scans only their contents. A third source of approximation compresses coordinates, changing the scores themselves. Candidate omission and score distortion are separate errors; either can remove the correct passage from the final ten.

    Define recall@10 as the fraction of the exact top ten IDs that appear in the approximate top ten, using the same vectors, metric, eligibility rules and tie policy. If seven IDs overlap, recall is 0.7. Average across held-out queries, and inspect the tails: the mean can hide an important product family with poor recall. Measure human relevance separately, using judged charging questions and passages.

    Distance computations measure search work; memory access patterns determine much of its cost. A thousand contiguous comparisons can beat a few hundred random graph visits. Compression can reduce bytes per comparison while adding decoding or table lookups. Tune against measured latency and throughput on the target machine as well as recall, and include embedding latency separately. An index that takes 2 ms does not make a 200 ms encoding call disappear.

    Exact search sets the reference answer. Approximation chooses where to spend the comparisons you can afford.

    Level 05/09Runtime

    Navigate a graph at several scales

    A proximity graph stores vectors as vertices and links each one to selected neighbors. To search, begin at an entry vertex, evaluate its neighbors against the query, move toward a better candidate, and repeat. The graph replaces “read every vector” with “follow promising addresses.” Local links make short steps possible; longer links help the walk escape a remote region. A graph containing only the very closest neighbors can navigate badly between clusters.

    Malkov and Yashunin’s HNSW organizes such links into a hierarchy. Every point appears in layer zero. A randomly selected fraction also appears in layer one, fewer in layer two, and so on, with exponentially decreasing population. Upper layers offer coarse navigation among widely spaced points. Lower layers refine the search among denser neighborhoods. The maximum-height vertex serves as an entry point.

    A query descends greedily through upper layers: compare neighbors, take an improvement, stop when the current vertex has no better neighbor in that layer, then descend from that vertex. At layer zero it keeps multiple promising candidates instead of one. A candidate queue orders unexpanded vertices by distance to the query, while a bounded result set keeps the best found so far. Expand the nearest pending candidate and consider its unseen neighbors.

    The search stops when the nearest remaining candidate is worse than the worst retained result, once that result set is full. Unseen points can still be closer; graph structure and search breadth determine how much the search misses. The visited set prevents repeated work within a layer. Query distance and pairwise neighbor distance are distinct computations: one guides traversal, the other helps construct good links.

    Incremental 2-D HNSW · M = 4 · efConstruction = 12

    • Best · diamond
    • Retained · ring
    • Expanded · filled
    • Greedy route and descent
    • Query

    Toy 2-D HNSW: maximum height 3 gives four layers, 0–3; sorted queues, no optional neighbor fill.

    Inserted
    0
    Active layer
    0
    Distances so far
    0

    Follow the query from sparse upper layers into the full graph below. The amber route traces improvements and carries the same vertex down between layers.

    The diamond marks the current best, rings mark the other retained candidates, and a filled circle marks the expanded vertex. A vertex can be both best and expanded. With efSearch = 6, the base layer retains up to six candidates while the counter includes every query distance, including repeat comparisons in different layers. Step through the amber route to see where a better point is found and where the search descends.

    Three knobs, two phases

    M controls the link budget and therefore graph memory and navigability. More links usually improve routes at the cost of storage and work per expansion. Implementations may give layer zero a larger degree budget; the demo permits 2M there and M above. efConstruction controls how broadly insertion searches for candidate neighbors. A larger construction search can create a better graph, but costs indexing time. A weak graph cannot always be rescued cheaply at query time.

    efSearch controls the size of the retained search set at query time. Increase it to explore more alternatives before stopping. Expanding one vertex can discover many unseen neighbors, so the visited count can far exceed ef. To return k results, use a breadth of at least k in implementations that bind the result set to ef. The stepper displays that retained set and singles out its nearest member.

    Insertion first navigates existing upper layers, then searches more broadly in the layers the new vertex will occupy. It chooses neighbors, adds reverse links and prunes overfull lists. The neighbor-selection heuristic favors diversity. Consider candidate c while choosing links for a new point p. If an already chosen neighbor is closer to c than p is, c may be redundant: that neighbor already offers a route in c’s direction. Keeping slightly farther links in other directions can be better than spending every link on one tight cluster.

    This heuristic is easiest to understand with our support corpus. A new charging passage could connect only to five near-duplicate adapter passages. Those links all lead into the same pocket. A more diverse set includes a link toward cable faults or product-specific troubleshooting, giving later queries more ways into and out of the pocket. The graph is optimizing routes through the space, not merely recording each point’s exact nearest neighbors.

    Check yourselfYou double efSearch on an unchanged HNSW index. What changes directly?

    Level 06/09Runtime

    Search lists of compressed codes

    Graphs save comparisons, but vectors and links still consume memory. An inverted-file index, IVF, takes another route. Train a set of coarse centroids with k-means, assign each corpus vector to its nearest centroid, and store the resulting groups as lists. A query compares itself with the centroids, chooses the nearest few lists and searches inside those lists. Here each list represents a geometric region; keyword indexes organize their lists by terms.

    nlist names the number of coarse partitions. nprobe is how many are searched per query. With perfectly balanced lists, candidate scoring touches about N × nprobe/nlist vectors, plus routing work. Real lists are unequal, so count actual candidates. A nearby neighbor can lie across a partition boundary; searching only the nearest centroid’s list can miss it. Raising nprobe trades more list reads for better recall.

    Real IVF-flat · 3,000 points · 16 dimensions · 24 lists

    Mean recall@10
    …
    Mean distances / query
    …
    Brute-force distances
    3000
    Search batch time
    …

    Synthetic data; 24 held-out queries, 12 Lloyd iterations, full-precision L2. Counts include centroid routing; timing covers the search batch.

    Move nprobe and measure recall against a cached exhaustive baseline. Probing all 24 lists recovers every exact top-ten ID and costs 3,024 distances per query: 3,000 points plus 24 centroids.

    This lab is IVF-flat: every candidate still uses its original coordinates. Real systems may use a graph to find coarse centroids or combine lists with compressed residual vectors. If new data changes the distribution, old centroids can produce large, uneven lists and poorer routing. Retraining the coarse quantizer requires rebuilding assignments to match the new centroids.

    Product quantization stores choices, not coordinates

    A single codebook with 256 representative 768-dimensional vectors would use one byte per stored vector, but it would offer only 256 possible reconstructions. That is far too coarse for most retrieval tasks. Product quantization splits the vector into m subspaces and trains an independent codebook for each. Each subspace chooses one of K centroids. Combining independent choices gives Kᵐ possible reconstructions without storing Kᵐ full vectors.

    For d = 768, m = 96 and K = 256, each subspace has eight coordinates. One byte selects its centroid, so a code occupies 96 bytes rather than 3,072 float32 bytes. The shared codebooks occupy 96 × 256 × 8 × 4 = 786,432 bytes. That fixed cost is small at a hundred million vectors. An IVF-PQ variant often encodes the residual after subtracting the coarse centroid; the small encoder below uses plain PQ to isolate the mechanism.

    To score with asymmetric distance computation, leave the query uncompressed. For each subspace, precompute its squared distance to every codebook centroid. A candidate code then needs m table lookups and additions: one lookup per byte. This approximates distance from the query to the reconstructed candidate. You do not need to materialize the reconstructed vector. Faiss’s compression documentation shows how PQ codes combine with inverted lists.

    4-D input · two subspaces · four centroids per subspace

    Code bytes (hex)
    …
    Squared reconstruction error
    …
    Exact squared query distance
    …
    Lookup-table distance
    …

    Toy codebooks; two-bit IDs stored in bytes. Query = [1, 0, −1, 0]; input coordinates two and four stay at 0.3 and −0.4.

    Move coordinates across centroid boundaries and watch the code bytes change. Compare exact distance with the lookup-table approximation.

    Scalar quantization makes a different compromise. An int8 representation stores one quantized scalar per coordinate, typically with scales and perhaps offsets. For a simple symmetric scheme, zᵢ = clamp(round(xᵢ/s), −127, 127), and reconstruction is s × zᵢ. Clipping and rounding distort scores. Whether the scale is global, per dimension, per block or per vector changes both accuracy and the correction arithmetic. “Int8” names a storage type, not a complete distance formula.

    Binary quantization can keep just one sign bit per coordinate. Comparing codes with Hamming distance is extremely cheap, but discards magnitudes. For arbitrary real vectors, Hamming distance between signs is not identical to cosine distance. Learned transformations and richer estimators can retain more information. Retain more candidates, then rescore using higher-precision originals when the quality budget requires it.

    Payload memory for 100 million 768-dimensional vectors, on a linear scale. The float32 payload is 307.2 GB, about 286.1 GiB.

    Memory has several owners. At M = 16, a layer-zero capacity of 32 four-byte neighbor IDs alone is 128 bytes per vertex, or 12.8 GB for 100 million vertices, before upper layers, offsets, labels and allocator overhead. Graph links can outweigh the compact vector code. Keeping all float32 originals for exact rescoring adds the full 307.2 GB back somewhere, perhaps on SSD. Three replicas multiply whatever each replica retains.

    Rescoring fixes the order of candidates that survived retrieval and compression. It cannot resurrect an adapter passage from a list you never probed or a graph region you never reached. A sound tuning order separates these losses: measure candidate recall with original scores, then measure compression’s ranking error, then choose how many candidates to rescore. The same end-to-end recall can hide very different bottlenecks.

    Check yourselfA PQ search omits the correct passage entirely. Can exact rescoring of its returned candidates recover that passage?

    Level 07/09System

    Keep retrieval correct while data changes

    Our customer’s question now has a good vector and a fast candidate search. The system still has to enforce “only this customer’s passages.” A filter is part of the query’s meaning, not an optional cleanup. The correct reference answer is the nearest ten among eligible vectors. Searching the whole corpus for ten neighbors and then removing ineligible ones is a different operation, and can return fewer than ten even when thousands of eligible passages exist.

    For a sequential scan, filtering first is simple: enumerate matching IDs and score them. For a graph, excluding vertices during traversal can remove the bridges that connect eligible regions. A customer’s passages may be scattered throughout a graph built across all customers. An ineligible vertex can be useful as a routing point even though it must never appear in the result. Engines therefore distinguish the predicate for accepting results from the policy for visiting vertices.

    A six-node proximity graph · query beside D · allowed nodes A, E, F

    A six-node chain isolates filtering behavior. Dashed circles are disallowed; rings mark results and the cross marks the query.

    Restricting traversal strands the search at A; filtering the global top two returns only E. A broader candidate pool recovers E and F.

    Post-filtering preserves graph routes but can starve the result list. If each candidate independently passes with probability p, a rough expectation is k/p candidates to collect k matches. That estimate can fail badly because eligibility correlates with geometry: product and tenant clusters are not independent coin flips. Adaptive search can keep exploring until it has enough eligible results or exhausts its budget. For very selective filters, an exact scan over a metadata index’s matching IDs may be cheaper and more reliable.

    Pgvector 0.8.0’s iterative index scans address this result starvation directly. Set hnsw.iterative_scan = strict_order to continue scanning when filtering removes candidates, until the query has enough results or reaches its scan limits. strict_order preserves distance ordering among returned rows; relaxed_order allows slight disorder for better recall. Exploration is bounded by hnsw.max_scan_tuples and the memory budget controlled by hnsw.scan_mem_multiplier, so a restrictive filter can still exhaust the budget.

    These options produce a planner problem: use a partition dedicated to a large tenant, traverse a shared graph while testing an allow-list, or scan a small filtered subset exactly. Filter-aware graph construction can help when predicates are predictable. No single placement of a filter wins for all selectivities. Evaluate with real filter distributions, including rare combinations. A filter that performs well for the biggest customer says little about the thousands of tiny ones.

    Measure filtered recall against a filtered exact baseline. If tenant 7 has only six passages, the target contains six results even when k is ten. If it has six thousand passages but the engine returns two, that may be candidate starvation. Record result count alongside recall and latency, and separate an exhausted eligible set from an exhausted search budget. Otherwise a dashboard can make a fast, incomplete answer look like a successful query.

    Deletes, updates and concurrent insertion

    Deleting a row from a graph can damage routes. A tombstone can make the row invisible as a result while preserving its vertex temporarily for navigation. Over time, dead entries consume storage and search work, so a maintenance process must reclaim or rebuild them without violating visibility. A system may maintain immutable segments, a mutable buffer, or repair links in place. The right policy depends on update rate and consistency requirements.

    Upserting the charging passage also changes its searchable representation. Updating text immediately but embedding it asynchronously creates a window where the stored vector describes old content. Record source and embedding versions; define when new content becomes searchable. A successful write acknowledgment may mean durable storage, index visibility, or both, depending on the engine. Application logic should not silently assume those events are simultaneous.

    1. 01 / Durable mutationPersist ID, source version, metadata and vector in a log or transactional store.
    2. 02 / Mutable search stateMake new versions searchable; suppress deleted and superseded IDs.
    3. 03 / Background maintenanceMerge segments or repair the graph; reclaim obsolete storage safely.
    A log-backed serving design separates durable writes, searchable versions and background maintenance. A visibility rule connects those stages.

    When the index exceeds RAM

    DiskANN demonstrates graph search designed around SSD storage, using the Vamana graph construction and a memory/storage split. Compressed representations in RAM help prioritize candidates; graph neighborhoods and richer vector data can live on SSD. Search batches reads and caches useful nodes to reduce dependent storage trips. Moving an ordinary RAM graph to a memory-mapped file does not automatically give it these properties.

    Sharding divides capacity across machines. With arbitrary document sharding, send the query to each shard and merge candidate lists. If every shard returns its exact local top k under comparable scores, their union contains the global top k. Approximate shard searches can still miss candidates, and one slow shard can dominate tail latency. Semantic routing to a subset of shards saves network and search work but adds another omission risk. Quantized scores may need common rescoring before they can be compared safely.

    Replication is a different axis: multiple copies of a shard support availability and read throughput. They also require a policy for write propagation, failover and stale reads. Keep organization restrictions consistent across replicas and recheck permissions before presenting source content. Index recall, visibility lag and authorization correctness deserve separate metrics; excellent vector-search recall does not establish the other two.

    A search index serves a changing, filtered view of data. Its navigation graph is only one part of that contract.

    Level 08/09System

    Retrieve broadly, rank carefully

    A semantic model bridges “won’t charge” and “battery power delivery,” but support queries also contain exact identifiers. “Adapter XPS-65W revision B” is a different search problem from “my laptop seems dead.” A lexical engine can reward those exact terms strongly. A vector encoder may blur the model number with related products. Combining lexical and semantic retrieval gives the ranker two different ways to discover evidence.

    BM25 scores documents using term occurrence, term rarity and document-length normalization, with saturation so repeated occurrences do not increase score linearly forever. Its inverted index can go directly to postings for the query’s words. The vector index can retrieve a passage with little lexical overlap. Neither score scale is inherently comparable to the other: a BM25 score of 12 and cosine similarity of 0.8 do not mean one passage is fifteen times better.

    Reciprocal rank fusion, RRF, combines positions rather than raw scores. For each document, sum 1/(k + rank) over the lists containing it, using ranks starting at one. An absent document contributes zero for that list. The rank constant k dampens the difference between positions near the top. Cormack, Clarke and Büttcher used k = 60 in their RRF work; tune this rank constant separately from the number of results you request.

    Comma-separated IDs. Empty entries are ignored; duplicates count once per list. Missing ranks contribute zero. Equal scores sort by ID.

    IDBM25 rankVector rankScore

    Fuse two real ranked ID lists. With k = 60, an ID ranked second in both lists earns 2/62 ≈ 0.032258, more than the 1/61 ≈ 0.016393 of an ID ranked first in only one.

    RRF gives consensus a strong role and avoids having to calibrate incompatible score scales. That simplicity also discards information: it treats a tiny score gap between first and second like a huge gap. Retrieval depth matters. If the vector list stops at ten, a passage ranked eleventh contributes nothing from that channel. Tune list depths, weights if used, and the fusion constant on judged queries. Compare fusion against the stronger individual channel on your judged queries.

    For the charging question, imagine lexical search finds an exact adapter part number while vector search finds the paraphrased troubleshooting passage. Their union provides both specific and general evidence. Deduplicate IDs before fusion, and consider collapsing overlapping chunks after retrieval so that one long article does not crowd out every other source. Use the same eligibility rules in both channels; fusing cannot repair a channel that retrieved unauthorized material.

    A practical evaluation set includes paraphrases, exact part numbers, misspellings, contradictory instructions, obsolete source versions and questions outside the corpus. Hold it out while tuning. Compare lexical-only, vector-only and fused retrieval at the same candidate depth, then compare the reranked outputs. Save the IDs produced by every stage. For one failed charging answer, those traces show whether the relevant passage was absent from retrieval, displaced during fusion, or rejected by the final ranker.

    A more expensive comparison at the end

    A A model that jointly processes the query and a candidate passage, allowing token interactions before producing a relevance score. reranker reads a question and passage together. Unlike a bi-encoder’s single-vector comparison, it can model detailed interactions between words across the pair. That can help distinguish “adapter does not supply enough power” from “the adapter is known to work.” The BERT ranking study by Qiao and colleagues explores joint query-document modeling for ranking.

    1. 01 / Candidate retrievalUp to 200 lexical + 200 vector candidates, each restricted to eligible passages.
    2. 02 / Fusion and deduplicationRRF orders the union; retain 50 distinct passages for expensive comparison.
    3. 03 / Joint rerankingA cross-encoder scores 50 pairs; choose 5 sources for the answer context.
    Each stage spends more work on fewer IDs: retrieve hundreds, rerank dozens, then select a few sources.

    The cost explains why the reranker is late in the pipeline. A bi-encoder lets you precompute every passage vector once and reuse it for many queries. A cross-encoder must revisit passage text for every query-passage pair. It is suitable for tens or hundreds of candidates, not necessarily ten million. Context length, batching and accelerator utilization determine its actual serving cost.

    There are now several independent budgets: graph breadth or nprobe, compressed candidate depth, exact-rescore depth, lexical list depth and cross-encoder depth. Measure each stage’s marginal benefit. If the correct adapter passage never reaches the union, increasing reranker capacity wastes time. If retrieval has high candidate recall but the answer still cites an irrelevant paragraph, inspect reranking, chunk boundaries and context selection before rebuilding the graph.

    Evaluation should include a “no useful answer” case. Top-k retrieval always has something nearest, even when the question has no support in the corpus. A threshold may help if calibrated for the model and data, but a universal cosine cutoff is not reliable. Require adequate evidence, preserve citations, and allow the application to say that its sources do not answer the question. Judge the selected sources before judging the fluency of the answer.

    Check yourselfWhy fuse ranks instead of directly adding BM25 and cosine scores?

    Level 09/09Machine

    A dot product waiting for memory

    Every route eventually reaches a small kernel: read coordinates, multiply, add, compare. For normalized float32 embeddings, a dot product is enough to order cosine neighbors. A scalar implementation processes one coordinate per iteration. SIMD, single instruction multiple data, operates on several coordinates in parallel. A 256-bit register holds eight float32 values; a 512-bit register holds sixteen. Arm’s 128-bit NEON holds four.

    The following x86 C function uses AVX-width loads and fused multiply-add, FMA. Each instruction updates eight lane accumulators with aᵢ × bᵢ + accumulator. After processing full blocks it sums the lanes and handles the remaining coordinates with a scalar tail. Unaligned loads accept ordinary float pointers; they still require every loaded element to lie within valid accessible storage. The loop bound is what prevents reading beyond the vector.

    A complete AVX2/FMA-targeted float32 dot product
    #include <immintrin.h>
    #include <stddef.h>
    
    // x86-64; compile with -O3 -mavx2 -mfma.
    // Call only on a CPU supporting AVX2 and FMA.
    float dot_f32(const float *a, const float *b, size_t n) {
      __m256 acc = _mm256_setzero_ps();
      size_t i = 0;
      for (; i + 8 <= n; i += 8) {
        __m256 x = _mm256_loadu_ps(a + i);
        __m256 y = _mm256_loadu_ps(b + i);
        acc = _mm256_fmadd_ps(x, y, acc);
      }
    
      float lanes[8];
      _mm256_storeu_ps(lanes, acc);
      float sum = 0.0f;
      for (size_t lane = 0; lane < 8; lane++) {
        sum += lanes[lane];
      }
      for (; i < n; i++) {
        sum += a[i] * b[i];
      }
      return sum;
    }

    The intrinsic names and instruction families are documented in the Intel Intrinsics Guide. FMA is a distinct CPU feature from AVX2; production libraries dispatch to a supported kernel after checking capabilities. AVX-512 can widen this loop, and AArch64 NEON has corresponding vector loads, multiply-adds and reductions. Wider registers alone do not guarantee lower latency once memory or dependency chains dominate.

    A tuned kernel often uses multiple independent accumulators so that one FMA’s dependency latency does not stall the next. Its reduction order differs from a scalar loop, and fused arithmetic rounds once instead of rounding the product and addition separately. Near-tied floating-point scores can therefore differ by a few low bits. Define stable tie behavior where reproducibility matters, and do not confuse such differences with gross index recall failures.

    a = [1, …, 16], b = [1, −1, 1, −1, …]. Each block adds eight products to the same eight float32 lane accumulators.

    Horizontal sum
    …
    Products accumulated
    …

    Enter eight binary digits; XOR marks differing bits and popcount counts them.

    Accumulate two blocks of eight products, then inspect their horizontal sum. Compare binary codes below with XOR and population count.

    Fewer bits change the instructions

    Quantized dot products can use integer multiply-accumulate instructions. For example, the original AVX-512 VNNI VPDPBUSD form accumulates groups of unsigned-byte × signed-byte products into 32-bit lanes. It is not an unrestricted signed-int8 × signed-int8 operation. An implementation must choose compatible encodings and apply scale or zero-point corrections; newer instruction families offer other signedness combinations. The kernel must match the encoding’s signedness, scales and offsets.

    For binary codes, XOR produces a one wherever two bits disagree, and POPCNT counts those ones. A 768-bit sign code occupies twelve 64-bit words; its Hamming distance is the sum of twelve word popcounts after XOR. Vector population-count instructions can process more words together on supporting CPUs. This scores the binary representation, with its coarser geometry.

    Bandwidth for scans, latency for walks

    Consider one cold scan of normalized float32 data. Each coordinate brings in four corpus bytes and contributes about two floating-point operations, one multiply and one addition. If the query stays cached, arithmetic intensity is about 0.5 FLOP per byte. Sustained bandwidth B then caps this part of the scan near 0.5B FLOP/s, regardless of a much larger advertised peak compute rate. Top-k selection, memory layout and implementation overhead can lower achieved performance further.

    100M × 768 × 4 bytes = 307.2 GB

    At 100 GB/s: scan time ≥ 3.072 s

    2 FLOP / 4 bytes = 0.5 FLOP/byte

    100 GB/s × 0.5 FLOP/byte = 50 GFLOP/s

    At an assumed 100 GB/s, reading the float32 payload takes at least 3.072 seconds. Batching reuses each loaded vector across several queries.

    A graph walk reduces total bytes but makes them harder to fetch. The address of the next useful vertex depends on the current vertex’s neighbor IDs. Those IDs and coordinates may miss in several cache levels, and page translations can miss in the TLB. Within a fetched 768-dimensional vector there is still sequential work, but the next vector may be far away. Low-dimensional graph navigation is especially sensitive to this dependent access pattern; larger vectors can add substantial bandwidth and compute cost as well.

    Hardware prefetchers excel at streams and struggle with unpredictable addresses. Search beams expose several candidates that can be prefetched or scored concurrently, trading extra work for memory-level parallelism. Compact adjacency arrays, compressed vectors, cache-aware placement and query batching can matter as much as the arithmetic kernel. The memory dive explains the cache-line, TLB and DRAM mechanisms behind those stalls.

    This is why a benchmark must describe its working set. Repeating the same query against an index that fits in the last-level cache measures a different path from serving diverse queries against hundreds of gigabytes. Report corpus size, vector dimension, metric, precision, filters, recall target, concurrency and warm-up policy. Include a latency distribution rather than only an average. Those details explain whether a faster result came from fewer comparisons, cheaper data access, or simply an easier experiment.

    GPUs need enough parallel work

    A GPU makes an exact batched scan attractive through high memory bandwidth and matrix operations. Graph search needs a design that exposes many concurrent comparisons and avoids wasting too much work on irregular traversal. CAGRA is an example of graph construction and ANN search designed for GPU parallelism. Whether it fits a service depends on batch size, resident index capacity, transfer costs and the latency target. A tiny, infrequent query may still be cheaper on a CPU.

    Our original sentence has now become a sequence of physical reads and arithmetic operations. Training decided which comparisons might be useful. The index chose which vectors to fetch. Filters decided which IDs could survive. Compression chose how faithfully to retain coordinates, and reranking spent more compute on the survivors. At the bottom, the CPU or GPU cannot see “charging trouble.” It sees addresses, bytes and sums. Good retrieval depends on keeping the intended relationship intact through every one of those translations.

    The cheapest distance is the one you avoid. The next cheapest is the one whose data is already close to the core.

    End of Vector databases · 9 levels, Idea to Machine

    Where to next

    Practical notes

    1. Note3 min read

      Tune pgvector HNSW for recall and filtered queries

      Start with default graph settings, tune ef_search against exact results, and enable iterative scans for filtered queries. Build memory and graph construction settings solve different problems.

    2. Note3 min read

      Choose cosine, dot product or L2 for embeddings

      For unit-normalized embeddings, cosine similarity, dot product and squared L2 produce the same ranking. Match your index operator and ordering to the embedding model.

    Browse all 34 divesAll topics