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

• URL: http://arxiv.org/abs/2607.17082v1
• Date: Sun, 19 Jul 2026 05:23:17 GMT
• Title: Otap:Structure-Aware Optimal Transport for Evaluating Planning and Execution in Agent Trajectories
• Abstract summary: Current evaluation metrics reduce such a trajectory to a binary success flag or compare it against a reference by exact matching.<n>We instantiate trajectory evaluation as a distance between the agent's execution graph and a set of valid solution graphs.<n>The resulting score, termed otap, is a pseudo-metric that is provably invariant to dependency-preserving reorderings.
• Score: 13.06173852232351
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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 or compare it against a reference by exact matching. 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 accuracy is highest when the dependency graph is recovered exactly, and drops only when the graph is inferred heuristically from free-text traces.

Related papers

• TaPeR: Probabilistic Recovery of Sparse Task Precedence Graphs from a Handful of Demonstrations [16.604293152314995]
  Long-horizon manipulation tasks are often only partially ordered.<n>Existing approaches typically infer task structure from human demonstrations using both temporal and symbolic supervision.<n>We present an approach for extracting task dependency structures from demonstrations using only simple kinematic graphs and distributions over relative object poses.
  arXiv  Detail & Related papers  (2026-08-21T12:31:50Z)
• Fantastic Adaptive Taxonomies and How to Use Them [100.20614173157708]
  AdaMAST converts execution traces into a compact, evidence-grounded failure taxonomy.<n>No code is hand-authored, no trace human-annotated.<n>In agent-system search, taxonomy-coded diagnoses of failed candidates outperform free-form.
  arXiv  Detail & Related papers  (2026-07-17T17:41:16Z)
• What Resolve Rate Hides: Trajectory Structure Diagnostics for Coding Agents [14.988334585821939]
  Coding agents are ranked almost entirely by resolve rate.<n>A single pass/fail label says nothing about why a run failed or why an accepted run spent extra steps, time, or tokens.<n>We present TraceProbe, a trajectory-diagnostic framework that recovers what resolve rate hides.
  arXiv  Detail & Related papers  (2026-07-07T12:09:46Z)
• FALAT: Tracing Failures in LLM Agent Trajectories via Dependency-Guided Search [11.638321375070047]
  We propose FALAT, a diagnostic framework for failure attribution in LLM agent trajectories.<n>We evaluate FALAT on the Who&When benchmark, which includes both algorithm-generated and hand-crafted multi-agent failure trajectories.
  arXiv  Detail & Related papers  (2026-05-30T15:11:35Z)
• TraceGraph: Shared Decision Landscapes for Diagnosing and Improving Agent Trajectories [61.51984029109709]
  We introduce TraceGraph, a graph-based framework that turns released multi-model agent trajectories into shared decision landscapes.<n>For each task, TraceGraph builds a graph over observable action-observation states from pooled rollouts before model identity is introduced.<n>It then overlays outcome-informed productive cores and trap regions, and summarizes each rollout with three events: Access, Trap exposure, and Repair.
  arXiv  Detail & Related papers  (2026-05-29T13:40:31Z)
• Phantom transitions in language model fine-tuning [0.0]
  Fine-tuning a language model on contexts with a near-synonym competitor often fails silently.<n>We study this regime across five transformer architectures spanning two families and a fivefold parameter range.<n>We observe sharp catapult-like jumps in the order parameter that resemble a phase transition.
  arXiv  Detail & Related papers  (2026-05-25T10:44:42Z)
• Proper Scoring Rules for Agentic Uncertainty Quantification [0.038379177968040606]
  Trajectory Proper Score (TPS) is a predictor-agnostic family of strictly proper trajectory-level scoring rules.<n>Trajectory ECE is resolution-blind, while scalarized Trajectory Brier elicits only the collapsed scalar, not the full trace.
  arXiv  Detail & Related papers  (2026-05-23T22:22:00Z)
• From Patches to Trajectories: Privileged Process Supervision for Software-Engineering Agents [56.31499185764872]
  Supervised fine-tuning (SFT) on long teacher trajectories is the dominant way to instill investigation and reasoning in open software-engineering (SWE) agents.<n>We propose Patches-to-Trajectories (P2T), which uses $pstar$ as privileged information during curation and formulates trajectory construction as bi-objective optimization over per-step effectiveness and trajectory length.
  arXiv  Detail & Related papers  (2026-05-21T04:54:55Z)
• TopoCurate:Modeling Interaction Topology for Tool-Use Agent Training [53.93696896939915]
  Training tool-use agents typically rely on Supervised Fine-Tuning (SFT) on successful trajectories and Reinforcement Learning (RL) on pass-rate-selected tasks.<n>We propose TopoCurate, an interaction-aware framework that projects multi-trial rollouts from the same task into a unified semantic quotient topology.<n>TopoCurate achieves consistent gains of 4.2% (SFT) and 6.9% (RL) over state-of-the-art baselines.
  arXiv  Detail & Related papers  (2026-03-02T10:38:54Z)
• SMATCH++: Standardized and Extended Evaluation of Semantic Graphs [4.987581730476023]
  The Smatch metric is a popular method for evaluating graph distances. We show how to fully conform to annotation guidelines that allow structurally deviating but valid graphs. For improved scoring, we propose standardized and extended metric calculation of fine-grained sub-graph meaning aspects.
  arXiv  Detail & Related papers  (2023-05-11T17:29:47Z)
• FGOT: Graph Distances based on Filters and Optimal Transport [62.779521543654134]
  Graph comparison deals with identifying similarities and dissimilarities between graphs. A major obstacle is the unknown alignment of graphs, as well as the lack of accurate and inexpensive comparison metrics. In this work we introduce the filter graph distance approximation.
  arXiv  Detail & Related papers  (2021-09-09T17:43:07Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  We cast a new formulation for the one-to-many graph alignment problem, which aims at matching a node in the smaller graph with one or more nodes in the larger graph. We show that our method leads to significant improvements with respect to the state-of-the-art algorithms for each of these tasks.
  arXiv  Detail & Related papers  (2020-03-12T22:31:59Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.