Scaling Web Agent Training through Automatic Data Generation and Fine-grained Evaluation

We thank the reviewers for their insightful comments. Reviewers noted that we present an effective approach for automatic evaluation and partial trajectory extraction using constraints (puzT, mfjm, 3xdz, 3mSW), demonstrate significant improvements over baselines on key benchmarks (puzT, mfjm, 3mSW), and introduce a new benchmark valuable for future research (mfjm, 3xdz, 3mSW). We address specific review points below.

Ability to handle soft constraints
Our framework does not restrict the form of constraints -- In principle, they can capture arbitrarily complex constraints (such as if/else constraints). However, such scenarios do not appear in our benchmark.
Our benchmark is a step towards studying agents in longer horizon and more structured tasks. As we demonstrate, existing agents such as Browser Use and Claude Computer Use which have been shown to perform well in other tasks struggle in this setting.
We leave the exploration of more complex constraint types to future work.

Evaluation of constraint extraction
Note that we do not use any predefined ontology to derive the constraints and LLMs are used to generate the constraints as free form text. We leverage powerful LLMs (e.g., LLaMA 3, GPT) to extract constraints, resulting in highly accurate outputs. To evaluate their quality, we conducted a human study on 120 test tasks. Annotators were presented with a task description and asked to identify an exhaustive set of constraints. Our key findings were:

• In all cases, the constraints identified by human annotators were a subset of those extracted by the LLM. In some instances, the same constraint was expressed differently (e.g., a human might annotate "trip type: one-way" while the LLM outputs "flight_type: one-way"). We treat such semantically equivalent constraints as matches.
• In a few cases, human annotators failed to capture all constraints accurately. For example, when a task required both departing and return flights to be non-stop, human annotator only provided "non-stop: True", which can be ambiguous.

In summary, constraint extraction using LLMs proved to be highly accurate and robust for our test tasks.

use of partial trajectories seem to provide only a small boost in performance
When leveraging partial trajectories, task success rate improves from 16% to 25% compared to using successful trajectories only, which is a relative improvement of 56%.

Which partial trajectories are useful
Success/failure is a strict metric that can limit data yield, especially on harder websites with low success rates. Partial trajectories let us capture meaningful progress made by the teacher agent, even if the task wasn't fully completed (e.g., Figure 2). Including them is essential for scaling data coverage and learning from a wider range of agent behaviors.

Why should we assume that an evaluator that assess the underlying model as correct more often is itself more correct than a harsher one?
Our main intention was to point out that environment-based signals (e.g., screenshots, URLs) are more reliable than agent-based signals (e.g., action histories), which often lead to hallucinations.
For instance, comparing screenshot only vs screenshot + action history, the former is more stringent, and in fact more reliable, as inclusion of action history leads to hallucination (which was also verified with human evaluation).
However, when comparing screenshot only vs screenshot + url, although the former is more stringent, it also penalizes cases where agent made progress that is not reflected in the final page (we provide an example in line 246). The url can complement information in the screenshot, providing a more holistic view of the agent's progress.
So our conclusion isn’t that lenient evaluators are better, but that evaluation should rely on observable environment signals, which are more trustworthy.

same model for generating trajectories and fine-tuning
This is an interesting case, but we haven't tried it. But we do expect improvements in this case as well.

Why use only final screenshot for evaluation?
Reasoning over multiple screenshots introduces complexities, such as detecting whether a previously satisfied constraint was later undone by another action. In contrast, the final page more directly reflects the cumulative outcome of all agent actions. This simplifies the evaluation process and enables the use of LLMs/VLMs that may not reliably reason over multiple observations.

WebVoyager evaluation
Note that we do not use constraint-based evaluation for reporting WebVoyager performance - Rather, we use the Webvoyager evaluation protocol .

Formatting
Thanks for pointing out the formatting issues, we will fix this in the revision.

We thank the reviewers for their insightful comments. Reviewers noted that we present an effective approach for automatic evaluation and partial trajectory extraction using constraints (puzT, mfjm, 3xdz, 3mSW), demonstrate significant improvements over baselines on key benchmarks (puzT, mfjm, 3mSW), and introduce a new benchmark valuable for future research (mfjm, 3xdz, 3mSW). We address specific review comments below.

