arXiv CSopen access

Chronos: Efficient Bolt-on Branching Across Data Stores for Stateful Agentic Applications

Chronos: Efficient Bolt-On Branching Across Data Stores for Stateful Agentic Applications Xinjing Zhou

Jason Mohoney

Samuel Madden

MIT CSAIL Cambridge, MA, USA

MIT CSAIL Cambridge, MA, USA

MIT CSAIL Cambridge, MA, USA

Michael Stonebraker MIT CSAIL Cambridge, MA, USA

Shared Enterprise Data

arXiv:2609.14889v1 [cs.DB] 14 Sep 2026

ABSTRACT Data-centric applications increasingly use speculative execution to explore multiple candidate paths where each path modifies state distributed across heterogeneous data stores. This trend is intensified by the rise of tool-calling agents. Hence, applications need data systems that can create branches quickly, isolate state-modifying paths, and merge changes consistently across stores without imposing substantial query overhead. Existing systems provide only partial support, forcing applications to coordinate branches and merges manually, which increases overhead and risks inconsistent cross-store state. To solve this problem, we introduce Chronos, a bolt-on system that provides branching capability across heterogeneous data stores. We make two contributions. First, Chronos introduces a compact interval-based versioning technique that enables efficient branching and data sharing through simple query rewrite. Second, Chronos introduces a bolt-on architecture that separates branch management from data path within each store. Combined with interval-based versioning, this separation provides atomic crossstore visibility for merges and enables Chronos to support diverse data stores without modifying their engines. We implement Chronos for PostgreSQL, SQLite, DuckDB, Qdrant, and a DBMS-backed filesystem. We evaluate it using crossstore agent workflows, MCTS-style exploration, and per-store benchmarks. Chronos runs MCTS-style exploration up to 16.7× faster than existing approaches while maintaining practical query performance across the underlying stores. Under concurrent crossstore workflows, Chronos prevents partially visible merges while substantially outperforming serialized execution.

1

Lei Cao University of Arizona Tucson, AZ, USA

File System

Relational DB

NoSQL DB

inherit Support

Engineering

SRE

Existing Systems

Engineer A

Engineer B

Manual cross-store coordination Fork cost vs. query overhead Partial merge exposes inconsistent state

Fix A

Fix B

Incident

Follow-up

Figure 1: An enterprise agentic platform in which branches inherit shared enterprise data spanning filesystem, relational database, and NoSQL database. Existing systems require manual cross-store coordination, trade fork cost against query overhead, and can expose inconsistent state during a partially visible merge. optimization [32, 34, 36, 51, 70, 84], scientific simulation [13, 40, 62], and hardware and computational design [22, 44, 90]. Reinforcement learning for tool-using agents introduces another use case. Parallel rollouts read and modify isolated databases and filesystems before policy updates [69, 87]. Each rollout must fork its state quickly, modify it, and run queries that compute its reward. Cross-Store Speculative State. A key problem is that maintaining an isolated version becomes difficult when logical application state spans several data stores. Figure 1 illustrates this problem in an enterprise agentic platform whose shared enterprise data includes source code and documentation, structured records, and a vector index for semantic retrieval. Support, SRE, and Engineering teams inherit this data while maintaining additional team data. Within the Engineering team, each employee may use coding agents that can evaluate competing fixes on private branches, extend a promising fix with a nested branch, and investigate an unrelated incident concurrently. Each investigation may update source files, provenance records, and the corresponding vector index. When a reviewed result is merged, these dependent changes would ideally become visible consistently across all stores so that an entry in vector db never refers to a document that is not yet visible on filesystem. Applications therefore need one branch abstraction that spans multiple heterogeneous stores, supports fast and flexible branching,

INTRODUCTION

Versioning for Exploratory Workloads. Modern data-centric applications increasingly create isolated versions of durable state to evaluate tentative changes. Developers branch databases to test application changes without affecting production state [1, 49, 65, 68]. Data analysts similarly branch evolving shared datasets to isolate transformations and preserve their history [8–11, 29, 43, 66, 67, 73]. The rapid rise of tool-calling LLM agents both intensifies these established versioning workloads and introduces new exploratory applications. By automating multi-step development and analysis tasks, agents increase the frequency and concurrency with which existing workflows create and modify versions. At the same time, they generate and evaluate multiple execution paths at test time [33, 41, 72]. Through tool calls, each path may update files, database records, and generated artifacts before evaluation determines which changes to retain or roll back. This form of speculative execution appears in automated algorithm discovery and machine-learning 1

Xinjing Zhou, Jason Mohoney, Samuel Madden, Michael Stonebraker, and Lei Cao

efficient query, preserves isolated versions across many tool calls, and allows changes to be merged atomically or discarded. Existing systems fall short. Existing mechanisms cover only parts of these cross-store versioning requirements. Git [80] versions source files but does not isolate the associated database state. Database transactions [7, 28] can isolate changes, but the isolated state is transient because its lifetime is tied to a single transaction. Physical cloning incurs significant storage and creation costs. Dataset versioning systems and branchable databases provide durable alternatives [16, 17, 29, 50, 66], but can introduce significant query overhead [3]. Combining separate mechanisms for each store leaves the application responsible for aligning their versions and coordinating every cross-store merge, increasing the complexity of the application and the risk of exposing inconsistent state across stores. Chronos. In light of these gaps, we introduce Chronos, a lightweight polystore versioning layer that provides a unified branch abstraction for application state distributed across heterogeneous stores. An application can fork a consistent state, let each execution modify its private branch, and then compare, retain, merge, or discard the result without cloning every store. Chronos operates through existing data store interfaces and requires no changes to engine internals, while preserving each store’s native data and query paths. Its mechanisms apply independently of the application, while its design targets frequent, long-running branches such as those created by stateful agents. Providing frequent branching across existing stores—without modifying their engines or sacrificing query performance—raises three systems challenges. Challenge #1: Branching Performance. Speculative execution frequently creates branches and executes ordinary queries within them, placing both operations on the critical path. The challenge is to make branch creation independent of the amount of existing data without introducing branch-history reconstruction into the query path. Query execution performance should remain close to the native store as the branch tree grows. Challenge #2: Store Heterogeneity. Speculative execution state may span stores with different data models, query interfaces, and transactional mechanisms. These stores expose no common branching facility, while a bolt-on layer cannot rely on changes to their internal implementations. Nevertheless, a branch must select the corresponding record versions in every participating store and provide the same isolation semantics across them. The challenge is to enforce this common branch view using only capabilities that heterogeneous stores already support efficiently, without modifying their engines or replacing their native data and query paths. Challenge #3: Cross-store Consistency. An accepted candidate may contain dependent changes to files, relational records, and search indexes. Applying these changes through independent store operations can leave the target in an inconsistent state if an operation fails or the target changes concurrently. A merge must therefore provide atomic visibility for the complete resolved result across participating stores, while changes that are not part of the accepted result remain isolated from the target. Chronos addresses these challenges with a lightweight intervalbased versioning approach and centralized transactional branch coordination. Together, they enable efficient query execution and lightweight branching across heterogeneous stores.

In interval-based record versioning, each branch is assigned a half-open interval, with the root branch spanning the entire interval space. Creating a subbranch partitions its parent’s interval, and recursively partitioning intervals naturally represents the branch hierarchy. Each physical record version is tagged with the interval of the branch in which it is created. A record version is visible to a branch when its visibility interval contains the branch’s read point, which can be evaluated using a simple predicate. Because a subbranch is assigned an interval contained within its parent’s interval, it automatically shares and can read records created by its parent. When a branch updates a shared record, it performs record-level copy-on-write, creating physical versions with disjoint intervals to preserve isolation among branches. This interval-based representation enables efficient query processing using simple filter evaluation without joins. Chronos addresses the second challenge by applying the interval representation across data stores, leveraging the filtering capabilities common to most data systems. Branch metadata is managed and accessed centrally in a relational data store, giving all stores a consistent representation of the branch hierarchy. Before accessing a branch, Chronos obtains the branch’s interval metadata from the relational store. This interval metadata is then used to augment queries to data stores with interval predicates in a store-specific shim layer. The underlying stores therefore remain responsible for query execution, indexing, durability, and physical storage, allowing Chronos to support heterogeneous systems without modifying their engines. Chronos addresses the third challenge with a merge-publication protocol that provides atomic cross-store visibility. A merge first stages its record versions without making them visible. Only after every participating store has durably staged its changes does Chronos publish the merge by atomically updating the branch metadata in its transactional relational store. Readers therefore observe either the state before the merge or the complete merged state, never a partially published merge. We implement and evaluate Chronos on PostgreSQL, SQLite, DuckDB, Qdrant, and ChronosFS, a DBMS-backed filesystem. Across PostgreSQL TPC-C and YCSB-C, DuckDB TPC-H, and Qdrant vector search, Chronos outperforms the next-best versioning alternative by 3.4–17.9×, while incurring a 1.12–1.75× slowdown relative to unversioned systems. Chronos completes all five BranchBench [3] workflows. On the branch-intensive Monte-Carlo-Tree-Search workflow, it is 6.0× faster than Doltgres and 16.7× faster than PostgreSQL cloning on Btrfs. Chronos is currently deployed at CMS Computing Operations [42] at CERN as a storage layer for managing agent knowledge, data sandboxing and ingestion staging. In summary, we make the following contributions: • A polystore branching abstraction for managing speculative execution state. We design a unified branch API that lets developers and agentic applications fork, query, diff, merge, and delete isolated states across multiple data stores. • Interval-based branch management. We present an efficient interval-based data versioning approach for branch creation, record-level copy-on-write, queries, diff, and merge without reconstructing versions through membership joins. 2

Chronos : Efficient Bolt-On Branching Across Data Stores for Stateful Agentic Applications

Table 1: Core Chronos branching API

Agentic Applications Fork/Checkout/Delete/Merge Branch

SQL/POSIX @ Branch

API Query Interface

Unified Branch API

Semantics

Figure 2: Chronos architecture. A transactional metadata store coordinates branch state, while store shims connect the branch abstraction to existing data stores.

Create a child branch from an existing branch with a hint about the branch subtree structure (Section 4.1). checkout(branch) Create a session for accessing a branch. diff(b1,b2) Compute changes of a branch with respect to a target branch (Section 4.4). merge(src,dst) Merge changes with atomic cross-store visibility (Section 4.4). delete(branch) Remove a branch subtree and reclaim its physical versions (Section 4.5).

• An extensive evaluation. We evaluate Chronos using crossstore agent workflows, BranchBench [3] workloads, and microbenchmarks.

Data Record Format

fork(source, hint)

Lightweight Versioning & Query Rewrite Layer RDBMS Branch Metadata

2

User Data

RDBMS-backed File System

Vector/Document Database

Object Store

User Data

User Data

User Data

User Data

CHRONOS ARCHITECTURE

In this section, we describe the Chronos architecture, its assumptions, and how applications interact with it. Figure 2 sketches the architecture. Chronos sits between an agentic application and the data stores that hold branchable state. It uses a transactional relational database for keeping track of branch metadata and a storage shim for each participating data store in the Chronos system. The shims are responsible for rewriting queries, maintaining record versions, and acting as a proxy for the application. Each store handles its own query execution, indexing, durability, and physical storage and is generally unaware of the branching layer.

2.1

high

deleted

writer

Versioning Metadata Figure 3: Chronos record format. Each physical version stores application data together with interval visibility metadata, a writer identifier, and deletion state. session remain isolated within its branch. A promising Fix B can be forked again to create the Follow-up branch. After evaluating the candidates, Engineer A uses diff to compare their changes with her branch. She then uses merge to propagate the accepted Follow-up changes, making the corresponding file, relational, and search updates visible together. She uses delete to discard Fix A and reclaim its unreachable versions. The next section explains how interval metadata implements them.

Chronos Assumptions

