Complete Cyclic Subtask Graphs for Tool-Using LLM Agents: Flexibility, Cost, and Bottlenecks in Long-Horizon Workflows

Abstract:Long-horizon tool-using tasks sometimes benefit from revisiting earlier subtasks, but explicit revisitation also adds routing, coordination, and token cost. We study complete cyclic subtask graphs for large language model (LLM) agents: a workflow controller in which executable subtasks are fully connected and a unified state-analysis-and-routing agent selects transitions from natural-language criteria. We evaluate task-specific (Spec-Cyc) and benchmark-generic (Gen-Cyc) cyclic graphs on TextCraft, ALFWorld, and Finance-Agent against ReAct and dependency-directed workflows. Our main dependency-directed controller is DepDAG, which permits same-subtask retry while preserving forward dependency constraints. The evaluated case studies suggest three workflow signatures rather than a universal architecture ranking. TextCraft behaves like a prerequisite-chain setting, where cyclic routing often adds overhead. ALFWorld behaves like a partially observable recovery setting, where explicit revisitation improves exploration and success. Finance-Agent behaves like an open-ended evidence-synthesis setting, where workflow control alone is insufficient without stronger retrieval, grounding, and verification mechanisms. We add a qualified workflow-signature matrix, fault-injection robustness analysis, token-cost accounting, graph-stability reporting, transition-audit checks for DepDAG, and failure-mode structure for trajectory analysis. Overall, complete cyclic subtask graphs are best understood as a diagnostic workflow-control tool: they expose when flexible backtracking is worth its cost and when simpler, locally retrying, or sparsified controllers are preferable.

37 pages, 8 figures. Published in Transactions on Machine Learning Research (TMLR), 2026. Supplementary material included as ancillary material

Multiagent Systems (cs.MA); Artificial Intelligence (cs.AI)

arXiv:2604.22820 [cs.MA]

(or arXiv:2604.22820v2 [cs.MA] for this version)

https://doi.org/10.48550/arXiv.2604.22820 Focus to learn more arXiv-issued DOI via DataCite

SUPPMAT_TMLR_2026_R2.pdf

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.