Pith. sign in

REVIEW 4 major objections 5 minor 32 references

Agent-plan score separates valid plans where text metrics fail

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-04 04:11 UTC pith:CAUJSOG2

load-bearing objection OTAP offers a fresh, honest way to score agent trajectories as dependency graphs, but its headline separation result rests on the authors' own ordering and needs external validation. the 4 major comments →

arxiv 2607.17082 v2 pith:CAUJSOG2 submitted 2026-07-19 cs.AI cs.CLcs.LG

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

Babak Barazandeh , Subhabrata Majumdar , George Michailidis This is my paper
classification cs.AI cs.CLcs.LG
keywords optimal transportagent trajectory evaluationGromov-Wassersteindependency graphsplanning evaluationLLM agentsprocess-level metrics
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper argues that evaluating an LLM agent's trajectory should not reduce to a success flag, exact sequence matching, or another model's judgment. Instead, it proposes measuring the distance between the agent's execution graph and a set of known-valid solution graphs. The proposed score, OTAP, uses an unbalanced fused Gromov-Wasserstein transport problem over attributed dependency DAGs, which aligns steps by both meaning and causal structure. The paper shows that OTAP provably ignores dependency-preserving reorderings, tolerates missing or hallucinated steps via unbalanced marginals, and ranks valid trajectories above causally inverted ones in settings where semantics-only metrics score below chance. If correct, OTAP offers a deterministic, auditable process-level evaluation signal for open-ended agentic tasks where no formal verifier exists.

Core claim

The paper's central claim is that trajectory evaluation should be formulated as a distance between the agent's execution graph and a set of valid solution graphs, and that this distance can be computed as an unbalanced fused Gromov-Wasserstein (UFGW) transport problem over attributed dependency DAGs. The resulting score, OTAP, is a pseudo-metric that provably remains unchanged under dependency-preserving reorderings (Proposition 2) and changes by at most O(r/n) when r redundant leaf steps are inserted (Proposition 3). OTAP distinguishes valid plans from causally inverted ones even when the step text is identical, and its unbalanced marginals absorb missing or hallucinated steps without forci

What carries the argument

The central object is the signed dependency-distance matrix over an attributed DAG, combined with an unbalanced fused Gromov-Wasserstein transport objective. Each step is represented by embeddings of action, arguments, effect, and tool; edges encode data or causal dependencies. The signed matrix assigns positive distance to ancestor relations, zero to incomparable steps, and negative distance to descendant relations, so that a causal inversion incurs a quadratic penalty while a valid reordering of independent steps incurs none. The transport coupling T aligns agent steps to reference steps, with KL penalties on the marginals to handle cardinality mismatches, and a temperature-controlled soft

Load-bearing premise

The load-bearing premise is that dependency edges can be extracted faithfully from the agent's trace; if edges are guessed wrong, valid reorderings get penalized as dependency violations and the metric's edge over surface scores disappears.

What would settle it

Take an agent trajectory with a faithfully extracted DAG, generate a valid dependency-preserving reordering, and compute OTAP with the same reference: Proposition 2 predicts an exactly identical score, so any nonzero difference falsifies the invariance claim. Alternatively, measure dependency-edge precision on free-text traces and check whether OTAP's AUROC advantage vanishes when extraction error is high.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Valid plans that reorder independent steps receive the same OTAP score as the canonical plan, so the metric does not punish legitimate planning flexibility.
  • Inserting distractor steps changes the score by only O(r/n), making OTAP robust to low-level noise in execution traces.
  • On hand-curated tasks and on benchmarks with exact or explicit dependency graphs, OTAP separates valid from invalid trajectories in a regime where sequence-matching and embedding-based metrics score below chance.
  • The benefit shrinks when dependencies must be inferred from free text; the paper attributes this to extraction fidelity rather than the transport objective.
  • When a formal verifier exists, OTAP predicts validity worse than surface metrics, which positions OTAP as a complement for open-ended domains without verifiers rather than a replacement for them.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If dependency extraction can be improved, for example with uncertainty-weighted edges, OTAP's advantage could extend to free-text traces; the paper's own attribution suggests extraction, not the transport formulation, is the limiting factor.
  • Because the transport objective is differentiable and the reference aggregation is soft, OTAP is a natural candidate for a dense process reward in agent training, though the pseudo-metric caveat means it should not be used as an unconstrained optimization target on its own.
  • The paper's validity ordering is stipulated rather than human-judged; a study comparing OTAP's ranking to human practitioner rankings would test whether the metric matches real preferences outside synthetic perturbations.
  • Granularity invariance remains unresolved: merging or splitting steps perturbs both the dependency matrix and the mass distribution, so future work on hierarchical or quotient-graph costs could close this gap.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper proposes OTAP, a trajectory-evaluation metric that represents an agent's execution as an attributed DAG of steps and compares it with a set of reference graphs via an unbalanced fused Gromov-Wasserstein transport problem (Eq. 3). The claimed contributions are a pseudo-metric structure, invariance to dependency-preserving reorderings, bounded sensitivity to redundant insertions, and empirical separation of valid from invalid trajectories in settings where semantic-only baselines fail. Experiments cover a hand-curated perturbation corpus, three public benchmarks (PlanBench, WebArena, GAIA), and a PlanBench oracle study with formal validity labels. The paper is unusually explicit about its limitations, including the fact that its perturbation validity ordering is the authors' stipulation and that OTAP is the weakest metric on the only externally labeled benchmark.