Chronos relies on the following assumptions about branch access and data stores. • At Least One Transactional Store. Chronos requires at least one store to support transactions for branch coordination and metadata management. • Unique Record Keys. Each record in the branchable state has a stable logical key shared by all of its physical versions. • Efficient Metadata Filtering. Data stores can keep record metadata and filter it efficiently. • Atomic Record Updates. A data store can atomically install the versions produced by one logical write and serialize conflicting updates to the same physical versions. Once acknowledged, these versions are durable and readable by later Chronos sessions. • Controlled Access. Chronos assume every query sent to each table managed by Chronos is sent through the shim.

2.2

low

3

INTERVAL-BASED DATA ISOLATION AND RECORD UPDATES

In this section, we describe the interval-based versioning model that underlies Chronos. The model compactly represents both the branch hierarchy and versioned application state, enabling efficient branch operations and query execution. Chronos uses integer intervals as lightweight metadata to encode which record versions are visible to each branch. It rewrites queries with simple predicates over this metadata, allowing each branch to access its visible state without traversing branch history. The same representation supports record-level copy-on-write, allowing branches to share unchanged data while isolating their modifications. In this section, we describe the high-level versioning scheme and its invariants, and then, in the next section, provide details about how intervals are allocated and how specific operations on branches are implemented. For clarity, we assume the data store is a relational database in this section. The same technique applies to other data models as long as records can carry interval metadata and the store can efficiently filter on that metadata.

Application Interaction

Applications interact with Chronos through the branch APIs and sessions summarized in Table 1. A branch identifies one application state across the participating stores. In the running example shown in Figure 1, Engineer A’s branch therefore includes source files, provenance records, and the corresponding search index. To evaluate competing fixes, she uses fork to create Fix A and Fix B, which initially inherit the same data. She then uses checkout to create a session for each branch and runs ordinary SQL, search, and filesystem operations through these sessions. Changes made through a 3

Xinjing Zhou, Jason Mohoney, Samuel Madden, Michael Stonebraker, and Lei Cao

3.1

Version Representation and Reads

3.2

Chronos represents the branch hierarchy using an integer range. Each branch owns a half-open interval [𝑙, ℎ), and each child receives a subinterval of its parent’s interval. Interval containment therefore encodes branch ancestry without storing it with each record. Each branch also maintains an allocation frontier 𝑓 , initially 𝑙 + 1. The frontier advances monotonically as the branch creates children, partitioning its interval into ranges allocated to earlier branches and an active range [𝑓 , ℎ) for future writes and forks. Chronos uses the same interval representation to encode record visibility. Figure 3 shows the physical record layout. Each physical version of a logical record is tagged with a visibility interval [low, high) in addition to its application data. The deleted bit represents a tombstone. The writer field identifies the active range in which a version was created. Each active range has a unique 4-byte writer identifier stored in every version created there. For reads, the branch frontier 𝑓 acts as a read point. A physical version is visible when its interval contains 𝑓 and not a tombstone: low ≤ 𝑓 < high

∧

deleted = false

Thus, Chronos can select the visible version using an ordinary range predicate rather than traversing branch ancestry. Figure 4 illustrates this mechanism. Initially, record R’s visibility interval spans branch A’s active range, so A can read R. Creating branches A1 and A2 assigns them disjoint subintervals without modifying R. Because R’s visibility interval also contains the read points of A1 and A2, all three branches share the same physical version. Forking therefore copies no record data; a new physical version is created only when a branch modifies R. Non-overlapping interval invariant. For each logical record, Chronos ensures the visibility intervals of any two distinct physical versions 𝑣𝑖 and 𝑣 𝑗 do not overlap: [low𝑖 , high𝑖 ) ∩ [low 𝑗 , high 𝑗 ) = ∅.

Writes and Interval Splitting

To ensure isolation among branches, all writes maintain the nonoverlap invariant defined in Equation (1) over the branch’s active range 𝑤 = [𝑓 , ℎ). Chronos uses record-level copy-on-writes that never overwrite a physical version’s data visible to another branch. An insert with no overlapping version creates a new physical version tagged with 𝑤 and 𝑤’s writer identifier. The branch and its future descendants share this version. Updates and deletes are more interesting when the target version is inherited from another branch. Overwriting the inherited version would change the value observed by other branches. Instead, Chronos splits its visibility interval at 𝑤’s boundaries. Portions outside 𝑤 retain the inherited value and writer identifier; the portion within 𝑤 is replaced by the new value or a tombstone tagged with 𝑤’s writer identifier. The resulting intervals remain disjoint. Figures 4c and 4d illustrate this operation. In the running example, updating record R in branch A2 replaces only the interval assigned to A2, leaving the old value visible to branch A and A1. Deleting record R in branch A1 similarly installs a tombstone only over A1’s interval, without affecting the versions visible to branch A or A2. Unmodified ranges therefore remain shared across branches. Algorithm 1 sketches the interval split procedure for one logical key. It first finds physical versions whose visibility intervals overlap 𝑤, preserves any portions outside 𝑤, and installs a replacement over 𝑤. If no version overlaps 𝑤, an insert creates the first version; an update or delete is a no-op. The retained fragments and replacement occupy disjoint intervals, preserving Equation (1). Algorithm 1: Copy-on-write Record Interval Split Input: operation 𝑜𝑝 ∈ {insert, update, delete}, logical key 𝑘𝑒𝑦, active range 𝑤 = [ 𝑓 , ℎ), branch writer id 𝑤𝑟𝑖𝑡𝑒𝑟 , and 𝑝𝑎𝑦𝑙𝑜𝑎𝑑 for insert/update 1 Function write(op, key, w, writer, payload) 2 if 𝑜𝑝 = delete then 3 𝑟𝑒𝑝 ← tombstone 4 else 5 𝑟𝑒𝑝 ← 𝑝𝑎𝑦𝑙𝑜𝑎𝑑

(1)

The invariant ensures that the visibility predicate selects at most one physical version of each logical record. Logical query rewrite. Let 𝑅 be a logical relation with application attributes 𝐴𝑅 , and let 𝑅b be its physical relation containing the application attributes and the interval metadata. At frontier 𝑓 of a branch, the logical contents of 𝑅 are   b . 𝑅 𝑓 = 𝜋𝐴𝑅 𝜎low≤ 𝑓 <high ∧ ¬deleted (𝑅) (2)

6 7 8 9 10

The selection filters out physical versions not visible to the branch, and the projection removes the interval metadata. By Equation (1), 𝑅 𝑓 contains at most one physical version of each logical record and is therefore an ordinary relation representing 𝑅 at frontier 𝑓 . To evaluate a query at frontier 𝑓 of the branch, Chronos applies a rewrite using to every scan in the logical plan over an intervalversioned relation. The scan reads the physical relation 𝑅b under the visibility predicate and exposes its application attributes as 𝑅 𝑓 . This rewrite is compositional because it substitutes the branch-visible relation independently at each table scan. Hence, joins, aggregations, and other operators can evaluate over the resulting 𝑅 𝑓 relations, preserving the original logical plan above the scans. Each rewritten scan adds one fixed predicate whose complexity is independent of branch depth and history.

11 12 13 14 15 16 17 18

𝑉 ← physical versions of 𝑘𝑒𝑦 that overlap 𝑤 if 𝑉 = ∅ then if 𝑜𝑝 = insert then insert a new version with 𝑟𝑒𝑝, interval 𝑤, and 𝑤𝑟𝑖𝑡𝑒𝑟 return foreach 𝑣 ∈ 𝑉 do 𝑅←∅ if 𝑣.𝑙𝑜𝑤 < 𝑤.𝑙𝑜𝑤 then 𝑅 ← 𝑅 ∪ {𝑣 tagged with interval [𝑣.𝑙𝑜𝑤, 𝑤.𝑙𝑜𝑤 ) } if 𝑤.ℎ𝑖𝑔ℎ < 𝑣.ℎ𝑖𝑔ℎ then 𝑅 ← 𝑅 ∪ {𝑣 tagged with interval [𝑤.ℎ𝑖𝑔ℎ, 𝑣.ℎ𝑖𝑔ℎ) } replace 𝑣 with the versions in 𝑅 insert a new version with 𝑟𝑒𝑝, interval 𝑤, and 𝑤𝑟𝑖𝑡𝑒𝑟

Concurrent interval splits. Sibling branches may update the same inherited physical version even though their active ranges are disjoint. Their writes can therefore attempt to split the same physical version concurrently. Chronos serializes such splits using 4

Chronos : Efficient Bolt-On Branching Across Data Stores for Stateful Agentic Applications

Allocation Frontier f A.high

A.low 0

∞

Branch A

A.low 0

200

0

A1.high/A2.low 100

Branch A1

Record R written in Branch A inherits the interval from the branch A’s active range [A.AllocationFrontier, A.high) 0

∞

Insert Record R R.low

∞

0

0

A1.high/A2.low 100

Branch A1

Branch A2

Creation of Branch A1 and A2 cuts A’s interval monotonically 0

∞

0

200

200

Branch A2

Update to R in Branch A2 splits the physical record into three non-overlapping copies 100

(b) Create branches

A1.high/A2.low 100

Branch A1

200

∞

0

R.high

200

100

200

4.1

R.high

(d) Delete record

Branch Creation

Algorithm 2 sketches the metadata changes for branch creation. Branch creation reserves a subinterval from the parent’s active range and advances the parent’s frontier in one metadata transaction. Given a parent branch with active range [𝑓 , ℎ), the allocator chooses a split point 𝑚. Chronos reserves [𝑓 , 𝑓 + 1) for the fork base, a special read-only branch that represents the parent’s state at the time of the fork which will be used for merging in Section 4.4. It assigns [𝑓 + 1, 𝑚) to the child with frontier 𝑓 + 1 and advances the parent’s frontier to 𝑚. The child and parent thus receive disjoint active ranges for subsequent writes, while both continue to see the versions visible at the original frontier 𝑓 . Therefore, branch creation updates only metadata and copies no record versions. Algorithm 2: Branch Creation Function create_branch(parent, name, hint) BEGIN metadata transaction 3 𝑓 ← frontier(𝑝𝑎𝑟𝑒𝑛𝑡 ), ℎ ← high(𝑝𝑎𝑟𝑒𝑛𝑡 ) 4 𝑚 ← choose_split(𝑝𝑎𝑟𝑒𝑛𝑡 .𝑙𝑜𝑤, 𝑓 , ℎ, ℎ𝑖𝑛𝑡 ) // Reserve [ 𝑓 , 𝑓 + 1) as the read-only fork base 5 create_fork_base(𝑝𝑎𝑟𝑒𝑛𝑡, 𝑛𝑎𝑚𝑒, 𝑓 ) // assign [ 𝑓 + 1, 𝑚) to the child branch 6 create_child(𝑛𝑎𝑚𝑒, [ 𝑓 + 1, 𝑚), 𝑓 + 1) 7 advance_frontier(𝑝𝑎𝑟𝑒𝑛𝑡, 𝑚) 8 COMMIT 9 return 𝑛𝑎𝑚𝑒

1

2

4.2

BRANCH OPERATIONS

Epoch-Based Coordination

Branch creation must preserve data isolation for sessions that execute concurrently with interval reassignment in a branch. Although Algorithm 2 changes the interval metadata atomically, a session may cache the parent’s interval before the fork and issue a later write after part of that interval has been assigned to the child. Such a stale write could enter the child’s range and violate isolation. More generally, the same anomaly can accompany any change to a branch frontier or writable interval. Refreshing the cached state before every query would eliminate the race, but would place synchronization overhead on every query.

The previous section showed how interval metadata isolates branchlocal versions while allowing unchanged data to remain shared. This section describes how Chronos creates and maintains the branch metadata that drives this representation, including branch creation, interval allocation, merge, and deletion. At a high level, Chronos stores this metadata in a transactional relational store so that branch operations update the hierarchy and interval assignments atomically, which significantly simplifies branch management and coordination.

5

∞

deleted=1

Figure 4: Overview of Chronos interval operations. Initially, record R spans branch A’s interval. Two forks reserve disjoint subintervals for branches A1 and A2 without copying record R. An update in branch A2 replaces only branch A2’s range, while a deletion in branch A1 installs a tombstone tagged with branch A1’s interval.

