CS Paper Radar

Commitment Hierarchies under Intent Revision: A Belief-Revision Account of Salvage in Tool-Use Agents

Spandan Ghose Chowdhury

cs.AI ·submitted 2026-09-28 06:23 UTC · v1
publishedtheory

Abstract

When a user changes their mind partway through a task, an agent that has already split the task into sub-goals and paid for tool calls must decide, per cached sub-result, whether to keep, patch, or discard it (salvage), restarting wastes valid work and continuing unchanged answers the old question. Our main finding is that salvage quality is a matter of role design rather than model capability: a language model asked the keep/patch/discard question one node at a time is unreliable, but asked to classify the revision once, with a deterministic layer propagating the decision, it reaches the cost-optimal oracle on all three models tested, from two vendors. Modeling the plan as a commitment hierarchy and the intent change as a belief-revision operator with AGM style postulates, we prove that no policy observing only a node's local view can be both safe and cost optimal, while the single classification design is both. Across three environments the policy recovers the full achievable savings, 43% cheaper than restart, at 100% correctness.

Comment
Accepted in the 27th International Conference on Principles and Practice of Multi-Agent Systems

Closest papers

Nearest neighbours by meaning across the whole index.

Invalidation Contracts for Cross-Episode Agent Memory

cs.AI ·2026-08-31 ·Michael Wu, Arquimedes Canedo
similarity 0.65
Abstract

LLM agents that cache recovery suggestions from API errors can skip re-derivation in later episodes, spending fewer tokens and fewer model calls on constraints they have already learned. Server-side data drift turns those cached fixes into silent failures, and the usual remedy, re-deriving on every episode, gives the savings back. We introduce invalidation contracts, a protocol layer that attaches version stamps and cacheability hints to every recovery suggestion so the client can evict stale entries without trial and error, and keep the rest. The contract decomposes realized savings into two independent factors: validity, the fraction of cached suggestions that remain correct after a drift event, and compliance, the fraction the planner applies on the first attempt. Validity depends only on the protocol and is vendor-independent. Compliance depends on the planner model: identical wire bytes yield 100% first-try compliance on Claude Haiku 4.5 and 11% or below on Claude Sonnet 5, which exhibits input-schema conservatism, refusing fixes that add fields the original request did not contain. We evaluate across seven models, three serving paths, two domains, and approximately 9,400 episodes. Row-level invalidation raises compliance by 0 to 66.7 percentage points across the seven models, 55.6 to 66.7 on three, and recovers 29-33% of baseline token cost on four of seven models, while table-level invalidation destroys co-located entries and drops post-drift first-try rates to 0% on five of seven. Eviction precision is 1.00 at row granularity on every model under the row-level oracle of Section 4.1. The contract adds 15% to response payload. Version-stamp validity is deterministic by construction and produced identical results across every model and serving path, with zero contract failures in the entire evaluation.

0.45

StateHarness: Maintaining Evolving Project State for Long-Horizon Coding Agents

cs.SE cs.CL ·2026-10-13 ·Chuan Zou, Yujun Zhou, Xiaonan Luo, Xiangliang Zhang
similarity 0.65
Abstract · 20 pages, 4 figures, 11 tables

Long-horizon coding requires agents to maintain an evolving view of the project they are changing: what problem is currently being solved, what has already been learned or modified, which other artifacts may be affected, and what work remains unresolved. When this information is scattered across a growing interaction history, local edits can become disconnected from their later consequences and progress can be difficult to carry forward. We introduce StateHarness, a runtime framework that maintains evolving project state without updating model parameters. The working agent records its current problem and hypothesis, important findings and decisions, discovered repository relationships, and unfinished work. Runtime support prompts record updates, searches for callers, tests, and documentation that may be affected by a change, and maintains a compact working brief for subsequent decisions. When behavioral signals accumulate, a separate diagnostic session revisits the recorded history and surfaces overlooked evidence. Across three repository-level evaluations, StateHarness improves task completion and several measures of change consistency. On RefactorBench, full-chain completion increases from 29.4% to 35.3% and cleanup-check accuracy from 87.0% to 95.4%. On five LHTB software-engineering tasks, mean reward improves from 0.427 to 0.576, exceeding LongHorizon-Harness at substantially lower recorded execution cost. On ChainSWE, bug-fix rate increases from 35.1% to 39.5% and residual debt decreases from 60 to 43 items, although pass-to-pass regressions increase. These results show that maintaining project state can improve long-horizon coding while introducing measurable execution and regression trade-offs.

