MnemoverseDocs

Appearance

Edward Izgorodin·Published Jul 10, 2026

How AI Agents Navigate Knowledge Graphs: The Policy, Not the Graph ​

A knowledge graph is a world model only when it is navigable: a set of entities and typed relations an agent can move through to answer a question, rather than a static triple-store dumped into a prompt.

A traversal policy is the agent's decision procedure over the graph: from a seed, which relation to follow, how wide to branch, how deep to go, and when to stop.

TL;DR ​

  • The main lever is usually the agent's traversal policy — how it moves through the graph — more than the sheer amount of graph data. On the tasks measured below, an agent that navigates the graph beats one that dumps a subgraph into context.
  • Agents need a coherent read-side verb surface: observe, hop, path, summarize, as-of, why, and enough.
  • Reach depends on three coupled choices: frontier size, level of detail, and serialization format.
  • Graphs help most with multi-hop reasoning and belief over time. They still impose a graph tax, degrade at scale, and can lead agents to trust graph tools without verification.

Building the graph solves only the storage side of agent memory. The harder question is how an agent consumes that structure. A large graph does not choose a route. It does not decide which edge matters, whether a summary is sufficient, or whether an old fact remains valid. Those choices belong to the agent's policy and tool surface. A plain triple-store dumped into a prompt is not navigation; it is context stuffing.

The design follows from that: keep the graph external, let algorithms perform structural operations, and use the LLM as a controller that chooses operations, evaluates returned evidence, and decides when to stop. This is the consumption-side companion to Knowledge-Graph Memory for AI Agents, which covers the graph as a memory substrate.

AI agent knowledge graph traversal: policy over data ​

Several research lines point to the same conclusion: navigation actions matter more than placing a larger subgraph in the prompt.

Search-on-Graph lets an LLM issue iterative, informed navigation steps rather than retrieving one subgraph and reasoning over it once. With GPT-4o, it reports Hits@1 of 91.3 on WebQSP, 86.9 on GrailQA, 75.1 on CWQ, and 84.8 on SimpleQA. The authors also report at least 46.4% fewer LLM calls and 69.9% fewer output tokens than earlier graph-reasoning methods. On WebQSP, it uses 3.9 calls versus 8.4 for Think-on-Graph — a 53.6% cut in round-trips.

GraphRunner separates traversal into plan, verify, and execute. It validates a proposed multi-hop route against the graph schema before running it. On GRBench with GPT-4, the authors report a 10–50% GPT4Score improvement over the iterative GRAPH-CoT baseline. Measured wall-clock response time is 2.5–7.1 times faster. Its reported 3.0–12.9 times lower inference cost is an estimate derived from token counts and GPT-4 list prices, not measured billing — a distinction worth keeping.

Budgets matter even when the policy is simple. Think-on-Graph uses beam search in which the LLM selects relations and entities to expand. Its default fixes both beam width and maximum depth at 3. That makes the core design choice explicit: traversal is a bounded search, although the bound is hand-set rather than adapted to the question.

Tool access can matter more than model-only structural reasoning. GraphWalk removes real-world knowledge leakage by testing mazes and synthetic random graphs. On 10×10 mazes, models score 0–10% without tools and 60–100% with navigation tools. On a 500-node graph, GPT-4.1 with tools holds about 26.7%, while o4-mini without tools falls to 4.2% from about 49% at 100 nodes. The study did not test o4-mini with tools, so those conditions should not be conflated. Give an LLM navigation actions and structural reasoning improves; without them, it degrades as the graph grows.

Structural computation should also remain outside the language model. GDS-Agent exposes centrality, shortest-path, and community algorithms as tools. On its 302-station London Underground benchmark with claude-sonnet-4, it reports 0.803 tool-F1 and 0.723 answer-match for the agent, without a comparative baseline. The authors note that LLMs "can only simulate basic algorithms on relatively small-scale simple graphs" — a reason to put structural operations in algorithms behind tools, not in the model's head.

Where these lines report a comparison, the gain comes from navigation actions, verification, and planning — not from simply enlarging the retrieved subgraph or the context window.

The verbs an agent needs on a knowledge graph ​

Most graph-memory interfaces lead with search. Search is useful, but it returns candidates rather than a route. Across today's production MCP graph and memory servers, multi-hop is rarely a first-class verb, and provenance — "why do you believe X?" — is seldom callable at all.

Graphiti illustrates the distinction. Its search_nodes and search_memory_facts tools accept center_node_uuid, which applies a node-distance reranker to already retrieved candidates. The MCP surface does not expose a first-class depth, expansion, or multi-hop path parameter. The underlying graphiti-core library does include breadth-first search, so the limitation is the MCP tool surface rather than the entire codebase.

Cognee documents 14 MCP tools, including get_chunk_neighbors. That operation retrieves adjacent chunks from the same document and acts as a local observation primitive. It and several other tools are direct-mode only and are omitted in API mode, leaving the live surface smaller than the documented list.

