PaperlayerView exact revision on arXiv

Source-linked AI summary

DART: Semantic Recoverability for Structured Tool Agents

Ke Yang, Panpan Li, Zonghan Wu, Kejin Xu, Huaxi Huang, Xiaoshui Huang

arXiv:2605.23311v1cs.AI

TL;DR

Structured tool agents can reuse partial progress, but existing mechanisms do not establish whether local restoration remains valid after downstream work is committed. DART certifies recoverable boundaries and admits a local restore only when dependency and effect constraints permit it. It recovers evaluated commitment-sensitive cases missed by baseline local recovery, while the paper scopes its claims to observable failures and reviewed configurations.

  • Problem

    Existing recovery approaches lack a criterion for whether local restoration remains semantically valid when downstream work has already been committed.

    Source: §1 · pp. 1–2

  • Method

    DART localizes the failed instance, certifies its recoverable boundaries, aligns checkpoints to them, and selects an admissible restore point under dependency and effect constraints or blocks.

    Source: §1 · p. 2, §4.3 · p. 5, §4.5 · p. 6

  • Results

    DART recovers every evaluated commitment-sensitive scenario correctly where entry-only restore fails, and its advantage over built-in checkpoint restore is reproduced on LangGraph.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Controller legality alone does not establish semantic validity, and any runtime admitting all controller-legal local rollbacks can produce invalid executions in commitment-sensitive settings.

    Source: §1 · pp. 2–3

    The empirical claims are scoped to observable-failure recovery under reviewed boundary configurations and the current dependency abstraction.

    Source: §6 · p. 9

Abstract

from arXiv · show

When a structured tool agent fails mid-execution, the runtime faces a dilemma: replaying the entire task is safe but wasteful, while restoring from a local checkpoint is efficient but can leave committed downstream work tied to an upstream history that no longer exists. This tension is acute in commitment-sensitive settings, where rollback targets a single failed instance yet downstream consumers have already acted on its output. Existing recovery approaches provide mechanical rollback but no criterion for whether a local restore remains semantically valid after downstream commitment. We formalize this gap as semantic recoverability and address it in DART, a modular runtime that localizes the failed instance, certifies semantically recoverable boundaries of that instance, aligns checkpoints to those boundaries, and selects an admissible restore point that preserves committed downstream work under dependency and effect constraints-or blocks otherwise. Across three LLM-driven domains and external validation on a LangGraph-based substrate, DART correctly recovers all evaluated commitment-sensitive cases where baseline local recovery fails, and a five-domain safety audit finds no unsafe admitted rollbacks. These results show that controller legality does not imply semantic validity, and that sound local recovery requires an explicit admissibility check.

1 Introduction

Structured tool agents make partial-progress reuse possible, but existing recovery mechanisms do not determine whether a local restore remains semantically correct after downstream work is committed. DART checks that admissibility before restoring locally, recovering evaluated commitment-sensitive cases that baseline local recovery misses.

1 Introduction

  • Prior recovery methods either replay completed work through whole-task reruns or enable local restoration without checking whether preserved downstream commitments remain valid.The resulting gap is semantic admissibility, not merely whether a runtime can mechanically restore a state.Source: §1 · pp. 1–2, Figure 1 · p. 2
  • Controller legality does not guarantee semantic validity: a local restore can leave committed downstream work tied to an upstream history that no longer exists.In the scheduling example, already-sent invitations may refer to a time absent from any valid retry.Source: §1 · p. 2
  • DART localizes the failed instance, certifies a recoverable boundary, aligns checkpoints to it, and selects an admissible rollback target or blocks local recovery.When a step fails, DART falls back to whole-task rerun; the boundary must have no committed downstream work depending on the specific output being rolled back.Source: §1 · p. 2
  • DART recovers every evaluated commitment-sensitive scenario correctly, while entry-only restore fails and whole-task rerun incurs substantially larger replay.The contrast is also reproduced on LangGraph, where built-in checkpoint restore fails in the decisive case where DART succeeds.Source: §1 · p. 2
  • DART formalizes semantic recoverability, defines boundaries using four conditions, and argues that admitting every controller-legal local rollback necessarily permits invalid executions in commitment-sensitive settings.The paper also reports competitive performance outside those settings and no unsafe recoveries in a systematic safety audit.Source: §1 · p. 3