4

∞

A2.high

R.low

(c) Update record

the store’s isolation mechanism to atomically install the retained fragments and replacement versions. For stores that support transactions for isolation (i.e., most databases[46, 47, 54, 55, 57, 75]), a transaction can be used to group splits across multiple keys, so readers observe either the state before the logical write or its complete result. Stores with weaker transactional support can use other mechanisms, such as atomic batches, when the affected versions are co-located [27, 45, 61, 63]. Discussion. Chronos’s interval-based design optimizes for reads and simplicity. A branch read adds only a range predicate, regardless of how deep the branch is. Therefore the cost moves to writes: updating or deleting an inherited version may create mutliple physical versions, increasing storage and index maintenance overhead. Writes from additional active ranges can thus increase write amplification and the number of physical versions examined by scans. Chronos trades this write and storage overhead for a simple, branch-independent read path and metadata-only forks. This overhead is most pronounced when forks lead several branches to modify the same key. A fork creates separate writable intervals for the child and the parent. The first write in one of these intervals can split an inherited version into at most three versions: an unchanged part before the interval, the replacement within it, and an unchanged part after it. Each written interval therefore adds at most two live versions. If 𝑛 writable intervals created by forks modify the same key, the key has at most 2𝑛 + 1 live versions. Later updates or deletes in the same interval reuse the existing split and do not increase this count. A write that overlaps 𝑠 existing versions replaces them with at most three versions and requires 𝑂 (𝑠) row changes.

A.high

Branch A2

Deletion of R in Branch A1 sets the deleted bit

Record R

R.low

R.high

0

A1.low

A2.high

Record R

R.low

(a) Initial state

∞

A.low Branch A

A1.low

200

0

200

A.high

Branch A

A2.high

Record R

R.high

A.low

A.high

Branch A A1.low

Allocation Frontier f

Allocation Frontier f

Allocation Frontier f

Xinjing Zhou, Jason Mohoney, Samuel Madden, Michael Stonebraker, and Lei Cao

while retaining one range for the parent. We choose 𝑟 0 ≥ 𝑟 1 ≥ 𝑟 2 , decreasing the reservation with depth. Outside these reserved slots, Chronos uses an adaptive harmonic allocation when the fanout is unknown. Let 𝑅𝑛 be the active capacity after 𝑛 such children and let 𝑞 be a configurable fanout reserve. The next child receives 𝑅𝑛 /(𝑞 + 𝑛 + 1), leaving 𝑅𝑛+1 = 𝑅𝑛 (𝑞 + 𝑛)/(𝑞 + 𝑛 + 1) for the parent. Equivalently, relative to the capacity 𝑅0 when adaptive allocation begins, 𝑞 𝑞 𝑅𝑛 = 𝑅0 , 𝑠𝑛 = 𝑅 0 , 𝑞 +𝑛 (𝑞 + 𝑛 − 1)(𝑞 + 𝑛) where 𝑠𝑛 is the range assigned to the 𝑛-th child. The reserve prevents the first unknown child from consuming half of the range. The parent’s active capacity decreases harmonically with the observed fanout. We empirically find that 𝑞 = 8 is a good value for most use cases, while allowing applications to configure it for different expected fanouts. Finally, a terminal branch receives only the minimum writable range.

To minimize query-processing overhead, Chronos instead uses epoch-based coordination inspired by epoch-based reclamation [21]. Chronos associates an epoch with each branch’s interval metadata. A session may cache the interval metadata, but it also tracks the branch epoch associated with the cached state. Whenever the interval metadata needs to change, Chronos advances the branch epoch and waits for sessions in the old epoch to finish their ongoing operations. These sessions periodically refresh their cached interval metadata before entering the new epoch. The epoch change therefore forms a barrier between operations using the old and new interval assignments. Crucially, enforcing this barrier does not require per-query metadata refresh. Chronos periodically tracks which branch epoch each session has observed, independently of query execution. A session can therefore reuse its cached interval metadata while remaining in the same epoch. An interval-changing operation waits only for sessions using the old branch state; otherwise, it proceeds immediately.

4.3

Interval Allocation Algorithm 3: Hybrid Integer-Interval Allocation

Branch creation leaves one policy question: how should the allocator choose the split point 𝑚? Giving a child a larger range preserves more capacity for its descendants but leaves less capacity for additional siblings. The allocator must therefore balance branch depth and fanout within a fixed-width integer domain. Consider a rootto-leaf path on which the branch at depth 𝑑 may create 𝐹𝑑 children. Preserving an active range for the parent and one for each child requires approximately ⌈log2 (𝐹𝑑 + 1)⌉ coordinate bits at that level. A path of depth 𝐷 therefore requires 𝑏≳

𝐷 −1 ∑︁

  log2 (𝐹𝑑 + 1) ,

Function choose_split(low, f, high, hint) 𝑖𝑛𝑖𝑡𝑖𝑎𝑙 ← ℎ𝑖𝑔ℎ − 𝑙𝑜𝑤 − 1 3 𝑎𝑐𝑡𝑖𝑣𝑒 ← ℎ𝑖𝑔ℎ − 𝑓 − 1 4 𝑑 ← ℎ𝑖𝑛𝑡 .𝑑𝑒𝑝𝑡ℎ 5 if ℎ𝑖𝑛𝑡 .𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑙 then 6 𝑐ℎ𝑖𝑙𝑑_𝑤𝑖𝑑𝑡ℎ ← 1 7 else if ℎ𝑖𝑛𝑡 .𝑓 𝑎𝑛𝑜𝑢𝑡 > 0 then // Known fanout: use equal ranges 8 𝑐ℎ𝑖𝑙𝑑_𝑤𝑖𝑑𝑡ℎ ← ⌊𝑖𝑛𝑖𝑡𝑖𝑎𝑙/(ℎ𝑖𝑛𝑡 .𝑓 𝑎𝑛𝑜𝑢𝑡 + 1) ⌋ 9 else if 𝑑 < 3 then // Unknown fanout near root: use reservation 𝑟𝑑 10 𝑐ℎ𝑖𝑙𝑑_𝑤𝑖𝑑𝑡ℎ ← ⌊𝑖𝑛𝑖𝑡𝑖𝑎𝑙/2𝑟𝑑 ⌋ 11 else // Unknown fanout: adaptive harmonic allocation 12 𝑛 ← ℎ𝑖𝑛𝑡 .𝑐ℎ𝑖𝑙𝑑𝑟𝑒𝑛_𝑐𝑟𝑒𝑎𝑡𝑒𝑑 13 𝑐ℎ𝑖𝑙𝑑_𝑤𝑖𝑑𝑡ℎ ← ⌊𝑎𝑐𝑡𝑖𝑣𝑒/(𝑞 + 𝑛 + 1) ⌋ 1

2

(3)

𝑑=0

where 𝑏 is the coordinate width. This bound exposes the fundamental width–depth tradeoff of any nested-interval representation. An allocator can distribute the available bits according to the expected tree shape, but it cannot guarantee unbounded fanout and depth without widening the coordinates or reassigning existing intervals. However, branching is rarely uniform across depth in real-world workloads. For example, a study [94] shows that among 2,923 opensource projects hosted on GitHub, only 91 (3.1%) created more than 30 branches. With the rise of agentic applications, we expect the need for branching will increase mostly from search-oriented workloads [3]. These workloads may create many more branches, but their broadest expansion commonly occurs near the root, after which only promising alternatives are extended. Many branches are also created for one-off use cases such as debugging or simulation. Those branches do not branch further, which we call terminal branches. Based on these insights, Chronos proposes a hybrid policy in Algorithm 3 that adapts to both known and unknown fanout scenarios using application hints. When the application knows that a branch will create 𝑘 children, the allocator divides its initial capacity into 𝑘 + 1 equal-width ranges, one for each child and one retained by the parent. When fanout is unknown, Chronos reserves equal-width child slots near the top of the tree, where fanout is most likely to consume a large fraction of the available coordinate space. At depth 𝑑 < 3, reserving 𝑟𝑑 bits provides up to 2𝑟𝑑 − 1 child slots

14

return 𝑓 + 1 + 𝑐ℎ𝑖𝑙𝑑_𝑤𝑖𝑑𝑡ℎ

4.4

Atomic Visibility for Cross-Store Merge

After evaluating a branch, an application may incorporate some or all of its changes into a target branch. A cross-store merge should move the target branch from one complete logical state to another: a reader must not observe merged relational data without the corresponding filesystem and vector database updates. Chronos provides this atomic-visibility guarantee without requiring the participating stores to commit their physical updates through a distributed transaction. Algorithm 4 sketches the protocol, while Figure 5 gives a visualization of the protocol which involves reserving a staging interval, writing the resolved changes, and publishing them with one metadata transaction. Comparison and conflict resolution. Algorithm 4 begins by comparing the source and target branches against their nearest shared fork-base branch, introduced in Section 4.1. For each key changed since that fork base, let 𝐵, 𝑆, and 𝑇 denote its state at the fork base, source branch, and target branch, respectively. Table 2 6

Chronos : Efficient Bolt-On Branching Across Data Stores for Stateful Agentic Applications

Table 2: Three-way Merge Cases for One Logical Key

(a) Reserve the staging range 𝑓new = 𝑓old + 2 < ℎ

Fork base Source branch Target branch Merge action 𝐵 𝐵 𝐵 𝐵 𝐵

𝐵 𝑆 ≠𝐵 𝐵 𝑆 ≠𝐵 𝑆 ≠𝐵

𝐵 𝐵 𝑇 ≠𝐵 𝑇 =𝑆 𝑇 ≠ 𝐵,𝑇 ≠ 𝑆

𝑓old

𝑙𝑜𝑤

Target Branch Interval

No action Apply 𝑆 to the target branch Keep 𝑇 Keep the common state Require conflict resolution

𝑓old + 1

𝑓new

staging range

ℎ new active range

frontier

𝐼𝑚 = [ 𝑓old + 1, ℎ) remains hidden at 𝑓old

(b) Stage merge writes in participating stores resolved changes Δ Relational store Δ over 𝐼𝑚

summarizes the comparison. Conflicts are resolved by an agent, user, or application policy before publication, producing the resolved change set Δ that enters the staging phase in Figure 5(b). Coordination and reservation. After computing Δ, Algorithm 4 establishes the epoch barrier from Section 4.2 for the source and target branches. Chronos then leverages a metadata transaction to check that neither branch has changed since the comparison and that the target branch is not reserved by another merge. A failed check restarts the comparison; otherwise, the transaction reserves the target branch until publication. For the example in Figure 5(a), the target branch has active range [𝑓old, ℎ). The transaction chooses 𝑓new = 𝑓old + 2 < ℎ and reserves 𝐼𝑚 = [𝑓old + 1, ℎ) for the merge. Because 𝑓old ∉ 𝐼𝑚 , the target branch cannot yet see versions staged over this range. Staging and publication. Once the target branch is reserved, Chronos writes the resolved changes durably to all participating stores, using 𝐼𝑚 as their visibility interval (Algorithm 4 and Figure 5(b)). Staging applies Δ using the record-level copy-on-write mechanism as ordinary branch updates described in Section 3.2 where it creates new physical versions, or tombstones for deletions, tagged with 𝐼𝑚 , while leaving the versions visible at 𝑓old unchanged. If any store fails, Chronos keeps the target branch at 𝑓old and cancels publication, leaving all staged versions invisible. After every store confirms durability, the final metadata transaction advances the target branch to 𝑓new ∈ 𝐼𝑚 and clears the reservation. This is the single visibility transition shown in Figure 5(c): all staged versions become visible together, and subsequent writes use the new active range [𝑓new, ℎ). Recovery and fault tolerance. Chronos builds on the durability guarantees of the metadata store and participating data stores. We consider crash failures and assume that a failed store eventually restarts with all writes that it previously acknowledged as durable. Participating-store failures. If a participating store fails before acknowledging its staged writes, Chronos does not publish the merge. The target branch remains at 𝑓old , and versions staged by other stores remain hidden. The durable reservation prevents 𝐼𝑚 from being reused while the store is unavailable. After recovery, Chronos can either finish staging and publish after every store acknowledges durability, or remove the staged versions before clearing the reservation. If a store fails after publication, no rollback is required: the store had already made its staged versions durable and restores them when it restarts. Operations involving the failed store may be unavailable during recovery, but the failure does not expose a partial merge. Metadata-store failures. The metadata store is the authority on whether a merge was published. A failure before the reservation commits leaves the target branch unchanged. Once the reservation

