Confidence Coordination: Adaptive Decomposition and Execution of Long-Horizon Tasks

Large language models have made substantial progress in reasoning and task execution, but extending their capabilities to long-horizon operations requires careful problem decomposition and error control. Decomposition makes individual subproblems easier to solve but introduces additional coordination and state-transfer costs. Determining an appropriate decomposition therefore remains central to reliable long-horizon execution. This paper proposes the Confidence Coordination (CONCORD) framework, which addresses the problem through adaptive decomposition and Monte Carlo Tree Search-based execution. The framework explores alternative partial solutions using confidence estimates and dependency checks, allowing subproblems to contain multiple execution steps. The theoretical analysis provides a foundation for solvability and scalability by linking subproblem size and execution reliability to final-answer accuracy and cost over longer task horizons. To validate this theoretical advantage, experiments were conducted to compare CONCORD to state-of-the-art monolithic language models and prior decomposition approaches in a long-horizon challenge domain: matrix multiplication with varying numbers of matrices (horizon) and dimensions (complexity). CONCORD successfully solved the task at twice the horizon of the best-performing monolithic model with the same budget. More generally, the decomposition and execution configuration could be tuned to achieve lower cost and/or higher accuracy than alternative approaches. CONCORD thus provides a way to use given resources to solve more complex long-horizon problems.