🤖 machine learning

Offline Preference-Based Trajectory Evaluation

This paper proposes a preference-based trajectory evaluation method that compares agentic systems through temporal progress and time-to-return profiles, significantly reducing comparison ties and improving statistical efficiency compared to traditional terminal-success metrics that often lead to benchmark saturation.

Original authors: Fernando Diaz

Published 2026-06-17

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Fernando Diaz

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a coach trying to decide which of two athletes is better at running a marathon.

The Old Way (Success Rate)
Currently, most AI systems are judged like this: You watch them run the race, and at the very end, you ask, "Did they cross the finish line?"

If Athlete A crosses the line in 2 hours and Athlete B crosses it in 4 hours, the old method says: "Both are winners. They are tied."
If Athlete C trips and falls halfway, and Athlete D trips and falls at the very last second, the old method says: "Both are losers. They are tied."

The paper argues that this "Did they finish?" approach is broken. It throws away a huge amount of useful information. It's like grading a student only on whether they turned in their homework, ignoring whether they actually understood the material or how hard they tried. Because so many systems end up with the same "Win" or "Lose" label, it becomes impossible to tell who is actually improving. The authors call this "benchmark saturation"—the test is so blunt that it can't distinguish between good and great anymore.

The New Way (Preference-Based Trajectory Evaluation)
The authors propose a new way to judge these systems. Instead of just looking at the finish line, they watch the entire journey and ask: "Who got closer to the goal faster?"

They use three creative ways to compare the runners:

The "First to the Milestone" Rule (Lexicographic Return): Imagine the race has checkpoints. If Runner A reaches the 10-mile mark in 1 hour and Runner B reaches it in 2 hours, Runner A is better, even if they both eventually finish. This method looks for the first moment where one runner pulls ahead.
The "Cumulative Speed" Rule (Return-Paired Preference): This looks at the whole race. It asks, "At every single point in the race, who was ahead?" If Runner A is slightly ahead for the first half, and Runner B is slightly ahead for the second half, this method calculates the total time advantage. It treats the race as a continuous flow of progress rather than a single yes/no event.
The "Step-by-Step" Rule (Interval-Paired Preference): This focuses on the effort between checkpoints. If Runner A takes a long time to get from mile 1 to 2, but then zooms from 2 to 3, while Runner B is steady but slow the whole way, this method rewards the specific bursts of speed. It asks, "Who was faster to get from one small goal to the next?"

What Happened When They Tried It?
The researchers tested this new method on many different AI "games" and tasks. Here is what they found:

Fewer Ties: Under the old "Did they finish?" method, 75% of the time, two different AI systems ended up in a tie. Under the new "Watch the whole journey" method, ties dropped to about 35%. This means the new method can actually tell the difference between systems much more often.
More Data Efficiency: Because the new method gets more information out of every single run, you need to run fewer tests to know which AI is better. It's like getting a high-resolution photo instead of a blurry one; you need fewer photos to see the details.
Stability: The rankings produced by the new method were more stable. If you removed one test from the results, the old method would sometimes flip the winner, but the new method stayed consistent.

The Big Takeaway
The paper concludes that the reason AI benchmarks seem "stuck" or "saturated" (where no system seems to get better) might not be because the problems are too hard or the data is bad. It might be because the ruler we are using to measure them is too blunt.

By switching from a simple "Win/Lose" score to a detailed "Who got there faster and how?" comparison, we can see real progress again without needing to collect more data or change the AI systems themselves. We just need to look at the journey, not just the destination.

Technical Summary: Offline Preference-Based Trajectory Evaluation

Problem Statement

The paper addresses the growing inefficiency and insensitivity of offline evaluation metrics for agentic systems. Current standard practices, particularly Success Rate (SR), collapse complex multi-step trajectories into a single binary terminal value (success/failure). This approach creates two primary issues:

Information Loss: It discards granular signals regarding partial progress and the temporal dynamics of how a task is solved. Two trajectories with vastly different performance profiles (e.g., one solving a task quickly vs. one solving it slowly, or one making significant partial progress vs. none) are treated as identical if they share the same terminal outcome.
Statistical Inefficiency: The binary nature of SR induces a high rate of "ties" (indistinguishable comparisons). The authors observe that in diverse benchmarks, roughly 75% of instance-level comparisons result in ties under SR. This drastically reduces the effective sample size, weakening statistical power, destabilizing system rankings, and contributing to the phenomenon of "benchmark saturation," where benchmarks fail to distinguish between increasingly capable systems.

The paper argues that benchmark saturation is not solely a result of poor data collection or task difficulty but is significantly exacerbated by the choice of evaluation measure.

Methodology

The authors propose Preference-Based Trajectory Evaluation, a framework that shifts from assigning scalar values to individual trajectories to assigning signed preferences to pairs of trajectories based on temporal preference.