NoSQL database Δ over 𝐼𝑚

Filesystem

Δ over 𝐼𝑚

Durably staged in every store; the target branch remains at 𝑓old

(c) Publish with one metadata transaction 𝑙𝑜𝑤

Target Branch Interval

𝑓old

𝑓old + 1

𝑓new

staging range

ℎ new active range

frontier

𝐼𝑚 = [ 𝑓old + 1, ℎ) : merge versions become visible at 𝑓new

Figure 5: Cross-store merge publication. (a) Chronos reserves 𝐼𝑚 outside old frontier 𝑓old . (b) Participating stores durably stage their resolved writes over 𝐼𝑚 while the target branch remains unchanged. (c) One metadata transaction advances the target branch frontier to 𝑓new ∈ 𝐼𝑚 and clears its reservation, publishing all writes together. Algorithm 4: Cross-store Merge Function merge(source, target) 𝑓 𝑜𝑟𝑘_𝑏𝑎𝑠𝑒 ← nearest common ancestry of source and target 3 𝑝𝑟𝑒𝑣𝑖𝑒𝑤 ← three-way comparison on ( 𝑓 𝑜𝑟𝑘_𝑏𝑎𝑠𝑒, 𝑠𝑜𝑢𝑟𝑐𝑒, 𝑡𝑎𝑟𝑔𝑒𝑡 ) 4 𝑟𝑒𝑠𝑜𝑙 𝑣𝑒𝑑 ← resolve conflicts in 𝑝𝑟𝑒𝑣𝑖𝑒𝑤 via LLM or developers 5 establish an epoch barrier for 𝑠𝑜𝑢𝑟𝑐𝑒 and 𝑡𝑎𝑟𝑔𝑒𝑡 6 BEGIN metadata transaction 7 validate that 𝑝𝑟𝑒𝑣𝑖𝑒𝑤 is unchanged and 𝑡𝑎𝑟𝑔𝑒𝑡 is unreserved, or abort and retry 8 𝑓old ← 𝑓 𝑟𝑜𝑛𝑡𝑖𝑒𝑟 (𝑡𝑎𝑟𝑔𝑒𝑡 ), ℎ ← ℎ𝑖𝑔ℎ (𝑡𝑎𝑟𝑔𝑒𝑡 ) 9 𝑓new ← 𝑓old + 2 10 𝐼𝑚 ← [ 𝑓old + 1, ℎ) // staged merge versions 11 reserve 𝑡𝑎𝑟𝑔𝑒𝑡 and (𝐼𝑚 , 𝑓new ) from allocator 12 COMMIT 13 foreach 𝑠𝑡𝑜𝑟𝑒 ∈ participating stores do 14 durably stage 𝑟𝑒𝑠𝑜𝑙 𝑣𝑒𝑑 [𝑠𝑡𝑜𝑟𝑒 ] over 𝐼𝑚 1

2

15 16 17 18 19

on failure: clean up reservation and release epoch BEGIN metadata transaction set the target branch frontier to 𝑓new and clear its reservation COMMIT release the barrier; sessions enter the new epoch

commits, transactional recovery yields one of two states: either the target remains at 𝑓old with its reservation, in which case Chronos resumes or aborts the merge; or the target has advanced to 𝑓new and the reservation has been cleared, in which case the merge is complete. The second outcome is safe because publication follows durable staging at every participating store. While the metadata store is unavailable, Chronos pauses interval-changing operations 7

Xinjing Zhou, Jason Mohoney, Samuel Madden, Michael Stonebraker, and Lei Cao

rather than risk an ambiguous allocation. Thus, failures may reduce availability but do not expose a partially merged state under the assumptions in Section 2.1. Correctness. The non-overlap invariant from Equation (1) ensures that each store exposes at most one physical version of a logical record at either frontier. Before publication, 𝑓old ∉ 𝐼𝑚 , so the target branch excludes every staged version. Publication occurs only after all stores have durably prepared the versions covering 𝑓new . The epoch barrier and the transactional frontier change then place every operation entirely before or after publication. An operation therefore observes either the complete preceding state at 𝑓old or the complete merged state at 𝑓new , never a mixture of the two.

4.5

Schema changes. Chronos versions the mapping from logical schemas to physical tables. A branch can modify a table private to its current schema version directly. When the physical table is shared by multiple branches and there is a schema change request in the branch, Chronos creates a new physical schema and copies the rows visible to that branch before applying the change.

5.2

Branch Deletion

Branches that are no longer useful should purge both their metadata and the physical versions that only they can reach. Branch deletion in Chronos removes the selected branch metadata and reclaims those versions together. Since each version is tagged with its writer identifier, Chronos can quickly locate versions associated with the deleted branch’s active ranges without scanning the entire store.

5

IMPLEMENTATION ACROSS DATA STORES

We implement Chronos over PostgreSQL [56], SQLite [74], DuckDB [18], a DBMS-backed filesystem, and Qdrant [60] without modifying their engines. Each integration maps the interval operations from Sections 3 and 4 onto the store’s native keys, filters, and atomic-update mechanisms. We focus on the store-specific mechanisms needed for visibility filtering and interval splitting, then briefly discuss how Chronos could extend to object storage.

5.1

ChronosFS

Files require a different data path because applications access them through POSIX interfaces. We built ChronosFS, a file system backed by relational database [71] that stores the file blocks and directory hierarchy in relational tables and exposes it through Filesystem in Userspace (FUSE) [39] to offer POSIX compatibility. Relational representation. ChronosFS represents inode metadata, directory entries, and files using three logical relational tables keyed by inode identifier, parent-and-name pair, and file-and-offset pair, respectively. These tables are then versioned similarly to the relational store implementation described in Section 5.1. ChronosFS versions file contents at 4 KiB block granularity, so writes create new versions only for affected blocks while unchanged blocks remain shared across branches. Diff and merge use the same internal representation but translate affected keys back into file paths and offset ranges, with text conflicts reported as unified diffs. POSIX compatibility and host filesystem sandboxing. To provide POSIX compatibility, ChronosFS implements a FUSE daemon that translates file access into operations on the underlying relational database. Applications can therefore use ordinary POSIX interfaces while benefiting from the kernel page cache. On a cache miss, the daemon resolves paths through the inode and directoryentry tables and reads file contents from the block table. File-system operations that update multiple records, such as rename, are implemented within a database transaction to provide atomicity. Many agent workloads also begin with an existing directory (e.g., source code) from the host filesystem that must be made branchable. Copying the entire directory into ChronosFS would incur significant initialization overhead even though most files remain unchanged. To avoid this cost, ChronosFS lazily copies data from host filesystem. Specifically, Chronos initially only imports the directory-tree structures without copying file contents. Each regular file initially references its host path, and modified 4 KiB blocks are materialized as versioned records while unchanged ranges continue to reference the host file. The source directory must therefore remain read-only while any sandbox depends on it. Under this assumption, ChronosFS can branch a large host file system without duplicating its contents, while sandbox modifications remain isolated from the host directory.

Metadata Plane and Relational Stores

Chronos stores the branch hierarchy, interval allocations, and recovery state in transactional tables backed by PostgreSQL or SQLite. Checkout reads this metadata to construct sessions for all participating stores. A session then reuses the branch state throughout the branch’s current epoch. After an epoch barrier, it refreshes the frontier and active interval for all stores before admitting another operation. In this way, ordinary data operations do not consult the metadata plane on every access. The metadata store realizes branch epochs with a branch fence shared by sessions that may admit operations. A branch metadata update operation proceeds immediately if it can acquire the fence; otherwise, it asks those sessions to stop admission, waits for their current operations to drain, and then continues. Session liveness is renewed periodically. Relational tables. An application registers each logical table and its primary key, and Chronos creates a corresponding physical table containing the application’s columns and the four versioning fields from Section 3.1. The application’s primary key along with the lower interval bound constitutes the primary key in the physical table. Chronos then builds a secondary index over the logical key and upper bound to speed up visibility and overlap lookups. The shim for each relational store implements the query rewrites described in Sections 3 and 4 using the store’s native SQL and transaction mechanisms. PostgreSQL, SQLite, and DuckDB therefore retain their native optimizers and execution paths while providing the same interval-based branch semantics.

5.3

NoSQL Databases

NoSQL databases, including document databases and vector databases, typically support metadata filtering. Chronos attaches interval fields to each indexed document and applies the visibility predicate before ranking. Our prototype currently supports Qdrant [60], where each document or chunk is stored as a point containing its embedding, content, and filterable payload. Chronos treats the Qdrant collection and point identifier as the logical key, stores interval metadata in the payload, and builds payload indexes 8

Chronos : Efficient Bolt-On Branching Across Data Stores for Stateful Agentic Applications

500 0

Workflow

Workflow

1

2

4

8

16

32

64 128

Concurrent Workflows

(a) Workflow success rate

Doltgres+Btrfs+Qdrant-Serialized

Chronos

104 103 102

1

2

4

8

16

32

64 128

Concurrent Workflows

(b) Runtime (s)

Figure 7: Concurrent incident investigations: at 32 workers, Chronos exposes no partial merge and completes in 378 s, 18.2× faster than serialization; uncoordinated execution exposes incomplete cross-store states.

Figure 6: Enterprise agent workflows: Chronos is 5.60× faster on tool replay, and 1.40× faster end to end.

from EnterpriseRAG-Bench [77], a synthetic corpus of documents and communications from an AI inference company. We augment it with vLLM, LiteLLM, and Langfuse source code repositories as well as their public GitHub issues, pull requests, comments, reviews, and releases. The resulting corpus contains 628,082 documents and 10,704,652 indexed chunks, including 97,336 GitHub documents collected as of July 27, 2026. We organize the corpus into 23 long-lived branches for company-wide data, three departments, two teams per department, and individual employees. We curate 11 workflows that make concrete changes to this corpus. Eight ask an agent to resolve coding issues in vLLM, LiteLLM, or Langfuse: the agent searches issue and company evidence, creates an isolated branch, edits source code and tests, re-indexes the changed files, and records the reviewed decision as durable memory. Another workflow answers company questions with cited evidence and stores both the answers and a reusable evidence procedure. The final two create onboarding plans, a new team charter, and employee branches from the relevant organizational branches. Across these tasks, agents create task, team, or employee branches; update files, search indexes, and memory records; review their changes; and then merge, delete, or retain the branches as required. Since no existing system support branching across multiple data stores, we compose Doltgres for relational data, Branch-aware Qdrant for embeddings, and Btrfs snapshots for files. In this Doltgres+Btrfs+Qdrant baseline, the application merges data between branches independently across the three independent stores. To isolate the effect of the branching system from model nondeterminism, we first execute each workflow with Codex CLI v0.145.0 using GPT-5.6-luna at maximum reasoning effort. Codex accesses the enterprise data platform through an MCP server, and we record its model output and tool calls as a trace. We then replay the trace on each system from an identical corpus and branch hierarchy. Workflow performance. Figure 6a shows that Chronos has significantly lower replay time for all 11 workflows, with a 5.60× geometric-mean speedup over Doltgres+Btrfs+Qdrant. Figure 6b shows that the baseline spends 8.3× and 7.4× as much time in its relational and vector stores, respectively, because each store maintains and resolves its own branch representation, whereas Chronos uses interval predicates across both. Filesystem cost is more workload dependent. The largest difference occurs in Speculation, where Chronos is 49.1× faster. This workflow compares two nested candidate branches before selecting one to merge; deriving the two file-level differences from Btrfs snapshots of the full corpus

