Experience Graphs: The Data Foundation for Self-Improving Agents
2026-06-29 • Databases
DatabasesArtificial IntelligenceMultiagent Systems
AI summaryⓘ
The authors point out that tasks like code generation and scientific discovery involve many steps where agents try, fail, learn, and improve. They call the collection of these attempts an experience graph, but current systems treat this data as temporary and discard it. They propose Trellis, a database system that stores these experience graphs as valuable data that can be searched, reused, and learned from over time. This makes agents more reliable, scalable, and efficient, as shown in their testing at Meta where it sped up processes while saving costs. Overall, the authors suggest Trellis changes how agent experiences are managed, turning them into lasting resources instead of throwaway logs.
experience graphagentic tasksdatabase statequeryable datasearch patternscrash recoverycross-session reusematerialized viewKernelEvolveaccelerator-kernel optimizer
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
Abstract
The database community has repeatedly advanced the state of the art by recognizing that new workloads demand new system architectures. We argue that long-horizon agentic tasks -- code generation, scientific discovery, hardware design -- are such a workload. These agents explore: they generate artifacts, execute tools, observe failures, branch, and repair over hundreds of steps. This search produces a structured object we call an experience graph: executable artifacts, tool outputs, rewards, sibling comparisons, and causal lineage. Yet existing agent frameworks treat this experience as disposable state -- JSON checkpoints and session logs that cannot be recovered after a crash, queried across users, or materialized into training data. We propose Trellis: a data foundation that treats the experience graph as first-class, governed, queryable database state. The core insight is that search over experience graphs is a database access pattern. Frontier selection is a query, cross-session reuse is vector-seeded graph retrieval, training-data extraction is a materialized view, and reconstructing what an agent knew at any past step is a time-travel query. When the database owns the experience graph, agents become stateless compute, and crash recovery, horizontal scaling, and a closed-loop training flywheel emerge as architectural byproducts. We ground the design in KernelEvolve, a production accelerator-kernel optimizer at Meta, where cross-session reuse reaches a target speedup roughly 10x faster at 52% lower token cost. More broadly, Trellis turns inference-time search from disposable computation into a durable institutional asset: logs made databases reliable; experience graphs may make agents cumulative.