When your question is about how things connect, not what sounds alike, does a graph database beat search by similarity?
Can graph databases outperform embeddings when queries demand relational traversal?
This explores whether graph databases beat embedding-based (vector similarity) retrieval when a question depends on following chains of relationships, such as "which suppliers of X also supply Y", instead of finding text that sounds similar to the query.
This explores whether graph databases beat embedding-based retrieval when a question depends on following chains of relationships instead of finding text that sounds similar. The corpus says yes, with a price attached. Vector search fails on aggregate and relational queries in enterprise domains. Swapping its probabilistic similarity search for deterministic graph traversal (querying with Cypher) gives the precision and completeness those queries need When do graph databases outperform vector embeddings for retrieval?. The cost is that you have to build the graph first, which is much more work than embedding a pile of documents.
The reason embeddings struggle is architectural, so better tuning won't fix it. Embeddings measure association, not relevance. A passage can sit close to your question in vector space without being the entity two hops away that you needed. There is also a mathematical ceiling: embedding dimension limits which sets of documents a vector index can represent at all Where do retrieval systems fail and why?. A traversal follows explicit links, so it doesn't run into that limit.
The interesting work is in making graphs cheaper and less brittle. One approach skips the pre-built graph. LogicRAG builds a small graph from the query itself at inference time, which avoids construction overhead and stale data while keeping multi-hop reasoning Can query-time graph construction replace pre-built knowledge graphs?. A second problem is that a large graph won't fit in an LLM's context window. Graph-O1 has an agent explore the graph step by step, using Monte Carlo Tree Search and reinforcement learning to learn which paths to follow. That trades certainty about the whole graph for decisions made under uncertainty Can learned traversal policies beat exhaustive graph reading?.
The shape of the graph matters too. Ordinary edges connect two things, so a fact that binds three or more entities at once gets broken into pieces. Hypergraph memory keeps those joint constraints intact as evidence builds up across retrieval steps Can hypergraphs capture multi-hop reasoning better than graphs?. Graphs also reach questions flat retrieval can't touch. MegaRAG builds a hierarchical graph over whole books, including images as nodes, to answer cross-chapter questions that chunk-by-chunk search misses Can multimodal knowledge graphs answer questions that flat retrieval cannot?. Part of the benefit may come from planning the hops separately from writing the answer. Splitting those two jobs improves multi-hop performance on its own Do hierarchical retrieval architectures outperform flat ones on complex queries?.
So the choice depends on what the query looks like. Graphs win when the answer is a path or a complete set, and embeddings stay cheaper when it is a passage that sounds like the question. The head-to-head evidence in this collection is a single note. The rest of the corpus is about making the graph route cheaper or smarter, not about measuring the two against each other.
Sources 7 notes
Graph-oriented databases solve vector similarity's failure on aggregate queries by replacing probabilistic similarity search with deterministic graph traversal via Cypher. The tradeoff: higher construction cost but precision and completeness for enterprise use cases where query patterns are relational.
RAG systems fail at three structural levels: adaptive triggering (fixed intervals waste context), semantic-task mismatch (embeddings measure association, not relevance), and mathematical limits (embedding dimension constrains representable document sets). These require fundamentally different retrieval approaches, not tuning.
LogicRAG constructs directed acyclic graphs from queries at inference time rather than pre-building corpus-wide graphs, eliminating construction overhead, avoiding staleness, and enabling query-specific retrieval logic without sacrificing multi-hop reasoning capability.
Graph-O1 replaces whole-graph ingestion with step-by-step agentic navigation using Monte Carlo Tree Search and reinforcement learning. This approach fits within LLM context windows while learning domain-specific traversal policies, though it trades certainty about the full graph for decision-making under uncertainty.
HGMem organizes retrieved evidence as hyperedges rather than flat lists or binary graphs, allowing three or more entities to bind into single relations without decomposition. This structure accumulates coherent knowledge across retrieval steps, trading representational complexity for constraint expressiveness.
Show all 7 sources
MegaRAG builds hierarchical multimodal knowledge graphs from text and visuals to answer cross-chapter, global questions that flat chunk retrieval cannot reach. The hierarchy supports abstraction levels from high-level summaries to page-specific details while treating images as first-class graph nodes.
Separating query planning from answer synthesis into distinct components reduces interference and improves multi-hop query performance. This architectural principle mirrors documented benefits of separating planning from execution in agent design.
Papers this line draws on 8
The research behind the notes this line reads — ranked by how closely each paper relates.
- You Don't Need Pre-built Graphs for RAG: Retrieval Augmented Generation with Adaptive Reasoning Structures
- BM25 Wins at Scale: A Scaling Study of Retrieval-Augmented Generation Paradigms
- Chain-of-Retrieval Augmented Generation
- RAGU: A Multi-Step GraphRAG Engine with a Compact Domain-Adapted LLM
- Towards Agentic RAG with Deep Reasoning: A Survey of RAG-Reasoning Systems in LLMs
- Multi-hop Question Answering via Reasoning Chains
- RL Squeezes, SFT Expands: A Comparative Study of Reasoning LLMs
- From Local to Global: A Graph RAG Approach to Query-Focused Summarization