When Parallelism Pays Off: Cohesion-Aware Task Partitioning for Multi-Agent Coding

Multi-agent Large Language Model (LLM) systems offer a way to decompose complex tasks such as coding through parallelization and context isolation, but adding agents in practice introduces inter-agent communication overhead that can offset efficiency gains. We formalize multi-agent orchestration as a graph partitioning problem that captures the *communication-to-computation trade-off*: task decomposition can shorten critical-path computation, while cross-agent dependencies require costly context transfer. We instantiate this view in repository-level software engineering through **Co**hesion-aware **Coder** (CoCoder), which builds dependency graphs from static analysis, isolates structural hub files, partitions the graph via community detection, and executes the partition with a dependency-aware scheduler. Across \(28\) real-world tasks on DevEval and CodeProjectEval, CoCoder Pareto-dominates sequential and file-based parallel baselines as well as Claude Code with Agent Teams, improving pass rate by up to \(14.0\%\) on CodeProjectEval, achieving up to a \($2.10\times$\) wall-clock speedup, and reducing API cost by up to \(35\%\), with the largest gains on the most dependency-dense projects. CoCoder demonstrates how dependency-aware orchestration can make parallel coding agents both theoretically grounded and practically efficient, suggesting a broader design principle for multi-agent LLM systems.