PaperlayerView exact revision on arXiv

Source-linked AI summary

REVISE: Validity-Guided Recovery for Online Revisions in Agent Workflows

Ruoling Qi, Xuaner Wu, Penghang Liu, Jian Chen, Yirui Liu

arXiv:2609.00643v1cs.AI

TL;DR

Agent revisions create a correctness–efficiency trade-off: restarting protects latest-version correctness but discards progress, while reuse risks stale outputs and effects. REVISE uses provenance-guided recovery over a partially executed DAG, stopping invalid work and revalidating reused results. It matches a latest-version oracle without stale outputs or effects while reducing recomputation and improving serving goodput.

  • Problem

    Online revisions can change requirements, intermediate results, or control decisions, while existing restart and suffix-recomputation strategies discard unaffected progress and reuse can propagate stale work.

  • Method

    REVISE intersects revision deltas with recorded data and control dependencies, propagates impact through the executed DAG, selectively recomputes affected work, and revalidates reused outputs and effects before commit.

  • Results

    REVISE matches a latest-version oracle without stale outputs or effects and reduces model calls by 40.6–56.0% versus full restart and 31.3–43.6% versus suffix recomputation.

  • Takeaways & Limitations

    Real traces expose online intervention opportunities, while provenance-guided selective recovery preserves additional progress when revisions are local.

  • Takeaways & Limitations

    Offline traces lack token-level progress and dependency-complete execution state, so they cannot establish how much computation is avoidable.

Abstract

from arXiv · show

Agent revisions expose a fundamental correctness--efficiency trade-off during concurrent execution. Discarding ongoing work preserves latest-version correctness but wastes progress that may remain valid, whereas reusing prior work preserves efficiency but risks propagating stale state into outputs and tool effects. Existing recovery strategies resolve this trade-off in an imbalanced way with coarse-grained policies: they either favor efficiency by allowing potentially stale work to continue, or favor correctness by restarting the workflow or recomputing a linear suffix from the earliest conflict, thereby discarding unaffected progress. We present \textsc{Revise}, a validity-guided runtime for fine-grained recovery in structured agent workflows. When a revision arrives, \textsc{Revise} first intersects its delta with recorded data and control dependencies and propagates the resulting impact through the partially executed DAG to identify affected work. It then stops invalid work, preserves validity-established progress beyond the earliest conflict, and recomputes only the affected region. Incomplete provenance conservatively expands recovery, while reused results are revalidated before commit. Analysis of real coding-agent traces show online recovery opportunities: 118 sessions retain observable work before a queued later message is delivered; across 167 overlapping assistant responses, enqueue-to-completion overlap reaches 56.55~s at p95. Across 300 challenging revision/commit executions, \textsc{Revise} matches a latest-version oracle with no stale outputs or effects. On unmodified LangGraph and LLMCompiler applications using Qwen3-14B, it reduces model calls by 40.6--56.0\% relative to full restart and by 31.3--43.6\% relative to suffix recomputation. Under serving pressure, it further reduces revision-to-correct-completion tokens by 13.26\% and improves SLO goodput by 3.07--5.43\%.

1 Introduction

Online revisions create a correctness–efficiency trade-off because restarting preserves latest-version correctness but discards progress, while reuse can propagate stale work. REVISE addresses this with validity-guided, fine-grained recovery and shows correctness and substantial efficiency gains.

  • Motivation: Online revisions can invalidate ongoing or completed work, making latest-version correctness compete with preserving useful progress.Existing alternatives either allow potentially stale work to continue, restart entirely, or recompute a linear suffix from the earliest conflict.
  • REVISE: REVISE propagates revision impact through recorded data and control dependencies in the executed DAG, recomputing only affected work.It stops invalid work, preserves validity-established progress beyond the earliest conflict, and conservatively expands recovery when provenance is incomplete.
  • REVISE: REVISE revalidates reused outputs and staged tool effects against intervening revisions before commit.This makes reuse provisional rather than automatically trusted.
  • Results: 40.6–56.0% fewer model calls occur relative to full restart, and 31.3–43.6% fewer relative to suffix recomputation.The evaluation uses unmodified LangGraph and LLMCompiler applications with Qwen3-14B.
  • Results: 13.26% fewer revision-to-completion tokens and 3.07–5.43% higher SLO goodput occur under GPU serving pressure.Across 300 adversarial executions, REVISE also matches a latest-version oracle without stale outputs or effects.

2 Revision opportunities and the limits of offline evidence