Significance. If the claims held, OTAP would be a useful, deterministic, auditable process-level score for LLM-agent trajectories in open-ended domains without a formal verifier. The paper has real strengths: a clear graph-alignment formulation, explicit decomposition into semantic, structural, and marginal-penalty terms, reproducible deterministic evaluation, component ablations, and an honest discussion of where the method fails. However, the central theoretical claim (a pseudo-metric) is not established, the main invariance theorem requires a fixed graph that the empirical protocol re-extracts, one of the three propositions has a proof gap, and the headline empirical separation in the target regime rests on a validity ordering defined by the authors in terms of the same dependency violations OTAP measures. The only external labels, PlanBench, show OTAP performing worst, which the paper scopes out. These issues are load-bearing and need correction before the central claims can be accepted.

major comments (4)
  1. [§5, Proposition 1 and Remark 2] Proposition 1 calls d a pseudo-metric, but a pseudo-metric must satisfy the triangle inequality. Remark 2 explicitly concedes that the triangle inequality fails in the unbalanced regime, and averaging L(P,R) and L(R,P) does not restore it. Thus the object is not a pseudo-metric. Since the abstract and contributions advertise a 'provably invariant ... pseudo-metric', this is a central mislabel. Recommend renaming d a divergence or similarity measure and restating the theorem as establishing non-negativity, symmetry, reflexivity, and isomorphism invariance only.
  2. [§5, Proposition 2 and §6.1] Proposition 2's invariance is proved under Assumption 2, which requires that the dependency graph is fixed and not re-extracted from the serialized order. But §6.1 states that agent-side graphs are re-extracted from perturbed sequences by artifact tracing, and GAIA uses heuristic edge inference. Therefore the main experimental regime does not satisfy the theorem's precondition. A valid dependency-preserving reordering can perturb the extracted DAG and incur a structural penalty, exactly the GAIA degradation the paper observes. The abstract's unqualified 'provably invariant to dependency-preserving reorderings' needs a fixed-graph qualifier.
  3. [§5, Proposition 3 and Appendix A.4] The proof of Proposition 3 asserts that inserting redundant leaf nodes leaves the DAG height H unchanged because the new nodes are 'redundant' and 'do not lie on any longest source-to-sink path.' This is not guaranteed by the stated condition 'leaf nodes that carry no downstream dependencies': a leaf can still have incoming edges and can lengthen a source-to-sink path, changing H and hence every entry of D in Eq. (2). Without a precise definition of 'redundant' that prevents height changes, the bound is not established. The proof needs an additional assumption or a revised argument handling the renormalization of D when H changes.
  4. [§6.2, §6.6, and §7 (Limitations)] The central empirical claim—that OTAP separates valid from invalid trajectories in open-ended, no-verifier domains—is validated only against the authors' perturbation ordering {original, P1–P3} ≻ P4 ≻ P5. Since P4 and P5 are defined by dependency violations, and OTAP's core signal is the signed dependency distance (Eq. 2), agreement with this ordering is partly circular. The paper's own limitation statement concedes the ordering 'is our stipulation rather than a human judgment.' The only external validity labels, PlanBench (Table 6), show OTAP with the lowest AUROC (79.2) among all six metrics. Scoping out PlanBench is coherent, but it leaves the intended regime with no external criterion. An independent human-ranking study, or a verifier-labeled benchmark adapted to the target regime, is needed to support the headline separation claim.
