💻 computer science

Experience Graphs: The Data Foundation for Self-Improving Agents

The paper proposes Trellis, a database-centric architecture that treats the structured "experience graphs" generated by long-horizon agentic tasks as first-class, queryable data to enable stateless agents, robust crash recovery, and a closed-loop training flywheel, demonstrating significant efficiency gains in a production kernel optimizer at Meta.

Original authors: Gang Liao, Yujia He, Abdullah Ozturk, Zhouyang Li, Ying Wang, Zhitong Guo, Hongsen Qin, Yaobin Qin, Tao Yang, Zewei Jiang, Dianshi Li, Jort Gemmeke, Jiangyuan Li, Liyuan Li, Nathan Yan, Masha Basmanov

Published 2026-06-30

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Gang Liao, Yujia He, Abdullah Ozturk, Zhouyang Li, Ying Wang, Zhitong Guo, Hongsen Qin, Yaobin Qin, Tao Yang, Zewei Jiang, Dianshi Li, Jort Gemmeke, Jiangyuan Li, Liyuan Li, Nathan Yan, Masha Basmanova, Uladzimir Pashkevich, Matt Steiner, Pedro Pedreira, Rob Fergus, Anirudh Goyal, Carole-Jean Wu, Gaoxiang Liu, Andrew Witten, Daniel J. Abadi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Idea: From "Forgetful" Agents to "Cumulative" Learners

Imagine you are teaching a robot to solve a very hard puzzle, like designing a new computer chip or writing complex code.

The Old Way (Current Agents):
Right now, most AI agents work like a person trying to solve a puzzle in a single sitting. They try a step, maybe fail, try again, and keep going until they get an answer. But once they finish (or crash), they forget almost everything they learned during that specific attempt. If they try the same puzzle tomorrow, they have to start from scratch. Their "memory" is just a pile of messy notes (logs) that are hard to read or reuse.

The New Way (Trellis & Experience Graphs):
This paper proposes a new system called Trellis. Think of a trellis as the wooden lattice structure gardeners use to help vines grow. The vine (the AI agent) does the climbing and growing, but the trellis (the database) holds everything up, organizes the branches, and ensures the plant doesn't collapse.

In this new system, every single step the agent takes—every guess, every failure, every tool it uses, and the score it gets—is saved into a giant, organized, searchable structure called an Experience Graph.

The Core Metaphor: The "Garden of Attempts"

Instead of an agent just writing a final report, imagine it is exploring a massive garden.

The Experience Graph: This is the garden itself. Every path the agent walks, every flower it picks, and every dead end it hits is recorded as a permanent plant in the garden.
The "Vines": The AI agents are the vines. They grow, explore, and try new things.
The "Trellis" (Trellis System): This is the database that holds the garden. It doesn't grow the plants; it supports them. It remembers exactly where every branch is, how well it grew, and what happened if you tried a different path.

Why This Changes Everything

The paper argues that treating these "garden records" as a proper database (like the ones that run banks or airlines) changes how AI works in three main ways:

1. No More "Amnesia" After a Crash

The Problem: If a current agent crashes (like a computer freezing), it loses its progress. It's like a hiker falling off a cliff and forgetting the map they were holding.
The Trellis Solution: Because the "map" (the experience graph) lives in the database, not in the agent's head, the agent can be restarted instantly. It just asks the database, "Where was I?" and picks up exactly where it left off. The agent itself becomes "stateless"—it's just a worker that does the thinking, while the database holds the memory.

2. Learning from Others (Cross-Session Reuse)

The Problem: Currently, if Agent A solves a problem, Agent B doesn't automatically know about it. They are isolated.
The Trellis Solution: The database allows Agent B to look at Agent A's "garden." If Agent A found a shortcut or a way to avoid a dead end, Agent B can see that path immediately.

The Result: The paper tested this with a real-world tool called KernelEvolve (which optimizes computer code). When agents could "borrow" from the shared garden, they found good solutions 10 times faster and used 52% less computing power (tokens) because they didn't waste time repeating mistakes others had already made.

3. The "Time Travel" for Training

The Problem: To teach AI better, we usually need to scrape through messy logs to find examples of what worked and what didn't. This is slow and often inaccurate.
The Trellis Solution: The database automatically organizes the "garden" into training materials.

