When should trajectory comparison be exact-match, any-order, or subsequence?

## The strictness dial Comparing an observed trajectory to a reference is not one algorithm but a family, ordered by how much freedom the agent is allowed. Choosing a point on that dial is a modelling decision about the task, not a technical detail — and getting it wrong produces either false failures (too strict) or blind spots (too loose). **Exact-match** requires the agent's call sequence to equal the reference: same tools, same order, same length. It is the strongest signal when it passes and almost always the wrong default. Reserve it for procedures where order is externally mandated — a regulated approval chain, a deployment runbook, a payment flow where the authorization must precede the capture and nothing may sit between them. **Any-order (set or multiset) comparison** discards sequence entirely and asks only whether the right calls were made, with the right multiplicity. Use it where the steps are genuinely independent: an internal expense-report portal agent that must read the employee's cost centre and the current per-diem policy can fetch either first, and penalizing one ordering is measuring nothing. **Subsequence matching** is the middle ground and the workhorse. It asks whether the required calls appear in the required relative order, allowing arbitrary other calls in between. "Create the ticket before attaching the log" is exactly a subsequence constraint: the agent may search the knowledge base, notify the user, and check permissions in between, and it is still correct — but attaching a log to a ticket that does not yet exist is not. ## Edit distance and partial credit Between exact-match and set comparison sits **sequence edit distance**: the number of insertions, deletions and substitutions that turn the observed trajectory into the reference, usually normalized by reference length. It gives graded credit instead of a pass/fail bit, which makes it useful for tracking gradual regression across model versions — a suite whose mean edit distance drifts from 0.8 to 1.6 is degrading before any test flips to fail. Its weakness is interpretability: a distance of 3 does not tell you whether the agent skipped a critical write or added three harmless reads. Pair it with the categorical checks rather than replacing them. ## Hybrids are what real suites use A well-built reference is rarely a flat list. It is closer to a small dependency graph plus budgets: - ordered constraints (`create_ticket` before `attach_log`), - unordered groups (the two independent lookups, in any order), - required calls (some retrieval tool must be called before answering), - forbidden calls (never call a refund tool on this task), - a step budget rather than a fixed length. Scored this way, an agent that solves the expense-report task in five steps where the reference took seven still passes — it satisfied every ordering constraint and came in under budget — while an agent that attached a log first fails on a specific, nameable constraint. That specificity is the practical payoff: the failure message says which rule broke, not "trajectory mismatch". ## Choosing the mode in practice Ask, per pair of steps: would a competent human doing this task be wrong to swap them? If no, the order is not a constraint and must not be scored as one. Ask, per step: is this step required, or was it merely how the reference author happened to proceed? Only required steps belong in the comparison at all. This is the discipline that turns a reference trajectory from a transcript into a specification. A useful sanity check is to run the suite against two or three *known-good* trajectories produced by different competent solvers — different models, or a human. If your comparison fails any of them, it is too strict, and you have learned that before it starts blocking releases. ## Why over-strictness is the more expensive error Both errors are real, but they fail differently. A too-loose comparison misses a regression, which you eventually catch in production or in the outcome metric. A too-strict comparison produces failures on correct behaviour, and the human response to a noisy eval is to stop reading it — after which it catches nothing at all. Strictness also actively penalizes improvement: a newer model that solves in three steps what the reference does in seven is scored as a regression, so the eval quietly selects for imitating an older, slower path. Start loose enough to admit every genuinely correct path you can produce, then tighten only where you can name the property being protected.