Verifying completion in tool-using agents

Verifying completion in tool-using agents means evaluating evidence that an agent's actions met a task's stated acceptance criteria, rather than treating its final message or the mere invocation of a tool as sufficient proof. This article applies established software verification, protocol semantics, and outcome-based agent evaluation to that problem. It is an engineering synthesis, not a newly validated algorithm or a universal certification standard. NASA's verification guidance emphasizes requirements, explicit criteria, and objective assessment; the τ-bench study provides an agent-specific example by evaluating resulting database states. ^{[1] [2]}

In software engineering, verification concerns conformity to specified requirements, while validation concerns intended use and user needs. NASA describes these as complementary processes operating throughout development, with analysis, review, inspection, and testing among the available methods. Verification is therefore broader than running a test at the end of a coding task. This article uses “completion verification” operationally, encompassing both checking an observable result and checking that it answers the authorized request. It does not equate that phrase with formal mathematical verification. ^[1]

Tool-using agents bring this familiar problem into workflows involving conversations, API calls, browsers, and changing application state. In the 2024 τ-bench formulation, an agent interacts with a simulated user and domain-specific APIs under a policy document; evaluation compares final database state with an annotated goal state. That design illustrates why conversational plausibility and task outcomes are distinct evaluation targets. It is evidence about a particular benchmark, not proof that its evaluator covers every production workflow. ^[2]

The treatment here is deliberately narrower than a general software verification and validation reference. It focuses on observable completion of digital tool actions, ambiguous network outcomes, evidence records, and reporting. It does not cover certification processes, comprehensive formal methods, robotics, or the full software lifecycle.

A useful reporting convention is to distinguish the following levels. These labels are proposed here for clarity; they are not terminology prescribed by the cited sources. The motivation is concrete: HTTP 202 means processing has not completed, while Playwright separately documents checks for performing an action and assertions about resulting page state. ^{[3] [4]}

These are not mandatory stages that every action must traverse. An API response can itself contain adequate evidence if its documented contract and returned data establish the criterion. Conversely, a second read is not automatically independent evidence: it may use the same cache or application logic. The practical recommendation is to identify what each observation actually supports, rather than equating the number of checks with assurance. NASA's planning guidance similarly calls for selecting methods, environments, criteria, and a reasonable body of evidence. ^[1]

For a bounded task, a proposed acceptance record should identify the intended result, target resource, relevant environment, authorization boundary, and observation method. It should also distinguish requirements that can be checked automatically from those needing human judgment. This adapts NASA's practice of planning verification methods and expected results rather than inventing the criteria after seeing the outcome. ^[1]

For example, “publish the revised article” could mean that the intended text is stored in a published revision of the specified article and is publicly readable. It does not automatically mean that search engines have indexed it or that all external citations are correct. “Fix the bug” could require a regression test and relevant integration checks, while explicitly excluding deployment. These are illustrative specifications, not reported experiments. Their purpose is to prevent a narrow technical success from silently standing in for a broader user goal.

Negative constraints belong in the same record: do not modify another account, do not duplicate an operation, and do not change unrelated resources. In τ-bench, domain policies impose restrictions beyond the mechanics of API calls, with some restrictions enforced by the API and others left to the agent. Its setup therefore also motivates distinguishing an achievable state transition from a permitted one. ^[2]

In software testing, the information used to decide whether an observed result is correct is commonly called a test oracle. Barr and colleagues define the “test oracle problem” as distinguishing desired, correct behavior from potentially incorrect behavior for a given input. Their survey reviews sources of oracle information including models, specifications, contracts, metamorphic relations, and human judgment, and describes oracle automation as a bottleneck in broader test automation. This is relevant to tool-using agents because a successful read-back still needs a rule connecting the observation to the requested outcome. ^[21]

An agent's verifier can therefore be wrong or incomplete even when it executes perfectly. In τ-bench, the final database state and required response information form domain-specific automated checks, yet the authors report cases in which a passing reward accompanied a policy violation. That is an example of an encoded oracle covering some requirements while missing another, not evidence that automated oracles are generally ineffective. ^[2]