for speeding up visibility and overlap lookups. When a logical point requires an update, the shim retrieves its physical versions, identifies those overlapping the active range, constructs the retained fragments and replacement in memory, and submits them through one strongly ordered Qdrant upsert. Specifically, Chronos leverages Qdrant’s batch update API [58] to implement the split operation.

EXPERIMENTAL EVALUATION

In this section, we conduct extensive experiments to answer the following research questions: (1) How does Chronos compare with independently coordinated store-specific branching for cross-store agent workflows? (2) How do branch topology and branch count affect branch creation, deletion, and query performance? (3) What overhead does Chronos versioning impose on individual data stores? (4) How does interval-coordinate width affect execution and storage efficiency? All experiments ran on an AWS EC2 c5n.4xlarge instance with 16 vCPUs, an Intel Xeon Platinum 8124M processor, 40 GiB of memory, and Linux 6.17. Baselines. We compare against four branchable relational designs: OrpheusDB [29] stores immutable records separately from version membership, requiring joins for query. Doltgres [17] provides branching using content-addressed storage. PG-clone-Btrfs creates one PostgreSQL database per branch using Btrfs copy-onwrite snapshots [12]. PG-Savepoint emulates transient branches with nested transactions and savepoints. For vector data, we use Branch-aware Qdrant [59] which represents branch history as part of each document’s metadata and resolves it with complex filters.

6.1

50% 0%

(a) Workflow replay time, exclud- (b) Time breakdown by compoing model inference. nent.

6

100%

Runtime (s)

10

0

1000

Bat ch A PI Flas hIn fer Re t ry-A fter Tra ce m eta. Ro u ting KV ca c he Sc o res Sp e cula tion RAG QA On b oa rdin g Dia gno stic s

10

1

1500

Doltgres+Btrfs+Qdrant-Uncoordinated Relational DB Vector DB Filesystem Other Model inference

Success rate

102

2000

End-to-end time (s)

Chronos Doltgres+Btrfs+Qdrant

Bat ch A PI Flas hIn fer Re t ry-A fter Tra ce m eta. Ro u ting KV ca c he Sc o res Sp e cula tion RAG QA On b oa rdin g Dia gno stic s

Tool replay time (s)

103

Cross-Store Enterprise Agent Workflows

The first experiment simulates an agentic enterprise data platform whose shared data includes company documents, emails, workplace conversations, meeting records, and source code. Agents search this data, record durable memory, revise documents and code, and publish accepted changes to shared organizational branches. The data spans three stores: documents and code in a filesystem, provenance and durable agent memory in a relational database, and document embeddings in a vector database. We construct the company data 9

Xinjing Zhou, Jason Mohoney, Samuel Madden, Michael Stonebraker, and Lei Cao

Chronos

OrpheusDB

Branch creation p50 latency (ms)

Spine

Fanout

Bushy

Doltgres

Branch deletion Spine

103 102 101 100 10−1

PG-clone-Btrfs

Fanout

Bushy

1 4 16 64 128 1 4 16 64 128 1 4 16 64 128

Branches

Bushy

2×103 103 6×102 4×102

102 101 100 1 4 16 64 128 1 4 16 64 128 1 4 16 64 128

PG-Savepoint Query Spine Fanout

Branches

1 4 16 64 128 1 4 16 64 128 1 4 16 64 128

Branches

Figure 8: BranchBench topology sensitivity at scale factor 5: Chronos remains stable across 1–128 branches and tree shapes. Missing points indicate a 10-minute timeout or an unsupported shape. OrpheusDB

Doltgres

PG-clone-Btrfs

PG-Savepoint

baseline avoids these violations, but its runtime grows linearly because workflows cannot overlap. Figure 7b shows this trade-off at 32 agents: the serialized baseline takes 6,876 s, compared with 378 s for Chronos, an 18.2× difference. Thus, Chronos preserves cross-store visibility without serializing complete agent executions.

103

Software Dev

Failure Repro

Data Cleaning

99.996%

100

29.3%

101

45.9%

102 70.7%

Elapsed time (s)

Chronos

6.2

MCTS Simulation

Branching Scalability and Performance

Next, we compare Chronos with the four aboved-mentioned branching solutions on relational stores using BranchBench [3], which measures branch operations and workflows over TPC-C with different branch-tree topologies. Topology scalability. We start by isolating whether branch operations and query execution become more expensive as the branch tree grows. We construct branch trees with different tree shapes. A spine extends its newest branch, a fanout repeatedly forks from the root, and a bushy tree randomly selects parents from existing branches. Each branch represents a what-if fulfillment plan. After creating a branch, the workload selects 100 pending orders from a random starting point, applies the corresponding delivery updates in isolation, and evaluates the resulting backlog. Branching therefore allows alternative fulfillment plans to be explored without affecting other branches. Figure 8 shows that tree shape and branch count have little effect on Chronos. At 128 branches, Chronos creates branches 1.9–3.6× faster and deletes them 2.1–2.5× faster than Doltgres because these operations modify only compact interval metadata. Compared with PG-clone-Btrfs, Chronos creates branches nearly three orders of magnitude faster. PG-clone-Btrfs can nevertheless match or outperform Chronos on the queries because every clone retains PostgreSQL’s native query path. Chronos is 2.6× faster than Doltgres on the same queries at 128 branches because its interval predicates do not depend on branch history. Thus, Chronos keeps branch operations inexpensive without shifting a growing cost onto later updates and queries. Note that PGSavepoint supports only the spine shape. On completed points, OrpheusDB queries are 1.4–1.7× slower than Chronos, and several spine and bushy runs exceed the 10-minute limit. End-to-end workflows. The second experiment evaluates five workflows defined in BranchBench with a 2-hour limit per system. The MCTS workflow constructs a bushy tree of 1,000 branches with lightweight update-and-evaluate queries in each branch. The Simulation workflow creates a flat fanout of 1,000 branches. The Software Development and Data Cleaning workflows construct moderately deep trees while applying both schema and data transformations

Figure 9: BranchBench workflows: Chronos completes all five and runs MCTS 6.0×/16.7× faster than Doltgres/PG-cloneBtrfs. Percentages show successful steps in incomplete runs. accounts for 94% of the time, while Chronos restricts comparison to versions changed by the candidates. For most workflows, model inference dominates end-to-end execution time. Averaged across the 11 workflows, inference accounts for 91% of Chronos’s end-to-end time and 53% of the baseline’s. Concurrent incident investigations. We next run concurrent workflows that publish to one shared team branch – these workflows simulate agents performing incident investigations. Each agent acts as an on-call site reliability engineer for a distinct production failure. On a task, it first creates a private branch; then it searches tickets and documents, identifies the cause, proposes a mitigation, and generates a report stored on the filesystem with metadata stored in the DBMS and an index entry in Qdrant for the report. Finally, each agent merges changes in data stores from the private branch to the shared team branch. Chronos aborts and retries transient stale-preview or reservation conflicts until it succeeds. The Uncoordinated baseline runs workflows concurrently and applies each merge independently at the three stores, which can expose partial state. The Serialized baseline instead protects each complete workflow with a global lock, preventing partial visibility at the cost of concurrency. While benchmarking, we run a verifier that constantly checks for partial state during merges that violate the invariant that every visible report has matching records in both the relational and vector stores. Figure 7a reports the fraction of agent traces that complete without violations. Chronos completes all agents at every concurrency level through 128 agents without exposing a partially visible merge. The uncoordinated baseline records a cross-store violation at four agents and exposes incomplete state from 16 agents onward; at 32 agents, it completes only 10 traces while the verifier records 154 violations. The serialized 10

Doltgres

p95 latency (ms)

YCSB-C

400

2

200

1

0 0

1

Throughput (Ktxn/s)

0 0

25

Throughput (Kops/s)

(a) OLTP throughput and latency.

OverlayFS

2 1 0

1

4

8

12

16

20 22

Btrfs

ChronosFS

100 10−3

TPC-H query

(b) TPC-H.

branch create

read write-after-stable branch write

create

Unversioned Qdrant

AgentFS

103

delete

(c) Filesystem p50 latency.

p50 latency (ms)

PostgreSQL

TPC-C

p50 latency (ms)

Chronos

Slowdown vs. DuckDB

Chronos : Efficient Bolt-On Branching Across Data Stores for Stateful Agentic Applications

Branch-aware Qdrant

Qdrant + Chronos

20 20

10 0

0.93

0.96

0.99

Recall@10

0

1

4

16 32

Branches (0.99 recall)

(d) Qdrant latency (Dataset=DEEP).

6.3

Store-Level Overhead

In this subsection, we quantify the overhead added by Chronos’s interval-based versioning to each data store. For OLTP, we compare Chronos with unversioned PostgreSQL and Doltgres, a PostgreSQL-compatible database with built-in branching. We also compare Chronos applied to DuckDB against unversioned DuckDB, and ChronosFS against OverlayFS, Btrfs, and AgentFS. PostgreSQL OLTP. The PostgreSQL experiment uses 5 TPC-C warehouses and 5 million 1 KiB YCSB records. Each run uses a 10second warmup followed by a 30-second measurement and reports throughput against p95 latency. Figure 10a shows that Chronos incurs a 1.18–1.75× throughput slowdown over unversioned PostgreSQL while providing 3.4–5.9× the peak throughput of Doltgres. The gap to PostgreSQL is smaller for read-only YCSB-C than for TPC-C, whose updates create physical versions and maintain interval indexes. Chronos on DuckDB. For DuckDB, we use the TPC-H benchmark with a scale factor of 10, 4 execution threads, and a 10 GiB memory limit(Figure 10b). This setup reports a geometric-mean slowdown of 1.12×, with per-query ratios ranging from 0.88× to 1.76×. Visibility filtering therefore adds modest overhead on average when the data contains few physical versions, although individual queries vary more widely. Qdrant vector search. We evaluate Chronos on Qdrant using DEEP vectors [5]. Figure 10d shows the results. At 0.99 recall, Chronos incurs a 1.34× slowdown over unversioned Qdrant and is 3.5× faster than Branch-aware Qdrant [59]. From 1 to 32 branches, Chronos latency changes by only 1.02×, while Branch-aware Qdrant grows 10.7× as its predicate size increases; at 32 branches, Chronos is 17.9× faster as its interval predicate is constant-sized. Filesystem operations. We compare ChronosFS backed by SQLite with OverlayFS, Btrfs, and AgentFS using sixteen 128 MiB files. For each system, we create a branch over the files and issue one 4 KiB write to each inherited file. We time each operation from open through close to capture its copy-on-write cost and call this phase

1.04 1

Storage overhead

Throughput slowdown

Figure 10: Store-level overhead on PostgreSQL OLTP, DuckDB TPC-H, filesystem operations, and Qdrant vector search. Table 3: Allocator-supported branch count across intervalin each branch. The Failure Reproduction workflow creates ten coordinate widths. Counts exclude the root; Bushy follows short-lived branches for debugging. These workloads therefore BranchBench’s random-parent extension. vary both branch intensity and the work performed within each branch. Figure 9 shows that Chronos completes all five workflows. 32 64 128 256 512 1,024 PG-Savepoint fails on three workflows, while Doltgres encounters Spine 14 28 56 112 224 448 failures on Simulation; only PG-clone-Btrfs also completes all five. Fanout 1.02×103 1.05×106 1.10×1012 1.21×1024 1.46×1048 2.14×1096 Chronos performs particularly well on branch-intensive work4 6 6 Bushy 61 498 1.75×10 5.49×10 > 5.49×10 > 5.49×106 flows, running MCTS 6.0× faster than Doltgres and 16.7× faster than PG-clone-Btrfs, and Simulation 7.5× faster than PG-clone-Btrfs. YCSB-C YCSB-F 1% updated 1.20 1.20 Schema-heavy workflows remain less favorable because Chronos YCSB-E 10% updated 50% updated copies physical tables. Chronos is 5.3× faster than OrpheusDB on 1.12 1.12 MCTS workflow and 3.8× faster on Simulation workflow. 32 64 128 256 512 1024 Interval coordinate width (bits)