0.20

When "Must" Becomes "Maybe": Erosion of Workflow Constraints in LLM Agent Handoffs

cs.AI cs.MA ·2026-08-25 ·Yiheng Sun, Huifei Wang, Yancheng Zhu, Zhenyu Li, Zebin Zhao +1 more
similarity 0.64
Abstract · 16 pages, 4 figures. Revised title, abstract, and exposition; expanded discussion and reorganized appendix

Large language model (LLM) agents build on one another's work through summaries, plans, and other intermediate artifacts. These records let a downstream agent continue without revisiting the complete upstream context. We uncover a hidden loss in this process: handoffs can carry tasks forward while eroding judgments already established upstream. A requirement that must be satisfied before action becomes a caveat that the next agent may acknowledge and set aside. The issue remains visible, but its role has changed. We define operational state preservation as retaining an established judgment's role in constraining downstream action. Safety blockers provide a concrete instance: an unresolved prerequisite restricts the admissible actions until the condition is resolved. In our experiments, we confirm correct upstream detection, hold source permissions fixed, and vary the handoff supplied to a local-view executor. Direct-state controls preserve every blocker, whereas compression, plan assimilation, convergence, ownership deferral, and precedent substitution repeatedly weaken them. Ownership deferral produces 76.7% blocker deactivation; multihop compression produces 97.2%. Measuring the transmitted state separately from endpoint action exposes two routes to behavioral recovery. In fixed-artifact replays, restoring the full blocker description raises recognition from 6.2% to 99.2% and reduces forbidden action from 85.2% to 0.0%. An authorization-check prompt instead reduces forbidden action to 1.6% while leaving artifact deactivation at 95.3%. A successful endpoint can therefore conceal a damaged handoff. These findings make maintaining earlier judgments a core capability of reliable collaboration: each stage must carry forward both what earlier work established and what it requires of subsequent action. Semantic availability does not guarantee operational preservation.

0.50

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

cs.AI ·2026-09-01 ·Ruoling Qi, Xuaner Wu, Penghang Liu, Jian Chen, Yirui Liu
similarity 0.64
Abstract

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\%.

0.33

Recovery Gone Too Far: Understanding and Repairing Risky Fallback in LLM Agents

cs.CR cs.AIcs.SE ·2026-11-15 ·Liwen Wang, Jiangrong Wu, Zongjie Li, Zongyi Lyu, Shuai Wang +1 more
similarity 0.63
Abstract

Large Language Model (LLM) agents interact with their environments through tools, reading repositories, running builds, and pushing code. When a tool fails with an ordinary error, such as a rate limit or a timeout, the agent can fall back to a substitute tool and still complete the task. However, the same fallback that completes a task in one environment can cross an action boundary in another. For example, after a push is rejected, a forced push in one repository replaces only the agent's own commits, while in a different repository it also removes another author's commits. We call such a fallback a risky fallback. To understand this phenomenon, we conduct an empirical study on 304 scenarios that span eight domains and cover 55 real CVEs. All four mainstream models we evaluate exhibit risky fallback, with action-boundary violations in up to 96.8% of risky scenarios. We further evaluate three mainstream mitigations and find that none of them is effective against risky fallback. We then present nrepair. At each call to the substitute tool, nrepair scores the agent's context with a monitor whose threshold is calibrated on normal runs alone; when the monitor triggers, it withholds the call once and returns the decision to the agent. nrepair reduces action-boundary violations on all four models, by up to 76.0% (from 67.5% to 16.2%), at a negligible runtime cost. On most models, the normal success rate drops by less than 7%. We also evaluate nrepair on two production agents, Claude Code and Codex, and find that it is equally effective on both.

0.28

From Approval to Execution: Reconstruction-Aware Repair Analysis for LLM-Agent Software

cs.SE ·2026-09-22 ·Junchi Zhu, Zhenguang Liu, Shaojing Fan, Jianhai Chen, Qinming He
highly cited similarity 0.63
Abstract

