Retrieval as navigation over embedding geometry

Vector search treats a corpus as a flat cloud of points: embed the query, return its nearest neighbors. That works well for "find documents like this," but it has no notion of the corpus's structure: which documents form a theme, how themes connect, where the gaps are.

GraphRAG [1] adds structure by having a language model extract entities and relationships from every document, building a graph, finding communities in it with the Leiden algorithm, and summarizing each community. Its strength is global questions over a whole corpus, like "what are the main themes in these interviews?", which nearest-neighbor search cannot answer. The cost is a language model call per chunk at indexing time, and a graph that only contains what the model chose to call an entity.

This note proposes building the structure from the embeddings themselves.

Structure from geometry

The Mapper algorithm from topological data analysis [2] turns a point cloud into a graph:

1. Map each point through a lens $\ell : \mathbb{R}^d \to \mathbb{R}^k$ with small $k$, for example a 2D UMAP projection.
2. Cover the lens space with overlapping intervals or tiles $U_1, \dots, U_m$.
3. Cluster the original points whose lens values fall in each $U_j$.
4. Make each cluster a node, and connect two nodes when their clusters share a document.

The overlap is what produces edges. The result is a graph of document clusters in which connected clusters are close in embedding space and adjacent under the lens.

Search as descent

Give every cluster $c$ an energy with respect to a query $q$:

where $\mu_c$ is the cluster's mean embedding, $\sigma_c$ its spread (a penalty for incoherent clusters), and $a_c$ the median age of its documents. Search seeds a few starting clusters from an HNSW index [3] over the documents, then moves greedily to the lowest-energy neighbor until no neighbor is lower:

def search(q, graph, index, k=10, seeds=5):
    frontier = {graph.cluster_of(d) for d in index.knn_query(q, k=seeds)}
    best = None
    for c in frontier:
        while True:
            nxt = min(graph.neighbors(c), key=lambda n: energy(n, q), default=c)
            if energy(nxt, q) >= energy(c, q):
                break
            c = nxt
        if best is None or energy(c, q) < energy(best, q):
            best = c
    return rank(graph.documents(best), q)[:k], best

Starting from several seeds matters because greedy descent stops at the first local minimum, and a Mapper graph can have many.

What this is close to

Cluster-based retrieval. Returning the documents of the best cluster rests on the cluster hypothesis: documents relevant to the same query tend to be similar to each other [4]. Retrieval over clusters has been studied for fifty years, and it usually helps only when the clusters are good. The new part here is the graph walk between clusters, not the clustering.

RAPTOR [5] already builds structure from embeddings without entity extraction. It recursively clusters chunk embeddings, summarizes each cluster with a language model, and retrieves over the resulting tree. It answers the same question as this note, whether embedding geometry can replace entity graphs, and reports gains on long-document question answering. Any test of this idea should use RAPTOR as a baseline.

What could go wrong

• Instability. Mapper graphs change substantially with the lens, the cover resolution, the overlap and the clusterer. If small parameter changes reorder results, the method is not usable. This should be measured before anything else.
• The lens throws information away. Two clusters adjacent in a 2D projection need not be related in 768 dimensions. Using the lens only to build the cover and the full embeddings for clustering and energy limits this but does not remove it.
• No gain over the seeds. If the best cluster is almost always the one containing the top HNSW hit, the walk adds latency and nothing else.

How to test it

On BEIR [6] datasets with topical structure (SCIDOCS, NFCorpus, FiQA), compare nDCG@10 against dense retrieval alone, BM25, and RAPTOR, and report:

1. the variance of nDCG@10 across a grid of Mapper parameters;
2. how often the walk moves away from its seed cluster, and whether those moves help;
3. query latency.

I have not run this. The likeliest outcomes are that instability dominates or that the walk rarely leaves its starting cluster. Either would be worth writing up.

References

1. Edge et al. From Local to Global: A Graph RAG Approach to Query-Focused Summarization. 2024. arXiv:2404.16130
2. Singh, Mémoli and Carlsson. Topological Methods for the Analysis of High Dimensional Data Sets and 3D Object Recognition. 2007. doi:10.2312/SPBG/SPBG07/091-100
3. Malkov and Yashunin. Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. IEEE TPAMI, 2018. arXiv:1603.09320
4. Jardine and van Rijsbergen. The Use of Hierarchic Clustering in Information Retrieval. Information Storage and Retrieval, 1971.
5. Sarthi et al. RAPTOR: Recursive Abstractive Processing for Tree-Organized Retrieval. ICLR 2024. arXiv:2401.18059
6. Thakur et al. BEIR: A Heterogeneous Benchmark for Zero-shot Evaluation of Information Retrieval Models. NeurIPS Datasets and Benchmarks, 2021. arXiv:2104.08663