OTAP: Structure-Aware Optimal Transport for Evaluating Planning and Execution in Agent Trajectories

Babak Barazandeh, Subhabrata Majumdar, George MichailidisarXiv 2026 · arXiv

TL;DR

Evaluating large language model (LLM) agents is notoriously difficult because a single task can often be solved via multiple valid paths. This paper introduces OTAP (Optimal Transport for Agentic Planning), a novel evaluation metric that models agent trajectories as attributed dependency graphs and applies unbalanced optimal transport to measure similarity. OTAP successfully accommodates valid step reorderings and variations in plan granularity while strictly penalizing true causal errors and hallucinations.

What Problem Does This Paper Address?

When LLM agents tackle complex tasks, they generate a trajectory of interleaved plans, tool calls, and intermediate execution states. Currently, researchers evaluate these trajectories using three flawed paradigms:

  1. Outcome-only evaluation: A binary success flag that tells you if the agent succeeded, but provides no diagnostic signal for failures and can't distinguish a robust solution from a lucky one.
  2. Reference-matching metrics (e.g., BLEU, ROUGE, exact match): These treat trajectories as flat text strings, heavily penalizing agents that reorder independent steps or use different phrasing, even if the plan is completely valid.
  3. LLM-as-a-judge: Flexible, but computationally expensive, non-deterministic, and prone to self-preference biases.

The authors argue for a paradigm shift: instead of checking if an agent reproduced an exact sequence of reference steps, evaluation should be treated as a holistic graph alignment problem: How close is the agent's execution graph to the set of valid solution graphs?

Methods

OTAP represents an agent's execution history as an attributed Directed Acyclic Graph (DAG), where nodes are actions/tools/states and edges represent strict causal or data dependencies.

To compare an agent's graph ($P$) against a reference graph ($R$), OTAP uses an Unbalanced Fused Gromov-Wasserstein (UFGW) optimization framework:

  • Node Cost: Measures semantic distance between step components (actions, arguments, tool choices, and environment states) using text embeddings.
  • Structure Representation: Computes a signed pairwise dependency distance matrix based on shortest path hop distances. The sign preserves causal direction, ensuring that swapping independent steps incurs no penalty, while a true causal inversion triggers a massive quadratic penalty.
  • Unbalanced Marginals: Traditional optimal transport requires total mass conservation. OTAP relaxes this using Kullback-Leibler (KL) penalties. Unmatched reference mass naturally captures missing steps (recall failure), while unaligned agent mass flags hallucinated steps (precision failure).
  • Multi-Reference Support: To handle multiple valid strategies, OTAP aggregates scores across an ensemble of reference graphs using a temperature-controlled softmin function.
Table 3: Ablations on the hand-curated corpus, modifying one component of Eq. (3) per row. Benign denotes mean PRA over P1–P3; AUROC ×100; ρ comes from the graded ladder over all levels.

Datasets

The authors validated OTAP across several datasets:

  • Hand-curated corpus: 20 realistic tasks (e.g., travel booking, database migration) represented as 6-step attributed DAGs with valid reordering options.
  • PlanBench: A deterministic blocksworld planning benchmark with formally verified exact dependency graphs and ground-truth validity flags.
  • WebArena: A realistic web environment where reference plans are derived explicitly from a rule engine.
  • GAIA: A general AI assistant benchmark where reference graphs must be heuristically traced from free-text annotator solutions.

Key Insights and Ideas

  • Graphs > Sequences: Linear sequences force an arbitrary ordering on independent tasks. By evaluating trajectories as DAGs, metrics can naturally tolerate valid permutations.
  • The Power of "Unbalanced" Transport: Allowing mass to be destroyed or created via KL penalties provides an elegant, mathematically rigorous way to score hallucinations and omissions without breaking the alignment of the rest of the trajectory.
  • Fidelity Matters: A structure-aware metric is only as good as its graph. OTAP performs best when dependency edges are explicitly derived from operator semantics or tool schemas, rather than heuristically guessed from free text.

