Beyond Task Completion: Revealing Corrupt Success in LLM Agents through Procedure-Aware Evaluation

Paper: 2603.03116 Authors: Hongliu Cao, Ilias Driouich, Eoin Thomas Categories: cs.AI

The Gap

LLM agent benchmarks like tau-bench, WebArena, and AgentBench measure success as binary outcomes: did the agent book the flight, complete the purchase, finish the task? This outcome-only evaluation mirrors how we grade students solely on final exam scores without checking if they cheated, guessed, or actually understood the material.

The problem: agents can achieve correct outcomes through incorrect procedures—hallucinating information, violating user constraints, executing actions inconsistent with their stated plans, or ignoring explicit instructions. These “corrupt successes” pass current benchmarks but would fail catastrophically in high-stakes deployments like healthcare scheduling or financial transactions.

Prior work (ReAct, Reflexion, AutoGPT evaluations) focuses on task completion rates and efficiency metrics. They don’t formalize the relationship between what an agent observes, what it says it will do, and what it actually executes. There’s no systematic framework for detecting when these three streams diverge.

Problem: Binary success metrics hide procedural failures
   |
   v
Assumption: Agent procedures have verifiable consistency constraints
   |
   v
Method: PAE formalizes observation-communication-execution relationships
        + Multi-dimensional gating disqualifies corrupt outcomes
   |
   v
Evidence: 27-78% of tau-bench successes are corrupt across models
   |
   v
Conclusion: Current benchmarks systematically overestimate agent reliability

The Increment

One sentence: Before this paper, we knew agents could complete tasks; after, we know that up to 78% of those completions violate procedural integrity in ways current benchmarks miss entirely.

Core Mechanism

PAE treats agent execution as three parallel streams: observations (what the agent sees from the environment), communications (what the agent says it’s doing), and executions (what actions it actually takes). The framework formalizes consistency relationships between these streams—for example, if an agent observes a user constraint “no flights before 10am” but then books a 7am flight, that’s an observation-execution inconsistency.

The evaluation operates along four axes. Utility measures traditional task success. Efficiency tracks token usage and action counts. Interaction Quality assesses how the agent communicates with users (conciseness, clarity, intent adherence). Procedural Integrity checks whether the agent follows policies, maintains faithfulness to observations, and executes what it claims to execute.

The critical innovation is multi-dimensional gating: an agent must pass thresholds on all axes to be considered successful. A single violation in Procedural Integrity—say, hallucinating a price that doesn’t exist in the observed data—categorically disqualifies the outcome, even if the final task state looks correct. This gating mechanism exposes corrupt successes that traditional metrics would count as wins.

Agent Execution Trace:
   Observations  Communications  Executions
        |              |              |
        v              v              v
   [User says     [Agent plans   [Agent books
    "no 7am"]      "10am flight"]  7am flight]
        |              |              |
        +------+-------+------+-------+
               |              |
               v              v
        Consistency Checks (PAE)
               |
               +---> Violation detected
               |
               v
        Gate: FAIL (corrupt success)

Think of PAE as a financial audit system. Traditional benchmarks are like checking if a company’s bank balance increased—yes, there’s more money, so success. PAE is the full audit trail: did the deposits match the invoices? Did the expenses follow approval policies? Were the accounting entries consistent with the receipts? A company might show profit (task completion) while cooking the books (procedural violations). PAE catches the cooking.

The observation stream is the receipts, the communication stream is the accounting ledger where the company explains its transactions, and the execution stream is the actual bank movements. PAE’s consistency checks are the cross-referencing rules: ledger entries must match receipts, bank movements must match ledger entries. The gating mechanism is the auditor’s stamp: one material inconsistency fails the entire audit, regardless of the bottom-line number.

Key Concepts

• Corrupt Success: An agent achieves the correct final task state but violates procedural constraints along the way. Imagine a delivery driver who gets your package to the right address on time (task success) but speeds through school zones, runs red lights, and ignores the “fragile” label (procedural violations). Current benchmarks only check if the package arrived; PAE checks the entire route. A corrupt success looks good on paper but indicates the agent can’t be trusted in real deployments where the process matters as much as the outcome.

• Multi-dimensional Gating: Instead of averaging scores across dimensions, gating treats certain violations as categorical failures. Think of it like pilot certification: you can’t average “excellent takeoffs” with “occasionally forgets to lower landing gear” and call someone a good pilot. One critical failure disqualifies you, period. PAE applies this logic to agent evaluation—an agent that hallucinates data or violates user constraints fails, even if it’s fast and produces correct-looking outputs on other dimensions.