Approval mechanisms have become a primary safeguard for consequential actions in LLM-agent software. Yet the action shown for approval is often not the object ultimately consumed: workflow reload, transcript projection, argument rebinding, and durable-state lookup may reconstruct it before execution. Existing fieldflow and check-coverage analyses can establish that expected fields were inspected, but not that the inspected object version reaches the sink or that no replacement intervenes between check and use. Consequently, a locally complete repair may still leave a residual authorization bypass after reconstruction. We address this problem through three designs. (1) We formulate reconstruction-stable authorization (ReSA) over representation transitions, sink dependencies, consumed versions, and grant scope. (2) We derive obligations that judge candidate repairs and expose residual sink suffixes. (3) We implement the analysis in APAS-Finder and freeze predictions before an independent sink oracle observes execution. Predictions agree with all 28 controlled outcomes. Four matched pairs require opposite judgments despite identical field-flow and check coverage; a CodeQL composite recovers all eight when supplied object flow, dominance, interference, and the same grant contract. Two analysts agree on all four model-validation dispositions and 19/20 sink dependencies. On released consumers, five repairs prevent 60/60 tested out-of-scope effects, while three mechanism contrasts expose the predicted residual effects. Repair sufficiency therefore depends on the reconstructed action consumed, not merely on an approval record or earlier checked representation.

0.47

Revision-Aware Independent Agent Graphs for Dynamic Reasoning

cs.AI cs.CL ·2026-10-01 ·Yan Luo, Selim-Antoine Lali, Jeremy Moebel, Iliass Khoutaibi, Ahmadou Aidara +1 more
similarity 0.63
Abstract

Conventional reasoning protocols present a fixed, preselected task, so they cannot test whether an agent propagates relevant updates, preserves unaffected work, or reconstructs a historical task binding. We therefore study \emph{dynamic task routing}, in which an event stream revises task bindings and a system must select the document version valid at each query time before solving it. To study this problem, we repurpose six widely used benchmarks: MMLU, MMLU-Pro, MedMCQA, MATH, GPQA, and HumanEval into 31{,}119 dynamic episodes comprising 373{,}428 temporally categorized queries. This setting exposes a central trade-off: recomputing after every event wastes work, whereas unguarded reuse returns stale conclusions. We introduce the Revision-Aware Independent Agent Graph (RIAG), a bounded multi-agent policy that separates deterministic temporal resolution from task reasoning. RIAG caches solutions by immutable document identity, starts each fresh task with two unexposed attempts, and conditionally invokes audit and repair, using at most four calls per document version. On this collection, homogeneous RIAG achieves 54.24\% joint routing-and-answer accuracy at 0.62 calls/query, compared with 32.22\% at 18.00 calls/query for the strongest comparison method; heterogeneous RIAG reaches 49.78\% at 0.63 calls/query.

0.22

Suggested Is Not Superseded: A Pre-Registered Evaluation of a System-One Model as a Memory-Retirement Gate

cs.AI ·2026-10-11 ·Xupeng Chen, Chenqian Le
benchmark similarity 0.63
Abstract · 11 pages, 3 figures, 4 tables

Long-term memory for assistants needs a gate that decides when a new utterance retires an old stored claim. Benchmark labels for this step mark a pair as changed or not, so they cannot tell a gate that acts on established change from one that acts on a hint. We write a task contract that separates the two (SUPERSEDED vs. NEEDS-CONFIRMATION vs. COMPATIBLE), label 500 test pairs built from STALE (change pairs plus same-user controls) with three LLM annotators and two human adjudicators (one author and a second annotator; provenance reported), and evaluate Jev, a typed "System One" decision model, under pre-registered hypotheses. Of the 179 test pairs STALE marks as changed, 72 meet the contract's bar for an established change. Jev never retired a claim on 141 same-conversation non-changes. Its failure is premature retirement: the binary gate retires 39.2% of claims whose change is only suggested. A three-way decision cuts this to 15.5% at a 15.3-point detection cost, which misses our pre-registered 10-point budget, and it lands on the binary gate's own threshold frontier; these verdicts hold under three readings of the gold labels. On a held-out vault scored against a second annotator's labels, a cascade that escalated uncertain cases to a reasoning model and looked best on development data was indistinguishable from simply raising the threshold (premature retirement 26.8% vs. 6.5% on dev). Part of the gap comes from the gold labels: relative to that annotator's reading, LLM-majority gold shares most of its errors with a same-family escalation model, and an identity for binary labels says how much such shared errors hide. The rest is small-sample selection on development data. For builders this means a binary score should not be wired to delete: route suggested changes to pending evidence, and do not trust a cascade selected on development data of this size.

0.34