TLDR: This research introduces ProgSearch, a novel two-pronged data synthesis pipeline that generates challenging question-answer pairs for training web agents. It progressively increases task difficulty using a baseline web agent for validation and filtering. The pipeline employs both top-down (tree-of-facts) and bottom-up (rare entity anchor) approaches to create diverse and complex questions. Despite being smaller, the resulting ProgSearch dataset enables the training of more effective web agents, leading to stronger performance on benchmarks, more diverse tool-use actions, and lower error rates compared to existing datasets.
Web-based “deep research” agents are designed to tackle complex question-answering tasks by interacting with online tools over extended periods. These agents, often powered by large language models (LLMs), face significant hurdles because LLMs are not inherently optimized for the long-term reasoning and exploration required for such tasks. A major challenge lies in creating high-quality training data that accurately reflects the complexity and multi-step nature of real-world web interactions.
Understanding the Challenge for Web Agents
Previous efforts to create instruction-tuning datasets for these agents often relied on knowledge graphs. However, these methods frequently lacked precise control over the difficulty and overall quality of the generated data. This often resulted in synthetic data that didn’t fully capture the intricate reasoning needed for long-horizon tasks. Furthermore, many studies inadvertently mixed the effects of data quality with the effects of different training optimization techniques, making it hard to pinpoint whether improvements came from better data or better training methods.
Introducing ProgSearch: A Novel Data Synthesis Pipeline
To address these limitations, researchers at Salesforce AI Research and the University of Wisconsin-Madison have introduced a new data synthesis pipeline called “Progressive Search,” or ProgSearch. This innovative pipeline generates question-answer pairs by progressively increasing task complexity. A key aspect of ProgSearch is its use of a baseline web agent, which plays multiple crucial roles: it attempts the generated questions, validates factual accuracy, checks for alternative answers, and enforces strict filtering criteria. This integration of an active agent into the data generation process allows for fine-grained control over difficulty and quality.
The Two Approaches: Top-Down and Bottom-Up
ProgSearch employs a two-pronged approach to data synthesis, ensuring diversity in question styles and structures.
Top-Down Synthesis with Tree-of-Facts
In the top-down method, the pipeline constructs a “tree-of-facts” starting from a seed entity. Instead of traditional knowledge graphs, this tree links relational facts, allowing for the systematic creation of questions with gradually increasing difficulty. The process involves iteratively expanding a fact pool and prompting a questioner agent to generate QA pairs. If a baseline solver agent successfully answers a question, new facts are added to make the next question harder. This continues until the solver agent fails, indicating an appropriately challenging question has been created.
Bottom-Up Synthesis with Rare Entity Anchor
The bottom-up approach focuses on generating challenging questions centered around a specific, rare entity. The process begins by selecting a less popular entity as the ground truth answer. An initial question is then generated, and if the solver agent answers it correctly, the question is progressively “hardened.” This hardening involves obfuscating details, removing easily identifiable clues, and incorporating new information from web searches, all while ensuring the question still uniquely points to the rare entity. This iterative process continues until the solver agent can no longer correctly answer the question, yielding a complex QA pair.
Ensuring Quality: The Consolidated Filter
A critical component of ProgSearch is its aggressive filtering process, applied both during iterative generation and after QA pairs are finalized. This “consolidated filter” ensures high-quality data by checking several criteria:
- Question Standards: Questions must be natural, readable, seek a single concrete short-form answer, and require complex multi-hop, compositional, abductive, mathematical, or temporal reasoning. The answer should not be trivially deducible from the question.
- Factuality Verification: All generated QA pairs and their supporting facts are rigorously checked against web sources to ensure factual and contextual accuracy.
- Dealing with Alternative Answers: The pipeline specifically addresses cases where question hardening might inadvertently lead to multiple plausible answers. If the baseline agent’s conflicting answer is reasonably supported by its browsing results, the QA pair is discarded to prevent unfair penalization during training.
Also Read:
- Evaluating AI’s Deep Research Abilities: A New Standard
- PRISM: A New Agentic Approach to Smarter Information Retrieval for Complex Questions
Impactful Results and Key Insights
The ProgSearch pipeline generated a dataset of approximately 12,000 high-quality QA pairs, which, after rejection sampling for distillation trajectories, resulted in about 6,000 usable samples for supervised fine-tuning. Despite being smaller than existing datasets like Taskcraft (20,000 samples) and Asearcher (35,000 samples), ProgSearch demonstrated superior performance.
Experiments showed that models fine-tuned on ProgSearch data achieved significant gains on widely used web-based benchmarks such as FRAMES, GAIA, Humanity’s Last Exam (HLE), and BrowseComp. For instance, Qwen3-8B trained with ProgSearch saw improvements of up to 16% on FRAMES and 11% on GAIA over the base model, consistently outperforming models trained on other datasets.
A key finding was the increased complexity and reasoning depth of ProgSearch’s synthesized QA pairs. Trajectories generated from ProgSearch data contained an average of 20 tool calls, which is twice as many as Asearcher and four times more than Taskcraft. This indicates that ProgSearch provides richer, longer-horizon trajectories that better prepare agents for complex tasks. Furthermore, models trained on ProgSearch data exhibited more diverse and effective tool use, along with a lower tool call failure rate, leading to stronger benchmark performance without simply inflating the number of tool calls.
The dataset also boasts a broader topical diversity, covering subjects relatively evenly with a slight bias towards history, which is believed to contribute to stronger downstream web agent performance compared to datasets heavily concentrated in specific domains.
In conclusion, the ProgSearch pipeline offers a principled method for creating higher-quality training data for web agents. By progressively increasing task difficulty and using a frontier baseline agent for validation and filtering, it produces datasets that are more diverse, factually reliable, and aligned with the demands of long-horizon reasoning. This research highlights that thoughtful design and controlled complexity in data synthesis can be more impactful than sheer scale in advancing the effectiveness of web agents. For a deeper dive into the methodology and experimental details, you can read the full research paper here.