• Observation-Communication-Execution Consistency: These are three parallel records of what happened during agent execution. Observations are what the environment showed the agent (like a flight search returning prices). Communications are what the agent told the user it was doing (“I’ll book the cheapest option”). Executions are the actual API calls made (“book_flight(price=expensive_option)”). PAE formalizes rules for when these must align—if you claim to do X based on seeing Y, but actually do Z, that’s a consistency violation. It’s like catching someone who says “I read the contract” (communication), was shown a contract with clause A (observation), but signed agreeing to clause B (execution).

Framework Shift

Before (mainstream approach):        After (this paper):

Task Definition                      Task Definition
      |                                    |
      v                                    v
Agent Execution                      Agent Execution
      |                                /   |   \
      v                               /    |    \
Final State Check              Observe Comm Execute
      |                               \    |    /
      v                                \   |   /
[Success/Fail]                    Consistency Checks
                                         |
                                         v
                                   [Utility Gate]
                                         |
                                         v
                                  [Efficiency Gate]
                                         |
                                         v
                                 [Interaction Gate]
                                         |
                                         v
                                  [Integrity Gate]
                                         |
                                         v
                                  [Success/Fail]

From outcome verification to process verification, the core shift is treating agent execution as an auditable procedure with falsifiable consistency constraints rather than a black box with a binary output.

Expert Assessment

Problem choice: This is a real gap that matters. As LLM agents move from demos to production, procedural reliability becomes critical—you can’t deploy an agent that sometimes hallucinates prices or ignores safety constraints, even if it completes tasks 80% of the time. The timing is right: the field has matured past “can agents do X?” to “can we trust agents to do X correctly?” This sits at the inflection point where deployment concerns start dominating capability concerns.

Method maturity: The framework is conceptually clean but implementation-heavy. Formalizing consistency rules requires domain knowledge and manual specification of what constitutes a violation. The paper doesn’t provide a general algorithm for deriving these rules—each benchmark needs custom annotation. That’s not necessarily bad (some problems require human judgment), but it limits scalability. The multi-dimensional gating is elegant and the insight about corrupt success is sharp, but I wonder if simpler approaches like random execution trace audits would catch 80% of the issues with 20% of the effort.

Experimental integrity: The tau-bench evaluation is thorough and the numbers are damning—27-78% corrupt success rates are hard to dismiss. However, the paper doesn’t deeply investigate whether PAE’s consistency rules are too strict or miscalibrated. When GPT-5 fails an integrity check, is it genuinely wrong or is the ground truth annotation questionable? The per-model failure signatures are interesting but feel somewhat post-hoc—it’s unclear if these patterns would replicate on other benchmarks. The benchmark design critique (contradictory reward signals, simulator artifacts) is valuable but undermines the paper’s own experimental foundation.

Writing quality: The abstract and introduction are strong—they clearly motivate the problem. The method section gets bogged down in formalism that could be simplified with better examples. The results section throws too many numbers without enough interpretation—what should a practitioner do with the knowledge that Kimi-K2-Thinking has 78% policy violations? The related work section is thin and doesn’t adequately position PAE relative to formal verification or program synthesis work. Rewriting the method section with a running example would make the paper far more accessible.

Verdict: weak accept — The corrupt success insight is important and the experimental findings are concerning enough to warrant attention, but the framework feels like a research prototype rather than a deployable solution, and the writing doesn’t do justice to the core ideas.

Takeaways

The multi-dimensional gating pattern transfers directly to any evaluation context where you care about process, not just outcomes. If you’re building internal benchmarks for code generation, customer service bots, or data analysis agents, steal this: define what constitutes a procedural violation (hallucination, constraint violation, inconsistency), then categorically fail any execution that violates these rules regardless of output quality.

The observation-communication-execution consistency framework gives you a concrete checklist for debugging agent failures. When your agent misbehaves, trace these three streams and look for divergence points. Did it see the right data? Did it claim to do the right thing? Did it actually execute what it claimed? Most bugs live in the gaps between these streams.

The corrupt success framing is rhetorically powerful for convincing stakeholders that high task completion rates don’t mean your agent is production-ready. Use this when pushing back against premature deployment: “We have 85% success, but how many of those are corrupt successes where we got lucky despite procedural failures?”

The benchmark design critique—contradictory reward signals, simulator artifacts, task scope gaps—is a template for auditing your own evaluation setups. If your benchmark has these flaws, your agents are optimizing for the wrong thing.