Scoring Agent Trajectories When Multiple Tool Paths Are Valid

An agent can complete the same task through several legitimate tool paths. It may fetch a record directly, search before fetching, batch related reads, ask for a missing identifier, or recover from a transient failure. A trajectory evaluator that accepts only one recorded sequence mistakes imitation for correctness.

Score trajectories in layers. First verify the final state and required evidence. Next enforce safety and side-effect invariants. Then judge whether the observed path belongs to an allowed equivalence class. Only after those gates pass should efficiency affect the result.

Specify the Goal as Observable State

Write the task contract in terms of preconditions, desired postconditions, allowed changes, forbidden changes, evidence requirements, and user-visible output. For "reschedule order 184," the goal is not lookup -> cancel -> create. It may be a valid final booking linked to the original order, no duplicate charge, preserved customer authorization, and a confirmation containing the new date.

Separate hard invariants from preferences. Authorization, approval before irreversible work, and no duplicate side effects are hard. Using a batch read instead of two reads is a preference unless the task has a strict operational constraint. This distinction prevents a weighted average from passing a fast but unsafe path.

Capture a Replayable Trajectory

Record tool identity and contract version, validated arguments, result status, structured output, start and end times, parent step, retry attempt, idempotency key, approval evidence, and state diff. Include model generations and handoffs when they affect control flow, while redacting sensitive payloads according to policy.

The OpenAI Agents SDK tracing guide describes traces composed of spans and lists generations, tool calls, guardrails, and handoffs among traced events. A useful evaluation export should preserve those causal relationships rather than flattening everything into a log line sequence.

Snapshot external state before and after execution. Tool return text alone cannot prove that a refund occurred once, a record remained unmodified, or a notification was not sent. Where direct state inspection is impossible, use a controlled fake, event ledger, or provider reconciliation endpoint.

Normalize Syntax Into Semantic Actions

Different tools may implement the same logical operation. get_customer_by_id and search_customers followed by get_customer can both produce an authorized customer record. Map low-level calls into semantic actions such as resolve_customer, inspect_order, request_approval, and apply_schedule_change.

Normalization must retain security-relevant detail. Do not erase which tenant was queried, whether a mutation was dry-run, or whether an approval token was checked. Collapse harmless pagination and transport retries only after verifying they caused no semantic side effect.

Version the normalizer. A mapping added after seeing a candidate can change historical scores, so rerun the affected evaluation set or clearly mark the score contract change. Store raw traces beside normalized actions for audit and future reinterpretation.

Represent Multiple Valid Paths as Constraints

Use an allowed path graph, partial-order rules, or state machine instead of a single array. Specify required nodes, alternatives, predecessor constraints, conditional recovery, and prohibited transitions. Read-only inspections may commute; a charge and its approval do not.

{
  "task": "reschedule-order",
  "required": ["resolve-order", "verify-eligibility", "apply-change", "confirm-result"],
  "alternatives": [["direct-order-lookup"], ["search-order", "fetch-order"]],
  "mustPrecede": [["verify-eligibility", "apply-change"], ["approval", "apply-change"]],
  "conditional": {"missing-date": "clarify-with-user"},
  "forbidden": ["charge-without-approval", "cross-tenant-read"]
}

Do not enumerate every interleaving. Express only ordering that matters. If two independent reads can happen in either order or concurrently, a partial-order rule is more stable than duplicate reference paths.

Evaluate Outcomes and Evidence First

Check the final application state, returned answer, cited records, and event ledger. A path fails when the goal was not achieved, when the answer claims a result that state does not confirm, or when required evidence is missing. It also fails if it reaches the goal through a prohibited action.

Use deterministic assertions for IDs, amounts, statuses, ownership, approvals, and event counts. Use calibrated semantic review for explanation quality or whether a clarification was relevant. The Ragas metrics catalog includes agent goal accuracy and tool-call metrics; choose metrics that match your contract rather than treating one catalog score as a complete trajectory oracle.

