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

OTAP: Structure-Aware Optimal Transport for Evaluating Planning and Execution in Agent Trajectories Babak Barazandeh, Subhabrata Majumdar, George Michailidis Cribl AI Research Lab, IIMB, UCLA

Overview

LLM agents solve tasks by generating trajectories that interleave planning, tool calls, and intermediate results. Current evaluation practice reduces such a trajectory to a binary success flag, compares it against a reference by exact matching, or delegates judgment to another language model. A success flag cannot distinguish a sound solution from a lucky one; exact matching penalizes plans that are valid but reordered or decomposed differently; and LLM judges are non-deterministic and give no reproducible explanation.

This paper reframes trajectory evaluation as a distance between the agent's execution graph and a set of valid solution graphs, instantiated as an unbalanced fused Gromov--Wasserstein transport problem over attributed dependency graphs. The resulting score, OTAP (Optimal Transport for Agentic Planning), is a normalized discrepancy that is invariant to dependency-preserving reorderings, handles missing or hallucinated steps through unbalanced marginals, and decomposes into interpretable sub-losses -- so a bad score points to what went wrong (a semantic mismatch, a broken dependency, a missing or extra step), not just that something did.

Files

Installation

pip install -r requirements.txt

The core OTAP solver requires only NumPy and SciPy. The evaluation scripts additionally need sentence-transformers (pulls in PyTorch) and scikit-learn. The optional LLM-judge baseline requires anthropic.

Quick start

Run the full experiment suite (recommended)

python exp.py

This produces all three paper tables in one run (20 tasks, 508 trajectories, K=3 references each):

• Table A -- perturbation meta-evaluation: pairwise ranking accuracy (PRA) per family P1..P5, severity ordering (P4 > P5), and valid-vs-invalid AUROC
• Table B -- correlation with graded quality: Spearman rho / Kendall tau, overall and damaged-only
• Table C -- ablations of every OTAP component

Results are printed as markdown tables and written to otap_results.json.

Run with options

python exp.py --quick              # fast smoke test (fewer variants)
python exp.py --embedder hash      # no-download debug run (hash embedder)
python exp.py --judge              # include LLM-as-a-judge baseline (needs ANTHROPIC_API_KEY)
python exp.py --human-ratings ratings.csv   # use real human ratings for Part B

Run the standalone Part A pipeline

python main.py                     # main PRA table
python main.py --ablations         # + ablation table
python main.py --llm-judge         # + LLM judge baseline (needs ANTHROPIC_API_KEY)
python main.py --encoder tfidf     # TF-IDF fallback (no sentence-transformers needed)

Results

All numbers below are from a single deterministic run (seed=20260706, embedder=all-MiniLM-L6-v2). No LLM judge is used anywhere in the metric pipeline; no per-corpus tuning is applied.

Table A: Perturbation meta-evaluation -- pairwise ranking accuracy (%)

P1--P3 are validity-preserving perturbations (paraphrase, valid reorder, merge/split); P4 is causal inversion; P5 is corruption (deletion, hallucination, tool swap). Higher is better for all columns.

Table B: Correlation with graded quality

Spearman rho and Kendall tau, computed per task then averaged. "Damaged-only" restricts to quality levels Q1--Q4 (the regime where outcome flags carry no signal).

Table C: Ablations

Each row removes or replaces one OTAP component. "Benign (avg)" averages PRA over P1--P3.

Key hyperparameters

lam controls how aggressively the solver destroys mass for unmatched steps and is the primary parameter to calibrate per embedding encoder.

Reproducing the results

pip install numpy scipy sentence-transformers
python exp.py --out otap_results.json

The full run takes approximately 10--15 minutes on a laptop CPU (no GPU required). All results are deterministic given the fixed seed. The output JSON contains raw scores for every trajectory, all summary tables, and timing data.

To verify with the hash embedder (no downloads, ~1 minute):

python exp.py --embedder hash --out otap_results_hash.json

Citation

@article{barazandeh2026otap,
  title={OTAP: Structure-Aware Optimal Transport for Evaluating Planning and Execution in Agent Trajectories},
  author={Barazandeh, Babak and Majumdar, Subhabrata and Michailidis, George},
  journal={arXiv preprint arXiv:2607.17082},
  year={2026}
}

License

Apache 2.0