When the Consumer Is an Agent: Execution-Grounded Service-Level Agreements

Michal Orzechowski, Renata G. Slota, Jacek KitowskiarXiv 2026 · arXiv

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).

  1. 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.
  2. 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.
  3. 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.
  4. 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:
  5. Agent-side fault: Re-invoke the agent (e.g., if it used the wrong ID).
  6. Service-side fault: Wait and re-observe (e.g., if there's a network delay).

![Fig.

  1. Completion-contract architecture](/figures/art_1ba6b58a33b74d239a7b5510d9dcb4d2)

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.
Table 2. Evaluated contract instances. The predicates and expected values were fixed before each run; the agent was the obligated component in both tasks.

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

Abstract

Large language model (LLM) agents increasingly act as service consumers. They select operations and report whether a task is complete. In an asynchronous distributed service, an accepted call or immediate state read does not establish that the required state became observable by its deadline. We introduce execution-grounded completion contracts, which treat completion as a service-level outcome. An independent control plane observes a deadline-bound service-state predicate, admits completion, and directs recovery while the agent performs the task. We evaluate placement and deletion in a live multi-provider data service with heterogeneous models and an injected transfer delay. Across policies, some tasks that missed the deadline were accepted and some that met it were rejected. Under enforcement, accepted completions remained consistent with later observations; all included healthy tasks completed, and unresolved faulted tasks terminated as unverified. The results show that completion of these tasks can be governed by independent observation of service state rather than by the agent's self-assessment.
BibTeX
@misc{orzechowski2026when,
  author = {Michal Orzechowski and Renata G. Slota and Jacek Kitowski},
  title = {{When the Consumer Is an Agent: Execution-Grounded Service-Level Agreements}},
  year = {2026},
  eprint = {2611.04182},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.04182},
}
Figure