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

As large language model agents become more complex, evaluating their performance has shifted from simple binary success flags to analyzing the entire execution trajectory. Traditional metrics like exact string matching or token-level overlap fail to account for the fact that multiple valid, structurally distinct paths can solve the same task. The authors ask: how can we rigorously measure the distance between an agent's execution graph and a set of valid solution graphs while remaining invariant to valid reorderings and sensitive to true causal errors?

The authors propose Otap (Optimal Transport for Agentic Planning), which treats agent trajectories as attributed directed acyclic graphs (DAGs). Each node represents a step (action, tool, arguments, and effects), and edges represent causal dependencies. The evaluation is framed as an unbalanced fused Gromov-Wasserstein transport problem. This formulation allows the metric to:

• Accommodate non-uniform plan granularity (e.g., one high-level step matching multiple sub-steps).
• Handle missing or hallucinated steps via unbalanced marginal constraints.
• Penalize causal inversions while ignoring dependency-preserving reorderings.
• Aggregate scores across multiple valid reference trajectories using a temperature-controlled soft-minimum function.

Otap significantly outperforms standard lexical and semantic metrics (like BLEU, ROUGE, and embedding-based matching) in distinguishing valid trajectories from those containing causal inversions or corruptions. In controlled experiments, while text-only metrics often score broken plans higher than valid ones due to superficial semantic similarities, Otap maintains high AUROC by leveraging the underlying dependency structure. The authors prove that Otap is a pseudo-metric that is invariant to dependency-preserving permutations and has bounded sensitivity to redundant step insertions.