1.04 1

32 64 128 256 512 1024 Interval coordinate width (bits)

(a) Throughput slowdown rela- (b) Storage overhead relative to 32tive to 32-bit coordinates. bit coordinates.

Figure 11: Interval-coordinate width sensitivity: at 1,024 bits, throughput slowdown is at most 1.26× and storage overhead is at most 1.26× relative to 32-bit coordinates. write-after-branch. We then remount the branch and measure 4 KiB reads, 4 KiB writes, file creation, and file deletion. We repeat the complete experiment five times. Figure 10c reports the median p50 latency across runs. ChronosFS creates a branch in 0.86 ms, 3.2× faster than OverlayFS and over 50× faster than Btrfs and AgentFS. Read latency is similar because all four systems use the kernel page cache. Like Btrfs, ChronosFS uses block-level copy-on-write, making write-after-branch over 4,000× faster than OverlayFS and 10,000× faster than AgentFS, which copy the complete 128 MiB file. Relative to kernel-based Btrfs and OverlayFS, ChronosFS’s overhead is mostly in stable writes and file metadata operations.

6.4

Coordinate Width and Fragmentation

Coordinate width. We next quantify the impact of interval coordinate width with respect to query performance and storage overhead on PostgreSQL. Chronos uses PostgreSQL’s NUMERIC type to represent interval coordinates. Table 3 shows how wider interval coordinates increase the maximum branch count supported for each tree shape. The workload contains one million YCSB records with a 1 KiB payload and a 16-branch spine. We use 16 workers, each operating on a separate branch and a disjoint key partition. For each coordinate width, we run YCSB-C, YCSB-E, and YCSB-F with a 10-second warmup followed by a 30-second measurement. We report throughput slowdown relative to 32-bit coordinates. To measure storage, we update 1%, 10%, or 50% of the records once across the 16 branches and report the resulting storage overhead relative 11

103 10

2

10

1

100

Zipf factor 0.5

0

0.9

p95 latency (ms)

Max versions per key

Xinjing Zhou, Jason Mohoney, Samuel Madden, Michael Stonebraker, and Lei Cao

0.95

1 10 100 Sibling branches

(a) Live versions per key.

1,000

3 × 100 2 × 100

native implementation of interval-based versioning within a database engine. A database that only requires local branching could incorporate interval visibility into table scans and interval splitting into its update path, eliminating shim and query-rewrite overhead.

Zipf factor 0.5

0

10 6 × 10−1 4 × 10−1 3 × 10−1 2 × 10−1

0.9

0.95

Read

0

Write

1 10 100 Sibling branches

1,000

7

Hierarchical labels and version indexes. Nested-set and nested-interval schemes use interval containment to encode ancestry within hierarchical data [14, 82]. DeltaNI extends these schemes to versioned hierarchies [20]. The BT-tree and BTR-tree use version-tree ancestry to organize records in specialized indexes over keys, branches, and time [30, 31]. Chronos instead uses one interval representation for both branch ancestry and record visibility. Attaching these intervals to application records reduces visibility to a simple range predicate, enabling isolated branches across heterogeneous stores without specialized temporal indexes. Database and dataset branching. Database and dataset branching is closest to Chronos because both provide durable branches over relational data. Doltgres and Neon provide durable branches within one relational database or storage service [3, 16, 17, 50]. Dataset versioning systems [8–10, 29, 43, 66] similarly provide shared versions and branches for relational data. These systems primarily target infrequent branching within a single relational store and may incur substantial query overhead. Chronos instead supports frequent branching across heterogeneous stores using intervals. Transactions and polystores. Transactions, nested transactions, MVCC, and optimistic concurrency control provide shortlived isolation and can emulate transient branches while an enclosing transaction remains open [6, 7, 28, 38, 48]. Keeping agent candidates open across model inference and tool execution, however, prolongs contention and delays reclamation [35]. Polystores compose heterogeneous engines [23, 76, 78, 85], while cross-store transaction protocols coordinate atomic or serializable operations across them [15, 24, 37, 79, 91, 93]. Epoxy is closest to Chronos because it also uses version metadata and read filtering across heterogeneous stores [37]. These systems coordinate individual transactions, whereas Chronos uses short-running transactions to manage durable branches that span many transactions and can later be forked or merged. A merge is published through shared branch metadata, avoiding a distributed transaction. Agent state and execution sandboxing. Agent systems isolate speculative execution through copy-on-write filesystems [64, 89], capability and system-call confinement [25, 88], container sandboxes [53, 81], microVMs [2], and agent execution environments [4, 19, 26, 52, 86, 92]. AgentFS stores an agent’s files, key-value state, and tool history in a snapshotable SQLite database [83]. These systems branch an agent’s execution state, but do not coordinate corresponding versions in external relational and NoSQL databases. Chronos complements them by providing one durable branch across filesystem, relational, and NoSQL state.

(b) Read/write p95 latency.

Figure 12: Hot-key fragmentation and access cost under sustained updates from sibling branches. to 32-bit coordinates. Figures 11a and 11b show that wider coordinates impose modest overhead. At 1,024 bits, throughput slowdown ranges from 1.13× to 1.26× across workloads, while storage overhead ranges from 1.01× to 1.26× across update rates. Even with 50% updates, storage overhead remains at most 1.03× through 256 bits. YCSB-F updates cost more because they create more interval endpoints and index entries. PostgreSQL’s variable-length NUMERIC type allocates storage dynamically, so its storage consumption does not grow proportionally with the configured coordinate width. Hot-key fragmentation. We next stress interval splitting by having 0–1,000 sibling branches repeatedly run YCSB-F over the same one-million-record dataset with Zipf factors of 0.5, 0.9, and 0.95. Up to 32 branches run concurrently, and every branch updates for 30 seconds. After compacting PostgreSQL’s internal MVCC history, we measure the live interval versions and probe YCSB-C reads and YCSB-F writes from a fresh branch using a 10-second warmup and 30-second measurement period. Figure 12 shows that fragmentation is concentrated on the hottest keys and increases with the number of sibling branches that modify them. At 1,000 branches, the maximum is 65, 613, and 999 live versions for Zipf factors 0.5, 0.9, and 0.95, respectively. Repeated writes within one branch do not continually add live interval versions. Each branch maintains its own version after the initial copy-on-write. Consequently, versions for a key are bounded by the number of branches that modify it. Read and write latency remains stable at 0.17ms and 2.49–2.54ms, respectively, showing that the resulting interval rows impose little additional cost at the tested scale.

6.5

RELATED WORK

Discussion and Future Work

The results show that Chronos is most effective for applications that frequently branch and modify records. Metadata-only branch creation and record-level sharing make these workloads substantially faster than existing alternatives, while interval filtering keeps query overhead modest and independent of branch history. However, these benefits come with two limitations. First, Chronos provides atomic cross-store visibility under controlled access, rather than atomic commits of physical writes. This guarantee requires controlled access through Chronos, durable store-local writes, and a transactional metadata store. Second, Chronos’s bolt-on design currently cannot enforce integrity constraints within the engines, and semantic merge conflicts remain the application’s responsibility. One possible approach to address this problem is to enforce these constraints in the Chronos layer before updates are published; we leave this to future work. Another direction for future work is a

8

CONCLUSION

Stateful agentic applications need to explore alternatives whose changes span heterogeneous data stores. Chronos provides such a

12

Chronos : Efficient Bolt-On Branching Across Data Stores for Stateful Agentic Applications

durable cross-store branching abstraction without modifying storage engines. Chronos introduces interval-based versioning, which shares data and keeps query cost independent of branch history, along with a bolt-on architecture that coordinates branch management and cross-store merge visibility. We implement Chronos for PostgreSQL, SQLite, DuckDB, Qdrant, and a DBMS-backed filesystem. Chronos completes every evaluated BranchBench workflow and runs MCTS 6.0× faster than Doltgres and 16.7× faster than PostgreSQL cloning on Btrfs. These results show that efficient branching can be provided as a unified abstraction across existing heterogeneous stores. Chronos is open-sourced at https: //github.com/mitdbg/chronos

[20] Jan Finis, Robert Brunel, Alfons Kemper, Thomas Neumann, Franz Färber, and Norman May. 2013. DeltaNI: an efficient labeling scheme for versioned hierarchical data. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data (SIGMOD/PODS’13). ACM, 905–916. https: //doi.org/10.1145/2463676.2465329 [21] Keir Fraser. 2004. Practical lock-freedom. Technical Report UCAM-CL-TR-579. University of Cambridge, Computer Laboratory. https://doi.org/10.48456/tr-579 [22] Deepak Narayan Gadde, Keerthan Kopparam Radhakrishna, Vaisakh Naduvodi Viswambharan, Aman Kumar, Djones Lettnin, Wolfgang Kunz, and Sebastian Simon. 2025. Hey AI, Generate Me a Hardware Code! Agentic AIbased Hardware Design & Verification. In 2025 38th SBC/SBMicro/IEEE Symposium on Integrated Circuits and Systems Design (SBCCI). IEEE, 1–5. https: //doi.org/10.1109/sbcci66862.2025.11218681 [23] Vijay Gadepally, Peinan Chen, Jennie Duggan, Aaron Elmore, Brandon Haynes, Jeremy Kepner, Samuel Madden, Tim Mattson, and Michael Stonebraker. 2016. The BigDAWG polystore system and architecture. In 2016 IEEE High Performance Extreme Computing Conference (HPEC). IEEE, 1–6. https://doi.org/10.1109/hpec. 2016.7761636 [24] D. Georgakopoulos, M. Rusinkiewicz, and A. Sheth. 1991. On serializability of multidatabase transactions through forced local conflicts. In [1991] Proceedings. Seventh International Conference on Data Engineering. IEEE Comput. Soc. Press, 314–323. https://doi.org/10.1109/icde.1991.131479 [25] Seyedhamed Ghavamnia, Tapti Palit, Azzedine Benameur, and Michalis Polychronakis. 2020. Confine: Automated System Call Policy Generation for Container Attack Surface Reduction. In 23rd International Symposium on Research in Attacks, Intrusions and Defenses (RAID 2020). USENIX Association, San Sebastian, 443–458. https://www.usenix.org/conference/raid2020/presentation/ ghavanmnia [26] GitHub. [n.d.]. About Cloud and Local Sandboxes for GitHub Copilot. https: //docs.github.com/en/copilot/concepts/about-cloud-and-local-sandboxes. Accessed September 11, 2026. [27] Google. [n.d.]. Cloud Firestore Documentation: Transactions and Batched Writes. https://firebase.google.com/docs/firestore/manage-data/transactions. Accessed September 11, 2026. [28] Jim Gray. 1981. The Transaction Concept: Virtues and Limitations (Invited Paper). In Very Large Data Bases, 7th International Conference, September 9-11, 1981, Cannes, France, Proceedings. IEEE Computer Society, 144–154. https: //www.sigmod.org/publications/dblp/db/conf/vldb/Gray81.html [29] Silu Huang, Liqi Xu, Jialin Liu, Aaron J. Elmore, and Aditya Parameswaran. 2017. OrpheusDB: Bolt-on Versioning for Relational Databases. Proceedings of the VLDB Endowment 10, 10 (2017), 1130–1141. https://doi.org/10.14778/3115404.3115417 [30] Linan Jiang, Betty Salzberg, David Lomet, and Manuel Barrena. 2003. The BTR-Tree: Path-Defined Version-Range Splitting in a Branched and Temporal Structure. In Advances in Spatial and Temporal Databases. Lecture Notes in Computer Science, Vol. 2750. Springer Berlin Heidelberg, 28–45. https://doi.org/ 10.1007/978-3-540-45072-6_3 [31] Linan Jiang, Betty Salzberg, David B. Lomet, and Manuel Barrena. 2000. The BT-Tree: A Branched and Temporal Access Method. In Proceedings of the 26th International Conference on Very Large Data Bases. Morgan Kaufmann, 451–460. https://www.vldb.org/conf/2000/P451.pdf [32] Zhengyao Jiang, Dominik Schmidt, Dhruv Srikanth, Dixing Xu, Ian Kaplan, Deniss Jacenko, and Yuxiang Wu. 2025. AIDE: AI-Driven Exploration in the Space of Code. arXiv:2502.13138 [cs.AI] https://arxiv.org/abs/2502.13138 [33] Zhewei Kang, Xuandong Zhao, and Dawn Song. 2025. Scalable Best-of-N Selection for Large Language Models via Self-Certainty. In Advances in Neural Information Processing Systems, D. Belgrave, C. Zhang, H. Lin, R. Pascanu, P. Koniusz, M. Ghassemi, and N. Chen (Eds.), Vol. 38, Main Conference. Curran Associates, Inc., 19720–19745. https://doi.org/10.52202/085713-0663 [34] Andrej Karpathy. [n.d.]. autoresearch: AI Agents Running Research on Single-GPU nanochat Training Automatically. https://github.com/karpathy/ autoresearch. Accessed September 11, 2026. [35] Jongbin Kim, Hyunsoo Cho, Kihwang Kim, Jaeseon Yu, Sooyong Kang, and Hyungsoo Jung. 2020. Long-lived Transactions Made Less Harmful. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data (SIGMOD/PODS ’20). ACM, 495–510. https://doi.org/10.1145/3318464.3389714 [36] Lingdong Kong, Xian Sun, Wei Chow, Linfeng Li, Kevin Qinghong Lin, Xuan Billy Zhang, Song Wang, Rong Li, Qing Wu, Wei Gao, Yingshuo Wang, Shaoyuan Xie, Jiachen Liu, Leigang Qu, Shijie Li, Lai Xing Ng, Benoit R. Cottereau, Ziwei Liu, Tat-Seng Chua, and Wei Tsang Ooi. 2026. AI for Auto-Research: Roadmap & User Guide. arXiv:2605.18661 [cs.AI] https://arxiv.org/abs/2605.18661 [37] Peter Kraft, Qian Li, Xinjing Zhou, Peter Bailis, Michael Stonebraker, Matei Zaharia, and Xiangyao Yu. 2023. Epoxy: ACID Transactions across Diverse Data Stores. Proceedings of the VLDB Endowment 16, 11 (2023), 2742–2754. https://doi.org/10.14778/3611479.3611484 [38] H. T. Kung and John T. Robinson. 1981. On optimistic methods for concurrency control. ACM Transactions on Database Systems 6, 2 (1981), 213–226. https: //doi.org/10.1145/319566.319567