2 Related Work

Prior work supplies workflow repair, scoped rollback, or persistence and retry mechanisms, but generally leaves the recoverable unit, rollback boundary, or semantic admissibility criterion unspecified.

Recovery Units Assumed in Advance

  • Workflow-exception and runtime-repair approaches typically assume the recoverable object is authored in advance as an activity, exception scope, or service-level region.DART instead asks the runtime to identify a unique failed semantic instance before local recovery.Source: §2 · p. 3

Rollback Scope Assumed in Advance

  • Distributed snapshots, transaction recovery, nested transactions, sagas, and idempotent-effect patterns generally fix rollback scope in advance.The open question is whether a controller-legal local restore is admissible under current dependency and effect context.Source: §2 · p. 3

Persistence Without Semantic Admissibility

  • Graph runtimes and other systems expose persistence, retry, or fault-tolerance primitives, but do not define when local restoration remains semantically admissible.Related work also studies inspectable control structure [24], agent diagnosis and debugging [26] [27] [31], tool-failure self-correction [28], resilient multi-agent execution [30] [32], SagaLLM [29], and diagnosability.Source: §2 · p. 3
  • The unresolved questions are how to identify the recoverable unit, when a legal checkpoint is a valid recovery boundary, and whether persistence primitives suffice without dependency- and effect-aware admission.These gaps span assumptions about the recovery unit, rollback scope, and semantic correctness.Source: §2 · p. 3

3 Problem Setting and Scope

The paper studies explicit-control tool agents with observable action-boundary failures and instance-level recovery, using explicit FSMs as a transparent instantiation. Its current realization relies on reviewed recovery configurations and excludes several broader detection and rollback problems.

3 Problem Setting and Scope

  • The paper fixes the execution model, observable failure signal, and subtask-instance recovery unit as its problem setting.Explicit FSM control serves as a transparent canonical instantiation of the broader explicit-control class.Source: §3 · p. 3, §3.4 · p. 4

3.1 Basic Execution Model

  • The execution model uses explicit states and actions, legal transitions, runtime memory, and recorded step history; the recovery contribution is separate from the agent model architecture [24].Each step exposes at least a current state, executed action, successor state, and memory delta.Source: §3.1 · p. 4

3.2 Observable Failure Events

  • Failures are observable signals exposed at action boundaries, including tool exceptions, timeouts, governor denials, missing inputs, execution-chain exceptions, and contract violations.Silent-failure detection, latent semantic error discovery, and general root-cause diagnosis are outside scope.Source: §3.2 · p. 4

3.3 Subtask Skeletons and Subtask Instances

  • A subtask skeleton is a reusable template with reviewed identity, lifecycle, interface, and effect-policy fields; a subtask instance is a concrete occurrence identified by skeleton, entity, and ordinal.The instance, rather than the whole task or skeleton template, is the recoverable unit, including when a stage re-enters.Source: §3.3 · p. 4

3.4 Scope Commitments and Non-Goals

  • The study covers structured runtimes in the explicit-control class, instantiated with explicit FSM control and instance recovery; current recoverable boundaries come from reviewed configurations rather than automatic discovery.The system concentrates semantic review on audited boundary, interface, and effect objects; it does not address universal boundary synthesis or unrestricted rollback under arbitrary irreversible side effects.Source: §3 · p. 3, §3.4 · p. 4

4 Method

DART makes semantic recoverability an explicit four-step runtime procedure, determining whether a failed instance can be restored locally without invalidating surrounding execution. It certifies boundaries, aligns checkpoints to the instance, and selects an admissible restore point or rejects local rollback.

4.1 Method Overview: Four Recovery Questions

  • DART makes failed-instance localization, boundary certification, instance-aligned checkpointing, and admissible rollback selection explicit recovery questions.These decisions are necessary within the scoped setting studied to prevent semantically invalid recovery.Source: §4.1 · p. 5

