Agents + Graphs

Chapter 1: ReAct Framework

In 2022, Yao et al. published ReAct: Synergizing Reasoning and Acting in Language Models. The key observation: when a model just generates reasoning traces ("Chain-of-Thought"), it can drift into hallucination because it has no feedback. When a model just acts (issues API calls), it has no reasoning to connect results. ReAct interleaves both.

The ReAct loop is exactly three steps, repeated until the agent decides it has the answer:

ReAct in Practice: Prompting

ReAct works via few-shot prompting. You give the model 2-6 examples of the Thought/Action/Observation format, and it continues the pattern for a new question. No fine-tuning required — the in-context examples teach the format.

ReAct trace (few-shot example in prompt)
Question: What is the population of the capital city of the country that
         borders Spain to the south?

Thought: I need to find which country borders Spain to the south.
Action: Search("countries bordering Spain to the south")
Observation: Morocco borders Spain to the south (via the Strait of Gibraltar).

Thought: The capital of Morocco is Rabat. I need its population.
Action: Search("Rabat population")
Observation: Rabat has a population of approximately 577,000.

Thought: I have the answer.
Action: Finish("Approximately 577,000")

Chapter 2: Reflexion

ReAct is powerful but brittle: if the agent goes down a wrong reasoning path and gets a wrong answer, it doesn't know it got it wrong. It just reports the result with confidence. Reflexion (Shinn et al., 2023) adds a second loop: after each episode, the agent reads its own trace and writes a self-critique that it carries into the next attempt.

Think of it as the difference between a student who submits an exam and forgets it, versus a student who reviews the graded exam, identifies their mistake, and keeps that insight as a note for the next test. Reflexion is the "keep the note" mechanism.

The Three-Memory Architecture

Reflexion: reflection written after a failed episode
# Episode 1 failed: agent answered "Christopher Nolan" for a question
# about the director of a 2023 film it didn't correctly identify

Reflection: "I made an error in step 2: I assumed the film was Oppenheimer
without verifying that it was actually released in 2023. I should
always verify year-specific facts with a lookup before building
further reasoning on them. In the next attempt, verify the film
title and release year before looking up its director."

# Episode 2 context (prepended before the new question):
# [Reflection from ep1 inserted here]
# Question: [same question]
# Thought: Based on my previous error, I should first verify...

Chapter 3: Graph-Grounded Agents SHOWCASE

We've seen ReAct and Reflexion in abstract. Now let's run a real graph-grounded agent on a knowledge graph question. The agent needs to answer: "Which drug targets the same protein as Imatinib, and is used to treat a disease caused by the same gene mutation?"

This requires three hops: (1) find Imatinib's protein target, (2) find other drugs targeting that same protein, (3) for each candidate drug, check if its disease has the same gene mutation as Imatinib's primary disease. No LLM can reliably answer this from memory — it must traverse the biomedical KG.

What Makes Graph Grounding Different from RAG?

Retrieval-Augmented Generation (RAG) retrieves a chunk of text (a paragraph) based on embedding similarity. Graph grounding retrieves a structured subgraph — a set of typed triples — based on entity traversal. The difference matters for multi-hop reasoning.

Chapter 4: Tool Use on Graphs

The agent doesn't directly access the knowledge graph — it calls tools that abstract the graph operations. This is a crucial design decision: exposing graph APIs rather than raw graph queries lets the LLM reason in natural language while the tool handles the graph traversal logic.

The Graph Tool Toolkit

A well-designed graph agent toolkit has three classes of tools. Think of these like a GPS app: you don't compute shortest paths yourself — you call "navigate to X" and get back a route.

Graph tool API (Python)
class KGToolkit:
    def lookup_entity(self, name: str) -> dict:
        # Returns: {"id": "Q123", "type": "drug", "description": "..."}
        return self.kg.get_entity_by_name(name)

    def get_neighbors(self, entity_id: str, rel: str = None) -> list:
        # Returns: [{"entity": "BCR-ABL1", "relation": "targets"}, ...]
        return self.kg.neighbors(entity_id, relation_filter=rel)

    def sparql_query(self, query: str) -> list:
        # LLM writes SPARQL; tool executes against KG
        # Returns list of matching triple patterns
        return self.kg.execute(query)

# Agent action format in the ReAct loop:
# Action: get_neighbors("imatinib", rel="targets")
# Observation: [{"entity": "BCR-ABL1", "relation": "targets"}]

SPARQL-Style Queries from LLMs

Modern agents (like KG-GPT and ToG) can generate structured queries over KGs. The LLM is prompted with the graph schema (entity types, relation types) and generates a query. The tool executes it, returning a subgraph that the LLM can reason over.

Chapter 5: RL for Agent Optimization

Prompt engineering and few-shot examples take you far, but they don't adapt. If your agent consistently makes the same class of mistake, you need a mechanism to update it. Two approaches dominate: PPO (Proximal Policy Optimization) for online RL with a learned reward, and DPO (Direct Preference Optimization) for offline learning from human preference pairs.

Treating the Agent as a Policy

Cast the agent in the RL framework: the state is the current context (question + Thought/Action/Observation history), the action is the next token (or the next tool call), and the reward is given at episode end — +1 if the final answer is correct, 0 otherwise. The goal: maximize expected reward over episodes.

