ProST: Progressive Sub-task Training for Pareto-Optimal Multi-agent Systems Using Small Language Models

Biddut Sarker Bijoy, Mohammad Saqib Hasan, Pegah Alipoormolabashi, Avirup Sil, Aruna Balasubramanian, Niranjan Balasubramanian · 2025

Read ProST: Progressive Sub-task Training for Pareto-Optimal Multi-agent Systems Using Small Language Models by Biddut Sarker Bijoy, Mohammad Saqib Hasan, Pegah Alipoormolabashi, Avirup Sil, Aruna Balasubramanian, Niranjan Balasubramanian (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-04508.txt.

Introduction

Biddut Sarker Bijoy and five co-authors train teams of small language models to handle complex app tasks in a 2025 research paper. Multi-agent systems built from small models could rival one big model on cost and speed, but small models struggle to learn long task trajectories, even when specialized by role. Their strategy, ProST, introduces new sub-tasks progressively during each training pass, like a curriculum that adds homework gradually. Tests run inside the AppWorld environment of simulated apps.

Progressive training improved multi-agent effectiveness at every configuration tried. A Pareto analysis, which weighs quality against cost, favored fine-tuned multi-agent systems for the trade-off. Ablations confirmed the strategy cuts sub-task error rates. Small-model teams become a credible budget option.

Catalog record

CREATORBiddut Sarker Bijoy, Mohammad Saqib Hasan, Pegah Alipoormolabashi, Avirup Sil, Aruna Balasubramanian, Niranjan Balasubramanian
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE63 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-04508

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

ProST: Progressive Sub-task Training for Pareto-Optimal Multi-agent Systems Using Small Language Models Biddut Sarker Bijoy, Mohammad Saqib Hasan, Pegah Alipoormolabashi, Avirup Sil, Aruna Balasubramanian, Niranjan Balasubramanian Abstract Multi-agent systems with smaller language models (SLMs) present a viable alternative to single agent systems powered by large language models (LLMs) for addressing complex problems. In this work, we study how these alternatives compare in terms of both effectiveness and efficiency. To study this trade-off, we instantiate single and multi-agent systems for the complex problems in the AppWorld environment using different sized language models. We find that difficulties with long-trajectory learning in smaller language models (SLMs) limit their performance. Even when trained for specialized roles, SLMs fail to learn all subtasks effectively. To address this issue, we introduce a simple progressive sub-task training strategy, which introduces new sub-tasks progressively in each training epoch. We find that this novel strategy, analogous to instance level curriculum learning, consistently improves the effectiveness of multi-agents at all configurations. Our Pareto analysis shows that fine-tuned multi-agent systems yield better effectiveness-efficiency trade-offs. Additional ablations and analyses shows the importance of our progressive training strategy and its ability to reduce subtask error rates. 1 Introduction Solving complex problems requires a wide-range of capabilities including planning sub-tasks, acting in an environment via coding, reasoning about the actions, recovering from errors, as well as tracking and managing the execution of sub-tasks. LLMs with their strong coding and reasoning abilities and advances in handling long contexts have shown impressive breakthroughs on such complex problems (e.g., AppWorld ( Trivedi et al. 2024 ) and SWE-Bench ( Jimenez et al. 2024 ) ). However, these large models incur high computational and API costs. Another viable alternative is to use multi-agent solutions with smaller language models 1 1 1 Small and large are subjective terms. For this paper we use SLM for models with fewer than 40B parameters. (SLMs). The core idea is to identify specialized roles in solving these complex tasks (e.g, orchestration, code writing, and critiquing) and use separate SLMs (or SLM calls) for each role. Belcak et al. 2025 argue that SLMs are much more cost-effective and practical for training, adapting, and deploying multiple specialized experts for different agentic routines. Shen et al. 2024 show these multi-agent solutions with SLMs can be effective for complex problems requiring tool use via APIs. We consider two challenges that arise in this context. First, for SLMs, even specialized roles can be difficult to learn. Complex problems often have multiple subtasks resulting in long trajectories. Despite their improving capabilities, SLMs still struggle to learn all subtasks under standard fine-tuning. Second, while the per-token compute depends on the size of the models, the overall computational cost also depends upon the nature of their solutions (e.g their length). Therefore, it is important to explicitly consider both the effectiveness and efficiency of these solutions to better understand the trade-offs. We address these challenges using AppWorld benchmark. We design a multi-agent solution with three agents: an Orchestrator that plans subtasks incrementally, an Executor that interacts with the environment via code to solve subtasks, and a Critic agent that critiques the Executor output. We make two specific contributions on this multi-agent setup: 1) Progressive Sub-task Training To address the inconsistent performance on large trajectories, we introduce a progressive training strategy. We find that SLMs are unable to solve some sub-tasks of these complex problems, even in role-specialized learning settings. We propose a simple curriculum-style learning strategy, where we introduce sub-tasks progressively in training epochs. This allows the small capacity SLMs to gradually expand their learning, covering all aspects of the problem trajectories. 2) Pareto Analyses We compare different instantiations of single and multi-agent systems. In particular, we plot the efficacy of different solutions against inference-time FLOPs . The Pareto curve for these solutions helps choose the best solution at different compute budgets. We evaluate these ideas using the Qwen family of models. We distill training trajectories for a single agent from a frontier model ( Claude-3.7-Sonnet ). Then, we translate these into role-specific multi-agent training trajectories for three agents, namely, an Orchestrator (planner), an Executor (coding) agent, and a Critic agent. Our evaluations yield multiple interesting observations AppWorld tasks: (i) While larger models tend to have higher effectiveness, multi-agent solutions can achieve better efficiency versus effectiveness trade-offs. (ii) Progressive Subtask Training yields a better Pareto-front compared to standard fine-tuning. (iii) Stronger (higher compute) agents for planning are more effective (and efficient) than using stronger coding and critic agents when finetuning using Progressive Subtask Training. 2 Related Work SLM-based Agents SLMs are being used as agents due to lower computational cost, but struggle with complex planning and tool use ( Shen et al. 2024 ) , skills essential for agents. Hence, many strategies are proposed: separation of roles to only tackle small, concrete tasks ( Shi et al. 2024 ; Qiao et al. 2024 ) ; distilling training data from powerful LLMs ( Shi et al. 2024 ) , Direct Policy Optimization (DPO) ( Feng et al. 2025 ) ; online learning by generating data from unsuccessful attempts ( Qi et al. 2025 ) , masking loss from erroneous steps ( Fu et al. 2025 ) ; learning only from critical steps ( Chen et al. 2025d ) . Contrary to these works, we formulate ProST which optimizes SLMs, as part of multi-agent design, by initiating with important parts of the trajectory and iteratively increasing steps, a strategy never tried for agents. Multi-Agent Optimizations Many works propose techniques to make multi-agents more robust. These techniques include dynamically reducing redundant agents and messages ( Wang et al. 2025b ; Zhang et al. 2024 ) , iterative answer refinement through feedback ( Chen et al. 2025b ) , optimizing collaboration strategies ( Wang et al. 2025a ; Zeng et al. 2025 ) and communication protocols ( Xiao et al. 2025 ) , and test-time search for effective tool planning ( Chen et al. 2025a ) . Recent works propose using cost-effective SLMs for multi-agent setups: Erdogan et al. 2025 uses smaller 32-B models as planning and execution subagents; Belcak et al. 2025 argue for SLM multi-agents based on their improved capabilities, cost, ease of adaptability, and deployment. Our work introduces ProST , a training algorithm for SLMs in multi-agent setups that iteratively trains on subtasks. Unlike previous works, we show how ProST produce SLMs effective at solving tasks as well as computationally efficient. Efficiency of Multi-agents Recent works have sought to assess and improve the computational efficiency of multi-agent systems. For example, Wang et al. 2025b use token consumption as a metric to prune redundancies in multi-agent collaborations. Yue et al. 2025 show, via Pareto fronts, that their language model routing strategy in multi-agent systems reduces dollar cost while improving accuracy. Wang et al. 2025a use token accuracy ratio to compare multi-agent collaboration strategies. In contrast, we analyze computational cost against task accuracy to measure Pareto optimality . Based on this, we design ProST , which gives better performance accuracy with higher computational efficiency (more Pareto optimal ). 3 Multi-Agent Design for AppWorld Multi-agent systems using SLMs instead of LLMs have emerged as an alternative for better cost-performance trade-off Erdogan et al. 2025 ; Belcak

Read the complete text