CrossEnv: Synthesizing Verifiable Cross-Environment Tasks for Long-Horizon Agent Training

Zhengfeng Yu, Tian Lan, Zhijing Wu, Enbo Zhao, Xuannan Liu, Feihu Jiang, Qianghuai Jia, Longyue Wang, Zhao Xu, Weihua Luo, Xian-Ling MaoarXiv 2026 · arXiv

TL;DR

CrossEnv is a novel framework that automatically synthesizes complex, multi-service training tasks (e.g., travel planning involving flights, hotels, and dining) for LLM agents. By ensuring data consistency across different virtual environments and employing a progressive CrossEnv-Curriculum, it enables agents to master long-horizon coordination with significantly fewer training examples than previous methods.

What Problem Does This Paper Address?

While Large Language Models (LLMs) are increasingly used as agents that can call tools, training them for "long-horizon" tasks—those requiring many steps across different services—remains a major hurdle.

Existing synthetic training environments typically focus on single services in isolation. However, real-world workflows are messy and interconnected: booking a restaurant depends on your flight's arrival time and your hotel's location. Synthesizing these "cross-environment" tasks is difficult because the data must be perfectly aligned. If the "Hotel Booking" tool thinks a hotel is at one address, but the "Restaurant Search" tool uses a different database where that address doesn't exist, the agent's plan will fail through no fault of its own.

Figure 1: Independent tasks and a cross-environment task. (a) Flight, hotel, and dining tasks are completed and verified independently. (b) A travel-planning task uses flight arrival time, hotel location, and personal preferences to guide restaurant reservation, with joint verification of cross-environment requirements.

Methods

The authors introduce CrossEnv, which uses an entity-tool graph to bridge the gap between disparate environments. The framework operates in five phases:

  1. Research: Collecting "seeds" from tool documentation to build a taxonomy of business domains and capabilities.
  2. Local Dependency Graphs: Mapping how specific tools in one environment relate to entities (like "Person" or "City").
  3. Cross-Environment Graph Composition: Merging these local graphs via shared entities to identify potential multi-service workflows.
  4. Tool Synthesis: Automatically generating executable code for missing tools to ensure the environment is fully interactive.
  5. Task Instantiation & Verification: This is the "secret sauce." CrossEnv aligns task-specific data across environments (e.g., injecting the same hotel address into both booking and dining tools) and generates programmatic verification rules based on a "reference execution" path.
Figure 2: The five-phase pipeline for synthesizing verifiable cross-environment tasks.

To train the agents, they propose CrossEnv-Curriculum, which moves from simple single-tool use (L1) to coordinating two environments (L2), then three or more (L3), then across different business domains (L4), and finally adding human-in-the-loop interaction (L5).

Datasets

The authors synthesized a massive pool of tasks using 801 MCP seeds and 682 skill seeds, resulting in over 14,000 tool capability descriptions.

For evaluation, they tested their models on four diverse external benchmarks:

  • $\tau^2$-bench: Interactive tool use and user coordination.
  • DeepPlanning-Shopping: Long-horizon planning under constraints.
  • VitaBench: Coordinated service interactions.
  • Claw-Eval: General assistant tasks and professional dialogue.

Key Insights and Ideas

  • Data Consistency is King: The primary reason agents fail in multi-tool scenarios isn't just logic; it's often data fragmentation. By explicitly aligning entities across tool databases, CrossEnv creates a "verifiable" ground truth that provides high-quality feedback during reinforcement learning.
  • The Power of the Curriculum: Training on a mix of all task difficulties is less efficient than a staged approach. The curriculum allows the model to solidify basic execution skills before being overwhelmed by the complexity of cross-domain coordination.
  • Efficiency through Reuse: Because CrossEnv reuses environment data and entity relations, the average "construction cost" (in terms of tokens) per candidate task actually decreases as the environment pool grows.

Key Results

The CrossEnv-trained models (based on Qwen3) showed significant improvements over both base models and specialized environment-trained baselines like EnvScaler and Agent-World:

  • Competitive with Less Data: With only ~3,000 training records (roughly 25% of what some competitors use), CrossEnv-8B achieved top-tier performance on DeepPlanning and Claw-Eval.

  • Quantitative Gains: On the 8B model size, scores jumped from 1.7 to 10.8 on DeepPlanning and 14.4 to 23.6 on Claw-Eval compared to the base model.

  • Curriculum Advantage: As shown in Figure 4, the curriculum-based training achieved higher success rates at every task level compared to a "mixed" training strategy given the same compute budget.
Figure 4: Curriculum vs. Mixed (8B): (a) strict success at similar GPU-hours; (b) cumulative rollouts.

Limitations and Future Work

  • Simplicity vs. Reality: While executable, these synthetic environments are still cleaner than the real world. Real-world services have noisy APIs, rate limits, and non-deterministic behavior that this framework doesn't fully capture.
  • Seed Dependency: The diversity of synthesized tasks is ultimately limited by the initial pool of tool "seeds."
  • Future Directions: The authors suggest extending the framework to handle more complex, dynamic operational conditions and exploring how these agents transfer to live, real-world web services.

Summary updated

Abstract

Executable synthetic environments provide scalable training tasks and verifiable feedback for long-horizon agents. Existing environment synthesis methods primarily generate tasks within individual environments. However, these tasks do not adequately capture real-world interactions across services, where actions in one service depend on information obtained from another. Synthesizing such tasks is challenging because data generated across environments must remain consistent to support executable and verifiable interactions. To address this challenge, we introduce CrossEnv, a framework that uses an entity-tool graph to identify connections between environments and aligns task-specific data to synthesize executable, verifiable cross-environment tasks. We further propose CrossEnv-Curriculum, which progresses from single-environment tool use to coordination across more environments and business domains, before introducing user interaction. Across four external benchmarks, combining cross-environment training data with this curriculum achieves competitive performance with fewer training examples. Further analyses support the benefits of cross-environment data and curriculum training, and provide evidence of transfer to new environment combinations, external tasks less similar to the training data, and longer workflows.
BibTeX
@misc{yu2026crossenv,
  author = {Zhengfeng Yu and Tian Lan and Zhijing Wu and Enbo Zhao and Xuannan Liu and Feihu Jiang and Qianghuai Jia and Longyue Wang and Zhao Xu and Weihua Luo and Xian-Ling Mao},
  title = {{CrossEnv: Synthesizing Verifiable Cross-Environment Tasks for Long-Horizon Agent Training}},
  year = {2026},
  eprint = {2611.22777},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.22777},
}
Figure