Where τ is a full agent episode (the trajectory of Thoughts, Actions, Observations), π_θ is the LLM policy parameterized by weights θ, and R(τ) is the episode reward (correct answer = 1, wrong = 0, or a shaped intermediate reward).

PPO for Agents

PPO keeps the updated policy close to a reference policy to prevent catastrophic changes. The policy generates trajectories, a reward model scores them, and the gradient update improves high-reward trajectories while the KL penalty keeps the model from drifting too far from its pretrained behavior.

Where r_t(θ) = π_θ(a_t|s_t) / π_old(a_t|s_t) is the probability ratio, Â_t is the advantage estimate (how much better was this action than average?), and ε clips the ratio to prevent large updates.

DPO for Agents

DPO skips the explicit reward model. Instead, you collect pairs of agent trajectories on the same question: one that got the answer right (preferred) and one that got it wrong (rejected). DPO directly optimizes the LLM to prefer the correct trajectory over the incorrect one, using only cross-entropy loss over the pair.

Where τ_w is the winning (correct) trajectory and τ_l is the losing (incorrect) trajectory. DPO is simpler to implement than PPO — no separate critic network, no online sampling loop during training.

Chapter 6: Benchmarks

How do we know if a graph-grounded agent is actually better? We need benchmarks that test multi-hop reasoning over structured knowledge — not just reading comprehension or simple factoid lookup. Two benchmarks from CS224W stand out: STaRK and UnknowBench.

STaRK: Semi-Structure Retrieval Benchmark

STaRK (Wu et al., 2024) tests agents on three knowledge graphs: Amazon product graphs, biomedical KGs (PrimeKG), and academic citation graphs (MAG). Queries require combining structured graph traversal (follow edges) with unstructured text reasoning (understand entity descriptions).

UnknowBench: Testing Knowledge Boundaries

UnknowBench tests a different capability: does the agent know when to say "I don't know"? It contains questions whose answers are absent from the knowledge graph — the correct response is to recognize the gap and say so, rather than hallucinate an answer.

This is critical for real-world deployment. An agent that confidently gives a wrong answer is more dangerous than one that says "I couldn't find this in the graph." UnknowBench rewards appropriate uncertainty.

Chapter 7: Multi-Agent Graph Systems

A single agent can handle one reasoning chain. But some tasks require parallel exploration — multiple competing hypotheses, different tools for different subtasks, or expert specialization. Multi-agent systems assign different agents to different subgraphs or reasoning tracks, coordinating via a shared message-passing protocol.

Here's the key insight: the coordination structure of the agents can itself be a graph. Agents are nodes; information flows between them along edges. This creates a recursive pattern — a graph of agents operating on a knowledge graph.

Common Multi-Agent Architectures

Message Passing Between Agents

Agents share partial results as structured messages: "I found that BCR-ABL1 targets Imatinib — does any other drug in your subgraph also target BCR-ABL1?" This is analogous to GNN message passing: each agent aggregates messages from its neighbors (other agents), updates its belief state, and passes new messages forward.

Chapter 8: Challenges

Graph-grounded agents are powerful, but they come with a set of hard, open problems that the field is actively working on. Being honest about these limitations is as important as understanding the successes.

Challenge 1: Hallucination at the Interface

Grounding reduces hallucination for facts in the graph, but the agent still hallucinates when reasoning over graph results. The KG returns correct triples; the LLM combines them incorrectly. This is especially common when the agent must aggregate multiple graph results — it may invent a logical connection that the data doesn't support.

Challenge 2: Incomplete Knowledge Graphs

Real KGs are always incomplete. Freebase covered roughly 3% of world knowledge before it was shut down. Wikidata has many missing relations. When the agent queries for a fact that should be in the graph but isn't, it either incorrectly says "I don't know" (missing a valid answer) or falls back to parametric memory and hallucinates.

Challenge 3: Grounding Latency

Each tool call adds latency. A 5-hop reasoning chain with 2 tool calls per hop requires 10 round trips to the KG. For a graph with millions of nodes, each query takes 10-100ms. Total agent latency can hit 5-10 seconds — too slow for interactive applications.

Challenge 4: Symbolic-Neural Mismatch

Knowledge graphs use discrete symbolic relations (drug targets protein). LLMs operate in continuous embedding space. Bridging them requires translation: embedding entities in the LLM's token space, or converting graph results to natural language. Both introduce information loss — the structured precision of the graph is partially lost in translation.

Chapter 9: Connections

Graph-grounded agents sit at the intersection of several major research streams. Understanding how they connect to adjacent topics shows you both where the field came from and where it's going.

Key Papers

• Yao et al. (2022). ReAct: Synergizing Reasoning and Acting in Language Models. ICLR 2023.
• Shinn et al. (2023). Reflexion: Language Agents with Verbal Reinforcement Learning. NeurIPS 2023.
• Sun et al. (2023). Think-on-Graph: Deep and Responsible Reasoning of LLM on KG. ICLR 2024.
• Wu et al. (2024). STaRK: Benchmarking LLM Retrieval on Textual and Relational Knowledge Bases. NeurIPS 2024.
• He et al. (2024). G-Retriever: Retrieval-Augmented Generation for Textual Graph Understanding.

What's Next

"The structure of the graph is the structure of knowledge. An agent that can traverse it has access to what we know; one that can reason over it has access to what we can infer."