TL;DR
AI agents increasingly use databases as "working memory" to speculatively explore trees of hypothetical actions, requiring rapid database branching, mutation, and evaluation. This paper introduces BranchBench, the first benchmark designed to evaluate branchable databases under these agentic workloads, revealing a critical architectural tension between fast branch management and fast query performance.
What Problem Does This Paper Address?
Modern AI agents don't just query databases linearly; they speculatively explore trees of hypothetical actions using algorithms like Monte Carlo Tree Search (MCTS). To do this efficiently, an agent needs to fork a database state, apply mutations (such as data updates or schema changes), evaluate the outcome, and then either merge the "winning" state or discard the branch entirely.
Traditional relational databases (RDBMS) rely on nested transactions or full database copies, which fail to provide the persistent isolation and high-frequency concurrency required by autonomous agents. While a new class of "zero-copy" branchable databases (like Neon and Dolt) has emerged, they use fundamentally different underlying mechanisms. Until now, the performance trade-offs of these architectures under intense agentic exploration remained completely unstudied.
Methods
The authors first establish a taxonomy of existing zero-copy branching designs based on where they sit in the database stack: Storage Substrate (block-level CoW), Recovery Manager (WAL-based reconstruction), or Storage Manager (content-addressed trees or delta overlays).
To evaluate these designs, they introduce BranchBench, which consists of two main components:
- Macrobenchmarks: These simulate five representative agentic workflows—Agentic Software Engineering (ASE), Failure Reproduction, Data Curation, MCTS, and Simulation—using a parameterized branch–mutate–evaluate–prune loop executed by parallel workers.
- Microbenchmarks: These isolate the raw latency and storage costs of individual branch lifecycle primitives (create, connect, delete, and execute) to separate infrastructure overhead from query execution.
Datasets
BranchBench unifies the transactional and analytical capabilities of the CH-benCHmark schema (which combines TPC-C and TPC-H tables) to form the basis of its evaluation. The benchmark evaluates performance across varying tree topologies (flat stars, deep/narrow trees, and bushy trees) defined by parameters like root fanout ($F_r$), inner fanout ($F_i$), and maximum depth ($D$).
Key Insights and Ideas
- The Agility vs. Query Performance Tension: There is a fundamental architectural divide. Systems optimized for instantaneous branching (like Dolt's content-addressed Merkle/prolly-trees) suffer massive read penalties as branches deepen because they must constantly traverse complex tree structures. Conversely, systems optimized for fast data operations (like Neon's WAL-based reconstruction) suffer from high branch creation and switching latencies.
- Compute vs. Storage Trade-offs: Neon provisions a dedicated compute instance per branch, ensuring fast queries but bottlenecking branch creation with control-plane overhead. Dolt runs everything within a single process, making branching cheap but causing severe resource contention during concurrent reads.
- The Scale Gap: No current production database can successfully run these representative agentic workloads at full scale; every system tested either crashed, timed out, or hit API rate limits.
Key Results
- Branching Latency: Dolt's branch operations are near-instantaneous. In contrast, Neon is 25× slower to create branches and 1500× slower to switch between them due to cloud control-plane roundtrips and compute provisioning delays.
- Read Performance: Neon's data operations incur near-zero overhead. However, Dolt's read latency is 2 to 4000× higher than Neon's across workloads—particularly for range read queries—as mutations accumulate.
- Capability Failures: Traditional baselines (PostgreSQL savepoints or file-copy clones) failed almost all workloads due to strict connection requirements or lack of persistent named branches. Neon's cloud service capped concurrent live branches to 20, causing partial failures in multi-agent scenarios.
Limitations and Future Work
- Single-Agent Focus: The benchmark currently isolates single-task exploration and does not address multi-agent coordination or cross-agent concurrency control.
- Missing Primitives: No evaluated system natively supports cross-branch aggregation (querying data across multiple branches simultaneously), forcing inefficient application-level collection.
- Call for Branch-Native DBMSes: The authors conclude that current systems are retrofitted developer tools. Future database engines must be designed from the ground up for high-frequency speculative branching, prioritizing metadata scalability, fast garbage collection for short-lived branches, and branch-native storage layouts.
Summary updated