On-Demand Multi-Agent Workflow Synthesis for Multimodal Long-Horizon Reasoning

Multimodal agentic tasks---spanning web operations, software workflows, and tool-augmented reasoning over heterogeneous information sources---increasingly require coordinating multiple specialized agents rather than scaling a single generalist through longer reasoning chains. Designing such multi-agent systems remains combinatorially hard: existing approaches commit to fixed templates and domain-specific training, or deploy autonomous generalists at growing inference cost. We introduce TSAS (Two-Stage Agent Synthesis), a framework that generates task-specific multi-agent systems on demand. Given a task description, a single meta-agent call produces both a pool of specialized agents and a directed acyclic graph defining their coordination, without iterative search or additional training. On the GAIA benchmark, which probes long-horizon reasoning across web search, image, audio, and structured-file modalities, TSAS achieves 47.18% accuracy with GPT-5-mini at $31.58 per run, matching the top autonomous system while reducing cost by 61%, and outperforming agents built on Claude Opus~4 and Claude-4.5 Sonnet by over 16 percentage points. We further show that workflow generation can be distilled: a fine-tuned meta-agent (GraphGen-14B, based on Qwen2.5-Coder) reaches 57.57% on GAIA validation, more than doubling prior fine-tuned baselines. The code is available at https://anonymous.4open.science/r/aa3ADD.