4.2 Failed-Instance Localization: From Observable Failure to Failed Instance

  • The runtime identifies a unique failed subtask instance from observable state and tool information, falling back to whole-task rerun when localization is ambiguous.Later boundary, checkpoint, and rollback judgments are indexed by that instance.Source: §4.2 · p. 5

4.3 Recoverable-Boundary Certification: From Failed Instance to Certified Boundary

  • A boundary is certified only when the instance remains identifiable, its reviewed handoff is complete, replay stays within the instance, and the effect policy permits rollback.The runtime evaluates reviewed commit- and exit-level candidates rather than searching arbitrary legal states or transitions.Source: §4.3 · pp. 5–6

4.4 Instance-Aligned Checkpointing: From Certified Boundary to Stable Recovery Anchor

  • Instance-aligned checkpointing materializes certified boundaries as restore objects attached to the failed instance, keeping later search within that instance’s checkpoint set.Entry and commit checkpoints are considered by default; exit checkpoints are used only under an explicit policy.Source: §4.4 · p. 6

4.5 Admissible Rollback Selection: From Stable Anchor to Admissible Local Rollback

  • Rollback selection restores the latest stable checkpoint satisfying scope, committed-consumer, and effect-policy checks, or rejects local rollback if none qualifies.Committed downstream consumers that have consumed the failed instance’s outputs trigger a conservative veto.Source: §4.5 · pp. 6–7

5 Experiments

Across the evaluated commitment-sensitive core-domain cases, entry-only recovery fails while reviewed admissible checkpoints succeed; DART also succeeds in the decisive external LangGraph-based case. The evaluation reports safe-equivalent audited rows, calibrated blocking, and ablations that distinguish semantic admissibility from checkpointing alone.

5.1 Experimental Setup

  • The evaluation covers navigation, schedule-form, and diagnosis, with controlled failures at observable action boundaries and frozen boundary, interface/effect, and audit specifications.Four baselines are compared under a matched runtime and failure protocol; primary metrics include success, replay actions, latency, and preserved completed instances.Source: §5.1 · p. 7

5.2 In-Domain Recovery Results

  • In all evaluated commitment-sensitive core-domain cases, entry-only recovery fails while reviewed admissible checkpoints succeed.The same pattern persists across model families: COMP-FROZEN succeeds with one-step replay, while retry-only requires full upstream replay; outside this regime, COMP-FROZEN remains competitive and mostly at parity with stronger local baselines.Source: §5.2 · pp. 7–8, Table 1 · p. 8

5.3 Cross-Runtime External Validation

  • In the decisive schedule-form commitment-sensitive case, LangGraph-based checkpoint-aligned restore fails, while DART succeeds with a one-step replay frontier.Navigation and schedule-form entry-aligned rows serve as controls; the gap appears where recovery depends on semantic admissibility beyond checkpoint alignment.Source: Table 2 · p. 8, §5.3 · p. 8

5.4 Semantic Audit and Blocking Calibration

  • All 54 comparable rows are safe-equivalent, with 0/35 unsafe admissions and 0/12 audited false blocks across 47 calibration events.The audit reports five domains overall, with the main-text table showing the three core LLM-driven domains.Source: §5.4 · p. 8, Table 3 · p. 9

5.5 Ablation Studies

  • Ablations show coarse retry remains overly broad without instance-aligned checkpoints, legal points can fail boundary certification, and omitting committed-consumer blocking permits downstream-invalidating rollback.Together, these findings attribute DART’s gains to semantic admissibility rather than checkpointing alone.Source: §5.5 · p. 9, Table 4 · p. 9

6 Discussion and Limitations

The claims are scoped to observable-failure recovery in structured tool agents using reviewed boundaries and the current dependency abstraction. In high-stakes settings, safeguards remain important because mis-specified boundaries or aggressive rollback could conceal errors.

