On the Reliability Limits of LLM-Based Multi-Agent Planning

arXiv:2603.26993v2 Announce Type: replace-cross Abstract: LLM-based multi-agent planning delegates operational decisions to specialists that communicate through finite reports. In this research, we study its reliability limits when a coordinator can revisit source records before completing a resource-constrained plan. A useful report can support an immediate decision or direct later reading, so its value depends on how these stages communicate. We derive exact communication and access tradeoffs and prove that two report forms suffice for a broad class of allocation requirements, one favoring immediate resource identification and the other distinguishing absence from unnamed availability. For shared capacity, this reduction permits joint optimization of reporting roles and adaptive reads for a fixed number of source types with unequal workloads and reading costs. Identical specialists can optimally report different facts, and maximizing immediate completion can impose an unbounded recovery cost penalty even with full-record access. We also conduct numerical experiments to quantify the benefits of the proposed joint optimization and show how source access improves language-agent decisions that already use their reports optimally. In particular, an exhaustive evaluation of 207,632 report designs on small allocation instances recovers the predicted joint optima. Our analysis suggests that reliable agent communication should be evaluated by the complete decisions it supports and the cost of finishing its unresolved cases, instead of solely by report length, local prediction accuracy, or immediate task completion, as is often the case in current practice.