Core Concept: Temporal Preference

Instead of temporal discounting (which requires assuming a specific, often arbitrary, relationship between time and utility via hyperparameters), the authors adopt temporal preference. This principle states: Given two systems achieving the same task progress, prefer the system that reached it sooner. This requires no additional hyperparameters and makes fewer assumptions about the domain.

Proposed Measures

The paper introduces three specific preference-based metrics that operate by comparing trajectories $f$ and $f'$ across return levels $R \in [0, 1]$ :

Lexicographic Return (LR): A conservative approach that prioritizes the highest return level where trajectories differ. If one trajectory succeeds ( $R=1$ ) and the other does not, the successful one is preferred. If both succeed (or both fail), it breaks ties by comparing the time-to-return at the highest level of difference. This aligns closely with SR but adds temporal resolution for ties.
Return-Paired Preference (RPP): This metric integrates time-to-return across all return levels. It sweeps uniformly through all achieved return levels, comparing the time required to reach each level for both trajectories. It aggregates these comparisons weighted by the segment width, effectively measuring cumulative temporal advantage.
Interval-Paired Preference (IPP): This metric focuses on local temporal efficiency. Instead of absolute time-to-return, it compares the time increment ( $\delta$ ) required to advance from one return level to the next. This captures consistency of progress at sub-goal transitions.

Evaluation Framework

The authors evaluate these methods against standard baselines (SR, Partial Return (PR), and Success weighted by Path Length (SPL)) across five benchmark families (AgentBoard, OpenHands-Index, TheAgentCompany, TALES, and a synthetic SGRL dataset).

The evaluation relies on meta-evaluation criteria:

Validity: Measured via inter-measure similarity (convergent validity) and agreement with an "oracle" ground truth (criterion validity) using the SGRL-oracle dataset.
Reliability: Assessed via split-half reliability and leave-one-out stability to determine ranking consistency under data perturbation.
Sensitivity: Measured by tie rate (reduction of indistinguishable pairs) and discriminative power (ability to detect statistically significant differences between systems).
Data Efficiency: Analyzed by measuring how quickly a metric converges to a stable ranking as the number of evaluation samples decreases.

Key Results

The empirical results across diverse agentic and interactive benchmarks demonstrate that trajectory-aware preferences outperform scalar metrics in all meta-evaluation dimensions:

Reduction in Ties: Preference-based methods reduce the tie rate from approximately 75% (under SR) to roughly 35%. This recovers a substantial portion of previously discarded signal.
Oracle Agreement: In the SGRL-oracle dataset, where ground truth rankings are known, SR and PR achieved only 12.8% accuracy in recovering true preferences. In contrast, trajectory-preference measures (LR, RPP, IPP) exceeded 94% accuracy. RPP, in particular, detected 63.2% of true preferences as statistically significant (under FDR correction), compared to 48.1% for SPL and 0% for SR/PR.
Reliability: Trajectory-preference methods (LR, RPP) demonstrated higher split-half reliability (correlation ~0.83–0.85) compared to scalar metrics (0.70–0.75). They also exhibited greater stability under leave-one-out perturbations.
Sensitivity and Discriminative Power: Preference-based metrics maintained high discriminative power across the full range of task difficulties, including domains where models were uniformly successful or uniformly failing. In contrast, SR's discriminative power collapsed at these extremes.
Data Efficiency: Preference-based measures reached stable system rankings with fewer evaluation instances. For example, RPP achieved significant accuracy with 50–60% of the data that SPL required for full-data performance.

Significance and Claims

The paper claims that the choice of evaluation measure is a critical, often overlooked, factor in benchmark utility. The primary significance of this work includes:

Reframing Benchmark Saturation: The authors suggest that the perceived saturation of benchmarks is partly an artifact of using insensitive metrics (like SR) that collapse distinct trajectories into ties, rather than an inherent limitation of the tasks or data.
Efficiency without New Data: The proposed methods recover lost signal and improve statistical power using existing trajectory logs, requiring no additional data collection, reweighting, or hyperparameter tuning.
Offline Preference Evaluation: The work establishes a rigorous framework for offline preference-based evaluation, offering the benefits of arena-style comparisons (variance reduction, improved sensitivity) while retaining the safety, speed, and counterfactual analysis capabilities of offline evaluation.
Methodological Shift: By moving away from temporal discounting (which assumes a fixed time-utility relationship) to temporal preference, the approach provides a more principled and robust way to evaluate agentic systems that interact with environments over time.

The authors conclude that shifting to preference-based comparisons over trajectory structure allows for more reliable, sensitive, and data-efficient evaluation of agentic systems, directly addressing the statistical inefficiencies inherent in current success-rate-based paradigms.