Building autonomous agents capable of navigating complex digital environments—such as websites, mobile operating systems, or data analysis sandboxes—requires massive amounts of high-quality data for both training and evaluation. Traditionally, creating these tasks has relied on expensive human engineering or naive top-down generation, where a Large Language Model (LLM) is simply prompted to write a list of user goals.
However, top-down generation suffers from a fundamental flaw: hallucinated feasibility. An LLM might generate a highly plausible instruction (e.g., "Book a flight from New York to London under $400 leaving tomorrow at 5 PM") that is completely impossible to execute given the live state of the environment or the specific constraints of the underlying software.
To overcome this bottleneck, recent research has shifted toward a new paradigm: grounded and collaborative task synthesis. Instead of inventing tasks from thin air, systems either discover what is possible by exploring the environment first and retroactively labeling the actions (bottom-up synthesis), or they deploy specialized networks of models to iteratively propose, simulate, and verify tasks (top-down multi-agent pipelines).
Bottom-Up Synthesis: Exploration and Hindsight Labeling
The core intuition of bottom-up synthesis is simple: if an agent has already successfully executed a sequence of actions to reach a specific environment state, that task is guaranteed to be feasible. By letting an agent explore an environment randomly or heuristically, researchers can use an LLM to retroactively infer what goal those actions accomplished. This is known as hindsight instruction labeling or reverse task synthesis.
[ Environment Sandbox ] ──(Random/Noisy Exploration)──> [ Successful Trajectory ]
│
(Hindsight Inference)
▼
[ Labeled Training Pair ] <──(Pair Instruction + Actions)── [ Synthetic Goal ]
An early realization of this mechanism was demonstrated by Gur et al., who introduced an auxiliary instructor agent. This instructor observes random interactions within a web environment and learns to predict the instruction that would have resulted in the observed final state, creating synthetic training pairs without human intervention.
This framework has been scaled and refined across several domains:
- Web and GUI Navigation: Murty et al. developed BAGEL, which bootstraps web agents by having them label their own random trajectories, transforming unstructured exploration into high-quality training data. For operating systems, Qiushi Sun introduced OS-Genesis, a reverse task synthesis framework that executes interactions within a graphical user interface (GUI) first, and then leverages an LLM to retroactively infer the intended goal from the observed state changes.
- Preventing Hallucinations: To avoid the impossible goals common in top-down generation, Pahuja et al. utilized interaction-driven exploration in Explorer to ensure that all synthesized web trajectories are grounded in actual website capabilities. Similarly, Ramrakhya et al. designed AUTOPLAY, a pipeline where an explorer model actively "pokes around" digital interfaces to discover valid states before a generator proposes objectives.
- Tool Use and Reward Modeling: Zhou et al. applied this to tool-use sandboxes with the Self-Challenging Agent (SCA) framework, where an agent explores environment capabilities first to generate verifiable "Code-as-Task" problems. For reinforcement learning, Chen et al. introduced ARMAP, which observes environment interactions to synthesize positive task descriptions, pairing them with perturbed negative trajectories to automatically train robust multimodal reward models.
Top-Down Synthesis: Multi-Agent Collaborative Pipelines
While bottom-up exploration guarantees that tasks are executable, it can sometimes struggle to generate highly structured, multi-layered, or adversarial scenarios required for rigorous benchmarking. To solve this, researchers deploy multi-agent pipelines that break down the task generation process into specialized, modular roles—such as creators, critics, simulators, and verifiers.
┌─────────────────┐ ┌────────────────┐ ┌─────────────────┐
│ Agent 1: Goal │ ───> │ Agent 2: Param │ ───> │ Agent 3: Logic │
│ Taxonomy / │ │ Generation / │ │ Verification / │
│ Deconstruction │ <─── │ Refinement │ <─── │ Debugging │
└─────────────────┘ └────────────────┘ └─────────────────┘
By simulating a peer-review or assembly-line process, these pipelines can synthesize highly complex tasks while maintaining strict logical consistency.
1. Structural Modification and Parameter Generation
Instead of generating a benchmark task in a single prompt, multi-agent frameworks separate the high-level task structure from the specific parameters. For example, Zheng et al. designed PlanningArena using a three-stage pipeline where distinct agents suggest structural modifications, generate task parameters, and verify logical consistency. To evaluate motivational reasoning, Lian et al. developed MotiveBench using a collaborative architecture of questioners, reviewers, and modifiers to precisely control task difficulty and logical flow.
2. Environment and Logic Coding
When evaluating advanced reasoning, the task itself might be an entire interactive environment. Yin et al. (and in their subsequent work Yin et al.) introduced ORACLE, a framework that uses a pipeline of specialized models to generate, simulate, and debug code-based logic tasks. This multi-agent approach ensures that the resulting black-box environments behave consistently when probed by an evaluation agent.
3. Grounding in Real-World Artifacts
Multi-agent pipelines are also used to translate complex human documentation or real-world data into structured agent tasks:
- Data Analysis: Hasanbeig et al. developed ConDABench, a pipeline that extracts query-answer pairs from real-world articles and automatically identifies the underlying code required to ground the tasks in actual data journalism.
- Software Engineering: Ran et al. built APPFORGE by assigning specialized roles to summarize software documentation, record user interaction traces, and generate formal specifications for Android development benchmarks.
- Fact-Checking: Lin et al. introduced FACT-AUDIT, which utilizes specialized roles for taxonomy construction, data generation, and quality validation to dynamically create fact-checking datasets.
- Instruction Evolution: Xue et al. developed AndroidArena, which extracts application functionalities from web documentation and applies instruction evolution techniques to automatically transform simple goals into multi-step, cross-app instructions.
Why It Works: The Intuition of Feasibility and Modularity
The success of these automated synthesis techniques rests on two core principles: reachability and separation of concerns.
Reachability Eliminates the Search Gap
In traditional reinforcement learning or agent training, the hardest problem is the "sparse reward" problem—an agent wandering randomly is highly unlikely to complete a complex, multi-step task like booking a specific hotel.
Bottom-up synthesis flips the mathematical difficulty of this search. By recording where the agent happens to go during exploration, the environment state space is pre-sampled. Hindsight labeling merely acts as a translator, mapping natural language onto a path that is already known to exist. This guarantees that the training data contains zero unexecutable tasks, allowing the model to focus entirely on learning the mapping between language and action.
Modularity Eliminates Single-Prompt Hallucinations
When a single LLM is asked to generate a complex task, it must simultaneously handle the creative design, the parameter constraints, the logical consistency, and the formatting. This high cognitive load frequently causes the model to lose track of constraints, leading to broken tasks.
Multi-agent pipelines succeed because they introduce adversarial and cooperative checks. By separating the generation role from the verification role, one model can focus entirely on proposing creative scenarios, while a second model acts as a strict critic or debugger. Forcing the generated tasks through an automated execution or simulation loop ensures that any logical inconsistencies are caught and filtered out before the task is ever presented to an agent.
Key Foundational Work
Learning to Navigate the Web (2019) — contributed 2 concept elements to this direction.
Understanding the Weakness of Large Language Model Agents within a Complex Android Environment (2024) — contributed 1 concept elements to this direction.
BAGEL: Bootstrapping Agents by Guiding Exploration with Language (2024) — contributed 1 concept elements to this direction.