Real coding-agent traces show that revisions can arrive while execution is still in flight and may be local enough for partial recovery. However, offline traces cannot certify which apparently unaffected work remains valid, motivating online provenance checks.

  • Evidence: SWE-chat evidence combines reconstructed execution timelines with manual semantic audits because timing alone does not establish that a later message is a revision.Static issue-resolution benchmarks lack interleaved revisions and execution timelines.
  • Temporal opportunity: 118 of 5,825 analyzable sessions retain observable work before a queued later message is delivered.Among 657 sessions with a matched queued-revision signal, these cases contribute 174 work-bearing queued-revision events.
  • Temporal opportunity: Overlap duration reaches 5.54 s at the median, 56.55 s at p95, and 853.16 s at maximum among assistant responses within intervention windows.These measurements establish that a runtime can sometimes stop ongoing work early.
  • Locality: The audit found 3 L0, 10 L1, and 6 L2-candidate revisions, plus one with no useful intervention window.The sample was intended for taxonomy construction, not prevalence estimation.
  • Evidence limits: Offline traces cannot certify safe reuse because they lack artifact versions and complete data/control provenance.Apparently independent branches may still depend on revised artifacts or control decisions.

3 REVISE

REVISE models workflows as dependency-aware DAGs and determines when earlier attempts remain reusable. Reuse requires validity of their reads, control decisions, parent work, and publishable effects.

  • 3 REVISE: Earlier attempts are reusable only when their data reads, control decisions, parent work, and publishable effects remain valid.A revision to plan.budget invalidates attempts that read it but need not affect independent attempts without that dependency.
  • 3 REVISE: A workflow is represented as a DAG whose nodes may invoke models, tools, verifiers, routers, or joins.Semantic artifacts carry monotonically increasing versions, while read selectors identify paths and whether reads provide data or control execution.

C CONTINUE join revalidate ✓ ✓ commit

REVISE identifies revision-affected work from provenance, assigns lifecycle actions, and recomputes only what cannot be shown valid. Commit-time certificate checks and staged effects prevent provisional or obsolete work from publishing.

  • Impact analysis: REVISE intersects revision deltas with recorded reads and traverses active descendants to form an impact set and recovery plan.The plan records direct taint, affected nodes, unsafe effects, and supporting evidence.
  • Lifecycle actions: The recovery plan assigns each node one of five actions: cancel, avoid, recompute, continue, or reuse.Continue and reuse retain only work supported by available validity evidence.
  • Recovery scope: Complete provenance enables affected-subgraph recomputation, while weaker evidence expands recovery to a suffix or full restart.Irreversible or incompletely covered effects require explicit handling or block execution.
  • Commit-time revalidation: Revision-time reuse remains provisional because a revision can precede an attempt’s final read.Each attempt runs on an immutable snapshot and accumulates a certificate.
  • Commit-time revalidation: At commit, REVISE checks post-start deltas, current parents, and staged effects; conflicting, unknown, or obsolete attempts are rejected.Later invalidation can also remove dependent outputs and revocable or versioned effects before recomputation.

4 Evaluation

Evaluation across replay, adversarial executions, and serving experiments shows that REVISE preserves latest-version correctness while reducing recomputation relative to restart and suffix baselines. Its serving benefit is pressure-dependent, and unavailable fine-grained provenance causes conservative full-restart behavior.

  • Correctness and effect safety: 15,939 executions match the latest-version/full-restart oracle with no stale outputs or committed effects.The adversarial matrix covers ordering races, late reads, consecutive revisions, unknown provenance, membership changes, and control-route invalidation.
  • Work reduction: 56.0% fewer model calls than full restart and 43.6% fewer than dynamic suffix occur on LangGraph.Model-wall time falls by 62.7% and 50.2%, respectively.
  • Work reduction: 40.6% fewer model calls than full restart and 31.3% fewer than dynamic suffix occur across 48 LLMCompiler workflows.Tokens fall by 7.9% and 5.8%, respectively.
  • Scope boundary: All 48 cases lacking fine-grained provenance recover equivalently to full restart.Dynamic suffix uses the same provenance as REVISE, isolating gains to recovery granularity.
  • Repository replay: 12.94% less recomputation and 10.38% less discarded completed work occur across 18 repository-replay configurations.All 180 executions remain equivalent in final output, pytest, file/patch state, and visible effects.
  • Serving pressure: 13.26% fewer revision-to-correct-completion tokens and 14.70% less model-wall time occur under 50% revised requests relative to suffix.Serving goodput gains increase under contention, while work reduction remains stable across load.

5 Related work

