The Orchestrator Bottleneck: Formal Coordination Strategies for Cost-Optimal Multi-Agent Enterprise Workflows

Multi-agent LLM systems increasingly depend on orchestrator agents to coordinate specialist agents, yet orchestration strategies remain informal, chosen by convention rather than analysis. We formalize the orchestrator as a constrained optimization problem over a typed agent registry with capability declarations, cost profiles, and trust boundaries. We define three coordination strategies, sequential delegation, parallel fan-out, and hierarchical decomposition, and derive threshold conditions under which each minimizes a combined cost-latency objective for a given task dependency structure. We implement OrchestRAte, a strategy-switching orchestrator that selects coordination mode dynamically via dependency graph analysis, and evaluate it on three enterprise workflow benchmarks: document processing, compliance review, and incident triage. On these benchmarks, OrchestRAte reduces end-to-end cost by 28–42% relative to static sequential baselines while trading at most 0.7 percentage points of task-completion quality. The cost gains come with a caveat: on highly parallelizable tasks, a static parallel baseline still achieves the lowest raw latency because it avoids the overhead of strategy selection entirely. We identify an empirical orchestrator overhead threshold around 15% of total token budget, beyond which the coordination cost of hierarchical strategies erodes their planning advantage.