Trajectory Evaluation for Tool-Using AI Agents

Trajectory evaluation checks how a tool-using agent reached its result, not just whether its final prose looked correct. Record observable actions and environment changes, enforce hard safety invariants at execution time, and accept multiple valid paths unless policy truly requires one sequence.

This is a deeper method for the trajectory checks introduced in the agent eval CI guide.

Separate outcome, process, and efficiency

An agent can fail in three distinct ways:

A correct answer can conceal an unauthorized write. A policy-compliant trajectory can still end in the wrong state. Score these layers separately before defining any aggregate.

WebArena evaluates agents in functional websites and emphasizes end-to-end functional correctness. The original work illustrates why a realistic, reproducible environment matters for long-horizon web tasks. Zhou et al., WebArena The τ-bench design similarly compares the final database state with an annotated goal state and repeats tasks to examine reliability. Yao et al., τ-bench

Record observable events, not hidden reasoning

Use an append-only normalized log:

type AgentEvent =
  | { readonly seq: number; readonly type: "model.response"; readonly outputDigest: string }
  | { readonly seq: number; readonly type: "tool.request"; readonly tool: string; readonly args: unknown }
  | { readonly seq: number; readonly type: "policy.decision"; readonly decision: "allow" | "deny"; readonly rule: string }
  | { readonly seq: number; readonly type: "tool.result"; readonly tool: string; readonly status: "ok" | "error"; readonly resultDigest: string }
  | { readonly seq: number; readonly type: "approval"; readonly scope: unknown; readonly expiresAt: string }
  | { readonly seq: number; readonly type: "state.snapshot"; readonly fixtureDigest: string };

In production, include timestamps, trace IDs, model/configuration fingerprints, duration, token counts, and redaction metadata. Preserve the actual arguments and relevant tool result in an access-controlled artifact or content-addressed store; a digest alone supports integrity but not diagnosis.

Do not log private chain-of-thought. Evaluation needs externally observable decisions, supplied evidence, calls, results, and effects. Logs can contain personal data, credentials, or hostile instructions, so minimize content, redact secrets, encrypt storage, and set retention and access policy.

Express invariants as executable checks

Hard constraints should fail at the point of effect and again in evaluation:

interface TrajectoryResult {
  readonly events: readonly AgentEvent[];
  readonly finalState: unknown;
}

function neverUsedTool(run: TrajectoryResult, forbidden: string): boolean {
  return !run.events.some(
    (event) => event.type === "tool.request" && event.tool === forbidden,
  );
}

function writesFollowApproval(run: TrajectoryResult): boolean {
  let approved = false;

  for (const event of run.events) {
    if (event.type === "approval") approved = true;
    if (event.type === "tool.request" && event.tool.startsWith("write_") && !approved) {
      return false;
    }
  }
  return true;
}

The example is intentionally simplified: real approval must be authenticated, unexpired, and bound to the exact action and arguments. “An approval occurred earlier” is not sufficient authorization.

Other deterministic invariants include tenant isolation, argument ranges, call-depth ceilings, citation-to-source mapping, no write after cancellation, and no retry for a non-idempotent effect without an idempotency key.

Avoid one golden trajectory

Exact-match action sequences are appropriate only when the sequence is required. Otherwise they punish valid alternatives and encourage test overfitting.

Use three levels:

1. required partial order: authentication must precede account access; approval must precede a write;
2. allowed action set: several read tools may supply equivalent facts; and
3. terminal-state predicate: the environment ends in any approved state.

Represent dependencies as a small directed acyclic graph rather than a list. For example, lookup_customer and read_policy may occur in either order, while both must precede issue_refund.

When a reference trajectory is valuable for teaching or diagnostics, call it a reference—not the ground truth. Compare semantic steps, not generated call IDs or harmless argument ordering.

Evaluate tool selection and arguments locally

Break errors into actionable classes:

• unnecessary tool call;
• missing required call;
• wrong tool among similar choices;
• invalid or fabricated argument;
• argument unsupported by user input or retrieved evidence;
• wrong ordering or dependency;
• ignored error, timeout, or partial result;
• repeated call with no new information; and
• correct call blocked or altered by policy middleware.

Validate arguments against the tool schema, then apply domain checks. Schema validity proves shape, not authority or truth. {"amount": 10000} can be valid JSON and still violate refund policy.

Trajectory-aware research reports selection, argument, and dependency/order metrics because final accuracy alone cannot locate these failures. Treat any published benchmark findings as specific to its tools and tasks. He et al., TRAJECT-Bench

Grade semantics with tightly scoped evidence

Some judgments—whether a call was necessary or whether evidence supported a claim—need expert or model-assisted review. Give the grader the task, policy, relevant observable events, and source text. Ask one question and require event IDs as evidence.

Calibrate automatic trajectory graders against expert labels. AgentRewardBench was created specifically to test automatic evaluation of web-agent trajectories and includes expert judgments about success, side effects, and repetition; its results warn against assuming one evaluator works equally well across benchmarks. Lù et al., AgentRewardBench

Never permit a semantic grader to waive an unauthorized effect. Route ambiguous or high-consequence judgments to a person.

Measure efficiency without rewarding reckless shortcuts

Report calls, retries, unique tools, model turns, tokens, latency, and external cost. Compare only after required outcome and safety criteria pass. Otherwise a zero-call agent that does nothing appears maximally efficient.

Use task-specific budgets and inspect the distribution. A median of three calls can hide a runaway tail. Flag repeated identical requests, cycles in semantic state, and calls made after the terminal condition was already satisfied.

Diagnose with state and event diffs

For every failure, retain:

case and fixture version
agent/model/prompt/tool-policy fingerprints
ordered normalized events
expected versus actual terminal-state diff
first violated invariant and its event IDs
tool errors and retry decisions
cost and latency counters
redaction record

Classify the first causal failure rather than every downstream symptom. A final unsupported answer may originate in a stale search result, an argument error, or a parser dropping provenance.

Trajectory-eval checklist

• Score outcome, process, safety, and efficiency separately.
• Assert terminal state in an isolated environment.
• Capture observable calls, results, policy decisions, approvals, and effects.
• Do not collect hidden chain-of-thought.
• Encode required partial orders and allow valid alternative routes.
• Validate both schema and domain authorization.
• Calibrate semantic trajectory graders against experts.
• Fail hard invariants regardless of semantic score.
• Compare efficiency only among safe, successful runs.
• Protect and expire sensitive trajectory data.