Your AI Agent Doesn't Need to Traverse Graphs: Lookup vs. Path

The Core Argument: Agents Don't Need to Traverse Graphs

Storing context in a graph database is a valid storage decision, especially when multiple agents need access to the same ontology. However, connecting an agent directly to that graph so it must traverse edges at query time is almost always wrong. The author illustrates this with a Fortune 500 insurance company that assumed every agent needed a managed graph database service because reference architectures showed a graph box with arrows. In reality, their questions — "Can this sales rep sell this product in this state? What is this policy's status?" — had clear, predetermined join paths that any data team member could sketch on a napkin. The company already ran a governed metadata layer containing most of the needed information. They didn't need a graph database, and more precisely, they didn't need the agent anywhere near the graph.

Lookup vs. Path: Classifying Agent Questions

The author proposes a binary classification that is more reliable than "depth":

Lookup — The answer is a value or set; the join path is known at design time. Examples: "Can this rep sell in this state?" "What is the policy status?" "How many claims last quarter in this region?" The agent only needs column definitions, join keys, grain, and governance rules. No second database, no traversal.

Path — The answer is the shape of the connections: shortest/all paths between two nodes, fraud rings (cycles), centrality rankings, N-hop neighborhoods. Here the path itself is the deliverable, not a means to an end.

Enterprise metadata is mostly wide but shallow (low fan-out, acyclic), making recursive CTEs in SQL perfectly adequate. A team traversing a 335,000-node tree cut latency from 47 seconds to 227 ms by moving the traversal into a C extension inside their existing engine — they did not buy a graph database. Another team found the breaking point at 500,000 nodes and depth 6. Pathfinding (betweenness centrality, community detection) is a different workload where SQL is both slow and wrong; graph engines have decades of algorithmic optimization for these.

When a Graph Database Is Actually Justified

Three conditions must all be met before adding a second database:

The output must be a path or topology result (shortest/all paths, cycle detection, community identification, centrality ranking).

The boundary really explodes — high fan-out, many back-edges, little prunability. Measure, don't guess.

Under concurrent writes, each entity needs single-digit-millisecond traversal latency — index-free adjacency makes hop cost independent of total graph size, critical for operational serving but irrelevant for analytical tasks.

Even when these hold, the agent still shouldn't touch the graph. A separate service can run the traversal and return results. Aggregation, rollups, and temporal-window calculations are explicit exceptions: graph query languages are weak at aggregation; columnar engines own that work.

Evidence from Benchmarks: GraphRAG and Text-to-SQL

The "Graph + LLM" narrative rests heavily on two misread papers:

Sequeda et al. reported accuracy rising from 16.7% to 54.2% on enterprise SQL schemas when a knowledge graph was added. The missed detail: the knowledge graph was an ontology plus mappings serving as a context layer for the model to read , not a graph the model traversed at query time.

Han et al. (GraphRAG) compared plain retrieval against four GraphRAG variants on single-hop, multi-hop, and detail-oriented benchmarks. The variant that matches the popular imagination — extract a knowledge graph from corpus, then retrieve on it — lost to plain retrieval on every QA benchmark . On MultiHop-RAG (designed for graph reasoning) it scored 48.5% vs. 67.0%; on HotpotQA F1 was 42.6 vs. 60.0. Indexing took 7,702 seconds vs. 135 seconds; retrieval took 14,434 seconds vs. 1,724 seconds — 50× preprocessing cost, 8× query cost, for worse performance on its supposed strong suit.

The winning GraphRAG variants (≈3 pp gain on multi-hop) used the graph only to decide which text chunks to retrieve ; the model never saw the graph . GraphRAG is a retrieval strategy over text, not a runtime reason to attach a graph database.

A critical regulatory number: on questions the corpus cannot answer (correct behavior = refuse), plain retrieval refused 96.0% of the time; the Community Summarisation variant refused only 19.3%, hallucinating answers the rest.

The Real Work: Curating High-Signal Context

Vendor benchmarks (90%+ accuracy) test only already-modeled scope — questions humans have fully defined. Real user requests ignore that boundary. Spider 2.0 (whole schema) saw frontier models score in the teens vs. 86.6% on Spider 1.0 (pre-modeled subset). A controlled comparison with fixed model (DeepSeek-R1) and varying scaffolding showed 13.7% (baseline scaffolding), 30.5% (agent framework A), 52.3% (agent framework B) — a 39-point swing with no storage or model change, only how the schema was described to the model .

Context and Chaos ran a controlled experiment: 13 tables, 174 natural-language questions, 522 runs, only the context layer swapped . Accuracy rose from 16.1% (bare schema) to 22.2% (high-signal context), statistically significant (p < 0.0001). Verbose documentation-style context reduced accuracy by 13.8% and increased cost by 52% compared to concise high-signal context.

Enterprise Text-to-SQL is neither unsolved nor solved. It responds stably to one thing: how much of the schema is truly described, and how well . The work is expanding the modeled scope and keeping it fresh — not picking a smarter retriever or adding a traversal step.

A governed semantic layer also changes failure mode: the system can refuse to answer instead of confidently returning a wrong number that ends up in a board deck.

Practical Exercise: Label 20 Questions

Take the last 20 questions your agent received (or expects). Tag each with three labels:

Path or Lookup? Count Path. If near zero, a graph database won't help regardless of data density.

Inside modeled scope or outside? The outside count is your true accuracy ceiling — the one vendor benchmarks don't measure.

Does the agent itself need to know the graph exists? Not your platform, not your pipeline — the agent. For every team the author has worked with, this column is empty .

The typical result: almost no Path questions, many outside modeled scope, third column blank. That trio signals a context problem — where the budget should go.

Final Takeaway

Your data has always been a graph. That was never the problem. The real problem: has anyone written down what it means, in a form the agent can understand without taking a single step?