Support partial credit only where the product can use it. A research agent that gathers two of three requested sources may be partially successful. A payment workflow that created an unauthorized charge is a failure regardless of the rest of its work.

Make Safety and Side Effects Vetoes

Define forbidden tools, argument ranges, data domains, tenant boundaries, confirmation requirements, and maximum side-effect multiplicity. Inspect state and provider ledgers after the run. A trajectory should not pass because the final answer looks correct while an intermediate call emailed the wrong recipient.

Test indirect paths to the same hazard. If delete_record is forbidden without approval, a general execute_sql tool must not become an alternate deletion route. Normalize by effect as well as tool name, and instrument tools that can hide several mutations behind one call.

Include failure recovery in the policy. Compensating a failed action may be valid, but compensation does not erase the original event. Score whether the system detected the failure, used an authorized recovery path, and left a reconciled final state.

Score Efficiency After Validity

Count model turns, tool calls, repeated semantic actions, retrieved bytes, wall time, and monetary cost when available. Compare valid paths within the same task and environment. A slower path that asks for required approval is not inefficient; it is compliant.

Use task-specific bounds and mark them illustrative. One local rubric might assign full efficiency credit below a measured call budget, taper credit for justified verification, and fail a planner loop after a separately defined ceiling. Do not present that ceiling as a property of agents generally.

Prefer Pareto analysis when cost, latency, and outcome quality compete. A path is clearly dominated when another valid path is no worse on all chosen dimensions and better on at least one. This avoids inventing arbitrary exchange rates between milliseconds, tool fees, and explanation quality.

Test Nondeterminism and Recovery Paths

Repeat complete tasks under controlled initial state. Compare the distribution of equivalence classes, outcomes, and side effects rather than requiring each run to choose the same route. Randomness is acceptable only within the invariant envelope.

Inject tool timeouts, empty searches, stale reads, rate limits, malformed results, and approval rejection. Confirm that fallback edges are allowed and bounded. Distinguish a transport retry from a planner calling the same mutation twice because it forgot prior state.

Unseen valid paths deserve adjudication. Review raw trace, state diff, and policy. Add a new graph rule only if the path is safe across the class of tasks, not merely because one run happened to end well.

Build a Layered Trajectory Report

Report outcome pass, safety pass, path validity, efficiency, and observability completeness as separate fields. Include failure reason codes and the first violated invariant. A composite score may help ranking, but it must not hide a safety veto or missing trace.

Analyze by task family, tool availability, permission level, recovery condition, model configuration, and trajectory class. Watch for policy drift: a candidate may preserve overall success while shifting toward a costly or fragile route.

Keep evaluator uncertainty visible. If missing telemetry prevents a side-effect check, the result is unevaluable, not a pass. Observability is part of the release contract for an agent that can change external state.

Review Checklist

• Define postconditions, prohibited state, and required evidence before collecting traces.
• Capture tool contracts, arguments, results, approvals, retries, and state diffs.
• Preserve raw traces and version semantic normalization.
• Model alternatives and partial ordering instead of one golden sequence.
• Check final state and evidence before stylistic output quality.
• Treat authorization and side-effect violations as vetoes.
• Separate transport retries, planner loops, verification, and compensation.
• Score efficiency only among correct and safe trajectories.
• Repeat tasks and compare equivalence-class distributions.
• Mark incomplete observability as unevaluable.

Action Plan: Replace Golden Paths With Invariant Gates

Choose one consequential agent task and write its observable goal, prohibited effects, approvals, and evidence requirements. Instrument a controlled environment, collect several known-valid paths plus failure recoveries, and define semantic action mappings. Build the smallest allowed graph that captures meaningful order without freezing harmless implementation details.

Run baseline and candidate repeatedly from identical state. Gate on outcome and safety first, adjudicate unseen paths, and add efficiency reporting only after the evaluator reliably distinguishes retries from duplicate actions. The resulting suite should explain not only whether the agent succeeded, but whether every route it used remained within the product's operational contract.