REFERENCES [1] Mahmoud Abdelwahab. 2023. A Database for Every Preview Environment Using Neon, GitHub Actions, and Vercel. https://neon.com/blog/branchingwith-preview-environments. Accessed September 11, 2026. [2] Alexandru Agache, Marc Brooker, Andreea Florescu, Alexandra Iordache, Anthony Liguori, Rolf Neugebauer, Phil Piwonka, and Diana-Maria Popa. 2020. Firecracker: Lightweight Virtualization for Serverless Applications. In 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI 20). USENIX Association, Santa Clara, CA, 419–434. https://www.usenix.org/conference/ nsdi20/presentation/agache [3] Elaine Ang, Sam Weldon, In Keun Kim, Kevin Durand, Kostis Kaffes, and Eugene Wu. 2026. BranchBench: Aligning Database Branching with Agentic Demands. arXiv:2604.17180 [cs.DB] https://arxiv.org/abs/2604.17180 [4] Anthropic. [n.d.]. Configure the Sandboxed Bash Tool. https://code.claude.com/ docs/en/sandboxing. Accessed September 11, 2026. [5] Dmitry Baranchuk and Artem Babenko. 2021. Benchmarks for Billion-Scale Similarity Search. https://research.yandex.com/blog/benchmarks-for-billionscale-similarity-search. Accessed September 11, 2026. [6] Philip A. Bernstein and Nathan Goodman. 1983. Multiversion concurrency control—theory and algorithms. ACM Transactions on Database Systems 8, 4 (1983), 465–483. https://doi.org/10.1145/319996.319998 [7] Philip A. Bernstein and Eric Newcomer. 2009. Principles of Transaction Processing (2nd ed.). Morgan Kaufmann. https://shop.elsevier.com/books/principles-oftransaction-processing/bernstein/978-1-55860-623-4 [8] Anant Bhardwaj, Amol Deshpande, Aaron J. Elmore, David Karger, Sam Madden, Aditya Parameswaran, Harihar Subramanyam, Eugene Wu, and Rebecca Zhang. 2015. Collaborative data analytics with DataHub. Proceedings of the VLDB Endowment 8, 12 (2015), 1916–1919. https://doi.org/10.14778/2824032.2824100 [9] Anant P. Bhardwaj, Souvik Bhattacherjee, Amit Chavan, Amol Deshpande, Aaron J. Elmore, Samuel Madden, and Aditya G. Parameswaran. 2015. DataHub: Collaborative Data Science & Dataset Version Management at Scale. In Proceedings of the Seventh Biennial Conference on Innovative Data Systems Research. https://www.cidrdb.org/cidr2015/Papers/CIDR15_Paper18.pdf [10] Souvik Bhattacherjee, Amit Chavan, Silu Huang, Amol Deshpande, and Aditya Parameswaran. 2015. Principles of dataset versioning: exploring the recreation/storage tradeoff. Proceedings of the VLDB Endowment 8, 12 (2015), 1346– 1357. https://doi.org/10.14778/2824032.2824035 [11] Souvik Bhattacherjee and Amol Deshpande. 2018. RStore: A Distributed MultiVersion Document Store. In 2018 IEEE 34th International Conference on Data Engineering (ICDE). IEEE, 389–400. https://doi.org/10.1109/icde.2018.00043 [12] Btrfs Developers. [n.d.]. Reflink. https://btrfs.readthedocs.io/en/latest/Reflink. html. Accessed September 11, 2026. [13] Sam Bydlon. 2024. Building an AI Simulation Assistant with Agentic Workflows. https://aws.amazon.com/blogs/hpc/building-an-ai-simulation-assistantwith-agentic-workflows/. Accessed September 11, 2026. [14] Joe Celko. 2004. Joe Celko’s Trees and Hierarchies in SQL for Smarties. Morgan Kaufmann. https://shop.elsevier.com/books/joe-celkos-trees-and-hierarchiesin-sql-for-smarties/celko/978-1-55860-920-4 [15] Akon Dey, Alan Fekete, and Uwe Röhm. 2015. Scalable distributed transactions across heterogeneous stores. In 2015 IEEE 31st International Conference on Data Engineering. IEEE, 125–136. https://doi.org/10.1109/icde.2015.7113278 [16] DoltHub. [n.d.]. Dolt SQL Database with Git Style Versioning. https://www. dolthub.com/. Accessed September 11, 2026. [17] DoltHub. [n.d.]. Doltgres Documentation: Merge. https://www.doltgres.com/ docs/concepts/git/merge/. Accessed September 11, 2026. [18] DuckDB Foundation. [n.d.]. DuckDB Documentation. https://duckdb.org/docs/ current/. Accessed September 11, 2026. [19] E2B. [n.d.]. Sandbox Forking. https://e2b.dev/docs/sandbox/fork. Accessed September 11, 2026. 13

Xinjing Zhou, Jason Mohoney, Samuel Madden, Michael Stonebraker, and Lei Cao

[39] libfuse Project. [n.d.]. libfuse: The Reference Implementation of the Linux FUSE Interface. https://github.com/libfuse/libfuse. Accessed September 11, 2026. [40] Knut-Andreas Lie, Olav Møyner, Elling Svee, and Jakob Torben. 2026. Agentic Scientific Simulation: Execution-Grounded Model Construction and Reconstruction. arXiv:2603.00214 [cs.SE] https://arxiv.org/abs/2603.00214 [41] Shu Liu, Soujanya Ponnapalli, Shreya Shankar, Sepanta Zeighami, Alan Zhu, Shubham Agarwal, Ruiqi Chen, Samion Suwito, Shuo Yuan, Ion Stoica, Matei Zaharia, Alvin Cheung, Natacha Crooks, Joseph E. Gonzalez, and Aditya G. Parameswaran. 2025. Supporting Our AI Overlords: Redesigning Data Systems to be Agent-First. arXiv:2509.00997 [cs.AI] https://arxiv.org/abs/2509.00997 [42] Pietro Lugato, Luca Lavezzo, Jason Mohoney, Hasan Ozturk, Muhammad Hassan Ahmed, Juan Pablo Salas, Viphava Ohm, Krittin Phornsiricharoenphant, Gabriele Benelli, Mariarosaria D’Alfonso, Manasvita Joshi, Warren Nam, Aron Soha, Samantha Sunnarborg, Austin Swinney, Jack Tucker, Dmytro Kovalskyi, Tim Kraska, and Christoph Paus. 2026. Archi: Agentic Operations at the CMS Experiment. arXiv:2606.04755 [hep-ex] https://arxiv.org/abs/2606.04755 [43] Michael Maddox, David Goehring, Aaron J. Elmore, Samuel Madden, Aditya Parameswaran, and Amol Deshpande. 2016. Decibel: the relational dataset branching system. Proceedings of the VLDB Endowment 9, 9 (2016), 624–635. https://doi.org/10.14778/2947618.2947619 [44] Harshitha Menon, Charles F. Jekel, Kevin Korner, Brian Gunnarson, Nathan K. Brown, Michael Stees, M. Giselle Fernandez-Godino, Walter Nissen, Meir H. Shachar, Dane M. Sterbentz, William J. Schill, Yue Hao, Robert Rieben, William Quadros, Steve Owen, Scott Mitchell, Ismael D. Boureima, and Jonathan L. Belof. 2026. Multi-Agent Collaboration for Automated Design Exploration on High Performance Computing Systems. arXiv:2603.11515 [cs.AI] https://arxiv.org/ abs/2603.11515 [45] Microsoft. [n.d.]. Azure Cosmos DB Transactional Batch Operations. https: //learn.microsoft.com/en-us/azure/cosmos-db/transactional-batch. Accessed September 11, 2026. [46] Microsoft. [n.d.]. SQL Server Documentation: Transactions. https://learn. microsoft.com/en-us/sql/t-sql/language-elements/transactions-transact-sql. Accessed September 11, 2026. [47] MongoDB. [n.d.]. MongoDB Documentation: Transactions. https://www. mongodb.com/docs/manual/core/transactions/. Accessed September 11, 2026. [48] J. Eliot B. Moss. 1985. Nested Transactions: An Approach to Reliable Distributed Computing. MIT Press, Cambridge, MA. https://mitpress.mit.edu/ 9780262132008/nested-transactions/ [49] Zach Musgrave and Tim Sehn. 2021. Dolt Use Cases in the Wild. https://www. dolthub.com/blog/2021-03-09-dolt-use-cases-in-the-wild/. Accessed September 11, 2026. [50] Neon. [n.d.]. Neon Branching. https://neon.com/docs/introduction/branching. Accessed September 11, 2026. [51] Alexander Novikov, Ngân Vũ, Marvin Eisenberger, Emilien Dupont, Po-Sen Huang, Adam Zsolt Wagner, Sergey Shirobokov, Borislav Kozlovskii, Francisco J. R. Ruiz, Abbas Mehrabian, M. Pawan Kumar, Abigail See, Swarat Chaudhuri, George Holland, Alex Davies, Sebastian Nowozin, Pushmeet Kohli, and Matej Balog. 2025. AlphaEvolve: A coding agent for scientific and algorithmic discovery. arXiv:2506.13131 [cs.AI] https://arxiv.org/abs/2506.13131 [52] OpenAI. [n.d.]. Agent Approvals & Security. https://learn.chatgpt.com/docs/ agent-approvals-security#os-level-sandbox. Accessed September 11, 2026. [53] OpenHands. [n.d.]. Docker Sandbox. https://docs.openhands.dev/openhands/ usage/sandboxes/docker. Accessed September 11, 2026. [54] Oracle. [n.d.]. MySQL Documentation: Transactional and Locking Statements. https://dev.mysql.com/doc/refman/8.4/en/sql-transactional-statements.html. Accessed September 11, 2026. [55] Oracle. [n.d.]. Oracle Database Documentation: Transaction Management. https://docs.oracle.com/en/database/oracle/oracle-database/23/cncpt/ transactions.html. Accessed September 11, 2026. [56] PostgreSQL Global Development Group. [n.d.]. PostgreSQL. https://www. postgresql.org/. Accessed September 11, 2026. [57] PostgreSQL Global Development Group. [n.d.]. PostgreSQL Documentation: Transactions. https://www.postgresql.org/docs/current/tutorial-transactions. html. Accessed September 11, 2026. [58] Qdrant. [n.d.]. Batch Update Points. https://api.qdrant.tech/api-reference/points/ batch-update. Accessed September 11, 2026. [59] Qdrant. [n.d.]. Branch-Aware Search. https://qdrant.tech/documentation/ tutorials-search-engineering/branch-aware-search/. Accessed September 11, 2026. [60] Qdrant. [n.d.]. Qdrant Documentation. https://qdrant.tech/documentation/ overview/. Accessed September 11, 2026. [61] Redis. [n.d.]. Redis Documentation: Transactions. https://redis.io/docs/latest/ develop/using-commands/transactions/. Accessed September 11, 2026. [62] Juha Riippi and Andrew Tweedie. 2026. Agentic AI for Multiphysics Simulation is Here. https://quanscient.com/blog/agentic-ai-for-multiphysics-simulation-ishere. Accessed September 11, 2026. [63] RocksDB. 2015. WriteBatchWithIndex: Utility for Implementing Read-YourOwn-Writes. https://rocksdb.org/blog/2015/02/27/write-batch-with-index.html.

