Experience Graphs: The Data Foundation for Self-Improving Agents¶

🕒 Published (v1): 2026-06-29 06:02 UTC · Source: Arxiv · link

Why this paper was selected

Database-community perspective on self-improving agents; fresh infrastructure paradigm

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

TL;DR¶

This paper proposes Trellis, a data foundation that treats the exploration state of long-horizon agentic tasks—what it calls the experience graph—as first-class, governed, queryable database state rather than ephemeral JSON checkpoints and session logs. It argues that separating compute from state makes agents stateless and crash-recoverable, and that search over experience graphs is fundamentally a database access pattern. Grounded in Meta's production kernel optimizer KernelEvolve, cross-session reuse converges ~10× faster at 52% lower token cost.

Problem¶

Current agent frameworks (Claude Code, Codex, AlphaEvolve, etc.) treat the exploration state generated by long-horizon search—executable artifacts, tool outputs, objective rewards, sibling comparisons, causal lineage—as disposable process-local state serialized to JSON and log files. The three-tier memory model that production agents have converged on (declarative facts, procedural skills, episodic logs) captures what an agent knows, not the reward-bearing experience graph of what its search tried. This missing abstraction means: progress is lost on crash, parallel workers need ad-hoc coordination, prior discoveries cannot be systematically reused, and training data requires brittle post-hoc scraping from logs.

Method¶

The paper defines a two-loop architecture: an inner loop of skill-driven, stateless agent sessions, and an outer loop that orchestrates search over a persistent data substrate. Search strategies (one-shot, linear, greedy, MCTS, evolutionary) are all policies over the same data interface—differing only in the selection query—not separate systems.

Trellis implements the substrate with a unified logical model over heterogeneous physical backends: - A four-level relational schema: Tasks (problem specification) → Sessions (algorithm + progress) → Nodes (parent link, artifact, fitness score, algorithm-specific metadata) → Prompt histories (exact LLM I/O). Large artifacts are stored by reference. - Queries compose SQL, Cypher (for graph traversal via virtual parent–child edges), and vector similarity under a single optimizer (Axiom over the Velox execution engine), routing each fragment to the appropriate backend (operational store, vector index, columnar warehouse). - Declarative and procedural memory (CLAUDE.md, skills) are stored as versioned artifacts in a distributed filesystem, mounted read-mostly via FUSE, so writes commit centrally. - Context is managed state in the substrate (not trapped in a live process), allowing a child node to inherit or reconstruct context via ancestor queries.

Results populate the substrate as materialized views: SFT trajectories, DPO preference pairs, GRPO groups—self-improving flywheel.

Key Contributions¶

Defines the self-improving agentic system as a two-loop architecture (inner agent + outer search orchestration) connected by a persistent data substrate, extended to multi-agent scientific societies.
Shows the three-tier memory model (declarative/procedural/episodic) is an incomplete special case, and proposes a concrete data foundation that unifies them with the reward-bearing experience graph through a query layer composing graph traversal, vector similarity, and structured filters.
Identifies the resulting access pattern as novel to the database community—append-heavy writes mixed with multi-hop path updates, vector retrieval, and as-of temporal reconstruction—and lays out new research opportunities in multi-modal query planning, consistency for concurrent tree search, and bi-temporal memory.

Results¶

10× faster convergence to target speedup and 52% lower token cost per valid solution, measured via a controlled study of cross-session reuse in KernelEvolve.
KernelEvolve delivers >60% inference throughput improvement on production ranking and recommendation workloads across NVIDIA, AMD, MTIA, and CPU targets.
An exploration–anchoring tradeoff is identified: reuse accelerates convergence but can bias the search toward known local optima.
All results are from production deployment at Meta; no Trellis-vs-baseline database benchmarks are reported (the paper is a CIDR vision/architecture paper).

Limitations¶

Trellis itself is a proposed architecture, not a fully implemented and benchmarked system—detailed latency/throughput comparisons against alternatives (e.g., pgvector, Neo4j, DuckDB) are absent.
The exploration–anchoring tradeoff is identified but not characterized: no guidance on when reuse harms exploration.
KernelEvolve results may not generalize to other agentic domains (scientific discovery, security research, hardware design) that produce structurally different experience graphs.
Multi-agent society aspects and governance semantics remain future work, not implemented designs.
The 10× speedup is time to reach target speedup using cross-session reuse vs. from-scratch search—not a wall-clock speedup of Trellis itself over existing frameworks.

Relevance to Harnesses / Meta-Harnesses¶

This paper directly systematizes the concept of a meta-harness. Its two-loop architecture—a stateless inner loop (any agent framework) orchestrated by an outer loop that selects frontiers via query—is the abstract definition of what a harness does. The key contribution for harness designers is that search strategy is a control-plane policy over a shared data interface, not a bespoke system: MCTS, evolutionary search, and greedy deepening all write and read the same tables, differing only in the selection query. For anyone building meta-harnesses, Trellis provides the database architecture foundation that turns exploration state from disposable computation into a durable institutional asset, enabling crash recovery, horizontal scaling, and a closed-loop training flywheel as architectural byproducts.