TL;DR
LLM agents often hallucinate task completion, especially in complex distributed systems where "success" signals don't always mean the job is actually done. This paper introduces execution-grounded completion contracts—an independent, deadline-aware control plane that verifies actual service state to ensure an agent's "done" really means "done."
What Problem Does This Paper Address?
As LLM agents move from simple chat to acting as "service consumers" (e.g., managing cloud files, triggering API workflows), we face a reliability gap. In asynchronous distributed systems, a tool call might return a "success" code immediately, but the actual data might take seconds or minutes to propagate across the network.
Current agents are prone to false success: they invoke a tool, see a green light, and prematurely report to the user that the task is complete, even if the final state hasn't been reached or a deadline was missed. Existing safety mechanisms usually govern what an agent does (actions), but they don't authoritativeley verify the outcome (state). The authors tackle the "oracle problem": how to provide an authoritative, independent judgment of task completion that doesn't rely on the agent's own fallible self-assessment.
Methods
The authors propose a service-control model that separates task execution (the agent) from completion authority (an independent verifier).
- Completion Contracts: Before a task starts, an operator instantiates a contract containing a machine-checkable state predicate (e.g., "file X exists at site B"), a deadline, and a recovery policy.
- Independent Verifier: A deterministic program that polls the backend service state on a fixed grid. Crucially, it operates outside the agent's context and doesn't see the agent's internal reasoning—only the resulting service state.
- Completion Gate: A logic gate that only releases the agent's "done" report if the verifier confirms the state predicate was met before the deadline.
- Attribution-Based Recovery: If a deadline is missed, the system analyzes agent-side and service-side evidence to attribute the failure. It then triggers specific recovery actions:
- Agent-side fault: Re-invoke the agent (e.g., if it used the wrong ID).
- Service-side fault: Wait and re-observe (e.g., if there's a network delay).

Datasets
The study doesn't use a static dataset; instead, it evaluates performance on a live Onedata federation, a real-world eventually consistent data management service.
- Tasks: The evaluation focused on two primary task types: Placement (replicating a file to a specific site) and Deletion (removing a file from all sites).
- Models: Seven LLMs from five families were tested, including GLM-4/5, Qwen3, Gemma-4, Claude 3.5 (Haiku/Sonnet), and Llama-3.3.
- Fault Injection: To test deadline enforcement, the researchers injected a 35-second transfer delay into a system with a 30-second task deadline.
Key Insights and Ideas
- Separation of Concerns: By moving completion authority to an independent control plane, the system treats completion as a service-level outcome rather than a conversational claim.
- The Asynchrony Trap: The results highlight that "report-time" reads (checking state exactly when the agent says it's done) are insufficient. You need continuous observation over a time window to handle eventual consistency.
- Heterogeneity Management: Different models have different success rates and costs, but the completion contract provides a uniform reliability bar. A weaker model might trigger more retries or higher latency, but the gate ensures it cannot report a false success.
- Attribution Works: The system was able to correctly attribute 100% of observable evidence cases to the injected fault, allowing for automated, targeted recovery instead of blind retries.
Key Results
- Zero False Successes: Under enforcement (the "gated" mode), 0% of admitted completions were later contradicted by service state.
- Self-Report Unreliability: In healthy trials, agents self-reported completion for 21 tasks that actually violated the deadline (false passes). In the faulted trials (with the injected delay), the self-report false pass rate jumped to 66%.
- Recovery Effectiveness: The system recovered 52% of healthy first-attempt failures and 95% of faulted trials through its automated recovery mechanisms.
- Low Overhead: Implementing the completion gate added only 5–17% to the total model spend, a small price for guaranteed state verification.
Limitations and Future Work
- Contract Derivation: The study used pre-defined templates for contracts. The authors note that automatically deriving these contracts from free-form natural language goals is a significant open challenge.
- Ambiguous Evidence: In some cases (like failed control-API calls), attribution is difficult. The authors suggest that "not-attributable" should be treated as a first-class outcome in production systems.
- Multi-Stage Workflows: The current model handles single tasks. Future work is needed to explore how deadlines and recovery policies compose across complex, multi-stage agentic workflows.
Summary updated