TMLR 2026
Complete Cyclic Subtask Graphs for Tool-Using LLM Agents: Flexibility, Cost, and Bottlenecks in Long-Horizon Workflows
Long-horizon tool-using tasks sometimes benefit from revisiting earlier subtasks, but revisiting costs routing, coordination and tokens. The paper studies complete cyclic subtask graphs, in which every subtask can hand off to every other and a single router picks each transition by checking natural-language criteria, and compares them with ReAct and dependency-ordered graphs on TextCraft, ALFWorld and Finance-Agent.
Cyclic graphs raise ALFWorld success from 33.8% (ReAct) to 58.2%, and the benchmark-generic graph keeps 87-96% of its TextCraft success when half of its routing decisions are replaced at random. ReAct stays stronger and cheaper on TextCraft; the paper maps where revisiting pays for itself and what it costs.
BibTeX
@article{gharzeddine2026cyclic,
title = {Complete Cyclic Subtask Graphs for Tool-Using {LLM} Agents: Flexibility, Cost, and Bottlenecks in Long-Horizon Workflows},
author = {Gharzeddine, Luay and Saab Jr, Samer},
journal = {Transactions on Machine Learning Research},
year = {2026},
url = {https://openreview.net/forum?id=FAkarhXCfI}
}