PaperlayerView exact revision on arXiv

Source-linked AI summary

ContractEval: Query-Conditioned Execution Matching for Procedural Instruction Conformance

Praphul Singh, Shanu Kumar, Akshat Agarwal, Ganesh Kumar

arXiv:2609.09458v1cs.AI

TL;DR

Procedural agents can produce plausible answers while skipping the query-specific checks, branches, dependencies, or invariants that justify them, and existing output-only or trace-aware judging does not identify those active obligations. ContractEval makes the obligations explicit through query-conditioned expected graphs and matches them against observed response or trace evidence; on audited graphs it detects and localizes all controlled perturbations, while LLM-backed extraction remains calibration-sensitive.

  • Problem

    Existing output-only and trace-aware evaluation can miss structural procedural failures because neither identifies which obligations were active for the query.

  • Method

    ContractEval represents instructions as query-conditioned expected graphs and matches their active obligations against evidence-grounded observed response or trace graphs.

  • Results

    Under audited expected and observed graphs, ContractEval detects and localizes all controlled perturbations; LLM judges miss many injected failures, while LLM-backed extraction preserves much of the signal.

  • Takeaways & Limitations

    ContractEval makes procedural conformance auditable by turning omissions, branch, ordering, invariant, extra-action, and output-contract failures into distinct diagnostic failures.

  • Takeaways & Limitations

    The benchmark is limited to text-centric SOP-style artifacts and controlled response or trace evidence, and conformance scores depend on graph granularity, equivalence judgments, and invariant calibration.

Abstract

from arXiv · show

As LLM agents move from answering questions to carrying out procedures, failures can be unwarranted rather than visibly wrong: the final response looks acceptable even though the system skipped the check, branch, dependency, or invariant that made the answer justified. Output-only evaluation sees the answer, and trace-aware judging sees activity, but neither identifies which obligations were active for the query. We introduce CONTRACTEVAL, a diagnostic framework for making those active obligations explicit. It represents procedural instructions as query-active obligations and matches them against response or trace evidence, turning omissions, wrong branches, ordering errors, extra actions, invariant breaches, and output-contract violations into distinct conformance failures. On a controlled suite of audited procedural contracts, output-only and trace-aware LLM judges miss many injected structural failures; under gold expected and observed graphs, ContractEval detects and localizes all of them. LLM-backed extraction preserves much of this signal but remains calibration-sensitive. ContractEval is therefore not a compliance guarantee; it makes procedural conformance auditable rather than implicit in final-answer quality.

1 Introduction

ContractEval addresses procedural failures hidden by plausible answers or busy traces by conditioning instructions on the query and matching active obligations against observed evidence. Its controlled evaluation shows that gold-graph matching detects and localizes injected structural failures that LLM judges often miss.

  • Motivation: Procedural systems must satisfy checks, preconditions, branches, dependencies, and invariants beyond producing an acceptable final answer.Failures can include skipped verification, wrong branching, reversed dependencies, unsupported intermediate actions, or violated output requirements.
  • Motivation: Output-only and trace-aware judges can accept plausible behavior because traces do not identify which obligations applied or whether observed actions satisfied them.A trace provides activity but not the query-specific denominator needed to judge conformance.
  • Approach: ContractEval conditions an instruction artifact on the query and compares active obligations with response or trace evidence.This makes failures traceable to missing or violated obligations rather than opaque judge preferences.
  • Results: 0.495 average detection and 0.400 localization were achieved by output-only LLM judges, versus 0.570 and 0.468 for trace-aware judges.The strongest trace-aware judge still missed 29.0% of perturbed cases.
  • Results: Under audited expected and observed graphs, ContractEval detects and localizes all controlled perturbations, while LLM-backed extraction remains calibration-sensitive.The study evaluates omissions, misbranching, reordering, extra actions, invariant breaches, and output-contract violations.
  • Contributions: The paper contributes a query-active obligation formulation, query conditioning, a controlled benchmark, evaluator comparisons, and component studies of graph extraction.The framework, audited contracts, prompts, and benchmark artifacts are intended to support reproducible research.

2 Related Work

Related work extends instruction-following evaluation from single-answer accuracy toward explicit constraints, complex instructions, and longer procedural artifacts. ContractEval is positioned as shifting evaluation toward matching active expected obligations against execution evidence while acknowledging evaluator sensitivity.

  • Instruction following and SOP evaluation: Instruction-following benchmarks evaluate explicit constraints, increasingly complex multi-level instructions, and longer procedural artifacts.Examples include IFEval, FollowBench, InfoBench, ComplexBench, SOPBench, LongProc, and SAGE.
  • Positioning: ContractEval shifts the evaluation object from output adherence or path coverage to active expected obligations matched against execution evidence.This reframes procedural evaluation around query-conditioned obligations rather than only final outputs or observed paths.
  • LLM-as-a-judge and evaluator reliability: LLM-based evaluators offer flexible rubric application and semantic-variation handling but are sensitive to prompts, presentation, and rubric design.The cited evaluation paradigm includes G-Eval, MT-Bench, Chatbot Arena, and Prometheus-style evaluators.
  • Positioning: ContractEval constructs a query-conditioned expected graph and matches it against evidence-grounded observed behavior.This adapts conformance-style reasoning to natural-language responses and noisy agent traces.

