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

File	Description
`OTAP.pdf`	Paper preprint
`exp.py`	Full experiment suite -- Part A (perturbation meta-eval), Part B (graded-quality correlation), ablations, runtime (Section 5)
`main.py`	Standalone Part A pipeline with optional ablations and LLM-judge baseline
`requirements.txt`	Python dependencies

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.

Metric	P1	P2	P3	P4	P5	P4>P5	AUROC
Exact step match	36.4	44.8	45.8	41.2	53.7	55.8	48.5
BLEU	49.2	67.2	52.8	48.3	70.7	68.3	59.9
ROUGE-L	56.7	45.8	82.9	84.4	47.7	21.1	67.4
Embed greedy (BERTScore-style)	41.1	66.7	31.7	25.4	69.2	86.4	46.8
Embed + Hungarian	41.7	66.7	28.9	25.5	67.8	84.2	46.2
OTAP (ours)	89.4	100.0	54.7	70.7	93.6	98.3	82.0

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).

Metric	rho (all)	tau (all)	rho (dmg)	tau (dmg)
Exact step match	0.755	0.655	0.562	0.474
BLEU	0.883	0.765	0.827	0.691
ROUGE-L	0.723	0.619	0.503	0.418
Embed greedy (BERTScore-style)	0.781	0.655	0.829	0.697
Embed + Hungarian	0.782	0.651	0.819	0.681
OTAP (ours)	0.923	0.837	0.851	0.748

Table C: Ablations

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

Variant	Benign (avg)	P4	P5	AUROC	rho (B)
OTAP (full)	81.4	70.7	93.6	82.0	0.923
(i) no structure (theta=0)	54.4	19.4	90.6	54.5	0.771
(ii) unsigned D	81.4	69.7	94.7	82.0	0.925
(iii) balanced marginals	78.5	67.0	91.7	79.2	0.929
(iv) Hungarian transport	50.7	18.1	85.5	51.4	0.787
(v) whole-step embedding	71.7	72.2	72.7	72.5	0.895
(vi) no tool term	67.8	69.3	68.4	68.9	0.910
(vii) K=1 reference	64.4	46.5	85.3	65.1	0.909
(vii) soft-min T=1.0	78.8	66.1	93.3	79.5	0.923
(viii) uniform mass	79.5	67.4	93.4	80.3	0.934
(ix) total-order edges	64.5	43.8	89.4	65.8	0.949

Key hyperparameters

Parameter	Default	Description
`alpha`	0.35	Action embedding weight in fielded node cost
`beta`	0.20	Context embedding weight
`gamma`	0.25	Effect embedding weight
`delta`	0.20	Tool substitution cost weight
`theta`	0.35	Structure (Gromov-Wasserstein) vs. attribute trade-off
`eps`	0.05	Entropic regularization
`lam`	1.0	KL marginal relaxation strength (both marginals)
`softT`	0.05	Soft-min temperature over multiple references
`K`	3	Number of reference trajectories used
`kappa`	1.0	Critical-mass weighting strength

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}
}