It can show the AI: "Here is a path where you succeeded (Good)."
It can show: "Here is a path where you failed (Bad)."
It can even do "Time Travel": It can reconstruct exactly what the agent knew at that specific moment in the past, without seeing the future results. This creates perfect, high-quality training data automatically.

The "Self-Improving Flywheel"

The paper describes a cycle that makes the system smarter over time:

Explore: Agents search the garden, trying new things.
Record: Every attempt is saved in the Trellis database.
Learn: The database turns these attempts into training data to teach the AI models.
Improve: The smarter models go back to the garden and explore even better.

Because the database holds the memory, the whole system gets better as more people use it. It's not just one agent getting smarter; it's a whole community of agents sharing a single, growing library of experience.

What the Paper Actually Claims (and What It Doesn't)

It Claims: They built a system (Trellis) that treats AI search history as a database. They tested it on computer chip optimization (KernelEvolve) and hardware validation. They showed it makes agents faster, cheaper to run, and more reliable.
It Claims: This architecture allows for "Recursive Self-Improvement" (agents getting better at their own job).
It Does NOT Claim: This paper does not discuss medical uses, clinical trials, or specific applications outside of software/hardware optimization (though it mentions the structure could apply to drug discovery or science, the actual results presented are only about computer code and chips).

Summary Analogy

Imagine a group of scientists trying to discover a new law of physics.

Without Trellis: Each scientist works in a separate room, writes notes on paper, and if they leave the room, the notes are thrown away. They have to reinvent the wheel every time.
With Trellis: All scientists work in a giant, shared library. Every experiment, every failure, and every success is written on a card and filed perfectly. If a scientist makes a mistake, the library knows. If another scientist needs a clue, they can look up the exact card from a colleague's experiment. The library itself is the "brain" that remembers everything, allowing the scientists to stand on each other's shoulders and reach further than ever before.

The paper concludes that logs made databases reliable, but experience graphs might make AI agents cumulative—meaning they can build knowledge that lasts and grows, rather than just solving one problem at a time.

Technical Summary: Experience Graphs: The Data Foundation for Self-Improving Agents

Problem Statement

The paper identifies a fundamental architectural gap in current self-improving agent systems. While long-horizon agentic tasks (e.g., code generation, scientific discovery, hardware design) rely on iterative search processes that generate rich, structured data—termed experience graphs—existing frameworks treat this data as disposable state.

Current systems serialize search trees into ephemeral JSON checkpoints or file-based logs. This approach leads to several critical failures:

Fragility: Progress is lost upon process crashes; recovery requires brittle, after-the-fact log scraping.
Isolation: Search statistics and causal lineage cannot be queried across users or sessions, preventing systematic reuse of prior discoveries.
Training Inefficiency: Extracting training data (e.g., for SFT, DPO, GRPO) requires fragile post-hoc scraping rather than direct querying, losing provenance and structural integrity.
Incomplete Memory Models: Production agents have converged on three memory tiers (declarative facts, procedural skills, episodic logs), but these capture what an agent knows, not the reward-bearing experience graph of what the search tried.

The authors argue that the database community has historically advanced by recognizing new workloads (e.g., transactions, streaming) that demand new architectures. They posit that the "search over experience graphs" in agentic tasks constitutes such a new workload, requiring a shift from ephemeral logs to a governed, queryable database foundation.

Methodology: The Trellis Architecture

The authors propose Trellis, a data foundation that treats the experience graph as first-class, governed database state. The architecture decouples the agent's compute from its state, enabling stateless, serverless agents.

Core Components

Two-Loop System Architecture:
- Inner Loop: An autonomous agent session (e.g., Claude Code, Codex) driven by specific "skills." It consumes a task, generates artifacts, executes tools in a sandbox, evaluates results, and persists the structured output (logs, metrics, fitness scores) as a node in the graph. The agent process itself holds no state.
- Outer Loop: A control plane that orchestrates search strategies (One-Shot, Linear, Greedy, MCTS, Evolutionary). It selects frontier nodes from the graph, assembles context (ancestors, siblings, prior failures), and dispatches the inner loop. The strategy is a policy over the data substrate, not a hard-coded algorithm.
Data Foundation (Trellis):
- Logical Model: A unified, algorithm-agnostic schema comprising four tables: Tasks (specifications), Sessions (search context), Nodes (individual attempts with parent links, artifacts, rewards, and algorithm-specific metadata like UCB scores), and Prompt_History. Large artifacts are stored in object storage, linked by reference.
- Physical Architecture: Disaggregates stateless query/execution engines (using Axiom over Velox) from durable storage. It supports a unified query layer that composes SQL (relational), Cypher (graph traversal), and vector retrieval into a single physical plan.
- Key Features:
  - Vector-Seeded Graph Retrieval: Combines vector similarity search (for task descriptions) with graph traversal to retrieve high-fitness subtrees from prior sessions, enabling cross-session knowledge reuse.
  - Multi-Version State & Time Travel: Uses a change log keyed by logical step numbers (evaluation order) rather than wall-clock time. This allows "AS-OF" reconstruction of the agent's state at any past step, crucial for training data fidelity (preventing data leakage from future search statistics).
  - Governance: Enforces access policies across raw traces, distilled skills, and derived training views.

Key Contributions

Definition of Self-Improving Agentic Systems: The paper formalizes these systems as a two-loop architecture (inner skill execution, outer search orchestration) over a persistent data substrate. It extends this from single-agent search to multi-agent "scientific societies" where agents share hypotheses and critiques.
Unification of Memory and Experience Graph: It demonstrates that existing memory tiers (declarative, procedural, episodic) are incomplete without the reward-bearing experience graph. Trellis unifies these via a query layer supporting graph traversal, vector similarity, and structured filters.
Identification of New Database Research Opportunities: The paper outlines specific access patterns and challenges requiring database innovation:
- Multi-modal Query Planning: Optimizing plans that fuse vector search, relational joins, and variable-length graph traversal.
- Consistency for Concurrent Tree Search: Defining isolation levels for MCTS backpropagation (requiring durability for node insertion but tolerating eventual consistency for statistics).
- Physical Design: Creating storage layouts optimized for mixed workloads (appends, path updates, multi-hop traversal, vector similarity).
- Governed View Maintenance: Managing the invalidation of training views when source nodes are retracted.
- Bi-temporal Memory: Separating valid time (when a fact was true) from transaction time.

Results: KernelEvolve Case Study

The authors ground their design in KernelEvolve, a production accelerator-kernel optimizer at Meta. They report preliminary measurements comparing a database-native state (Trellis) against a prior in-memory architecture:

Recovery & Statelessness: In the new architecture, crashed sessions resume automatically from the last committed node without warm-up or checkpoint deserialization. No progress is lost due to infrastructure failures.
Cross-Session Reuse: By injecting semantically similar prior tasks and nodes (via vector-seeded retrieval) into the search context:
- Convergence Speed: The system reached a 1.2× speedup threshold in ~5 steps with memory, compared to 51 steps for a cold start (a 10× acceleration).
- Token Efficiency: The rate of "buggy" nodes (triggering expensive debug-retry loops) dropped from 55% (no memory) to 21% (with memory injection rate $p=0.5$ ). This resulted in a 52% reduction in token cost per valid solution.
- Exploration-Anchoring Tradeoff: The authors observed that higher memory injection rates ( $p=0.5$ ) stabilized search and reduced bugs but suppressed diversity, leading to fewer "best-in-class" solutions compared to a cold start. A balanced setting ( $p=0.1$ ) offered the best compromise.
Training Data Extraction: Training data (SFT trajectories, DPO pairs, GRPO groups) is extracted as materialized views directly from the operational store, eliminating the need for separate, fragile scraping pipelines.

Significance and Claims

The paper claims that Trellis transforms inference-time search from "disposable computation" into a "durable institutional asset."

Architectural Shift: By externalizing the experience graph to a database, agents become stateless compute units. This enables horizontal scaling, crash recovery, and a closed-loop training flywheel as architectural byproducts rather than engineered features.
Collective Intelligence: The architecture enables a transition from individual agents searching private trees to "scientific societies" where agents share structured knowledge, critique results, and compound discoveries across sessions and users.
Database Community Impact: The authors assert that "experience graphs may make agents cumulative," just as logs made databases reliable. They position agentic memory as the next major workload driving database design, necessitating new interfaces for transactions, warehousing, and graph management tailored to recursive self-improvement.

The paper concludes that while larger models and context windows are insufficient, a governed data foundation where the experience graph lives as queryable, shared, and training-ready state is essential for the next generation of self-improving agents.