R5.2 · LESSON 2 OF 6

Exact versus approximate lookup

Design a retrieval record and explain filtering, indexing, partitioning, updates and consistency.

THE IDEA

Exact versus approximate lookup

Do the arithmetic before reaching for an approximate index. An exact scan of 100,000 vectors in 384 dimensions is 38.4 million multiply-adds, roughly 38 ms at 10⁹ per second: fine for many applications. At 10 million vectors the same scan takes around 3.8 s, and an approximate index becomes worthwhile. Exact search is also the reference for measuring any approximate index.

vectors100,000dimension384latency budget (ms)50billions of multiply-adds per second1

one exact scan = 38,400,000 multiply-adds ≈ 38.4 ms budget 50 ms → EXACT search fits: no approximation error, simplest to reason about

Start exact where the numbers allow it, and add approximation only after measuring corpus size, query shape and the relevance you need. A vector database can serve flat (exact) search as well as approximate indexes.

Vary the corpus size, dimension and latency budget.

Predict first. Does a vector database automatically make every query approximate?

Chapter context

A vector index solves similarity lookup; a retrieval application also needs durable records, metadata, permissions and updates. Database behavior determines which vectors are eligible and which version of a document an answer uses.

TRY IT YOURSELF

Part 1. Do it hands-on

Cost an exact scan by hand, then write the strategy chooser and exact search.

vectors100,000dimension384latency budget (ms)50billions of multiply-adds per second1

one exact scan = 38,400,000 multiply-adds ≈ 38.4 ms budget 50 ms → EXACT search fits: no approximation error, simplest to reason about

multiply-adds, 100k × 384 ms at 10⁹/s ms at 10M vectors always approximate? (yes/no)

To do: Exact scan of 100,000 vectors of dimension 384: multiply-adds per query?
To do: At an assumed 10⁹ multiply-adds per second, milliseconds per query?
To do: The same scan over 10,000,000 vectors: milliseconds per query?
To do: Does a vector database automatically make every query approximate? Type yes or no

Part 2. Do it in code

scan_ops(n, dim): n · dim.
scan_ms(n, dim, ops_per_sec): milliseconds for one exact scan.
choose_strategy(n, dim, budget_ms, ops_per_sec): "exact" if the exact scan fits the latency budget, otherwise "approximate".
exact_search(q, vectors, k, eligible=None): vectors maps ids to lists of floats; return the k ids nearest (squared L2) to q among the eligible ids (all ids if None), nearest first, ties: smaller id.
recall(returned, exact): fraction of the exact ids that were returned (1.0 if exact is empty).

def scan_ops(n, dim):
    pass

def scan_ms(n, dim, ops_per_sec):
    pass

def choose_strategy(n, dim, budget_ms, ops_per_sec):
    pass

def exact_search(q, vectors, k, eligible=None):
    pass

def recall(returned, exact):
    pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Does a database automatically make every vector query approximate?

ANoBYes

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

Raw vector storage is $M=Ndb$ for N vectors of dimension d and b bytes per coordinate. If a postfilter independently accepts fraction f of an initial k candidates, the expected survivor count is kf; this is an expectation, not a guarantee.

Worked example

Ten million vectors of dimension 768 in float32 require 10,000,000×768×4=30,720,000,000 bytes, or 30.72 decimal GB, before IDs, text, indexes and replicas. If a postfilter accepts 20% of ten candidates under a simplifying independence assumption, the expected survivor count is only two.

Reference code

The following example uses the Python standard library and does not call a remote service.

from math import isclose
bytes_used=10_000_000*768*4
assert bytes_used == 30_720_000_000
assert isclose(bytes_used/1_000_000_000,30.72)
assert 10*.2 == 2

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

Filter selectivity and ANN candidate recall interact. Replication adds storage. Matching vector dimension does not establish matching embedding space.