Source-linked AI summary
Tracking State Footprints: How Agents Can Transact
Oto Mraz, Rares Şerban, Kyriakos Psarakis, Burcu Kulahcioglu Ozkan, Asterios Katsifodimos
TL;DR
Multi-agent orchestrators increasingly run tasks in parallel but often do not track the state agents read and write, leaving coordination failures insufficiently addressed. The paper frames coordination as data management and proposes state footprints with deterministic orchestration. In a refactoring task, a repaired conflict-ordered plan succeeded for both LLM agents and reduced duration 1.23× versus sequential execution at comparable token cost.
Problem
Method
Results
In Task 4, a repaired conflict-ordered plan succeeded for both LLM agents and reduced task duration 1.23× compared with sequential execution at comparable token cost.
Source: §4 · p. 4Takeaways & Limitations
The paper argues that external systems should expose transactional interfaces so orchestrators can stage, validate, and revert state effects.
Source: §1 · p. 2The paper focuses on coding agents, where git provides a transactional substrate; most other domains lack version control and may have immediately visible, often irreversible effects.
Source: §7 · p. 6
Abstract
from arXiv · showhide
Can AI agents transact? We argue that they must: as multi-agent systems (MASs) increasingly write code, deploy infrastructure, modify databases, and call web services, lost updates or stale reads can be catastrophic. Although MASs increasingly execute plans in parallel, current orchestrators do not track the state that agents read and write. As a result, concurrency anomalies manifest even in simple coding tasks. We frame MAS coordination as a data management problem and propose to describe agents by their state footprint: the state they read and write across their own local context and state, as well as the state of the orchestrator and external systems. We posit that MASs require guarantees similar to those of databases, but providing them raises new challenges and opportunities: unlike database transactions, agents do not read from a fixed schema or an isolated snapshot, and cannot be replayed deterministically upon failure. They can, however, resolve conflicts semantically instead of aborting, enabling new forms of concurrency control and conflict resolution. Towards agents that can transact, we outline a vision for next-generation agent orchestrators and transactional interfaces for external systems to participate in agentic transactions.
1 INTRODUCTION
Multi-agent systems can fail even when individual agents succeed, because orchestrators often track task order but not the shared state agents read and write. The paper proposes state footprints and a deterministic orchestrator as a basis for database-like guarantees, while recognizing that agent execution differs from database transactions.
1 INTRODUCTION
- Orchestrators often track task order but not data flow, allowing stale reads and conflicting writes to break merged work even when agents act correctly in isolation.A better language model would not prevent these coordination failures.Source: §1 · p. 1
- A task’s state footprint is the state it reads and writes across agent-local, orchestrator, and external scopes.The paper argues that a deterministic orchestrator should record accesses and enforce ordering, rather than relying on models alone.Source: §1 · p. 1
- Unlike database transactions, agents do not read from a fixed schema, cannot be replayed deterministically after failure, and can resolve conflicts semantically instead of simply aborting.These differences mean MASs need database-like guarantees but not necessarily database mechanisms.Source: §1 · p. 1
- The paper characterizes coordination anomalies across four coding tasks and proposes footprints to capture cross-scope conflicts that can emerge during execution.Footprints and provenance are proposed as foundations for ACID guarantees, fault tolerance, reuse, and transactional interfaces for external systems.Source: §1 · pp. 1–2
2 A BRIEF INTRODUCTION TO MAS
Multi-agent systems coordinate specialized agents through plans that may run sequentially or in parallel. As orchestration has evolved toward dynamic, flexible execution, the paper argues that explicit data management and concurrency control are needed alongside planning.
2 A BRIEF INTRODUCTION TO MAS
- A planner decomposes a goal into constrained subtasks, which may run sequentially or in parallel using DAG-based scatter-gather plans.Sequential execution is safest but slowest; DAG plans merge artifacts after parallel work.Source: §2 · p. 2
- Early frameworks used static plans, while later runtimes added DAG execution, dynamic replanning, verification, and self-healing without guaranteeing shared-state correctness.State management and idempotency were left to users in early systems.Source: §2 · p. 2
- Runtime evolution toward flexible plans and roles increases shared-state coordination challenges, motivating explicit concurrency control and data management.The paper identifies this as a requirement for next-generation runtimes.Source: §2 · p. 2
3 MULTI-AGENT COORDINATION AS A DATA MANAGEMENT PROBLEM
The paper frames multi-agent coordination as a data-management problem: task ordering alone does not capture dependencies among agents’ reads and writes. A refactoring example shows how untracked shared-state interactions can escape ordering checks and surface as failures after merge.
3 MULTI-AGENT COORDINATION AS A DATA MANAGEMENT PROBLEM
- Orchestrators mainly capture control flow, while neglecting data dependencies and output visibility, so agents can act on stale or inconsistent state despite task ordering.The paper treats coordination and isolation as concerns beyond database settings.Source: §3 · p. 2
- In the refactoring workflow, T0 changes the Signal definition while T1–T3 update separate caller subpackages, creating parallel work over shared repository state.The workers’ write sets initially appear disjoint.Source: §3 · p. 2
- T1 and T2 both edit a shared test fixture, and a merge silently shadows one task’s setup even though tests pass.The global commit then integrates the outputs and validates the repository before releasing the PR.Source: §3 · p. 3
- T2 reads an attribute deleted by T0, an unplanned dependency that goes unnoticed until the final test suite fails.T2 runs after T0, but ordering alone does not check whether T0’s change is compatible with T2’s read.Source: §3 · p. 3
- Resolving these anomalies requires dependency tracking and merge strategies, not task ordering alone.The RAW failure persists despite T2 running after T0; WAW conflicts require reconciling concurrent writes.Source: §3 · p. 3
4 THE COST OF IGNORING DEPENDENCIES
The experiments show that unmodeled data dependencies produce coordination anomalies, while task complexity and the quality of dependency management shape whether parallel execution remains reliable. On Task 4, repairing dependencies with a conflict-ordered plan succeeds for both LLM agents and is faster than sequential execution.
Evaluation setup
- Across four SWE-Bench coding tasks, the study averages five runs using two LLMs and four execution topologies, with execution time, token use, cost, accuracy, and anomaly measures.The models were Claude Haiku 4.5 and Claude Opus 4.8; dynamic replanning was disabled.Source: §4 · p. 3
Missing data dependencies
- As harness parallelism increases, RAW violations and premature consumptions escalate; Opus produces more robust plans than Haiku, with fewer nodes and anomalies.A Haiku-Haiku setup had anomaly rates similar to Haiku-Opus, despite reduced time and token costs.Source: §4 · p. 3
- In Task 1, uncoordinated execution achieved up to 2.4× latency reduction and ∼26% cost savings, while detailed instructions already contained its load-bearing dependencies.In Tasks 2 and 3, limited diagnosis led all planners to defective plans regardless of topology; parallelism still reduced execution time.Source: §4 · pp. 3–4
Repairing broken data dependencies
- The repaired conflict-ordered Task 4 plan succeeded for both LLM agents and ran 1.23× faster than sequential execution at comparable token cost.The task-ordered topology was about 40% faster but sacrificed correctness and did not save tokens.Source: §4 · p. 4
5 THE THOUSAND FACES OF AGENTIC STATE
Agent state spans private agent-local state, orchestrator-managed state, and external systems, which differ in observability, reversibility, and reproducibility. A task footprint models its reads and writes across these scopes, where conflicts can arise dynamically.
State scopes
- The three state scopes differ in who can observe state, whether it can be reverted, and whether it can be reproduced after failure.The section identifies agent-local, orchestrator, and external state as the scopes compared in Table 2.Source: §5 · p. 4, Table 2 · p. 4
Agent-local state
- Agent-local state includes an agent’s changing context, tool-call status, and potentially private files or key-value storage; its context cannot be reproduced deterministically.After a crash, a restarted agent may need to redo reasoning or infer progress from partial local changes.Source: §5 · p. 4
Orchestrator and external state
- The orchestrator can log and revert its own state, while external state persists beyond the workflow and may require compensating actions or idempotent retries.External writes must be tracked for conflict detection; orchestrator-mediated blackboard accesses could in principle be checked for conflicts.Source: §5 · p. 4
Agent state footprints
- A task’s state footprint is its read and write sets across any state scope; two tasks conflict when one writes an item the other reads or writes.Because read/write sets emerge during execution, a sound approximation records everything observed through tool calls and task inputs.Source: §5 · p. 4
6 VISION AND RESEARCH CHALLENGES
The paper envisions orchestrators tracking task footprints and provenance to provide transactional guarantees across agent-local, orchestrator, and external state. It develops this vision through atomicity, isolation, recovery, reuse, and interfaces for external systems.
6 VISION AND RESEARCH CHALLENGES
- Footprints and provenance provide a shared basis for atomicity, isolation, recovery, and reuse, while enforcement mechanisms vary across state scopes.The orchestrator can relax individual guarantees when parallelism matters more than strictness; external-state enforcement must be exposed by the systems themselves.Source: §6 · p. 4
6.1 Atomicity and Reversibility
- A task may modify heterogeneous systems that must roll back together to the same logical point, without undoing concurrent agents’ effects.The vision propagates nested transaction identifiers to tools and systems, using snapshots where available and compensations otherwise; footprints scope aborts to affected writes and dependent tasks. Open questions include shared versioning conventions and abort granularity.Source: §6.1 · p. 5
6.2 Consistency and Isolation
- Because task footprints emerge during execution and invariants vary by task, orchestrators should detect conflicting schedules before publishing effects and support invariant-guided semantic recovery.A conflict invalidates the writes and decisions derived from them; open questions include specifying invariants, choosing read-tracking granularity, and balancing performance against accuracy.Source: §6.2 · p. 5
6.3 Durability and Fault Tolerance
- Agent replay is unreliable because reruns resample outputs and may repeat side effects, so recovery must account for the state scope and causal dependencies.The vision records provenance in a recovery log, restores or compensates effects by scope, and logs model outputs and tool responses for replay; open questions include checkpointing context and composing durability acknowledgments.Source: §6.3 · pp. 5–6
6.4 Reuse and Dynamic Replanning
- Footprints and provenance let orchestrators retain results whose read sets remain unchanged, replan by diffing plans, and serialize only newly conflicting tasks.Nested checkpoints could resume long-running agent loops at the last valid iteration; open questions concern reuse under nondeterministic reruns and checkpointing costs and granularity.Source: §6.4 · p. 6
6.5 Agent-Ready External Systems
- External systems must accommodate speculative, parallel, abort-heavy agent workloads, which can leave effects such as mistaken provisioning or payments difficult to undo.The proposed primitives include propagated transaction identifiers, tentative or compensable writes, read-conditioned writes, declared reversibility, and cheap state versioning or branching; open questions include protocols, retention, and compensation contracts.Source: §6.5 · p. 6
7 THE ROAD AHEAD
Footprints and provenance underpin the paper’s transactional guarantees, but the work focuses on coding agents, where git provides a natural transactional substrate. The authors argue that stronger models will not replace system-level coordination as agents take on longer, more parallel, and more consequential tasks.
7 THE ROAD AHEAD
- Footprints and provenance underpin all four guarantees, which can be relaxed independently when parallelism matters more than strictness.Atomicity uses write sets, isolation uses read and write sets, recovery uses provenance, and reuse uses read sets.Source: §7 · p. 6
- The study focuses on coding agents because git offers staging, atomic commits, and cheap rollback, while many other domains lack such a transactional substrate.Supply-chain operations, scheduling, and incident response may involve immediately visible and often irreversible effects.Source: §7 · p. 6
- The authors argue that stronger models will increase the state requiring coordination as agents take on longer tasks, more parallel work, and consequential side effects.They frame coordination, isolation, and recovery as system properties rather than model properties.Source: §7 · p. 6