A graph index organises stored vectors as nodes in a graph, with each node connected by edges to some of its nearest neighbours. Searching becomes a matter of walking this graph: starting at an entry point and repeatedly stepping toward whichever connected node is closest to the query, quickly converging on the most similar vectors.
This structure is the basis of the most popular approximate-nearest-neighbour algorithms, above all HNSW. Graph traversal scales beautifully — the number of steps needed grows only logarithmically with the dataset size — which is why graph indexes deliver both high recall and low latency, even across millions or billions of vectors.
The main cost of a graph index is memory: each vector must store not only its values but also its list of connections, and the structure generally lives in RAM for speed. It also requires care when filtering, since removing nodes can disrupt the graph’s navigability — a challenge addressed by in-graph and filter-aware techniques. Despite these costs, graph indexes are the dominant choice for in-memory vector search.