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:
- 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.
- 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.
- 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.
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.
- 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.
- Benchmark Consistency: This pattern held true across public benchmarks like PlanBench and WebArena, where structural edges are explicitly defined.
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.
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