minor comments (5)
  1. [Abstract and Table 1] The abstract says 'semantics-only metrics score below chance,' but Table 1 shows BLEU at 59.9 and ROUGE-L at 67.4 AUROC, both above chance; only the order-blind embedding baselines and exact match are below chance. Please qualify the claim.
  2. [§4.2, Eq. (6)] The causal mass weighting uses a free parameter κ, but no ablation or sensitivity analysis for κ is reported. The paper reports ablations for other components; adding κ would help assess robustness.
  3. [§5, Proposition 3 statement] The statement of Proposition 3 introduces ω and C̄ without defining them; they are defined only in the proof. Please define them in the statement or immediately before it.
  4. [§1] In the Introduction, the sentence 'In practice, valid plans often diverge in step ordering, granularity, tool selection, or overall strategy ()' has an empty citation. This appears to be a missing reference.
  5. [§5 vs §6.7] The complexity discussion says evaluations run in milliseconds for n,m ≤ 50, but §6.7 reports 23.9 s mean on GAIA's longer traces. The caveat in §5 is present, but the contrast could be stated more prominently to avoid an impression of a universal speed guarantee.

Circularity Check

1 steps flagged

Central 'separates valid from invalid' claim rests on an author-stipulated validity ordering that mirrors OTAP's own dependency objective; the only external labels (PlanBench) disfavor OTAP.

