How do vector indexes work?

Knowing that two vectors can be compared for similarity says nothing about how that comparison scales once there are millions, or billions, of stored vectors to check against. Comparing a query against every single one of them, one at a time, is the most obvious approach, and it’s also completely impractical at any real scale. Understanding why that obvious approach breaks down, and what specialized structure exists to fix it, explains why vector search can feel instantaneous even over enormous stores of memory.

Why Doesn’t Simply Comparing a Query Against Every Stored Vector Work at Scale?

The straightforward approach, calculating the distance between a query vector and every single vector in storage, is called exact nearest-neighbor search, and its cost grows directly with how much is stored. Comparing one 300-dimension query vector against ten million stored vectors means roughly three billion individual number comparisons for a single search, and that cost keeps climbing linearly as more memories get added. What takes an imperceptible fraction of a second against a thousand stored items can stretch into seconds, or far longer, against millions, making exhaustive comparison completely unworkable for any system expected to respond quickly at real-world scale.

This isn’t a problem that faster hardware alone solves, since the underlying math scales the same way regardless of how fast each individual comparison runs. What’s needed is a fundamentally different approach that avoids comparing against everything in the first place.

What Does “Approximate” Actually Mean in Approximate Nearest Neighbor Search?

Rather than guaranteeing it finds the mathematically exact closest matches every single time, an approximate approach deliberately trades a small amount of accuracy for an enormous gain in speed, organizing stored vectors ahead of time so that a search only has to examine a small, carefully chosen fraction of everything stored rather than all of it. The results this produces are very good approximations of the true nearest matches, not always the mathematically perfect answer, but close enough for virtually every real use case, while running dramatically faster than exhaustive comparison ever could.

This tradeoff is measured using recall, the fraction of genuinely closest matches that the approximate search actually managed to find. A well-tuned approximate search routinely achieves recall in the high nineties, meaning it finds nearly all of the true best matches, while running orders of magnitude faster than checking every single stored vector individually.

How Does Pre-Organizing Vectors Ahead of Time Actually Make Search Faster?

The core idea behind every approximate nearest-neighbor structure is doing organizational work upfront, when data is stored, so that far less work is needed later, when a query actually needs answering. Vectors that are close to each other in meaning get connected or grouped together during this upfront organization, so that a search can start near a plausible answer and explore only the nearby, likely-relevant region, rather than blindly checking everything from scratch on every single query. This is conceptually similar to how a well-organized library groups related books together on the same shelf, letting someone looking for a book on a specific topic go directly to the right section instead of scanning every single shelf in the building.

This upfront organizational cost is why building a vector index takes real time and computation when data is first added or substantially changed, a cost paid once, in exchange for every subsequent search benefiting from that organization without having to redo it.

Are There Different Ways to Organize Vectors for This Kind of Fast Approximate Search?

Several distinct strategies exist, connecting similar vectors through a navigable graph structure, grouping them into clusters based on similarity, or organizing them into a tree that progressively narrows down a search region. Each approach makes different tradeoffs between how much memory the organization itself requires, how quickly new data can be added without expensive rebuilding, and how high a recall it can sustain at a given search speed. None of these approaches is universally superior, the right choice depends on the specific balance a system needs between speed, memory use, and accuracy for its particular scale and update pattern.

How Does Weaviate Engram Benefit From This Underlying Indexing Machinery?

Weaviate Engram’s memory search runs on top of Weaviate’s underlying vector indexing, meaning every memory search benefits from exactly this pre-organized, approximate structure rather than ever having to exhaustively compare a query against every memory ever stored for every single search. Consider a seed-bank catalog search assistant helping agricultural researchers find germplasm accessions with specific drought-tolerance traits across a collection that has grown to hold hundreds of thousands of individually documented seed samples over decades:

from engram import EngramClient

client = EngramClient(api_key=os.environ["ENGRAM_API_KEY"])

client.memories.add(
    "Accession WB-4471 shows strong root-depth development under water-stress conditions, consistently outperforming regional controls in the last three drought trials.",
    properties={"program_id": "drought-resilience-wheat"},
)

A researcher searching this collection benefits from the underlying index without ever needing to think about it directly:

candidates = client.memories.search(
    query="Which accessions have shown strong root development specifically under water stress?",
    properties={"program_id": "drought-resilience-wheat"},
    retrieval_config=HybridRetrieval(limit=10),
)

Behind this single call, the underlying vector index means the search doesn’t compare this query against every one of the hundreds of thousands of accessions ever logged across the entire program’s history, it navigates directly toward the region of the vector space where genuinely relevant, drought-related entries actually live, returning results in a fraction of a second regardless of how large the underlying collection has grown. Without this indexing machinery, a search over a collection this size built up across decades of research would become measurably, and eventually unworkably, slower every single year the catalog kept growing. The specific mechanics of how one particular indexing approach, the graph-based structure most vector databases actually use in practice, accomplishes this deserve their own closer look.

Understanding that vectors get organized ahead of time to make approximate search fast explains the general principle behind the speed. The specific graph-based structure most modern vector databases actually use to implement this, and exactly how it navigates toward good answers so efficiently, deserves a closer, more concrete look. Our next chapter, What is HNSW?, takes up exactly that structure.