Significance of Results
In order to evaluate agents on a larger set of tasks, we doubled the number of tasks per website. Due to limited time, we compare our approach against Operator and UI-TARS, the top performing methods for this experiment (We will include Claude Computer Use and Browser Use results in the revision).
We present the result on all 240 tasks below (20 websites, 12 tasks per website), along with the delta from the previous result (on 120 tasks). We find that performance is generally consistent with our previous runs. The most significant delta was observed for Operator SR, but this does not alter the relative performance trend among models.

"travel booking scenarios is limited"
While our work focuses on travel booking tasks, the approach naturally extends to other structured, constraint-driven domains such as e-commerce. These tasks are common in real-world applications and pose challenges due to their long-horizon nature. Notably, they are (i) underrepresented in existing benchmarks like WebVoyager and (ii) difficult for prior methods (e.g., Browser Use, Claude Computer Use) to solve. For these reasons, we believe our booking benchmark offers a valuable contribution toward advancing the capabilities of autonomous agents.

applicability to tasks not defined in terms of explicit constraints
Due to the fuzzy nature of the constraints, our approach is also applicable to tasks that are not defined in terms of explicit constraints. For instance, we show that our approach works well on search tasks from the WebVoyager benchmark.

Performance Bounded by Teacher Model
We note that our fine-tuned student agent significantly outperforms the teacher model, despite also being much smaller. We present this comparison in Table 2, where the LLAMA 405B teacher agent achieves (SR, CSR) = (0.17, 0.48), whereas the Mistral 24B model trained on partial trajectories with LoRA achieves (SR, CSR) = (0.25, 0.56). We believe that large scale automated data generation coupled with effective data curation strategies can help advance the frontier of agents.

How do we ensure that the set of constraints is both stable and comprehensive?
We use powerful LLMs (e.g., LLaMA 3, GPT) to extract constraints as free-form text, resulting in high-quality outputs. To assess their accuracy, we conducted a human study on 120 test tasks. Annotators were given task descriptions and asked to exhaustively list all relevant constraints. Our key findings were:

• In all cases, the human-identified constraints were a subset of those extracted by the LLM. In some cases, constraints were phrased differently but were semantically equivalent (e.g., “trip type: one-way” vs. “flight_type: one-way”), which we treat as matches.
• In a few instances, annotators missed constraints. For example, when a task required both outbound and return flights to be non-stop, a human annotator provided only “non-stop: True,” which is ambiguous.

In summary, constraint extraction using LLMs was found to be both accurate and robust across our test set.