Key Results

OTAP significantly outperforms standard text-matching and embedding baselines when distinguishing valid trajectories from perturbed or corrupted ones.

  • Permutation Tolerance: On the hand-curated corpus, when valid steps were reordered (P2), text-based metrics like ROUGE-L penalized the plan heavily. OTAP achieved a perfect 100.0% accuracy, recognizing the plan's structural validity.
  • Inversion Detection: When causal steps were inverted (P4), standard embedding baselines scored below chance (<50%), while OTAP successfully flagged the invalid sequences.
Table 1: Pairwise ranking accuracy on hand-curated corpus, by perturbation family, severity ordering, and valid-versus- invalid AUROC (all values ×100; chance = 50).
  • Graded Degradation: As trajectories were progressively corrupted (from Q5 down to Q1), OTAP tracked the degradation linearly, maintaining the highest correlation ($\rho = 0.923$) with the true quality level.
Table 2: Correlation with the graded corruption level on hand-curated corpus. Damaged-only restricts to Q1–Q4; σρ is the cross-task standard deviation of ρ over all levels.
  • Benchmark Consistency: This pattern held true across public benchmarks like PlanBench and WebArena, where structural edges are explicitly defined.
Table 4: Perturbation results on the three public benchmarks (all values ×100; chance = 50). We report only P2 and P4 for brevity, see supplementary material for the full table.

Limitations and Future Work

  • Granularity Invariance: OTAP still struggles when a single high-level step is broken down into multiple sub-steps (or vice versa), as this dramatically alters the graph's mass distribution and dependency matrix.
  • Dependency Extraction Bottleneck: On datasets like GAIA, where edges must be inferred from free text, noisy edge extraction degrades OTAP's accuracy. Future work will explore uncertainty-weighted edges to soften structural penalties when tracing confidence is low.
  • Not a Substitute for Formal Verifiers: In strict, deterministic domains where a unique optimal plan is required (like PlanBench's oracle study), exact surface-matching metrics still correlate better with absolute validity than OTAP.
Table 6: PlanBench oracle study: AUROC (×100) of each metric’s score against verifier-checked plan validity over 720 real LLM plans.

Consequently, the authors position OTAP for open-ended domains where no formal verifier is available, serving as a graded diagnostic tool rather than a binary correctness checker.

Summary updated

Abstract

Large language model agents solve tasks by generating trajectories that interleave planning, tool calls, and intermediate results. Current evaluation metrics reduce such a trajectory to a binary success flag, compare it against a reference by exact matching, or delegate judgment to another language model. A success flag cannot distinguish a sound solution from one that succeeds by luck, and says nothing about why a failed run went wrong. Exact matching penalizes plans that are valid but reordered or decomposed differently from the reference. We reframe trajectory evaluation as a distance between the agent's execution graph and a set of valid solution graphs, and instantiate it via an unbalanced fused Gromov-Wasserstein transport problem over attributed dependency graphs. The resulting score, termed OTAP (Optimal Transport for Agentic Planning), is a pseudo-metric that is provably invariant to dependency-preserving reorderings and has bounded sensitivity to redundant steps. Its unbalanced marginals handle missing or hallucinated steps without forcing a match, and its soft coupling accommodates variation in plan granularity. On controlled perturbations and three public benchmarks, OTAP separates valid from invalid trajectories in a regime where semantics-only metrics score below chance. Its advantage tracks the fidelity of the dependency graph: largest where edges follow from operator semantics, smallest where they are inferred from free text. Where a formal verifier exists, strict surface metrics predict validity better than OTAP does, which places OTAP in open-ended domains where no verifier is available.
BibTeX
@misc{barazandeh2026otap,
  author = {Babak Barazandeh and Subhabrata Majumdar and George Michailidis},
  title = {{OTAP: Structure-Aware Optimal Transport for Evaluating Planning and Execution in Agent Trajectories}},
  year = {2026},
  eprint = {2607.17082},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2607.17082},
}
Figure