The gap between "search returns a blob" and "the agent can observe, hop, zoom, time-travel, and ask why" is where navigation lives — and much of it is unbuilt. As a research requirement, a coherent read-side surface needs six verbs:

text
observe(node)          → neighbors, relations        // cheap local introspection
hop(node) / path(a, b) → budget: width, depth        // first-class multi-hop
summarize(region)      → resolution, level-of-detail // zoom
as_of(time)            → view at a temporal slice     // when was this true?
why(fact)              → provenance chain             // why do you believe X?
enough?                → bool                          // sufficiency / STOP

These are requirements about what the field needs, not a claim about a particular product roadmap. Together, they turn retrieval from "search and paste" into controlled observation: a graph the agent can only search is a pile of facts; a graph the agent can observe, hop through, zoom into, time-shift across, and interrogate is a world model.

Provenance is beginning to receive dedicated treatment. Eywa, a recent single-author preprint, describes a deterministic multi-route read path with no LLM calls inside retrieval and provenance attached to each answer; its benchmark results remain author-reported. From Lossy to Verified reports an efficiency trade-off rather than an accuracy win: LoCoMo falls from 0.873 with raw-only memory to 0.851, while input tokens fall 54.1% and latency falls 60.7%.

Graph traversal reach, resolution, and budget ​

An agent cannot inspect an entire large graph for every question. It must spend a bounded budget across frontier size, resolution, and representation format.

Format alone can change what the model extracts. KG-LLM-Bench compares five graph serializations. Structured JSON averages 0.42, RDF Turtle 0.35, and JSON-LD 0.34; on individual tasks, the right encoding is worth up to 17.5 percentage points. The same graph takes about 13,500 tokens in JSON-LD versus 2,645 as a list of edges. Accuracy for aggregation by relation stays above 50% only through degree 4, then falls to about 10%. GraphOmni reports a maximum 40% accuracy gap between formats for GPT-4o on its diameter task. How you render a region of the graph to the model is a first-class navigation decision.

Level of detail provides another control. Microsoft's GraphRAG uses community summaries to answer global questions at different resolutions. Its root-level summaries use 97% fewer tokens than the full graph and achieve their reported comprehensiveness and diversity results at about 2.3–2.6% of maximum token cost. Those quality comparisons use an LLM evaluator because the study lacks gold-standard answers. CLAUSE instead constructs a question-specific subgraph adaptively. On MetaQA-2-hop, it reports 87.3 EM@1 versus 78.0 for GraphRAG (a 9.3-point gain), with 18.6% lower latency and 40.9% lower edge growth — pull only the detail the question needs.

Mnemoverse has published one research direction for continuous graph resolution. In our own preprint, Semantic Level of Detail for Knowledge Graphs: Discovering Abstraction Boundaries via Spectral Heat Diffusion, heat-kernel diffusion provides a continuous zoom operator, while spectral gaps identify abstraction boundaries without manual resolution tuning. This is a self-citation to Mnemoverse research, not a product capability claim.

Reach can also be computed locally. Personalized PageRank underlies retrieval in HippoRAG, while localized push-based methods — Andersen–Chung–Lang forward push, FORA (KDD 2017), and EdgePush — approximate PageRank from a local frontier rather than running full-graph power iteration, with bounded approximation error and top-k guarantees in FORA. "How far can the agent afford to look" becomes a tuned, local computation rather than an all-or-nothing global one.

The practical budget is therefore not just "maximum hops." It is frontier width × resolution × rendering cost × verification cost. Reach is a budget problem: spend it adaptively per question, and a small, well-aimed traversal can beat a big dump.

When a knowledge graph earns the name "world model" ​

A static graph records a snapshot. A world model must also represent changing belief: when a fact held, what superseded it, and which evidence supports the current view.

AriGraph combines semantic and episodic memory in a graph that an agent builds and navigates while acting. With a gpt-4-0125-preview backbone in TextWorld, it scores 1.0 on Cooking, compared with 0.18 for full history, 0.52 for summary, and 0.36 for RAG. On Cleaning, it scores 0.79, compared with 0.05, 0.35, and 0.39, respectively. On MuSiQue, AriGraph with GPT-4 reports 45.0 EM and 57.0 F1, versus 38.0 and 47.4 for GraphReader with GPT-4. An explicit navigable world-graph beats dumping history or flat RAG for sequential decision-making.

Zep's temporal knowledge graph records event time and ingestion time so that facts can be invalidated as conditions change. On LongMemEval, the paper reports GPT-4o improving from 60.2 to 71.2, a gain it states as up to 18.5%, while latency falls from about 28.9 seconds to 2.58 seconds because of the smaller prompt. On Deep Memory Retrieval it reports 94.8% versus MemGPT's 93.4% — a modest 1.4-point edge on a saturated benchmark.