Accessed September 11, 2026. [64] Ohad Rodeh, Josef Bacik, and Chris Mason. 2013. BTRFS: The Linux B-Tree Filesystem. ACM Transactions on Storage 9, 3 (2013), 1–32. https://doi.org/10. 1145/2501620.2501623 Enabling Evolution[65] Pramod Sadalage and Kevin Hartman. 2026. ary Database Development: Database Branching with Lakebase. https://www.databricks.com/blog/enabling-evolutionary-databasedevelopment-database-branching-lakebase. Accessed September 11, 2026. [66] Maximilian E. Schüle, Lukas Karnowski, Josef Schmeißer, Benedikt Kleiner, Alfons Kemper, and Thomas Neumann. 2019. Versioning in Main-Memory Database Systems: From MusaeusDB to TardisDB. In Proceedings of the 31st International Conference on Scientific and Statistical Database Management (SSDBM ’19). ACM, 169–180. https://doi.org/10.1145/3335783.3335792 [67] Adam Seering, Philippe Cudré-Mauroux, Samuel Madden, and Michael Stonebraker. 2012. Efficient Versioning for Scientific Array Databases. In 2012 IEEE 28th International Conference on Data Engineering. IEEE, 1013–1024. https: //doi.org/10.1109/icde.2012.102 [68] Tim Sehn. 2024. So You Want Database Branches? https://www.dolthub.com/ blog/2024-09-18-database-branches/. Accessed September 11, 2026. [69] Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Xiao Bi, Haowei Zhang, Mingchuan Zhang, Y. K. Li, Y. Wu, and Daya Guo. 2024. DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models. arXiv:2402.03300 [cs.CL] https://arxiv.org/abs/2402.03300 [70] Asankhaya Sharma. [n.d.]. OpenEvolve: An Open-Source Evolutionary Coding Agent. https://github.com/algorithmicsuperintelligence/openevolve Accessed September 11, 2026. [71] Athinagoras Skiadopoulos, Qian Li, Peter Kraft, Kostis Kaffes, Daniel Hong, Shana Mathew, David Bestor, Michael Cafarella, Vijay Gadepally, Goetz Graefe, Jeremy Kepner, Christos Kozyrakis, Tim Kraska, Michael Stonebraker, Lalith Suresh, and Matei Zaharia. 2021. DBOS: a DBMS-oriented operating system. Proceedings of the VLDB Endowment 15, 1 (2021), 21–30. https://doi.org/10.14778/3485450.3485454 [72] Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. 2025. Scaling LLM Test-Time Compute Optimally Can be More Effective than Scaling Parameters for Reasoning. In International Conference on Learning Representations, Y. Yue, A. Garg, N. Peng, F. Sha, and R. Yu (Eds.), Vol. 2025. 10131–10165. https://proceedings.iclr.cc/paper_files/paper/2025/file/ 1b623663fd9b874366f3ce019fdfdd44-Paper-Conference.pdf [73] Emad Soroush and Magdalena Balazinska. 2013. Time travel in a scientific array database. In 2013 IEEE 29th International Conference on Data Engineering (ICDE). IEEE, 98–109. https://doi.org/10.1109/icde.2013.6544817 [74] SQLite. [n.d.]. About SQLite. https://www.sqlite.org/about.html. Accessed September 11, 2026. [75] SQLite. [n.d.]. SQLite Documentation: Transactions. https://www.sqlite.org/ lang_transaction.html. Accessed September 11, 2026. [76] Michael Stonebraker. 2015. The Case for Polystores. ACM SIGMOD Blog. https://wp.sigmod.org/?p=1629 Accessed September 11, 2026. [77] Yuhong Sun, Joachim Rahmfeld, Chris Weaver, Weijia Chen, Roshan Desai, Wenxi Huang, and Mark H. Butler. 2026. EnterpriseRAG-Bench: A RAG Benchmark for Company Internal Knowledge. arXiv:2605.05253 [cs.IR] https://arxiv.org/abs/ 2605.05253 [78] Ran Tan, Rada Chirkova, Vijay Gadepally, and Timothy G. Mattson. 2017. Enabling query processing across heterogeneous data models: A survey. In 2017 IEEE International Conference on Big Data (Big Data). IEEE, 3211–3220. https://doi.org/10.1109/bigdata.2017.8258302 [79] Chuzhe Tang, Zhaoguo Wang, Jinyang Li, and Haibo Chen. 2025. Sonata: MultiDatabase Transactions Made Fast and Serializable. Proceedings of the VLDB Endowment 18, 10 (2025), 3449–3462. https://doi.org/10.14778/3748191.3748207 [80] The Git Project. [n.d.]. Git. https://git-scm.com/. Accessed September 11, 2026. [81] The gVisor Authors. [n.d.]. gVisor: The Container Security Platform. https: //gvisor.dev/. Accessed September 11, 2026. [82] Vadim Tropashko. 2005. Nested intervals tree encoding in SQL. ACM SIGMOD Record 34, 2 (2005), 47–52. https://doi.org/10.1145/1083784.1083793 [83] Turso. [n.d.]. AgentFS: The Filesystem for Agents. https://github.com/ tursodatabase/agentfs. Accessed September 11, 2026. [84] UC Berkeley Sky Computing Lab. [n.d.]. ADRS: AI-Driven Research for Systems. https://ucbskyadrs.github.io. Accessed September 11, 2026. [85] Marco Vogt, Nils Hansen, Jan Schönholz, David Lengweiler, Isabel Geissmann, Sebastian Philipp, Alexander Stiemer, and Heiko Schuldt. 2021. Polypheny-DB: Towards Bridging the Gap Between Polystores and HTAP Systems. In Heterogeneous Data Management, Polystores, and Analytics for Healthcare. Springer International Publishing, 25–36. https://doi.org/10.1007/978-3-030-71055-2_2 [86] Xingyao Wang, Boxuan Li, Yufan Song, Frank F Xu, Xiangru Tang, Mingchen Zhuge, Jiayi Pan, Yueqi Song, Bowen Li, Jaskirat Singh, Hoang Tran, Fuqiang Li, Ren Ma, Mingzhang Zheng, Bill Qian, Daniel Shao, Niklas Muennighoff, Yizhe Zhang, Binyuan Hui, Junyang Lin, Robert Brennan, Hao Peng, Heng

14

Chronos : Efficient Bolt-On Branching Across Data Stores for Stateful Agentic Applications

Ji, and Graham Neubig. 2025. OpenHands: An Open Platform for AI Software Developers as Generalist Agents. In International Conference on Learning Representations, Y. Yue, A. Garg, N. Peng, F. Sha, and R. Yu (Eds.), Vol. 2025. 65882–65919. https://proceedings.iclr.cc/paper_files/paper/2025/file/ a4b6ad6b48850c0c331d1259fc66a69c-Paper-Conference.pdf [87] Zhaoyang Wang, Canwen Xu, Boyi Liu, Yite Wang, Siwei Han, Zhewei Yao, Huaxiu Yao, and Yuxiong He. 2026. Agent World Model: Infinity Synthetic Environments for Agentic Reinforcement Learning. arXiv:2602.10090 [cs.AI] https://arxiv.org/abs/2602.10090 [88] Robert N.M. Watson, Jonathan Anderson, Ben Laurie, and Kris Kennaway. 2010. Capsicum: Practical Capabilities for UNIX. In 19th USENIX Security Symposium (USENIX Security 10). USENIX Association, Washington, DC. https://www. usenix.org/conference/usenixsecurity10/capsicum-practical-capabilities-unix [89] XFS Developers. [n.d.]. xfs_io(8) Reflink Documentation. https://man7.org/linux/ man-pages/man8/xfs_io.8.html. Accessed September 11, 2026. [90] Zeyu Xia, Jinzhe Ma, Congjie Zheng, Zhongyao Wang, Shufei Zhang, Yuqiang Li, Hang Su, P. Hu, Changshui Zhang, Xingao Gong, Wanli Ouyang, Lei Bai, Dongzhan Zhou, and Mao Su. 2026. VASP Agent: An Agentic Framework for Autonomous First-principles Calculations. arXiv:2512.19458 [cs.AI] https: //arxiv.org/abs/2512.19458 [91] Hiroyuki Yamada, Toshihiro Suzuki, Yuji Ito, and Jun Nemoto. 2023. ScalarDB: Universal Transaction Manager for Polystores. Proceedings of the VLDB Endowment 16, 12 (2023), 3768–3780. https://doi.org/10.14778/3611540.3611563 [92] John Yang, Carlos Jimenez, Alexander Wettig, Kilian Lieret, Shunyu Yao, Karthik Narasimhan, and Ofir Press. 2024. SWE-agent: Agent-Computer Interfaces Enable Automated Software Engineering. In Advances in Neural Information Processing Systems 37 (NeurIPS 2024). Neural Information Processing Systems Foundation, Inc. (NeurIPS), 50528–50652. https://doi.org/10.52202/079017-1601 [93] Jianqiu Zhang, Kaisong Huang, Tianzheng Wang, and King Lv. 2022. Skeena: Efficient and Consistent Cross-Engine Transactions. In Proceedings of the 2022 International Conference on Management of Data (SIGMOD/PODS ’22). ACM, 34–48. https://doi.org/10.1145/3514221.3526171 [94] Weiqin Zou, Weiqiang Zhang, Xin Xia, Reid Holmes, and Zhenyu Chen. 2019. Branch Use in Practice: A Large-Scale Empirical Study of 2,923 Projects on GitHub. In 2019 IEEE 19th International Conference on Software Quality, Reliability and Security (QRS). IEEE, 306–317. https://doi.org/10.1109/qrs.2019.00047

15

Related documents

• Databases with Missing Values that are Governed by Missingness Mechanisms#1043177
• Proof-of-Retention: A Framework for Auditable Cross-Organization Data Sharing#1043178
• AkasicMEM: Governed Enterprise Memory for Agents#1043179
• Spend Classification Without Leakage: An Evaluation Harness and What It Changed in a Deployed System#1043180
• A Functional Pilot for Certified Freshness-Aware Semantic--Spatial Range Retrieval#1043181