Vector Databases & RAG Complexity Profile

The algorithmic boundary of vector databases & rag modeled via graph theory.

A retrieval-augmented index is a similarity graph; the cost of coherent multi-hop retrieval tracks the treewidth of the activated subgraph, not its raw size. Every profile below reads the same substrate through a different graph invariant and structural regime, and prices it with Ross’s Law.

A retrieval-augmented index looks like a pile of vectors, but it behaves like a graph. Each chunk is a vertex; each strong semantic-similarity link is an edge. A single lookup touches one neighborhood and is cheap. The cost that surprises people is coherent multi-hop retrieval — pulling a set of chunks that have to make sense together — and that cost does not track the size of the index. It tracks the treewidth of the subgraph the query activates.

This is why a RAG system can feel sharp at ten thousand documents and start dragging in half the corpus at a million, with no change to the model or the prompt. What changed is the structure: the similarity graph crossed a threshold and stopped being separable. The five invariants below each measure where that threshold is, from a different direction. Each sorts the index into a shadow regime (clean neighborhoods, retrieval stays local and cheap), a mirror regime (one dense tangle where “relevant” means “everything”), or the equilibrium band between them.

Treewidth bounds

Treewidth is the quantity that actually prices multi-hop retrieval: the width of the worst cut you must reason across to assemble a coherent answer.

Graph degeneracy

Degeneracy is the early-warning gauge, polynomial to compute as the index grows. It measures the densest core of mutually-similar chunks — the part of the corpus that has fused.

Embedding-space entropy

The entanglement analogue for an index is the entropy of its embedding distribution across a partition — how much the two halves of the corpus “know” about each other. Concentrated embeddings are shadow; embeddings that fill the space are mirror.

Fiedler-value connectivity

The Fiedler value asks whether the similarity graph has a natural seam to cut — a clean way to split the corpus that retrieval can exploit.

Bipartite treewidth

The bipartite cut is the stress test: split the corpus in two and measure how wide the relevance interface between the halves is — the worst case for any partition-based retrieval scheme.