Its LoCoMo result also shows why benchmark provenance matters. Zep reported about 84%, while Mem0 later published a disputed recomputation of 58.44% ± 0.20, arguing that the denominator excluded adversarial questions whose answers remained in the numerator. Zep rejected the methodology and closed the issue and pull request unmerged on 2025-05-19. The recomputation is contested, not an accepted correction — which is the honest picture of vendor memory numbers: single-run and disputed.

World models can also be prepared before a query arrives. Sleep-time Compute, published as a 2025 preprint, has models process contexts offline and pre-compute useful quantities. It reports about a fivefold test-time compute reduction on Stateful GSM-Symbolic. The same pattern applies to graph memory: consolidate the navigable view before the agent needs it.

HippoRAG 2 uses Personalized PageRank as a graph-based indexing operation — a single graph-diffusion step doing the work of iterative retrieval. It reports R@5 gains from 76.5 to 90.4 on 2WikiMultiHopQA and 69.7 to 74.7 on MuSiQue over NV-Embed-v2, while using 9.2 million indexing tokens versus 115.5 million for GraphRAG. The original HippoRAG it builds on reports quality comparable to or better than iterative retrieval like IRCoT while running 10–30 times cheaper and 6–13 times faster.

Time, episodic context, and revision turn a graph from a store into a maintained belief state. Navigation makes that state usable. The label "world model" is earned by temporal, episodic, belief-revising graphs; it is marketing for a static triple-store.

The honest ceiling of GraphRAG and graph agents ​

Graph access does not guarantee sound reasoning, and a credible account names the limits — several of them peer-reviewed.

Agents can defer to graph tools without checking them. When the Tool Decides, a 2026 preprint, finds that agents accept a GNN tool's label 97.6–99.2% of the time. In 83% of queries, they make exactly one tool call, never probing the signal designed to flag when the label is wrong. Deference rises from 0.60 to 0.98 across Qwen2.5 sizes, while a selective-invocation gate recovers about half of the measured gap.

Scale remains a hard limit. GraphArena, published at ICLR 2025, reports Claude-3.5-Sonnet accuracy falling from 47.8% on small graphs to 7.2% on large graphs for NP-complete tasks. GPT-4o hallucination on the diameter task rises from 16% at 5 nodes to more than 80% at 30 nodes.

GraphRAG can also lose to plain RAG on ground-truth measures. RAG vs GraphRAG records ROUGE-2 scores of 6.99 for global GraphRAG versus 10.08 for plain RAG on SQuALITY, and 3.23 versus 6.32 on QMSum. It also finds that reversing the order presented to an LLM judge can flip the comparative verdict. GraphRAG's own head-to-head wins — 72–83% on comprehensiveness and 62–82% on diversity — are LLM-as-judge results, not ground-truth ones, as that paper explicitly states.

The graph tax depends on the task. When to Use Graphs in RAG gives 60.92% for plain RAG versus 49.29% for MS-GraphRAG on fact retrieval, while on complex reasoning HippoRAG 2 scores 53.38% versus 42.93% for RAG. MS-GraphRAG global prompts reach about 40,000 tokens, compared with about 879 for naive RAG. Do We Still Need GraphRAG?, also 2026, finds that agentic search narrows the dense-RAG-versus-GraphRAG gap but GraphRAG keeps its multi-hop lead (an average +27.23 on multi-hop and +0.47 on single-hop in the single-shot setting).

The defensible conclusion is narrower than "graphs make agents smarter." Graphs pay off for multi-hop reasoning and changing belief — and only when the agent can choose where to look, inspect why an answer exists, adjust resolution, distrust a tool when needed, and stop before traversal cost exceeds its value. That is the case for building the verb surface, not for dumping a bigger graph.

Common questions ​

How do AI agents use knowledge graphs? ​

AI agents use knowledge graphs by selecting seed entities, observing nearby relations, following bounded paths, changing resolution, checking provenance, and stopping when the retrieved evidence is sufficient.

What is a knowledge graph traversal policy? ​

A knowledge graph traversal policy decides which relation to follow, how wide and deep to search, which graph operation to call, and when the agent has enough evidence to answer.

Why does GraphRAG sometimes underperform plain RAG? ​

GraphRAG can add construction, summarization, and prompt costs that do not help simple fact retrieval. Its advantage is more defensible on multi-hop questions than on direct lookup.

What graph tools should an AI agent have? ​

A useful read-side surface includes observe, hop or path, summarize by resolution, as-of queries, provenance lookup, and an explicit sufficiency or stop decision.

When is a knowledge graph a world model? ​

A knowledge graph earns the world-model label when an agent can navigate it and the graph represents changing belief over time, including when facts were valid and why they are believed.

Edward Izgorodin · Mnemoverse · last updated 2026-07-10