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