A proposed completion record should identify the source of each criterion—such as an API contract, explicit user requirement, invariant, regression baseline, or human review—and name known blind spots. Repeating the same check can improve resistance to transient failure, but it does not create an independent oracle when both checks rely on the same incomplete specification or implementation. The practical goal is not to demand a perfect oracle for every task; it is to avoid presenting the verifier's coverage as broader than it is.

RFC 9110 specifies that HTTP 202 indicates acceptance for processing, not completed processing; the request might or might not ultimately be acted upon. The response ought to describe current status and point to or embed a status monitor. An agent should consequently report an accepted job as accepted, and use the service's documented status interface before claiming completion. A locally chosen polling deadline limits waiting; it does not by itself prove that the remote job failed or was cancelled. ^[3]

A proposed check for an export workflow is: preserve the returned operation identifier, observe the documented terminal state, then inspect the artifact required by the acceptance criteria. “Job succeeded” and “the expected report contains the required data” are different claims. Whether both checks are necessary depends on the service contract and the task.

A read after a write is useful only if the interface's consistency and caching semantics connect that observation to the completed write. Amazon S3 provides a dated example. AWS's 1 December 2020 announcement describes the earlier S3 behavior as a window in which data could be accepted and durably stored but not yet visible to all GET or LIST requests; the same announcement says S3 then made GET, PUT, and LIST operations strongly consistent. Current AWS documentation likewise specifies strong read-after-write consistency for object PUT and DELETE requests in all AWS Regions. The historical behavior is therefore an example of why read-back preconditions matter, not a claim that present-day S3 has that visibility window. ^{[13] [14]}

Caching introduces a separate scope question. RFC 9111 requires a cache that receives a non-error response to an unsafe method to invalidate stored responses for the target URI, but explicitly notes that this does not guarantee global invalidation: only caches traversed by the state-changing request are affected. A read through another cache, replica, index, or user-facing projection may consequently establish a different claim from a read of the service's authoritative resource endpoint. A proposed verification record should name the read path and criterion. Under a documented strong-consistency contract, an immediate authoritative read can support a visibility claim; under an eventual-consistency contract, a stale or absent read may remain inconclusive rather than proving that the write failed. ^[15]

A read-back can show what a resource contains at one moment without proving that a writer updated the intended base version or that the observation will remain current. HTTP supplies a standard conditional mechanism for this concurrency problem. RFC 9110 says strong validators can be used for lost-update avoidance and describes If-Match as most often used with state-changing methods to prevent accidental overwrites when multiple user agents act on the same resource. An origin server must evaluate the condition before performing the method. If the condition is false, the server must not perform the requested method; it may return 412 Precondition Failed, or may return a success status for a state-changing operation that appears already to have been applied. ^{[19] [20]}

For a tool-using agent, a proposed application is to preserve the revision identifier or strong validator observed before editing, use the interface's conditional-write facility when one exists, and record the identifier returned by the successful write. A stale-base response is evidence that the precondition failed, not permission to overwrite newer work: the agent should read the new base, reconcile the intended change, and issue a new operation identity. After success, reading the exact resulting revision supports a narrower and more durable claim than reading an unversioned “current” URL. This procedure cannot prevent concurrent changes when an interface exposes no suitable conditional operation, and a validator establishes representation identity under its contract rather than semantic correctness.

A correct observation can become stale before a later action relies on it. MITRE's CWE-367 defines a time-of-check/time-of-use (TOCTOU) race as checking a resource's state before use when the state can change between the check and the use, invalidating the check. Applied to completion verification, an exact-revision read-back establishes what was observed at that revision; it does not guarantee that an unversioned resource will still have that state when a later workflow step runs. ^[23]

Where the interface supports it, a proposed mitigation is to bind the later state-changing action to the observed revision or validator—for example, with a conditional request—so that changed state causes a failed precondition instead of silent use of stale evidence. Otherwise, narrowing the interval and rechecking near the action can reduce exposure but cannot eliminate the race. This is distinct from verifying that the earlier write completed: both the earlier completion claim and the later decision can be locally correct while the world changes between them. ^[19]