3 Problem Setup

ContractEval formalizes procedural conformance as matching an observed response or trace to the obligations activated by an instruction artifact and query. The expected graph preserves required dependencies and context without prescribing one surface execution trace.

  • Formal objective: The evaluator receives an instruction artifact A, query q, and observed behavior O, then tests whether O satisfies obligations active for q.A fluent or factually correct conclusion can still fail by omitting a required check, taking the wrong branch, or violating an invariant.
  • Declared contract: The declared contract represents semantic obligations, dependency edges, hierarchy, and global invariants in a structured graph.The hierarchy supports coarse tasks and finer substeps at different evaluation granularities.
  • Expected graph: The query-conditioned expected graph retains active obligations, prerequisites, necessary hierarchy, and applicable invariants while pruning inactive branches.It is a partial order over normative obligations, not a single prescribed trace.
  • Observed graph: Observed behavior is represented as an execution graph whose nodes are evidence-grounded behaviors and whose edges encode observed ordering or dependency relations.In oracle experiments it comes from audited executions and perturbations; scalable experiments extract it from response or trace text.
  • Alignment: Conformance aligns expected obligations with observed evidence, using unmatched required nodes and observed nodes to diagnose omissions and extra actions.The alignment can operate across nearby levels of the hierarchical task-network representation.

4 ContractEval Method

ContractEval separates contract compilation, query conditioning, observed-evidence extraction, hierarchical matching, and diagnostic scoring. This decomposition makes representation, extraction, matching, dependency, branch, invariant, and output-validity issues separately reportable.

  • Pipeline stages: Static contract compilation parses an instruction artifact into a declared hierarchical task network with typed action and obligation structure.The compiler is the first stage of the staged evaluation pipeline.
  • Pipeline stages: Hierarchical matching generates candidate expected-observed matches and solves a thresholded maximum-weight bipartite assignment.Candidates use node labels, descriptions, semantic types, and evidence spans; reported LLM-backed runs use fixed token-overlap similarity.
  • Diagnostic metrics: Required node recall measures the fraction of required expected nodes mapped by the alignment.The method defines required expected nodes as a subset of expected nodes and uses the alignment domain to compute recall.
  • Diagnostic metrics: Edge conformance evaluates whether mapped observations satisfy expected dependencies, while branch correctness evaluates agreement with active branch decisions.These dimensions distinguish ordering and branch failures from node-level omissions.
  • Diagnostic metrics: Invariant scores evaluate applicable non-topological invariants, and output validity separately reports strict final-output schema compliance.Together these dimensions localize failures instead of collapsing them into one opaque scalar.

5 Controlled Perturbation Evaluation Protocol

The evaluation uses audited executions and paired hidden-failure perturbations to test whether evaluators detect and localize specific procedural failures rather than accept plausible outputs or traces. It compares evaluator families under a controlled validity suite spanning structural, invariant, and output-contract failures.

  • Case construction: The protocol holds the contract, query, and base evidence fixed while injecting one hidden procedural failure, isolating evaluator validity from changes in task content.This tests whether an evaluator notices the failed obligation rather than merely accepting a plausible response or trace.
  • Case construction: Each case begins with an audited declared HTN, query-conditioned expected graph, and clean observed execution, then injects one controlled failure or retains a clean control.The six perturbation families are node omission, branch violation, topological swap, extra observed action, invariant breach, and output contract violation.
  • Evaluator comparison: Four evaluator families are compared: output-only LLM judges, trace-aware judges, gold-graph ContractEval, and ContractEval with LLM-extracted observed graphs.The comparison treats ContractEval as an evaluation method rather than a leaderboard of task solvers.
  • Metrics: Detection requires clean controls to be predicted clean and perturbed cases non-clean, while localization additionally requires the predicted failure family to match the injected family.The protocol reports detection, balanced detection accuracy, localization, clean false positive rate, and perturbed false negative rate.
  • Benchmark scope: The benchmark contains 10 SOP-style contracts, 200 clean executions, and 1,400 total cases, emphasizing deep, dependency-rich contracts rather than average instruction-following performance.Declared HTNs average 11.4 nodes and 11.1 edges, while expected graphs average 10.2 active nodes and 9.2 edges per query.
  • Audit substrate: The primary graph construction is author-audited, with a separate audit pass finding no path-changing disagreements across two contracts and 10 expected subgraphs.The authors still identify annotation cost, granularity sensitivity, and full-corpus agreement as limitations.

7 Results

