Source-linked AI summary
From Version Conflicts to Decision Conflicts: Selective Revalidation for Long-Running AI Agents
Yongjian Lyu, Yang Ren, Ruofei Lai, Wenting Liu
TL;DR
Long-running agents may act after the state supporting a decision has changed, and version checks alone cannot determine whether that change invalidates the action. ATR records executable premises, selectively revalidates affected conditions, and binds checked state to commit. Across controlled executions, it matched every developer-specified outcome, but the evidence remains limited to deterministic, developer-authored conditions rather than production generality or automatic premise extraction.
Problem
Long-running agents can act much later on state that has changed, while version checks alone do not reveal whether the pending action remains justified.
Method
ATR records typed decision premises and dependencies, rechecks only affected conditions, and uses target-side transactions or compare-and-set to bind checked state to execution.
Results
ATR produced the oracle outcome for every controlled trace, with 0 false allows and 0 false blocks.
Takeaways & Limitations
Recording evidence-to-effect dependencies and binding checked target tokens can retain harmless decisions while blocking invalid ones within the evaluated scope.
Takeaways & Limitations
The evidence is limited to one host, deterministic workloads, and developer-authored premises and ground truth; it does not measure production change distributions or automatic premise extraction.
Abstract
from arXiv · showhide
Long-running AI agents may read state, reason, wait for tools or human approval, and perform an external action much later. The state that justified the action can change in the meantime. For example, after an agent proposes an 80 GBP refund under a limit of 100, a customer-name change affects only presentation metadata, a new limit of 90 still permits the refund, a limit of 50 invalidates it, and a refund issued by another worker must prevent a duplicate. Standard optimistic concurrency control and version checks can detect that previously read state has changed, but by themselves do not determine whether that change invalidates the pending action's justification. We call any detected version change a version conflict; when that change invalidates the action's justification, it is also a decision conflict. ATR records the explicit, executable conditions that justify a pending action and rechecks only the conditions affected by a change before releasing the external operation. It can retain the action, refresh non-decisive metadata, require replanning, or block execution; a target-side transaction or compare-and-set binds checked state to commit. Across 210,000 controlled executions over 15 mutation cases, ATR matched every developer-specified outcome with no false allows or blocks. In ten durable SQLite checkpoint/resume cells, it evaluated 0.6 conditions per change versus 6.0 for FullScan. At 4,093 recorded reads, ATR took 9.3 microseconds versus 2595.9 microseconds for FullScan. These deterministic results establish controlled feasibility, not production generality or automatic extraction of the required conditions.
1 Introduction
Long-running agents can act on state that changes during reasoning, waiting, or approval, while version checks alone cannot tell whether the pending decision remains justified. ATR records executable decision conditions, selectively revalidates affected conditions, and binds permitted actions to target-side checks.
- Long-running agents separate state reads from later external actions across reasoning, tools, approvals, retries, and resumptions.A refund proposal may remain valid after a display-name change or a limit decrease to 90, but not after a limit decrease to 50 or a duplicate refund.
- Version checks detect changed state but do not determine whether the changed field matters to the pending action.Existing concurrency mechanisms remain responsible for target-local atomic updates, while agents may reason across databases, APIs, documents, and pauses.
- ATR records decision facts and executable conditions, then rechecks only affected conditions before releasing the external operation.The target database or API still enforces atomic execution; ATR does not claim global serializability or exactly-once execution across unrelated systems.
- ATR distinguishes version conflicts from decision conflicts and provides four operational outcomes with target-side checked-state binding.The paper evaluates an executable prototype for safety, selectivity, scaling, races, and dependency omission.
2 Model and Semantics
ATR models pending agent actions as dependency-linked decisions supported by typed, executable premises. A changed read triggers localized validation whose outcome can preserve, refresh, replan, or block an action, subject to explicit binding and safety assumptions.
- Agent Transactions and Premises: An agent transaction links reads, decisions, intents, and effects in a dependency graph used to compute the affected closure.A reverse index locates changed reads, and validation traverses downstream nodes that can reach a pending action.
- Agent Transactions and Premises: A typed premise records evidence fields, a deterministic validator, failure severity, and validator or policy version.Premises encode conditions that must remain true for a decision or action to stay justified; free-form rationale is not itself an ATR premise.
- Agent Transactions and Premises: A required premise is one whose failure changes the operational response, while binding tokens identify evidence versions the target can check atomically.Decision consistency holds when required premises evaluate true, except for explicitly refreshable non-decisive metadata; commit-time safety applies only to bound evidence.
- Validation Outcomes: Validation outcomes follow the dominance order BLOCK > REPLAN > REFRESH > KEEP.This ordering determines which operational response prevails when multiple premise outcomes apply.
- Version and Decision Conflicts: A version conflict triggers inspection, whereas a decision conflict occurs when current evidence falsifies or makes unverifiable a required premise.For the refund, a limit of 90 yields KEEP, a limit of 50 or an existing refund yields BLOCK, a display-name change yields REFRESH, and a corrected defect flag yields REPLAN.
- Conditional Safety and Localization: ATR’s conditional safety depends on complete dependencies, sound validators, faithful tokens, observation binding, and atomic target enforcement.Under these assumptions, an effect with a false block-critical premise covered by the binding set cannot commit through the ATR gate.
- Conditional Safety and Localization: Affected-closure traversal is confined to the recorded dependency subgraph, while conservative edges may visit irrelevant nodes and missing edges are unsafe.With exact reverse-index lookups, the stated traversal cost is O(|A_c| + |V_c| + L).
3 Runtime Design
ATR localizes validation to changed evidence and binds the checked result to target-side effect enforcement. Its design also marks the boundaries where external resources, crashes, and incomplete dependencies require stronger mechanisms.
- Change localization: ATR uses reverse-indexed dependencies to revisit only affected decisions or premises rather than scanning all provenance.Object or field capture may revisit every premise on a selected decision, while predicate capture can target explicitly indexed premises.
- Validation pipeline: At PRE_EFFECT, ATR rereads required evidence, computes version differences, validates affected premises, and applies the highest status under BLOCK > REPLAN > REFRESH > KEEP.Conditional application proceeds only when the resulting status permits the effect.
- Boundary conditions: When dependency attribution is uncertain, ATR links supplied inputs conservatively, but omitted or unsound premises cannot be repaired automatically.Authority- or irreversible-effect-critical cases fail closed through REPLAN or BLOCK.
- Effect binding: Target-local checks pass validated versions into transactions, CAS operations, constraints, leases, or domain commands to close the time-of-check/time-of-use gap.External policy, budget, or authorization changes require transaction binding or an equivalent reservation, capability, lease, or fencing token.
- Boundary conditions: ATR supplies decision provenance but does not handle crashes after external effects, partial multi-system effects, or non-idempotent APIs.Those concerns remain in workflow, recovery, or compensation mechanisms.
4 Prototype and Methodology
The prototype evaluates ATR through deterministic refund, cloud-remediation, procurement, and durable-workflow scenarios against baselines and controlled mutation outcomes. The methodology separates semantic correctness from selectivity, latency, durable integration, races, and binding limitations.
- Prototype: ATR was implemented as a Python 3.11 runtime with immutable records, typed validators, reverse indexes, append-only logs, and target version-token checks.SQLite harnesses cover target races, checkpoint/resume, and cross-resource commit conditions.
- Workloads: Three deterministic workloads use five mutations each: irrelevant, presentation-only, predicate-preserving, replanning, and authority- or target-critical blocking changes.The oracle is the explicit business rule defining each mutation category, not an LLM label.
- Durable evaluation: Durable workflow cells checkpoint to SQLite and introduce intervening changes from a second actor, including irrelevant, presentation-only, predicate-preserving, replanning, and blocking cases.The cells test durable checkpoint/resume behavior under controlled semantic changes.
- Evaluation design: The evaluation measures invalid effects, oracle agreement, unnecessary replans, closure size, serialized bytes, and in-process validation latency.FullScan re-evaluates all recorded typed premises, whereas ATR uses reverse traversal.
- Metric scope: Table 3 conditions unsafe-release and safe-replan rates on their respective mutation classes, while premises/change and p50 latency use durable-cell and in-process measurements.These metric scopes prevent direct interpretation as unconditional rates or end-to-end workflow latency.
- Experimental scale: 210,000 executions repeat 15 semantic mutation cases across seven balanced schedules, alongside SQLite races, fail-closed validator tests, and dependency-omission fault injection.The repetitions test deterministic outcome agreement and runtime variation rather than representing 210,000 distinct scenarios.
5 Results
ATR matched the declared oracle outcomes while selectively revalidating affected premises, with lower validation work and better scaling than FullScan. The evaluation also tests race handling and shows that safety depends on complete dependency capture.
- Controlled safety and selectivity: ATR produced the oracle outcome for every trace, with 0 false allows and 0 false blocks, while retaining or refreshing 84,000 safe intents.NoCheck released 126,000 invalid effects, whereas VersionAbort replanned all 84,000 safe changes.
- Durable workflow cells: 0.6 typed premises per resumed change were evaluated by ATR, versus 6.0 for FullScan across ten durable workflow cells.FullScan and ATR matched all 100 executions per method in the reported durable cells.
- Cost and granularity: At 4,093 recorded reads, ATR took 9.3 microseconds, whereas FullScan took 2595.9 microseconds.ATR changed from 8.8 to 9.3 microseconds as unrelated reads increased from 13 to 4,093; FullScan rose from 12.1 to 2595.9 microseconds.
- Evaluation overview: Figure 2 reports exact four-way outcome agreement across ten durable workflow cells and runtime scaling against recorded reads.The runtime plot uses log–log axes and 95% confidence intervals over seven repetitions.
- Scope: The reported microbenchmark is limited to a single process; distributed-store and connector latency remain unmeasured.
- Races and failure modes: Across 7,000 SQLite race pairs, exactly one update committed per pair, while checked policy tokens rejected all 100 cross-resource invalid effects.The target-only compare-and-set committed all 100 effects after the policy limit became false.
- Races and failure modes: Selective validation is safe only when dependency capture is complete or conservatively over-approximated.Omitting the sole critical dependency produced false-allow rates of 0.95%, 5.05%, and 9.97% at 1%, 5%, and 10% omission.
6 Related Work
Related systems address transaction execution, agent concurrency, semantic continuity, admission, effect release, and recovery. ATR instead occupies a narrower decision-validation layer between observation and external effect.
- Data execution: Database isolation, OCC, semantic serializability, and ATCC govern data execution or transaction schedules, not whether changed business evidence invalidates pending reasoning.
- Agent concurrency: CoAgent orders peers and repairs writes, whereas ATR checks the stated conditions for one pending action without ordering agents or repairing visible writes.
- Semantic continuity: SemIso protects compatibility among prompts, models, indexes, policies, and tools across durable continuations; ATR checks whether mutable business evidence still supports an action.
- Admission and recovery: Mnemosyne, Cordon, Atomix, Sagas, and Agentic Transaction address proposal admission, staged-effect release, progress, recovery, or broader semantic transaction architecture.
- Decision validation: ATR asks whether changed evidence falsifies a condition supporting a pending action, then relies on the target system for atomic commit.
7 Limitations and Conclusion
The evidence is deliberately narrow: ATR demonstrates controlled feasibility under authored deterministic conditions, while the conclusion identifies dependency tracking and target-side binding as the basis for retaining harmless changes and blocking invalid ones.
- Limitations: ATR was evaluated on one host with deterministic workloads, developer-authored validators and ground truth, and incomplete upstream task-pattern runs.
- Limitations: The study does not measure natural-language premise extraction, model replanning quality, distributed failure, or production change distributions.
- Limitations: Conservatively linking all supplied inputs can avoid missing-edge false allows, but it cannot compensate for an omitted or unsound premise.
- Conclusion: ATR records evidence-to-effect dependencies, revisits the affected closure, and binds checked target tokens to retain harmless decisions while blocking invalid ones.
- Conclusion: For cross-resource premises, the guarantee requires a transaction or explicit reservation or lease mechanism covering the external evidence.
- Conclusion: The next step is integration with a durable agent framework and transactional connectors, followed by evaluation on production-derived traces with measured extraction error.
Generative-AI Use Disclosure
OpenAI Codex supported prototype scaffolding, review, figure generation, and language editing, while human authors retained responsibility for the submitted artifacts and claims.
- Use: OpenAI Codex was used for prototype and code scaffolding, experiment-script review, figure generation, and language editing.
- Verification: Executable rules and evaluation labels were developer-authored, and reported aggregates were independently recomputed from raw checkpoints.
- Responsibility: The human authors inspected and took responsibility for all submitted code, data, citations, and claims.
Artifacts
The public artifact provides the complete prototype, experiment materials, outputs, and reproduction commands for the study.
- The GitHub artifact contains the complete Python prototype, workload and mutation definitions, tests, checkpoints, raw data, outputs, audit reports, scripts, and figure sources.It also includes summary JSON, binding traces, editable figure sources, and exact reproduction commands.
- The experiment runs with Python 3.11 and NumPy without network access.