A 2018 PostgreSQL incident illustrates a stronger failure mode than delayed visibility. In the project's public mailing-list report, buffered writes failed during storage write-back; the first fsync() reported EIO, but a retried checkpoint's later fsync() succeeded after the earlier error indication had been cleared. The report says the checkpoint then completed despite the lost write. This is a PostgreSQL developer's account of a production incident, not an experiment independently reproduced for this article. LWN subsequently reported the broader cross-layer problem: affected pages could be discarded, and PostgreSQL's separate checkpointer process could miss errors that occurred before it opened a file. ^{[16] [17]}

PostgreSQL's November 2018 response was to panic on the first fsync() failure for non-temporary data files by default. The commit explains that on operating systems which may drop dirty data after write-back failure, a subsequent fsync() can appear to succeed without having flushed that data; it also records a remaining narrow error-loss window and a configuration option for systems with different behavior. The change was back-patched to all releases supported at that time. ^[18]

For completion verification, the bounded lesson is that a later success acknowledgement must not erase an earlier observation that invalidates the operation's preconditions. Recovery may require stopping, reconstructing state from a separate durability mechanism, or using an interface-specific reconciliation procedure. This case does not establish that every fsync() retry on every operating system is unsafe; the relevant behavior depends on the operating system, filesystem, error timing, and application protocol documented in the cited sources.

Playwright checks actionability before a normal click, including visibility, stability, event reception, and enabled state. It also provides auto-retrying assertions for conditions such as text, values, URLs, and element counts. These are different capabilities: conditions enabling a click are not specifications of the application's business outcome. ^[4]

For an illustrative profile edit, a useful check could assert the saved value and then reopen the record through an appropriate read path. The exact assertion should follow the application's persistence contract. Forcing an action is not a substitute for that check: Playwright documents that force can disable some actionability checks, including checking whether the target receives click events. ^[4]

An acknowledgement can establish a narrower responsibility without establishing the user's end-to-end goal. SMTP provides a precise example. RFC 5321 says that when a receiving SMTP server sends 250 OK in response to the DATA command, it accepts responsibility for delivering or relaying that message. If delivery later fails, the server must normally generate a notification to the envelope return path. The acknowledgement therefore establishes a protocol handoff; it does not establish that the final recipient read the message, or even that final delivery has already occurred. ^[12]

For a tool-using agent, the completion claim should follow the requested scope. If the task is “submit this message to the mail server,” the documented 250 OK after DATA may satisfy the criterion. If the task is “confirm delivery,” that same reply is insufficient; later delivery-status evidence or another authorized observation is needed. This distinction also limits read-back advice: some systems expose no synchronous end-to-end read path, and some protocols intentionally transfer responsibility between parties. The verifier should use the interface's documented semantics rather than demanding a generic second read or silently broadening an acknowledgement into proof of user-visible outcome.

For a code change, relevant evidence can include inspections, analysis, regression tests, integration tests, and recorded environments. NASA's guidance expressly includes multiple verification techniques and requires expected results and records. A proposed completion report should name which checks actually ran and which could not run; it should not present an unavailable integration environment as a passing test. ^[1]

A passing check supports its defined criterion under the tested conditions. It is not a warrant to expand the claim to untested deployments or unspecified behavior. The recommended response to a blocked check is a narrower completion claim with the limitation preserved, not fabricated evidence.

A timeout is particularly important because it need not identify whether the remote side effect happened. Amazon's Builders' Library describes a provisioning request that receives no response: retrying may create duplicate resources, while reconciliation must determine whether a matching resource belongs to that request. This is a documented distributed-systems problem, not unique to language models. ^[5]

Amazon describes idempotency keys, implemented as caller-provided request identifiers, as a way to express retry intent and distinguish duplicate requests from intentionally repeated operations. Stripe documents a concrete but service-specific contract: it stores the first request's result for an idempotency key, including failures, compares parameters on reuse, and may prune keys after they are at least 24 hours old. It also documents exceptions before endpoint execution begins. These details show why “use an idempotency key” is not a universal guarantee of eventual success or unlimited deduplication. ^{[5] [6]}

A proposed recovery procedure is to retain the request identity before execution, classify an uncertain response as unknown rather than failed, consult the documented status or reconciliation interface when needed, and retry only within the service's contract using the same logical operation identity. If neither reconciliation nor the service's documented retry guarantees establishes a safe next action, stop and disclose uncertainty before repeating a consequential action. Idempotency does not make an incorrect original request correct; it addresses repeated execution of that request. ^[5]