6 Discussion and Limitations

  • Claims cover observable-failure recovery in structured tool agents under reviewed boundary configurations and the current dependency abstraction.The authors frame this scope as a choice for auditability and transparency.Source: §6 · p. 9
  • In high-stakes settings, mis-specified boundaries or overly aggressive rollback could conceal errors, so reviewed boundaries, conservative blocking, and explicit effect policies remain safeguards.The authors characterize these safeguards as more than optimization choices.Source: §6 · p. 9

7 Conclusion

The conclusion presents DART as a way to assess semantic recoverability when downstream commitments are preserved, and reports improved correctness on decisive cases alongside reduced replay and no unsafe admitted rollbacks. The appendices map supporting evidence across robustness, external validation, and safety and mechanism audits.

7 Conclusion

  • DART improves recovery correctness on decisive commitment-sensitive cases where baseline local recovery fails, reduces replay relative to whole-task rerun, and admits no unsafe rollbacks in the reported audits.The conclusion also reports external LangGraph validation and a five-domain safety audit.Source: §7 · p. 9
  • Persistence primitives alone are insufficient when structured runtimes preserve downstream committed work; sound local recovery needs an explicit admissibility criterion.The authors present this as the broader conclusion of the paper.Source: §7 · pp. 9–10

Appendix D

  • The appendix roadmap assigns paired tests, no-failure overhead, and checkpoint-granularity diagnostics to Appendix E.These items are identified as support for latency and replay robustness questions.Source: A Appendix Roadmap · p. 11, Appendix D · p. 12

Appendix F

  • Appendix F tests whether commitment-sensitive rollback failures reappear when persistence and resume are available in LangGraph-based runtimes.The roadmap describes external LangGraph validation, a transportability check, and a blocking witness.Source: A Appendix Roadmap · p. 11, Appendix F · p. 12

Appendix G

B Cross-Model Decisive-Row Evidence

  • Table 6 reports that across tested model families, entry-only restore fails, frozen local recovery succeeds with one-step replay and zero upstream replay, and retry-only replays the full upstream prefix.The table covers the decisive schedule-form commitment-sensitive row.Source: B Cross-Model Decisive-Row Evidence · p. 11, Table 6 · p. 12

C Cross-Model Generalization Results

  • Table 7 covers cross-model generalization in a navigation commitment-sensitive row, a LangGraph-based schedule row, and an official schedule-form control case.It reports one representative recovery controller per model in each setting.Source: C Cross-Model Generalization Results · p. 12

D Benchmark Universe and Deterministic-Domain Generalization

D.1 Five-Domain Benchmark Universe

The benchmark spans three live-agent domains and two deterministic domains, with deterministic-domain results offered as a narrower generalization claim. In deterministic commitment-sensitive settings, COMP-FROZEN succeeds with one-step replay where entry-only recovery fails.

D.1 Five-Domain Benchmark Universe

  • The five-domain benchmark includes externally grounded LLM-driven navigation, schedule-form, and diagnosis, plus deterministic ETL and travel-planning domains.Travel-planning cases use frozen planning skeletons with explicit commit/exit predicates and controlled observable-failure sites; Table 9 reports success and replay behavior for the deterministic domains.Source: §D.1 · pp. 12–13, Table 8 · p. 13, Table 9 · p. 13

D.2 Deterministic-Domain Generalization

  • In deterministic commitment-sensitive settings, entry-only recovery fails while COMP-FROZEN succeeds with a one-step replay frontier and eliminates upstream replay.The authors describe this as a narrower generalization claim for the official setting.Source: §D.2 · p. 13

E Statistical Robustness and Efficiency

Paired tests confirm the main qualitative pattern, with the largest latency reductions in commitment-sensitive rows and significant headline-setting comparisons against RETRY-ONLY across three core domains. The appendix also reports modest recovery-readiness bookkeeping, a checkpoint-granularity diagnostic, and external LangGraph validation.