specific steps
  1. self definitional [Sec. 6.1 (Perturbations and validity ordering) / Sec. 7 (Limitations); cf. Eq. (2)–(3)]
    "We take the validity ordering {original,P1,P2,P3} ≻ P4 ≻ P5, assuming that one inversion (P4) damages a plan less than deletion or distractor insertion (P5). ... Our constructed perturbations and degradations establish that Otap behaves as specified under a known ordering, but that ordering is our stipulation rather than a human judgment."

    The headline validity labels are defined by the authors in terms of dependency violations: P4 is 'causal inversion, swapping two steps across a dependency edge' and P5 is deletion/distractor/tool corruption. OTAP's Eq. (2) builds a signed dependency matrix whose 'sign preserves causal direction', and Eq. (3) penalizes |D^P - D^R|^2 quadratically. Hence P4/P5 are invalid by construction under exactly the structural criterion OTAP optimizes, while P1–P3 are dependency-preserving by construction. The reported AUROC/PRA/SEV therefore measure agreement with the authors' own validity taxonomy, not an independent ground truth. The paper concedes the ordering is 'our stipulation rather than a human judgment.' The only external labels (PlanBench verifier flags) show OTAP weakest (79.2 AUROC vs 86.7

full rationale

The mathematical core of OTAP is not circular: Propositions 1–3 are proved from the stated objective, hyperparameters are fixed defaults rather than fitted, and no load-bearing result is imported from a self-citation. However, the paper's central empirical claim—that OTAP 'separates valid from invalid trajectories in a regime where semantics-only metrics score below chance'—is supported primarily by controlled perturbations whose validity ordering is stipulated by the same dependency-preservation concept that Eq. (2)–(3) encode. The authors explicitly acknowledge that this ordering is 'our stipulation rather than a human judgment' and that the PlanBench labels are 'the only external criterion we report.' On that external criterion, OTAP is the weakest metric, and the paper excludes such verifier-labeled settings from its intended use case. Thus, within the regime OTAP is designed for, no independent validity labels exist, and the headline separation result is currently validated only against a self-defined ground truth. This is a disclosed limitation rather than a hidden fit, so the score is 6 rather than higher; the derivation itself is self-contained, but the empirical verification of the central claim is partly circular by construction.

Axiom & Free-Parameter Ledger

11 free parameters · 6 axioms · 0 invented entities

The metric relies on hand-chosen default hyperparameters and on the assumption that dependency graphs extracted from traces are faithful. The validity ordering used for evaluation is author-stipulated. No new physical or model entities are introduced. The embedding encoder and OT machinery are borrowed from prior work.

free parameters (11)
  • α = 0.35
    Weight on action-description cosine distance in Eq 1; hand-chosen default, not tuned per corpus.
  • β = 0.20
    Weight on context-argument cost in Eq 1.
  • γ = 0.25
    Weight on effect/artifact cost in Eq 1.
  • δ = 0.20
    Weight on tool-dissimilarity term in Eq 1.
  • η = 0
    Weight on state-log cost; set to 0 because no corpus logs environment state.
  • θ = 0.35
    Trade-off between attribute cost and structural GW cost in Eq 3.
  • ε = 0.05
    Entropic regularization strength in Eq 3.
  • λ1 = 1
    Row KL marginal penalty in Eq 3.
  • λ2 = 1
    Column KL marginal penalty in Eq 3.
  • T = 0.05
    Soft-min temperature over reference set in Eq 5.
  • κ
    Criticality weighting strength in Eq 6; no fitted value reported.
axioms (6)
  • standard math Node costs C_ij∈[0,1] and dependency distances D_ik∈[-1,1] are normalized as in Assumption 1.
    Normalization bounds the objective and is used in Proposition 3; stated in Appendix A.1.
  • domain assumption The text encoder ψ provides semantically meaningful embeddings for actions, contexts, and effects.
    All semantic costs in Eq 1 depend on the embedding model; no guarantee is provided beyond using MiniLM-L6-v2.
  • domain assumption Dependency graph extraction mechanisms (a)-(c) recover true causal dependencies; for free text, salient-token heuristics approximate them.
    Central to the metric's validity; the paper's own GAIA results show this assumption degrades performance.
  • ad hoc to paper The perturbation validity ordering {original,P1-P3} ≻ P4 ≻ P5 is the correct ground truth.
    Used in Sec 6.2 to define PRA/SEV/AUROC; the authors acknowledge in Sec 7 that it is a stipulation, not human judgment.
  • ad hoc to paper Assumption 2: permutation invariance assumes the graph is fixed and not re-extracted from the serialized order.
    Stated in Appendix A.3; violated in the GAIA pipeline, so the practical invariance claim is weaker than the theorem.
  • standard math Background optimal transport theory: entropic regularization, Sinkhorn iterations, and UFGW convergence.
    Borrowed from Cuturi 2013, Chizat et al. 2018, Titouan et al. 2019; used without reproof.

pith-pipeline@v1.3.0-alltime-deepseek · 14685 in / 15453 out tokens · 152404 ms · 2026-08-04T04:11:27.950574+00:00 · methodology

0 comments
read the original 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, compare it against a reference by exact matching, or delegate judgment to another language model. 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 advantage tracks the fidelity of the dependency graph: largest where edges follow from operator semantics, smallest where they are inferred from free text. Where a formal verifier exists, strict surface metrics predict validity better than OTAP does, which places OTAP in open-ended domains where no verifier is available.

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

32 extracted references · 1 linked inside Pith

  1. [1]

    2023 , eprint=

    Measuring Reliability of Large Language Models through Semantic Consistency , author=. 2023 , eprint=

    2023

  2. [2]

    2026 , eprint=

    Consistency as a Testable Property: Statistical Methods to Evaluate AI Agent Reliability , author=. 2026 , eprint=

    2026

  3. [3]

    2026 , eprint=

    TRACER: Trajectory Risk Aggregation for Critical Episodes in Agentic Reasoning , author=. 2026 , eprint=

    2026

  4. [4]

    2026 , eprint=

    Agentic Confidence Calibration , author=. 2026 , eprint=

    2026

  5. [5]

    International Conference on Learning Representations (ICLR) , year =

    Shunyu Yao and others , title =. International Conference on Learning Representations (ICLR) , year =

  6. [6]

    Advances in Neural Information Processing Systems (NeurIPS) , year =

    Shunyu Yao and others , title =. Advances in Neural Information Processing Systems (NeurIPS) , year =

  7. [7]

    International Conference on Learning Representations (ICLR) , year =

    Xiao Liu and others , title =. International Conference on Learning Representations (ICLR) , year =

  8. [8]

    GAIA: A Benchmark for General AI Assistants , booktitle =

    Gr. GAIA: A Benchmark for General AI Assistants , booktitle =

  9. [9]

    International Conference on Learning Representations (ICLR) , year =

    Shuyan Zhou and others , title =. International Conference on Learning Representations (ICLR) , year =

  10. [10]

    International Conference on Learning Representations (ICLR) , year =

    Yujia Qin and others , title =. International Conference on Learning Representations (ICLR) , year =

  11. [11]

    arXiv preprint arXiv:2406.12045 , year =

    Shunyu Yao and others , title =. arXiv preprint arXiv:2406.12045 , year =

    Pith/arXiv arXiv

  12. [12]

    NeurIPS Datasets and Benchmarks Track , year =

    Karthik Valmeekam and others , title =. NeurIPS Datasets and Benchmarks Track , year =

  13. [13]

    International Conference on Learning Representations (ICLR) , year =

    Hunter Lightman and others , title =. International Conference on Learning Representations (ICLR) , year =

  14. [14]

    Advances in Neural Information Processing Systems (NeurIPS) , year =

    Lianmin Zheng and others , title =. Advances in Neural Information Processing Systems (NeurIPS) , year =

  15. [15]

    IEEE Transactions on Systems, Man, and Cybernetics , volume =

    Alberto Sanfeliu and King-Sun Fu , title =. IEEE Transactions on Systems, Man, and Cybernetics , volume =

  16. [16]

    Computational Optimal Transport , journal =

    Gabriel Peyr. Computational Optimal Transport , journal =

  17. [17]

    Advances in Neural Information Processing Systems (NeurIPS) , year =

    Marco Cuturi , title =. Advances in Neural Information Processing Systems (NeurIPS) , year =

  18. [18]

    Scaling Algorithms for Unbalanced Optimal Transport Problems , journal =

    L. Scaling Algorithms for Unbalanced Optimal Transport Problems , journal =

  19. [19]

    Gromov--Wasserstein Distances and the Metric Approach to Object Matching , journal =

    Facundo M. Gromov--Wasserstein Distances and the Metric Approach to Object Matching , journal =

  20. [20]

    International Conference on Machine Learning (ICML) , year =

    Titouan Vayer and others , title =. International Conference on Machine Learning (ICML) , year =

  21. [21]

    International Conference on Machine Learning (ICML) , year =

    Matt Kusner and others , title =. International Conference on Machine Learning (ICML) , year =

  22. [22]

    Conference on Empirical Methods in Natural Language Processing (EMNLP) , year =

    Wei Zhao and others , title =. Conference on Empirical Methods in Natural Language Processing (EMNLP) , year =

  23. [23]

    International Conference on Learning Representations , volume=

    Agentbench: Evaluating llms as agents , author=. International Conference on Learning Representations , volume=

  24. [24]

    International Conference on Learning Representations , volume=

    Gaia: a benchmark for general ai assistants , author=. International Conference on Learning Representations , volume=

  25. [25]

    Advances in neural information processing systems , volume=

    Tree of thoughts: Deliberate problem solving with large language models , author=. Advances in neural information processing systems , volume=

  26. [26]

    International Conference on Machine Learning (ICML) , pages=

    Optimal Transport for structured data with application on graphs , author=. International Conference on Machine Learning (ICML) , pages=

  27. [27]

    SIAM Journal on Imaging Sciences , volume=

    Scaling algorithms for unbalanced optimal transport , author=. SIAM Journal on Imaging Sciences , volume=

  28. [28]

    International Conference on Learning Representations (ICLR) , year=

    BERTScore: Evaluating Text Generation with BERT , author=. International Conference on Learning Representations (ICLR) , year=

  29. [29]

    Computers & Operations Research , volume=

    Speeding up the Hungarian algorithm , author=. Computers & Operations Research , volume=. 1990 , publisher=

    1990

  30. [30]

    International Conference on Learning Representations , volume=

    Toolllm: Facilitating large language models to master 16000+ real-world apis , author=. International Conference on Learning Representations , volume=

  31. [31]

    International Conference on Learning Representations , volume=

    Let's verify step by step , author=. International Conference on Learning Representations , volume=

  32. [32]

    16th IEEE International Conference on Tools with Artificial Intelligence , pages=

    VAL: Automatic plan validation, continuous effects and mixed initiative planning using PDDL , author=. 16th IEEE International Conference on Tools with Artificial Intelligence , pages=. 2004 , organization=

    2004