Prior work addresses rollback, dependency tracking, effect-aware checkpointing, scheduling, execution overlap, KV editing, and sandbox restoration. REVISE distinguishes itself by applying validity decisions to partially executed agent DAGs and revision/commit races.

  • Revision and rollback recovery: Revisable by Design and other recovery systems roll back traces, checkpoints, or execution context after conflicts or errors.DART additionally considers dependencies and effects when admitting checkpoints.
  • Foundations and substrates: Self-adjusting computation provides dependency propagation, while REVISE extends that perspective to partially executed agent DAGs with cancellation and staged effects.The extension also addresses revision/commit races.
  • Foundations and substrates: AIOS, SGLang, Agentix, PASTE, Leyline, DeltaBox, and Crab provide scheduling, overlap, KV-span editing, or sandbox-restoration substrates rather than fine-grained revision recovery.These systems form complementary infrastructure around the recovery problem.

6 Conclusion

REVISE targets correct online revision handling without unnecessarily discarding valid progress. Its validity-guided recovery preserves supported work, recomputes affected regions, and maintains latest-version correctness while improving efficiency under contention.

  • Conclusion: REVISE identifies affected work from revision deltas and dynamic data/control dependencies, then stops invalid work and recomputes only affected regions.Incomplete provenance expands recovery conservatively, and outputs and staged effects are revalidated before commit.
  • Conclusion: Experiments across applications, repository replays, event orderings, and serving-pressure settings show latest-version correctness without stale outputs or effects.The evaluation also reports reduced unnecessary recomputation and improved serving efficiency under contention.

A.1 Online revision opportunity in SWE-chat

Observable work can remain in progress before queued revisions are delivered, creating opportunities for online intervention in SWE-chat workflows.

  • Online revision opportunity: 118 sessions retain observable work before a queued revision is delivered.These sessions contain 174 work-bearing queued-revision events.
  • Online revision opportunity: 173 events from 117 sessions have complete enqueue and delivery timestamps.The retained events support timing analysis of revision opportunities.
  • Audit cohort: The audit cohort contains 30 events spanning 29 sessions and 24 repositories.It includes all nine rare strict-overlap events and seven assistant-only events from each duration stratum.

A.2 Latest-version correctness

REVISE is evaluated against latest-version correctness under challenging revision and commit orderings and on reviewer-triggered repository issues.

  • Challenging event orderings: 300 runs exercise both possible orderings between revision and commit.Across all runs, REVISE matches the latest-version oracle without stale outputs or effects.
  • Challenging event orderings: Certificate validation costs 0.0026 ms p50, 0.0076 ms p95, and 0.0344 ms maximum across 800 commit checks.These measurements quantify the validation overhead used before commit.
  • Repository-grounded correctness: Repository-grounded correctness is evaluated on 30 reviewer-triggered issues from 20 repositories.The official verdict is joined to a reference Patch@v2, and a three-task canary reruns the official evaluator under all three policies.
  • Repository-grounded correctness: The repository-grounded experiment tests recovery correctness rather than patch quality.A separate local Qwen3-14B canary resolves 0/3 tasks, so no claim is made that REVISE improves patch generation.

A.3 Selective recovery efficiency

Selective recovery reduces recomputation while preserving latest-version correctness across LangGraph, LLMCompiler, and repository-grounded workloads, with benefits depending on revision frequency and provenance precision.

  • LLMCompiler portability: All 288 LLMCompiler runs match the latest-version oracle with no stale outputs or effects.All 48 local-identity cases remain selective, while all 48 cases lacking fine-grained provenance recover equivalently to full restart.
  • Revision-frequency sensitivity: 12–14% per-revision completion-token and model-wall reductions persist at nonzero revision fractions across 24,000 workflows.Aggregate benefit increases with the controlled revision fraction, while the sweep does not estimate production prevalence.
  • Provenance sensitivity: 50.0%, 81.7%, and 100% recomputation-to-active-work ratios occur under complete, half, and unknown provenance.Half coverage falls back to full-equivalent recovery for 60% of revised requests, and unknown provenance does so for 100%.
  • Provenance sensitivity: Complete provenance in the unmodified 10-node LangGraph application recovers all five expected recomputation sets without full-restart fallback.As provenance becomes less precise, recovery expands conservatively rather than reusing work whose validity cannot be established.
  • Serving pressure: The serving matrix evaluates 0.7–1.3× measured capacity, including intentional overload, across four single-H100 replicas and 64 tenant namespaces.It uses Qwen3-14B with SGLang 0.5.13 and evaluates 1.4, 1.8, 2.0, 2.2, and 2.6 workflows/s.
  • Framework integration: The unmodified LangGraph and LLMCompiler applications require adapters without application edits or selector annotations.The LangGraph wrapper captures six expected leaf reads, while the LLMCompiler adapter captures 1,584 explicit selector instances.
Loading 2609.00643v1…