Rethinking Parallel Multi-Agent Systems: A Cost-Aware Framework for Efficient Coordination

LLM-based agent systems are increasingly used to solve complex multi-step tasks, where sequential execution incurs substantial end-to-end latency. In principle, parallelizing work across multiple agents should yield near-linear speedups. However, in practice, existing parallel multi-agent systems often run slower than a single-agent baseline. We attribute this gap to two hidden costs that parallel execution incurs but a serial agent avoids. First, there is a \emph{re-exploration cost}: redundant effort spent by parallel workers reconstructing context that the orchestrator already possesses, including prior decisions, conventions, and intermediate reasoning that would otherwise be inherited implicitly in a serial execution. Second, there is an \emph{alignment cost}: the overhead required to reconcile inconsistencies across independently generated outputs. Based on this decomposition, we derive a principled decision criterion: a layer should be parallelized only when its critical-path cost, plus re-exploration and alignment overheads, is lower than the corresponding serial cost. While this criterion is naturally expressed in wall-clock time, we observe that LLMs are poorly calibrated when asked to estimate task duration. Their predictions are strongly anchored to human engineering intuition rather than model throughput. The resulting bias is not monotonic, so even the relative ordering of task costs can be reversed between estimates and actual execution. To address this, we instead measure cost in predicted output tokens, a quantity that LLMs can estimate more reliably because it corresponds directly to their own generation behavior. For a fixed model, token cost also serves as a backend-independent proxy for time. Building on this token-based criterion, we propose \textsc{CostPar}. It estimates all token budgets in a single planning step, forks each worker directly from the orchestrator’s session to eliminate re-exploration cost, and replaces post-hoc reconciliation with a pre-generated shared convention block that converts alignment into a bounded upfront cost. A deterministic scheduler then applies the criterion layer by layer. Empirically, \textsc{CostPar} achieves a 2.2$\times$ mean throughput improvement and a 2.6$\times$ mean wall-time speedup over Claude Code, and a 2.0$\times$ throughput improvement over the strongest multi-agent baseline.