Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

Vector Similarity Search: Metrics & Approximate Methods › Complexity Comparison

Michael BrenndoerferJanuary 25, 20264 min read

Language AI HandbookAll chapters

Part 44 of 67Retrieval-Augmented Generation

Chapter 338Vector Similarity Search: Metrics & Approximate Methods › Complexity Comparison

Reading section 6 of 11 · Complexity Comparison · 4 minSection 6 of 11 · 4 min

Section 6 of 11 · 4 min read

Vector Similarity Search: Metrics & Approximate Methods › Complexity ComparisonOne section · Sections in this chapter6 / 11 ↓

Sections in this chapter11

Reading tools Definitions & inline links

Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.

Article links

Make inline references clickable

Understanding the computational complexity of different search strategies helps you make informed decisions about which approach fits your scale. The differences between exact and approximate search are not marginal: they are qualitative changes in how query cost grows with collection size. Exact search grows linearly, meaning that doubling the collection size doubles the query time. Approximate methods grow sublinearly, meaning that doubling the collection size increases query time by much less than a factor of two. At large scales, this distinction is the difference between a system that responds in milliseconds and one that takes seconds.

Out[11]:

Visualization

Log-log plot comparing linear exact search with sublinear ANN search time curves. — Query time scaling for exact search versus two approximate search strategies as collection size grows from 1,000 to 100 million vectors. Exact search scales linearly, while graph-based ANN (HNSW) scales approximately logarithmically and IVF-style methods scale approximately as the square root of collection size. The practical benefit of ANN methods grows dramatically with collection size.

The table below summarizes the trade-offs across the major search strategies. Each row captures a different aspect of system behavior, from query-time latency to memory consumption, and the columns reveal how these aspects vary across the four principal approaches.

Comparison of search complexity and characteristics across algorithm families.
Property	Exact Search	Graph-based ANN	IVF-based ANN	Quantized ANN
Query time	$O(n \cdot d)$	$O(\log n \cdot d)$	$O(\sqrt{n} \cdot d)$	$O(n \cdot d')$ , $d' \ll d$
Index build time	$O(1)$	$O(n \log n \cdot d)$	$O(n \cdot d \cdot K)$	$O(n \cdot d)$
Memory	$O(n \cdot d)$	$O(n \cdot (d + M))$	$O(n \cdot d + C)$	$O(n \cdot d')$
Recall guarantee	100%	Tunable (95-99%+)	Tunable (90-99%+)	Tunable (85-95%+)
Best for	Small collections, ground truth	Large-scale, low latency	Very large scale	Memory-constrained

where:

$M$ : the number of graph connections per node (in HNSW)
$C$ : the centroid storage cost (in IVF)
$K$ : the number of clusters (in IVF)
$d'$ : the compressed dimension (in quantization methods)
$n$ : the number of vectors in the collection
$d$ : the dimensionality of the vector space

Several patterns in this table deserve attention. First, notice that exact search has $O(1)$ index build time, because there is no index to build: you simply store the raw vectors. All approximate methods require an upfront investment in index construction, whether that is building a graph (HNSW), clustering vectors into partitions (IVF), or learning codebooks (quantization). This build cost is amortized over all future queries, which makes it worthwhile when the collection will be queried many times.

Second, observe the memory column. Graph-based methods add $M$ connections per vector on top of the full vector storage, which increases memory usage but enables the fast navigable graph traversal that gives HNSW its speed advantage. IVF methods add a relatively modest centroid storage cost $C$ (proportional to the number of clusters, not the number of vectors). Quantization methods achieve the greatest memory savings by replacing the full $d$ -dimensional vector with a compressed code of dimension $d'$ , where $d'$ can be 8 to 32 times smaller than $d$ .

The graph-based approach (HNSW) typically offers the best recall at a given query speed, which is why it has become the dominant ANN method. However, it uses more memory than quantization-based approaches because it stores both the full vectors and the graph edges.