Source-linked AI summary
Synthesizing Agentic Data for Web Agents with Progressive Difficulty Enhancement Mechanisms
Shrey Pandit, Xuan-Phi Nguyen, Yifei Ming, Austin Xu, Jiayu Wang, Caiming Xiong, Shafiq Joty
TL;DR
Prior synthetic-data methods often lack fine-grained control over question difficulty, and differing training recipes make data effects hard to isolate. ProgSearch iteratively hardens questions using a baseline web agent and evaluates datasets under a controlled training setup. Its smaller dataset yields stronger benchmark performance than existing alternatives.
Problem
Prior synthetic-QA methods often lack fine-grained control over difficulty, while differing training processes and underlying models make data-synthesis effects difficult to isolate.
Source: §1 · pp. 1–2Method
ProgSearch uses top-down tree-of-facts and bottom-up rare-entity question generation, with a baseline web agent involved in refinement, factuality checks, and filtering.
Source: §1 · p. 2, §3 · p. 3, §3.3 · p. 6Results
Takeaways & Limitations
ProgSearch-trained agents achieve performance gains without substantially increasing tool calls compared with baseline datasets.
Source: §4.2.2 · p. 8
Abstract
from arXiv · showhide
Web-based 'deep research' agents aim to solve complex question - answering tasks through long-horizon interactions with online tools. These tasks remain challenging, as the underlying language models are often not optimized for long-horizon reasoning and exploration. Prior work has proposed workflows for constructing instruction-tuning datasets, often leveraging knowledge graphs. However, such methods typically lack fine-grained control over difficulty and quality, yielding synthetic data that falls short of capturing the complexity required for long-horizon reasoning. Furthermore, many studies conflate data and training effects by comparing models trained under different optimization recipes, making it difficult to isolate and evaluate the effectiveness of the data itself. We introduce a two-pronged data synthesis pipeline that generates question - answer pairs by progressively increasing task complexity until a frontier baseline web agent fails. The baseline agent plays multiple roles in this process: attempting the questions, validating factuality, checking for alternative answers, and enforcing filtering. To evaluate the effectiveness of our synthesis methods, we adopt a controlled training setup based on distillation from strong web agents. Experiments across multiple web-based benchmarks show that our dataset - despite being smaller - enables the training of more effective web agents than existing datasets. In particular, our data exhibits twice the diversity in tool-use actions, allowing models trained on it to achieve stronger performance while avoiding repetitive tool-calling behaviors.
1 INTRODUCTION
Web-agent data synthesis is difficult to evaluate separately from model optimization, while prior methods often lack fine-grained difficulty control. ProgSearch progressively hardens questions using a baseline web agent, and controlled comparisons report stronger downstream performance from its smaller dataset.
1 INTRODUCTION
- Prior synthetic-QA methods often lack fine-grained difficulty control against strong post-trained web agents, limiting their gains when tuning already capable models.The paper also notes that training and the underlying LLM can obscure the contribution of data synthesis.Source: §1 · pp. 1–2
- ProgSearch progressively increases question difficulty by adding supporting facts, with a baseline web agent helping refine and validate the questions.Its top-down approach builds a tree-of-facts; its bottom-up approach starts from a rare entity and generates increasingly difficult questions.Source: §1 · p. 2, Figure 1 · p. 2
- The evaluation varies only the training data source, using GPT-OSS-generated distillation trajectories to fine-tune Qwen3-8B and Qwen2.5-7B.The tuned models are evaluated on GAIA, HLE, and BrowseComp under a contamination blocklist.Source: §1 · p. 2
- Despite its smaller size, ProgSearch yields stronger downstream performance, with gains up to 8% on Qwen3-8B and 23% on Qwen2.5-7B.The dataset also produces more diverse tool use, which the authors connect to stronger benchmark performance.Source: §1 · pp. 2–3
2 RELATED WORKS
Prior web-agent work uses synthetic QA data, but existing approaches may not control difficulty with a live agent or consistently filter low-quality questions. ProgSearch combines two generation strategies, baseline-agent difficulty assessment, and filtering.
2 RELATED WORKS
- Earlier web-agent datasets and synthesis pipelines include knowledge-graph construction and iterative question transformations, but may not gauge difficulty with a live agent or rule out multiple plausible answers.Some prior datasets are also unreleased or insufficiently described for replication, and the paper notes a lack of systematic analysis independent of training algorithms.Source: §2 · p. 3
- ProgSearch combines top-down tree-of-facts question generation with bottom-up questions anchored on rare entities, while using a strong baseline agent to assess difficulty and filtering to address factuality and alternative answers.The two approaches target different question styles and structures.Source: §2 · p. 3
3 METHODOLOGY
ProgSearch repurposes topic-balanced questions from existing datasets as seeds, then splits them between tree-based top-down synthesis and rare-entity bottom-up hardening. Both streams undergo consolidated filtering.
3.1 TOP-DOWN SYNTHESIS WITH TREE-OF-FACTS
- The top-down arm expands relational facts into disjoint DFS branches, incrementally adding facts until the solver fails; ancestor exclusions keep each branch fact novel.The tree structure links new facts to prior context while excluding entities already mentioned in ancestor nodes.Source: §3.1 · pp. 4–5
3.2 BOTTOM-UP SYNTHESIS WITH RARE ENTITY ANCHOR
- The bottom-up arm selects a rare entity as the answer, then hardens questions through a researcher-questioner/solver loop until the solver misses that answer.Rarity is motivated by greater obscurity and reduced risk of pretraining contamination.Source: §3.2 · pp. 5–6
3.3 CONSOLIDATED FILTER
- The consolidated filter checks answer format, naturalness and reasoning complexity, verifies source support, and rejects ambiguity or solver-supported alternatives.If the baseline agent's conflicting answer is reasonably supported by its tool outputs, the QA pair is discarded.Source: §3.3 · p. 6
- From roughly 40K 2WikiMultihopQA questions, synthesis yields about 12K QA pairs and rejection-sampled distillation leaves approximately 6K SFT samples.Trajectories average 20 tool calls, with complex examples reaching 94.Source: §3.3 · p. 6
4 EXPERIMENTS
The experiments compare rejection-sampled training data and fine-tuned agents across web benchmarks, then analyze tool use and dataset characteristics. ProgSearch trajectories are longer, and trained checkpoints show effective tool use, lower failure rates, and broad topic coverage.
4 EXPERIMENTS
- The experiments and ablations evaluate the synthesis process and dataset through supervised fine-tuning and analyses comparing ProgSearch with baseline methods.The analyses cover rejection-sampled data, trained-checkpoint tool use, and dataset examples and domains.Source: §4 · p. 7, §4.2 · p. 7
4.1 SETUP & RESULTS
- Setup compares ProgSearch (12K samples) with Taskcraft (20K) and Asearcher (35K), using rejection-sampled ground-truth-consistent trajectories and four benchmarks under a contamination blocklist.The trajectories are used to fine-tune Qwen3-8B and Qwen2.5-7B-Instruct.Source: §4.1 · p. 7
4.2.1 TOOL USAGE OF REJECTION SAMPLING DATA
- 20.43 tool calls per trajectory in ProgSearch rejection-sampled data is twice Asearcher’s average and four times Taskcraft’s; this corresponds to 41.43 user and tool-result turns.ProgSearch data also has more search actions relative to browse and Python actions.Source: Table 2 · p. 8, §4.2.1 · p. 8
4.2.2 TOOL USAGE OF TRAINED CHECKPOINTS
- On FRAMES and GAIA, ProgSearch-trained Qwen3-8B averages 11.8 and 15.5 unique tool calls per trajectory, only about one more than Taskcraft, yet achieves up to 10% performance gains.Asearcher induces significantly more tool calls but yields lower accuracy.Source: §4.2.2 · p. 8, Table 3 · p. 9
- ProgSearch achieves the lowest tool-call failure rate among the compared checkpoints, improving performance while reducing wasted time and context tokens.#Error reflects invalid syntax or parameters.Source: §4.2.2 · p. 8, Table 3 · p. 9
4.2.3 DOMAINS & EXAMPLES
- ProgSearch spans topics relatively evenly, with a slight history bias, while Taskcraft is concentrated in Science, Art, Politics, and Other.The authors believe broader topical diversity contributed to stronger downstream performance.Source: §4.2.3 · p. 9, Figure 4 · p. 9
- A representative ProgSearch multi-hop question required the gpt-oss-20b agent to make 93 tool calls before reaching the correct answer.Table 4 presents the question-answer pair, ground truth, and tool-call count.Source: §4.2.3 · p. 8, Table 4 · p. 9
5 CONCLUSION
The conclusion presents ProgSearch as a two-pronged way to create training data aligned with long-horizon web reasoning. The authors report stronger benchmark performance despite smaller dataset size.
5 CONCLUSION
- The two-pronged synthesis pipeline progressively raises task difficulty and uses a frontier baseline agent for validation and filtering.The resulting data is described as more diverse, factually reliable, and aligned with long-horizon reasoning demands.Source: §5 · p. 9
- Despite being smaller, the resulting dataset enables stronger performance across benchmarks.Source: §5 · p. 9
- The authors conclude that careful design and controlled complexity can be more impactful than sheer scale in advancing web-agent effectiveness.Source: §5 · p. 9
6 STATEMENTS
The statements disclose limited LLM use in preparing the paper and make dataset release conditional on approval.
6 STATEMENTS
- The authors report using LLMs only to fix LaTeX code bugs for diagrams, styles, and figures, not to write the paper’s textual content.Source: §6 · p. 10
- The authors plan to open-source the full datasets, subject to approval from institutional leaders and regulatory advisors.Source: §6 · p. 10
A.1 DETAILS ON DATA SYNTHESIS ALGORITHMS
The appendix details three synthesis algorithms: recursively expanding a tree of facts, generating harder questions from its branches, and hardening questions around a rare entity anchor.
A.1 DETAILS ON DATA SYNTHESIS ALGORITHMS
- BuildTreeOfFacts recursively expands a seed entity into a depth-limited tree by adding k related facts that exclude entities already on the current ancestor path.Each new fact becomes a child node, and the process recurses until the maximum depth is reached.Source: §A.1 · p. 13
- TopDownGen generates QA pairs from tree branches, revising invalid questions and adding facts when the solver answers correctly, until it finds a hard question or exhausts its limits.A question is returned when validation succeeds and the solver does not produce the ground-truth answer.Source: §A.1 · p. 13
- BottomUp starts with a rare entity as the ground-truth answer, repeatedly rewrites the question using research facts, and returns the question with that answer if the solver's answer changes.If hardening reaches its limit while the solver still returns the anchor, the algorithm returns null.Source: §A.1 · p. 14
A.2 PROMPT USED FOR DATA SYNTHESIS
These prompts guide agents in gathering source-backed facts, generating difficult single-answer questions, and checking question–answer pairs for correctness and quality. They emphasize multi-hop reasoning, evidence-grounded and unambiguous answers, clues whose intersection uniquely identifies an answer, and explanations of the solver’s reasoning.
Fact seeker
- Fact-seeking prompts require real, meaningful, specific, self-contained facts supported by exact, valid URLs, favoring reputable sources and excluding webpage metadata or common knowledge.They prohibit using the agent’s own knowledge or fabricating facts or sources.Source: §A.2 · pp. 14–15
Fact seeker with exclusion
- An exclusion-aware fact seeker avoids researching excluded entities or details, so newly expanded fact trees do not form circular connections.For example, when a seed mentions A and B but excludes A and C, it should seek facts only about B.Source: §A.2 · p. 15
Verification with ground truth
- Ground-truth verification judges semantic consistency rather than exact wording and returns only yes or no, treating contradictions or missing key information as inconsistent.The prompt supplies comparison rules for numbers, dates, extra information, refusals, and other answer forms.Source: §A.2 · pp. 16–18
Validation against question-answer standards
- Validation accepts only readable questions seeking one concise answer that require difficult web research and complex reasoning, and rejects directly answerable questions or refusals.Valid questions should involve multiple facts and entities and yield concrete, non-intuitive answers.Source: §A.2 · p. 18
QA generation given facts
- Question generation must rely solely on supplied facts to create a difficult, unambiguous multi-hop question linking entities indirectly to one concise answer without searchable alternatives.The prompt also asks for an answer and a basic explanation based only on those facts.Source: §A.2 · p. 19
Bottom up approach - Initial Question (Q0) creation prompt
- The bottom-up approach begins Q0 creation with a prompt instructing a question-generation assistant to create search-intensive questions.The supplied passage gives this initial instruction but no further Q0 criteria.Source: §A.2 · p. 20
Question generation
- The prompt forbids exact or vague time references and specific or general geographic details that could narrow the search.Examples include exact years, vague periods, named places, and broad regional descriptions.Source: §A.2 · p. 20
- It also bars organization and award names, titles, exact numbers, names, and abstract or relative descriptions.The restrictions include references such as “multiple works” or “various achievements.”Source: §A.2 · p. 20
- Question generation combines individually common clues so their intersection identifies exactly one entity, with no alternative correct answer.The prompt requires checking that no other entity satisfies all the criteria.Source: §A.2 · p. 20
Bottom up approach - Solver LLM Prompt
- The solver prompt calls for systematic web searching, stepwise clue reasoning, a specific answer, and an explanation of searches and decisive clues.The response format separates the answer from detailed reasoning.Source: §A.2 · pp. 20–21
Bottom up approach - Difficulty enhancement loop
- The hardener is explicitly assigned the task of making an overly easy question much harder by removing or obscuring the clues used by the solver.It receives the easy question and the solver’s reasoning as inputs.Source: §A.2 · p. 21
- The difficulty loop takes an easy question and the solver’s reasoning, then obscures used clues, makes descriptions vaguer, removes identifying features, preserves the answer, and adds inference steps.A new clue may also be added to make the hardened question unique.Source: §A.2 · p. 21
- The hardener must keep the answer unchanged and ensure the revised question still has exactly one correct answer.It should retain enough subtle clues to identify the answer, adding a clue if another entity could fit.Source: §A.2 · p. 21
A.3 MORE SYNTHESIZED PROGSEARCH EXAMPLES
This section presents additional ProgSearch dataset examples selected from questions that required substantial effort from the baseline agent.
A.3 MORE SYNTHESIZED PROGSEARCH EXAMPLES
- The section presents additional examples from the ProgSearch dataset.The examples are among those the baseline gpt-oss-20b agent spent the most effort correctly solving.Source: §A.3 · p. 21
- The examples were selected from questions that gpt-oss-20b spent the most effort correctly solving.Source: §A.3 · p. 21
- The examples illustrate cases the baseline agent ultimately solved correctly.Source: §A.3 · p. 21
A.4 ADDITIONAL EXPERIMENTS
The additional experiments report that ProgSearch still improves performance when gpt-oss-20b is fine-tuned on its own rejection-sampled data, though the gains are relatively small.
A.4 ADDITIONAL EXPERIMENTS
- ProgSearch still improves over baseline datasets when gpt-oss-20b is fine-tuned on rejection-sampled data generated by that same agent.Table 6 covers four benchmarks under a contamination blocklist and compares ProgSearch with Taskcraft and Asearcher.Source: §A.4 · p. 21, Table 6 · p. 23
- The improvement margin is relatively small, which the authors attribute to gpt-oss-20b already being well-trained.Source: §A.4 · p. 21
- The authors say one-time rejection sampling, particularly by the same baseline agent, is not effective at pushing performance and that reinforcement learning may be more effective.Source: §A.4 · p. 21
- Table 5 provides additional multi-hop QA examples, their ground-truth answers, and the tool-call counts for gpt-oss-20b solving them.Source: Table 5 · p. 22