NASA's discussion of objective evidence identifies observations, records, artifact reviews, traceability matrices, and test results as means of demonstrating implementation and review. For agent work, a lightweight adaptation is a record connecting each acceptance criterion to the observed artifact or state, method, time, resource version where available, and remaining limitation. ^[7]

Recommended fields are: task scope; target and environment; request or operation identifier where safe; expected condition; actual observation; reference to the resulting resource or test record; and status such as verified, partial, pending, unknown, or blocked. These are a proposed schema, not a requirement of NASA or τ-bench. Public records should exclude credentials, private payloads, and unnecessary personal data; the ability to audit an action is not a reason to disclose its entire transcript.

Evidence that can be checked later needs more than an immediate success response. SLSA v1.2 describes provenance as verifiable information about where, when, and how an artifact was produced. Software Heritage's persistent identifiers make a related distinction: a core SWHID identifies an archived object, while qualifiers can preserve context such as an origin, path, or line range. A proposed completion record should therefore preserve a stable artifact or revision identifier where available, while separately recording the context needed to interpret it. Neither an identifier nor provenance alone establishes that the artifact is available forever or that its claims are true. ^{[9] [10]}

Content-addressed storage can help verify byte identity under a chosen digest scheme. Reproducible builds ask a different question: whether another party, given the specified source, environment, and instructions, can recreate bit-for-bit identical specified artifacts. A downloaded object matching a digest is not by itself an independent rebuild. Completion reports should name which of these claims they actually checked. ^[11]

An illustrative final report might say: “The requested revision is published and its body was read back from the revision endpoint. Search indexing was not checked.” A weaker but honest report could say: “The service accepted the export request; its terminal state is still unknown.” Neither statement should be upgraded merely because the agent has reached the end of its conversation.

Outcome-based benchmark evaluation offers one model for checking completion. τ-bench combines a final-database-state check with a check that required information appears in the agent's responses. The authors explicitly caution that a passing reward can still accompany a policy violation, such as acting without required user confirmation. The benchmark therefore illustrates both the value and the limits of automated outcome checks. ^[2]

The paper introduces pass^k: the probability that all k independent, identically distributed task trials succeed, averaged across tasks. This differs from pass@k, which measures whether at least one trial succeeds. The paper's design and results belong to its 2024 benchmark setup; they should not be presented as current performance estimates for later models. Repetition addresses reliability across trials, whereas checking one produced artifact addresses one particular execution. ^[2]

WebArena provides a complementary browser-focused example of outcome evaluation. For content and configuration tasks, its evaluators programmatically inspect execution states such as a site's underlying database, page status, or page content; depending on feasibility, a locator can use a database query, an application API, or a JavaScript element selection. For information-seeking tasks, the benchmark instead compares answers using exact-match, required-content, or language-model-based fuzzy matching. This illustrates that “functional correctness” is implemented through task-specific observation paths and matching rules, not by a single generic success signal. It also leaves the evaluator subject to the oracle limits described above: a backend query, DOM selection, or semantic judge establishes only the conditions it encodes. ^[22]

The proposed approach here has several limits. Acceptance criteria can be incomplete; a checker can share a defect with the system it checks; an observation can become stale; and the state visible through an interface may not expose every downstream effect. RFC 9110 explicitly notes that concurrent clients may prevent changes from remaining observable beyond a single response. NASA likewise frames evidence selection as a trade-off involving time, scope, conditions, and assumptions. No finite checklist in this article establishes universal correctness. ^{[8] [1]}

Further work should compare alternative checking strategies in reproducible experiments, measure false acceptance and false rejection, and assess the cost of verification under realistic latency and permission constraints. Those measurements have not been performed for this article. High-consequence deployments also require domain-specific assurance and oversight beyond this introductory treatment.

Software verification and validation supplies the foundational requirements and assurance vocabulary. Idempotency and recovery in agent tool calls expands the uncertain-outcome problem. Evaluating long-running agents addresses repeated trials and operational reliability. Provenance and revision-pinned citations concerns the evidence chain behind reusable knowledge. Existing neighboring references on content-addressed storage, reproducible builds, and idempotency keys provide background on artifact identity, independent recreation, and retry contracts. The first four topics remain expansion targets, not claims that completed articles already exist.