E.1 Paired Live Statistics

  • In navigation, COMP-FROZEN is statistically indistinguishable from Coarse-State-Retry and Comp-EntryOnly on failure-to-milestone latency (Holm-adjusted p = 0.18352 and 1.00000); in schedule-form, it retains selective latency improvements (p = 0.00060 and 0.00616).Against the stronger local baselines, replay, upstream replay, and preserved completed instances remain at parity in both domains.Source: §E.1 · p. 14
  • The official headline setting is significant against RETRY-ONLY in all three core LLM-driven domains, and paired tests show replay and upstream replay uniformly favor COMP-FROZEN.The latency table reports matched-run medians, paired median deltas with 95% bootstrap confidence intervals, and Holm-adjusted exact tests.Source: §E.1 · p. 14, Table 10 · p. 14

E.2 No-Failure-Path Overhead

  • Recovery-readiness bookkeeping remains small in absolute terms: the sidecar hook is on the order of tens of milliseconds, and peak serialized snapshots are around 12–15 KB.These measurements concern the currently instrumented setup; total no-failure wall-clock still reflects live-path variance.Source: §E.2 · p. 14, Table 11 · p. 14

E.3 Checkpoint Granularity Diagnostic

  • In the synthetic navigation checkpoint-granularity diagnostic, reviewed commit checkpoints sharply reduce replay once the admissible restore point lies beyond entry.The table notes that end-to-end latency is a synthetic harness estimate.Source: Table 12 · p. 14

F External Validation on LangGraph-Based Runtimes

  • The external validation tests whether commitment-sensitive rollback failures reappear when persistence and resume behavior are available in LangGraph-based runtimes.The two-domain overlay is external evidence, not part of the five-domain audit denominator; the runtime families use LangGraph execution and persistence primitives under a controlled benchmark protocol.Source: F External Validation on… · p. 15, Table 13 · p. 15

F.2 Regime-Aware Comparison

External validation shows that checkpoint-aligned recovery alone can fail when downstream work is committed, while DART’s admissibility checks preserve safe recovery behavior. The five-domain audit and mechanism checks examine the scope, calibration, and components underlying that result.

F.2 Regime-Aware Comparison

  • On schedule-form commitment-sensitive cases, RETRY-ONLY succeeds with 32618.41 ms and 25.5 replayed actions, LangGraph-SemiReal has 0.00 success, and DART succeeds with 1109.80 ms and 1.0 replayed action.The three-way comparison uses the shared regime-specific case intersection.Source: §F.2 · p. 15, Table 15 · p. 16

F.3 Semantic Equivalence

  • All comparable LangGraph-SemiReal versus DART pairs are safe-equivalent: 6/6 on the official track and 8/8 on the regime-balanced track.These are semantic-equivalence results, not latency measurements.Source: Table 16 · p. 16, §F.3 · p. 16

F.4 Mechanism Witness

  • Disabling committed-consumer blocking makes a producer-commit restore eligible but drops two committed consumers; the reconstructed LangGraph-style restore invalidates the same pair.With blocking enabled, DART rejects the rollback request because committed consumers are present.Source: Table 17 · p. 16, §F.4 · p. 16

G.1 Five-Domain Semantic Audit and Blocking Calibration

  • The five-domain audit distinguishes 54 comparable rows for safe-equivalence from 47 evaluated recovery events reaching the admissibility gate for blocking calibration.Human review freezes boundary, effect, and audit specifications; the authors do not claim an independent multi-annotator audit.Source: §G.1 · pp. 16–17, Table 18 · p. 17, Table 21 · p. 17

G.2 Failed-Instance Localization Audit

  • Across 270 repeat-level rows, observed recovery-scope prefixes and checkpoint types match their specifications in every row; weakening instance keys also exposes a schedule-form ambiguity that could erase a committed refined value.The offline ambiguity benchmark tests weakened identifiers, while the executable probes show concrete consequences.Source: §G.2 · p. 18, Table 23 · p. 18

G.3 Boundary Review Protocol and Boundary Evidence

  • Reviewer-burden evidence covers workflow-shaped reviewed-boundary domains, and the highlighted result is that review targets a much smaller set of candidate predicates and semantic annotations than the raw FSM size suggests.Timed reviewer telemetry is available for Schedule Form.Source: §G.3 · pp. 18–19, Table 26 · p. 19