Based on CSR, do you only discard intermediate steps that fail? How about the following steps?
As described in lines 133–136, we extract the trajectory prefix until timestep t' where t' is the timestep in the trajectory for which the most constraints were satisfied. The following steps (i.e., t > t') are discarded.

Formatting issues. Thank you for pointing this out. We will fix formatting issues in the revision.

We thank the reviewers for their insightful comments. Reviewers noted that we present an effective approach for automatic evaluation and partial trajectory extraction using constraints (puzT, mfjm, 3xdz, 3mSW), demonstrate significant improvements over baselines on key benchmarks (puzT, mfjm, 3mSW), and introduce a new benchmark valuable for future research (mfjm, 3xdz, 3mSW). We address specific review points below.

Overlap between train and test distributions
We examine the overlap between test tasks and training tasks.
For each test task and website, there is no training task that has the same exact combination of constraints and values.
When ignoring the values, the same exact combination of constraints appears in the training set for the same website for only 9/120 tasks. We further verify that, when excluding these 9 tasks from the evaluation, the task SR remains the same while CSR drops by 1%, indicating that these few overlapping cases are not driving the overall performance.
In addition, we also demonstrate competitive performance on the WebVoyager benchmark, which shows the transferability of knowledge from our training tasks to unseen tasks.

Details about BookingArena benchmark

• Task format: Each task is identified by a starting url and task description. There are no local copies of the websites as this tends to limit the evaluation. Agents are required to interact with actual websites. The tasks are general enough that they will remain robust to website changes.
• Number of steps: Yes, tasks often require multi-step navigation across different pages. The average length of successful trajectories from our fine-tuned agent in BookingBench is 10.6.
• Number of target constraints: Each of the 20 websites in the test set have a total of 6 tasks (2 easy, 2 medium, 2 hard). We report the minimum, maximum and average number of constraints in the tasks in each difficulty category below.
• Diversity: This shows that tasks are diverse both at the website level and difficulty level.
  We will incorporate these details into the revision.

Error analysis

We provide difficulty-wise performance for our fine-tuned agent below. Performance naturally declines as the task difficulty and number of constraints increases.

In contrast to LLM/VLM-as-judge approaches that produce a single success/failure judgment, our constraint-based evaluation offers fine-grained insights into which aspects of a task the agent struggles with. Specifically, we measure how often each constraint is successfully satisfied across tasks. Success rates for the 10 most frequent constraints are shown in the table below. Intuitively, location-related constraints have higher success rates, as they are often filled early in the task. In contrast, constraints related to amenities, such as pet-friendliness, are handled later in the task and have low success rates as a result, due to the dependency on prior actions.

Human evaluation of automatic evaluation
Protocol: For each task, a human annotator was shown the final screenshot from the agent’s trajectory and asked to label each constraint as either met or unmet. We also obtained met/unmet judgments for each constraint using an LLM. Agreement score was defined as the fraction of constraints for which the human and LLM judgments matched. The overall agreement score was computed by macro-averaging across tasks.

We evaluated 75 trajectories in this manner. When only the final screenshot was provided, the agreement score was 72.69%. When both the screenshot and the agent’s action history were provided, the agreement dropped to 69.42%. This suggests that including the agent’s actions and reasoning can sometimes mislead evaluators into believing certain constraints were satisfied, since agent actions may have failed or not achieved the intended outcome.

We thank the reviewers for their insightful comments. Reviewers noted that we present an effective approach for automatic evaluation and partial trajectory extraction using constraints (puzT, mfjm, 3xdz, 3mSW), demonstrate significant improvements over baselines on key benchmarks (puzT, mfjm, 3mSW), and introduce a new benchmark valuable for future research (mfjm, 3xdz, 3mSW). We address specific review points below.

Computational cost
All experiments were conducted on two machines, each with 16 × A100 40GB GPUs.
We deploy LLaMA 70B and LLaMA 405B (4-bit) models as LLM servers, each requiring 8 GPUs — allowing us to run up to four servers in parallel. These yield approximately 84k and 16k trajectories per week, respectively.
For evaluation, we use 4-bit quantized LLaMA 70B models, which can fit in 2 A100 GPUs. Unlike trajectory generation, evaluation does not require web interaction and is highly parallelizable. The full dataset was evaluated with step-level evaluation in 4 days. We will include these computational details in the revision.

Booking Arena task creation
The prompt used for generating tasks in BookingArena is given in Figure 3. For each of the 20 websites, we used this prompt to generate 6 tasks covering all three difficulty levels (2 easy, 2 medium, 2 hard). We provide examples of easy, medium and hard tasks below.

Example easy task: On booking.com, find a hotel available in Miami, FL for a single night on June 15, 2025.
Example medium task: On ihg.com, locate a pet-friendly hotel in Orlando, Florida with free Wi-Fi, available for the dates June 17, 2025 to June 22, 2025.
Example hard task: On kayak.com, find a multi-city flight itinerary starting from Chicago (ORD) to Paris (CDG) on June 10, 2025, and then from Paris (CDG) to Rome (FCO) on June 20, 2025, all in business class.

Human Studies
We conducted human studies to evaluate the quality of (i) constraint extraction and (ii) automatic evaluation. Our key findings are summarized below:

• Constraint Extraction
  Annotators were given 120 task descriptions from our test set and asked to exhaustively list all relevant constraints. In all cases, the human-identified constraints were a subset of those extracted by the LLM. In a few instances, annotators missed constraints. For example, when a task required both outbound and return flights to be non-stop, a human annotator provided only “non-stop: True,” which is ambiguous. Overall, constraint extraction using LLMs was found to be accurate and robust.

• Automatic Evaluation
  For each task, a human annotator was shown the final screenshot from the agent’s trajectory and asked to label each constraint as either met or unmet. We obtained the same judgments using an LLM. Agreement was defined as the fraction of constraints for which human and LLM judgments matched, and the overall score was computed by macro-averaging across tasks. Using this protocol, we observed an agreement score of 72.69% based on 75 evaluated trajectories.

We will include further details about these studies in our revision.