Evaluating Autonomous Agents Through Execution Trajectories

45 concepts36 papers1 proposal

When we evaluate a traditional machine learning model, we typically look at a static output: a classification label, a bounding box, or a generated paragraph. If the output matches the ground truth, the model succeeds; if not, it fails.

However, as Large Language Models (LLMs) transition into autonomous agents that interact with environments—navigating websites, executing code, or calling APIs—this binary, outcome-based evaluation paradigm breaks down. Imagine an AI agent tasked with transferring funds between accounts. It might successfully complete the transfer (a win according to outcome-based metrics), but along the way, it might have made twenty redundant API calls, temporarily exposed sensitive credentials, or violated corporate compliance policies. Conversely, an agent might fail a task due to a minor, single-character syntax error in its final tool call, despite executing a flawless sequence of reasoning steps up to that point.

To build reliable, safe, and efficient agents, the research community is shifting from evaluating what an agent achieves to how it achieves it. This direction is known as trajectory-based evaluation. Instead of treating the agent's operation as a black box that produces a final state, it treats the entire sequence of intermediate thoughts, actions, and environment responses as the primary artifact for assessment.

The Limitations of Outcome-Based Metrics

Evaluating an agent solely on its final state introduces significant blind spots. As Yipeng Li argues in Evaluation and Benchmarking of LLM Agents: A Survey, outcome-only metrics fail to capture the efficiency of an agent's operational path. By comparing an agent's actual trajectory to an ideal execution sequence, developers can pinpoint exactly where planning or tool-use capabilities break down during long-horizon tasks.

Without this granular view, it is impossible to distinguish between robust planning and accidental success. Xuefeng Bai et al. note in A Survey on the Feedback Mechanism of LLM-based AI Agents that process-based metrics are essential for identifying whether an agent's success was a fluke or the result of systematic reasoning. Furthermore, outcome-based evaluation struggles with non-determinism. In complex software environments, static code analysis cannot capture runtime failures. As shown by Alfin Wijaya Rahardja et al. in Can Agent Fix Agent Issues?, diagnosing logic errors in agentic systems requires dynamic analysis of execution trajectories and reasoning logs, as the underlying bugs are often invisible in the source code alone.

How Trajectory Evaluation Works

Evaluating a trajectory is fundamentally more challenging than evaluating a static output because there are often multiple valid paths to accomplish the same goal. If an evaluator strictly enforces a single human-demonstrated sequence of actions, it penalizes agents that find alternative, potentially more efficient routes.

To solve this, researchers use several flexible mechanisms to score trajectories without sacrificing rigor:

Flexible Trajectory Evaluation Mechanisms:

1. Milestone DAGs   ──► Verifies critical states are reached while allowing path flexibility.
2. Logical History  ──► Uses sequential/conjunctive operators to audit API/package histories.
3. Subsequence Alignment ──► Measures similarity to reference paths via Longest Common Subsequence.

1. Directed Acyclic Graphs (DAGs) of Milestones

Instead of checking for an exact string match or a rigid sequence, benchmarks can define a graph of required intermediate states and forbidden actions. In ToolSandbox: A Stateful, Conversational, Interactive Evaluation Benchmark for LLM Tool Use Capabilities, Jiarui Lu et al. implement this via on-policy evaluation. The agent can take any path it chooses, provided it hits the critical milestones specified in the DAG and avoids prohibited behaviors (such as violating a security constraint).

2. Logical History Verification

For environments driven by APIs or system packages, the execution history can be audited using logical operators. Shihan Deng et al. introduce a "CheckPoint" metric in Mobile-Bench: An Evaluation Benchmark for LLM-based Mobile Agents that uses sequential, conjunctive, and disjunctive operators to verify the presence of specific API calls in the action history, ensuring the agent followed a valid logical progression.

3. Longest Common Subsequence (LCS) Alignment

When evaluating agents in visual or user-interface environments, such as an Android operating system, an agent might take extra steps to dismiss a popup or scroll past an ad. To avoid penalizing these benign variations, HUI XUE et al. in Understanding the Weakness of Large Language Model Agents within a Complex Android Environment measure performance using the longest common subsequence between the agent's actions and a reference path. This rewards the completion of necessary sub-goals while tolerating minor deviations in UI interactions.

Uncovering Latent Failures and Policy Violations

Trajectory-based evaluation is particularly crucial for safety and compliance, where a failure is defined not by the final outcome, but by the rules broken along the way.

Many critical flaws are latent—they do not prevent task completion but introduce severe risks. For example, Xiaofei Wen et al. demonstrate in Towards Policy-Compliant Agents: Learning Efficient Guardrails For Policy Violation Detection that policy violations often emerge from the cumulative interaction of multiple seemingly benign actions over a full trajectory, making them invisible to single-step monitors.

Outcome-Based vs. Trajectory-Based Safety Audit:
[Task: Retrieve Data] ──► (Action 1: Call API) ──► (Action 2: Log Payload) ──► [Outcome: Success]
                                                       ▲
                                                       │
                                            Trajectory Audit Detects:
                                            Sensitive Data Leakage!

In a dedicated safety audit of autonomous agents with broad tool access, Tianyu Chen et al. in A Trajectory-Based Safety Audit of Clawdbot (OpenClaw) show that logging the entire interaction trace—including tool-call arguments and intermediate environment responses—is the only way to catch catastrophic escalations. An agent might successfully fulfill an ambiguous user prompt, but its trajectory might reveal that it executed irreversible real-world actions due to a lack of internal verification.

Decomposing Bottlenecks for System Optimization

Beyond grading agents, trajectory analysis provides the diagnostic data required to optimize them. By breaking down an execution trace into distinct cognitive stages, developers can isolate specific technical bottlenecks.

In Process-Level Trajectory Evaluation for Environment Configuration in Software Engineering Agents, Jiayi Kuang et al. decompose agent trajectories into planning, perception, feedback, and action phases. This granular tracking reveals a common paradox: modern LLM agents are often highly capable at perceiving and diagnosing errors in their environment, but they fail during the execution phase when generating the exact repair commands.

Furthermore, trajectories provide an intuitive framework for human-in-the-loop optimization. Jasmina Gajcin et al. demonstrate in Iterative Reward Shaping using Human Feedback for Correcting Reward Misspecification that evaluating full trajectories allows human supervisors to easily detect temporal dependencies and inefficient cycles. This holistic perspective makes it straightforward for humans to provide feedback that corrects reward misspecification, steering agents away from "reward hacking" behaviors that look successful on paper but are deeply flawed in practice.

Key Foundational Work

Understanding Human Creativity for Computational Play (2011) — contributed 2 concept elements to this direction.
Rank the Episodes: A Simple Approach for Exploration in Procedurally-Generated Environments (2021) — contributed 1 concept elements to this direction.
Language-Aligned Waypoint (LAW) Supervision for Vision-and-Language Navigation in Continuous Environments (2021) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_trajectory_based_evaluation_f737e7dc,
  title = {trajectory-based evaluation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/trajectory-based-evaluation/rdr_f737e7dc98f3413c8364a56fb1c7706a},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_trajectory_based_evaluation_f737e7dc_v1,
  title = {trajectory-based evaluation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/trajectory-based-evaluation/rdr_f737e7dc98f3413c8364a56fb1c7706a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake