What is vector indexing?

Summary slides

Why an index exists at all, and what problem it’s solving

Finding the closest vectors to a query by checking every single stored vector individually, an exhaustive search, always produces the exact correct answer, but its cost grows directly with the size of the collection, checking twice as many stored vectors takes roughly twice as long. A vector index exists to avoid this linear cost, organizing the collection ahead of time in a way that lets a search skip over most of the collection entirely, checking only a small, carefully chosen subset of vectors that are likely to contain the true closest matches, in exchange for accepting a small, usually well-controlled chance of missing the absolute best match in favor of one that’s nearly as good.

This tradeoff, accepting approximate rather than perfectly exact results in exchange for dramatically faster search, is the foundational idea behind essentially every practical vector index, and understanding that this tradeoff is deliberate and controllable, not an accidental compromise, is essential for understanding how to actually configure and evaluate a vector index for a specific application.

Graph-based indexing and how it navigates toward a match

Graph-based indexing, the most widely used approach in modern vector databases, builds a network connecting each vector to a set of its nearby neighbors, so that a search can start at some entry point in the graph and repeatedly move toward whichever connected neighbor is closest to the query, gradually converging toward the true nearest matches without ever needing to examine the full collection along the way. This is conceptually similar to navigating a network of acquaintances to find someone specific, each step moves toward someone more likely to be close to the actual target, rather than checking every single person in an entire directory one at a time.

The quality of this navigation depends heavily on how the graph itself was built, how many neighbor connections each vector maintains, and how those specific connections were chosen during construction, a graph with too few connections per vector risks getting stuck in a locally good but globally suboptimal region of the space, while a graph with too many connections improves search quality but costs more memory and takes longer to build and to navigate. This is exactly the kind of tunable parameter that lets a team trade search quality against memory and build cost to fit a given deployment’s actual constraints.

Cluster-based indexing and how it narrows the search space differently

Cluster-based indexing takes a different approach, grouping the entire collection into a number of clusters based on which vectors are naturally similar to each other, and at search time, first identifying which cluster or clusters are most likely to contain the query’s closest matches, then searching in detail only within those selected clusters rather than the full collection. This approach trades a coarser, cluster-level narrowing step for a more detailed search within a much smaller subset, rather than the step-by-step graph navigation the graph-based approach relies on.

The number of clusters a collection gets divided into, and how many of those clusters get searched in detail for a given query, are the primary tunable parameters here, more clusters searched per query improves accuracy since fewer genuinely relevant results get missed by having been assigned to a cluster that wasn’t checked, but it also increases search cost correspondingly, since more of the collection ends up being examined in detail. This tradeoff mirrors the same underlying speed-versus-accuracy balance the graph-based approach offers, expressed through a different set of tunable knobs.

Why there’s no single universally best indexing approach

Graph-based and cluster-based indexing each carry genuinely different tradeoffs beyond just search speed and accuracy, graph-based indexes tend to offer excellent search speed and accuracy but can be more memory-intensive and more expensive to build than cluster-based alternatives, while cluster-based indexes tend to use memory more efficiently and can be faster to build, at some cost to peak search accuracy compared to a well-tuned graph-based index. Which approach actually performs better for a given deployment depends on the balance of priorities that deployment cares about most, raw search speed and accuracy, memory efficiency, how frequently the index needs to be rebuilt as the collection changes.

This is why evaluating vector indexing approaches benefits from testing candidates against an application’s own actual data and actual query patterns, rather than trusting general claims about which approach is universally superior, connecting to the broader discussion of AI native testing covered elsewhere in this collection, the right indexing approach for a given deployment is an empirical question its own realistic testing needs to answer, not something that can be settled by reputation alone.

How index build time and update tolerance shape practical index selection

Beyond raw search performance, how easily an index tolerates ongoing updates matters enormously for how practical it is to operate in a real, changing production system, connecting directly to the operational challenges covered in this collection’s discussion of vector database scaling. Some index structures support adding new vectors incrementally with relatively little disruption, while others degrade in quality as more vectors get added incrementally without a full rebuild, eventually requiring that more disruptive rebuild to restore optimal search performance.

A team choosing an indexing approach purely based on search benchmark numbers, without considering how that index behaves under the specific update pattern its own application will actually generate, risks selecting an index that performs excellently on paper but becomes operationally painful once real, ongoing content changes start accumulating against it in production. This update tolerance deserves evaluation with the same seriousness given to raw search speed and accuracy, since it directly determines how manageable the index actually is to operate over its real, ongoing working life.

What tuning an index’s parameters actually involves in practice

Both major indexing approaches expose parameters a team can adjust to shift the balance between search speed, accuracy, memory usage, and build cost, and getting real value from a vector index typically requires actually tuning these parameters against a specific application’s own data and requirements rather than accepting default settings that were chosen to work reasonably across a broad range of unrelated use cases. A default configuration tuned for a generic benchmark rarely represents the actual optimal balance for any one application’s own particular collection size, query pattern, and accuracy requirements.

This tuning process benefits from the same empirical, measurement-driven approach covered throughout this collection’s broader discussion of calibration and threshold tuning, testing different parameter settings against a representative sample of an application’s actual queries and measuring the resulting tradeoff between search speed and retrieval accuracy directly, rather than guessing at reasonable-sounding values or accepting whatever a vector database’s default configuration happens to provide out of the box.

Common mistakes teams make around vector indexing

1. Accepting a vector database’s default indexing parameters without tuning them against the specific collection size and query pattern an actual application will generate.

2. Choosing between graph-based and cluster-based indexing purely based on general reputation, without testing both against the application’s own actual data and realistic queries.

3. Selecting an indexing approach based purely on search benchmark performance, without evaluating how well it tolerates the ongoing update pattern the application will actually produce.

4. Treating the approximate nature of vector indexing as an unfortunate limitation rather than a deliberate, controllable tradeoff worth actively tuning to fit a specific application’s needs.

5. Underestimating the memory and build-time cost differences between indexing approaches, discovering the operational impact only after committing to one at meaningful scale.

What connects these mistakes is treating vector indexing as a settled, automatic detail handled entirely by whichever vector database a team happens to adopt, rather than as a genuine engineering decision with real, tunable tradeoffs that deserve deliberate evaluation against an application’s specific data, query patterns, and operational constraints.

The deeper point about vector indexing is that the specific structure organizing a vector collection underneath a similarity search isn’t an invisible implementation detail, it directly determines the practical balance a production system strikes between how fast it searches, how accurate its results are, how much memory it consumes, and how gracefully it handles ongoing change, and understanding these tradeoffs well enough to tune them deliberately is what separates a vector search system that performs reliably under real, growing production demand from one that simply happened to work well during initial testing on a small, unrepresentative sample.