liveBook · Manning

Centroid

As explained in Retrieval Augmented Generation, The Foundational Ideas

A cluster centroid is the representative mean vector of the items assigned to a cluster.

A cluster centroid is the representative mean vector of the items assigned to a cluster. In vector search, centroids partition a large vector space into groups of similar vectors. section 2.2.1

K-means constructs centroids through an iterative procedure:

  • Initialize k centroids randomly. section 2.2.1
  • Assign each vector to its nearest centroid. section 2.2.1
  • Recalculate each centroid as the mean of its assigned vectors, then repeat until convergence. section 2.2.1

Centroids in approximate search

FAISS first compares an incoming query with cluster centroids, using only k comparisons. It then searches the selected cluster or clusters instead of exhaustively comparing the query with every vector, turning million-vector searches into thousand-vector searches. section 2.2.1

Figure 2.3 FAISS's Two-Stage Search Strategy.

Shows FAISS's two-stage strategy: route a query through centroid comparisons before searching vectors within the selected cluster. section 2.2.1

How Retrieval Augmented Generation, The Foundational Ideas covers it

How deep it goes
Explains k-means initialization, assignment, mean recalculation, convergence, and query routing, while deferring clustering and compression details.
Examples
Uses random initialization, nearest-centroid assignment, mean recalculation, and FAISS's two-stage query search as examples.
What you can do after
Apply it via FAISS to route queries into clusters before performing focused nearest-neighbor searches.
How it connects
Connects centroids to k-means clustering, approximate nearest neighbors, vector compression, GPU acceleration, and nearest-neighbor search.

Also explained in

Compare how 10 books explain centroid →

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.