liveBook · Manning

Vector clustering

As explained in Retrieval Augmented Generation, The Foundational Ideas

Vector clustering partitions vectors into groups whose members are similar according to their positions in vector space.

Vector clustering partitions a large vector collection into groups of similar vectors so nearest-neighbor search can avoid exhaustive comparison. section 2.2.1

A k-means index follows this offline procedure:

  • Initialize k centroids randomly. section 2.2.1
  • Assign every vector to its nearest centroid, recompute each centroid as the mean of its assigned vectors, and repeat until convergence. section 2.2.1
  • At query time, compare the query with centroids first, then search only the selected cluster or clusters for nearest neighbors. section 2.2.1

Million-vector search

A query can narrow a million-vector search to roughly a thousand candidates by selecting a relevant cluster before exact neighbor search, trading exhaustive coverage for speed. section 2.2.1

Figure 2.3 FAISS's Two-Stage Search Strategy.

Shows FAISS's clustered, two-stage search strategy. section 2.2.1

How Retrieval Augmented Generation, The Foundational Ideas covers it

How deep it goes
Explains k-means iterations and two-stage querying, but defers vector compression and implementation details.
Examples
Uses FAISS and a million-vector query narrowed to roughly a thousand candidate vectors.
What it assumes
Assumes vector representations and nearest-neighbor search, while defining the k-means clustering procedure.
What you can do after
Evaluate how centroid routing reduces nearest-neighbor comparisons before exact search.
How it connects
Connects approximate nearest-neighbor search with k-means clustering, vector compression, and GPU acceleration.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Retrieval Augmented Generation, The Foundational Ideas. The section links point to the parts of the book it draws on.