Direct LLM judges miss many controlled structural failures, whereas gold-graph ContractEval detects and localizes the injected failure families; LLM-backed extraction retains much of this signal but remains calibration-sensitive.

  • LLM judges: Output-only judges detect roughly half of controlled failures on average, and GPT-5.4 trace-aware judging still misses 29.0% of perturbed cases.Trace text helps, especially for the strongest model, but remains below diagnostic use.
  • LLM judges: GPT-5.4 still marks 157/200 omissions and 185/200 swaps as clean despite receiving the query-conditioned expected graph and trace or final answer.This gap indicates that graph exposure alone does not replace deterministic expected-observed matching.
  • Evaluation scope: Gold-graph ContractEval measures metric validity under audited expected and observed graphs rather than end-to-end automation.Balanced accuracy averages clean specificity and perturbed recall, while FPR and FNR denote clean false positives and perturbed false negatives.
  • Gold-graph ContractEval: Gold-graph ContractEval scores move in the intended direction for every perturbation family, with affected dimensions identifying the type of protocol failure.Omissions affect required-node recall and edge conformance, swaps ordering, extras observed precision, and branch, invariant, and output failures their corresponding checks.
  • LLM-backed extraction: GPT-4o reaches 1.000/0.916 and GPT-5.4 reaches 0.982/0.903 detection/localization with LLM-extracted observed graphs.Residual errors concentrate in clean false positives from extractor-added actions and perturbation localization misses.

8 Discussion

ContractEval makes query-active obligations the unit of accountability and evaluates evidence against an explicit expected graph rather than judging answers or surface trajectories holistically.

  • Accountability: ContractEval changes evaluation from an answer-level verdict to evidence for obligations activated by the query, making omissions, wrong branches, unsupported actions, and invariant violations inspectable.Expected graphs are evaluation objects, not scripts.
  • Expected graphs: The expected graph is a partial order that retains required checks, dependencies, branch choices, and invariants without prescribing one surface trajectory.Semantically equivalent or differently worded behavior can satisfy an obligation through hierarchical matching.
  • Passing: A correct final answer reached by skipping a required check fails the contract because passing requires evidence that active obligations were satisfied.This reframes passing as an evidentiary claim about process legitimacy rather than answer acceptability alone.
  • Scope of automation: The oracle setting validates the representation and metrics under audited graphs but does not show that graph extraction is solved.The paper therefore presents staged automation from high-validity audits toward scalable benchmarking.

9 Conclusion

ContractEval makes procedural conformance auditable by matching observed behavior to query-active obligations, while its controlled validity claims remain bounded by benchmark scope, isolated perturbations, graph assumptions, and non-guarantee status.

  • ContractEval exposes procedural failures that holistic judges may miss by matching observed behavior to obligations activated by the query.
  • The 10-contract, 1,400-case benchmark supports controlled validity for procedural conformance, not average instruction-following quality across deployment domains.
  • The benchmark isolates one failure at a time and therefore does not establish robustness to compound failures, recovery, missing logs, or live tool failures.
  • Scores depend on expected-graph granularity, auditor judgments about equivalent trajectories, and calibration of partial invariant violations.
  • ContractEval should not be used as a standalone safety or compliance guarantee, especially with sensitive real traces or high-stakes decisions.

A Gold Graph Audit and Matching Details

The audit converts SOP artifacts into checked hierarchical task networks and validates query-conditioned expected graphs before matching observed evidence, using fixed assignment rules and a worked omission example.

  • Gold graph audit: Each SOP becomes a declared HTN with typed nodes, dependencies, hierarchy links, explicit branch obligations, source spans, and global invariants.
  • Gold graph audit: The audit retains active branches, prerequisites, ancestors, descendants, and applicable invariants while excluding inactive branches from each expected graph.
  • Matching details: Candidate expected-observed matches are threshold-filtered and solved by maximum-weight bipartite matching under fixed scoring rules without per-model post-hoc tuning.
  • Worked example: Figure 3 presents the SOP fragment, declared HTN, query-conditioned expected graph, observed graph, matching assignment, and diagnostic metrics as concrete graph objects.
  • Worked example: In the worked example, omitting authentication leaves an expected node unmatched, reducing node recall and invalidating downstream dependency edges while observed precision remains high.

D Per-Family Localization

Per-family results show that free-form judges detect failures unevenly, whereas LLM-backed ContractEval preserves sensitivity to omissions and ordering while exposing extractor-calibration weaknesses.

  • Graph interpretation: Figure 3 links per-family diagnostics to matching among declared, query-conditioned, and observed graph objects.
  • Per-family results: Output-only judges are strong on clean cases and answer-changing branch failures but unreliable for omitted steps, topological swaps, and extra trace actions.
  • Per-family results: Trace-aware judging improves extra-action recognition, yet the best trace-aware run still has low recall for omissions and ordering swaps.
  • Per-family results: LLM-backed ContractEval keeps most perturbation families high while shifting residual errors toward observed-extractor calibration.

E Confusion Matrices

Confusion matrices show that structured LLM judges still confuse omissions and ordering failures with clean cases, while ContractEval shifts errors toward observed-extraction calibration.

  • Confusion-matrix findings: Strong trace-aware and expected-graph LLM judges confuse omissions and ordering failures with clean executions despite substantial procedural evidence.
  • Confusion-matrix findings: LLM-backed ContractEval preserves sensitivity to omissions and ordering while concentrating remaining errors on clean or extra-action extractor calibration.
  • Reported analyses: The benchmark reports separate tables for expected-subgraph extraction, static contract extraction, component scaling, judge performance, and confusion matrices.
Loading 2609.09458v1…