G.4 Failure-Signal Normalization and Snapshot-Depth Efficiency

  • The failure-signal matrix reports unchanged admissibility decisions and recovery signatures when raw observable signals vary at fixed sites; the schedule-form depth summary reports slower growth for registry-only storage with restore cost in the same order of magnitude.The supplied passages describe these checks but provide no numerical values for the depth comparison.Source: Table 28 · p. 20, Table 29 · p. 20, §G.4 · p. 20

G.5 Property-Wise Necessity Decomposition

  • Dependency-blocking witnesses and forced-override audits show why admissibility is needed both to preserve committed downstream semantics and to avoid replay across irreversible effect boundaries.The property-wise decomposition maps each Eq. (6) conjunct to counterexamples or audit evidence for its removal.Source: §G.5 · p. 20, Table 30 · p. 20

H Proof Sketches for the Semantic Soundness Theorems

The proof sketches distinguish controller legality from semantic recoverability and establish why committed-consumer conflicts must block local rollback. Under the stated checkpoint-ordering assumption, selection returns the latest admissible checkpoint.

H Proof Sketches for the Semantic Soundness Theorems

  • A controller-legal edge is not a recoverable boundary if any of decidability, closure, separability, or controllability fails for the associated instance.The proof sketch notes that controller legality establishes controller-level reachability but cannot supply a missing recoverability condition.Source: H Proof Sketches for the Semantic… · pp. 20–21
  • Rolling back a producer while leaving a committed downstream consumer in place, without compensation, invalidation, or joint rollback, cannot guarantee semantic equivalence; sound local recovery must block it.The argument assumes the committed consumer semantically depends on the producer’s output.Source: H Proof Sketches for the Semantic… · p. 21
  • When stable checkpoints are totally ordered by recency and at least one checkpoint is admissible, Eq. (10) selects the unique latest admissible checkpoint.Any checkpoint later than the selected one is inadmissible under the stated assumption.Source: H Proof Sketches for the Semantic… · p. 21

I Reproducibility and Additional Experimental Details

  • DART is realized as an online runtime sidecar rather than an offline trace analyzer, using reviewed boundary configurations, step lifting, named checkpoints, dependency tracking, and rollback selection.The realization is attached to the agent’s online recovery path.Source: I Reproducibility and Additional… · p. 21

I.1 Runtime Realization Details

DART attaches a recovery sidecar to the agent loop to identify failed instances, track dependencies, and select admissible checkpoints. Its interfaces are conservatively assembled from explicit manifests and reviewed annotations rather than inferred from arbitrary black-box runtime behavior.

Runtime realization

  • DART realizes failed-instance identity, reviewed recoverable boundaries, modular checkpoints, and admissibility checks in a runtime sidecar attached to the normal agent loop.It is an online recovery component, not an offline trace-analysis layer.Source: §I.1 · p. 21, Figure 3 · p. 22

Step records and interfaces

  • The sidecar lifts execution steps into recovery-aware records with resolved skeleton and instance identities, step-level read/write sets, and optional named checkpoints.The current realization assembles read/write sets conservatively from explicit state/action manifests, planner maps, and reviewed tool-I/O or effect annotations.Source: §I.1 · pp. 21–22

Dependency tracking

  • Instance-level write and read aggregates derive conservative producer-consumer edges, while committed-consumer detection may block otherwise admissible rollbacks because the interfaces over-approximate possible reads and writes.This conservatism is part of the stated safety envelope.Source: §I.1 · p. 22

Restore path

  • The registry-only path stores the instance registry, reconstructs snapshot-manager bookkeeping at restore time, and resumes from the chosen named checkpoint and sidecar state.Figure 3 summarizes this path.Source: §I.1 · p. 22, Figure 3 · p. 22

Runtime requirements and evaluation context

  • The method operates at the runtime-recovery layer and requires explicit state transitions, action boundaries, and step histories; the reported benchmarks include official and commitment-sensitive regimes across three core LLM-driven domains.The paper’s contribution is not a new language model or prompting method.Source: §I.1 · pp. 22–23
Loading 2605.23311v1…