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

• URL: http://arxiv.org/abs/2604.22820v1
• Date: Fri, 17 Apr 2026 15:31:20 GMT
• Title: Complete Cyclic Subtask Graphs for Tool-Using LLM Agents: Flexibility, Cost, and Bottlenecks in Multi-Agent Workflows
• Abstract summary: We study complete cyclic subtask graphs in which executable subtask nodes are fully connected.<n>We evaluate task-specific (Spec-Cyc) and benchmark-generic (Gen-Cyc) graphs on TextCraft, ALFWorld, and Finance-Agent.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Long-horizon tool-using tasks sometimes benefit from revisiting earlier subtasks for recovery and exploration, but added multi-agent workflow flexibility can also introduce coordination overhead and substantial inference cost. We study complete cyclic subtask graphs, a deliberately maximally flexible multi-agent architecture in which executable subtask nodes are fully connected and a unified state-analysis-and-routing agent selects transitions using natural-language criteria. This makes unrestricted revisitation explicit and directly analyzable at the subtask level. We evaluate task-specific (Spec-Cyc) and benchmark-generic (Gen-Cyc) graphs on TextCraft, ALFWorld, and Finance-Agent, with ablations over planner/executor/router strength, tool exposure (generalist vs specialized), $n$-shot successful trajectory summaries, and fault-injected random subtask perturbations. The benchmarks expose three distinct regimes. ALFWorld highlights a setting where explicit revisitation supports recovery and exploration; TextCraft, a largely prerequisite-chain domain, often favors the efficiency of simpler forward execution; and Finance-Agent remains bottlenecked by retrieval, grounding, and evidence synthesis more than by workflow flexibility alone. Shared-win token comparisons further show that the added flexibility can be substantially more expensive than a single ReAct agent. Overall, we use complete cyclic subtask graphs as a maximally flexible experimental lens for measuring when multi-agent revisitation helps, when it mainly adds coordination cost, and when external task bottlenecks dominate.

Related papers

• Hybrid Workflow Composition for Extreme-Scale Data Processing: A Case Study on the HL-LHC (Extended Version) [0.5156484100374059]
  This paper presents a novel simulation framework for characterizing the interplay between taskset granularity and system-level constraints.<n>Results show that hybrid composition strategies can yield up to 3.8x throughput increase and a 14.9x reduction in network overhead.
  arXiv  Detail & Related papers  (2026-07-29T13:07:31Z)
• A Matter of TASTE: Improving Coverage and Difficulty of Agent Benchmarks [25.713629634281077]
  We propose TASTE: Task Synthesis from Tool Sequence Evolution, an automatic method that generates challenging tasks with broader tool-use coverage.<n> TASTE selects representative sequences from the pool via clustering, instantiates them into complete benchmark tasks, and refines them through difficulty evolution.<n>Our results suggest high scores on existing benchmarks often reflect saturation rather than robust task-solving ability.
  arXiv  Detail & Related papers  (2026-05-27T14:45:59Z)
• Why Search When You Can Transfer? Amortized Agentic Workflow Design from Structural Priors [51.95306551061392]
  Automated agentic workflow design currently relies on per-task iterative search.<n>We present SWIFT, a framework that amortizes workflow design into reusable structural priors.<n> SWIFT outperforms the state-of-the-art search-based method on five benchmarks.
  arXiv  Detail & Related papers  (2026-04-27T21:25:00Z)
• AgentSwing: Adaptive Parallel Context Management Routing for Long-Horizon Web Agents [115.18197165538943]
  Large language models (LLMs) evolve into autonomous agents for long-horizon information-seeking.<n>Existing context management methods typically commit to a single fixed strategy throughout the entire trajectory.<n>We introduce a probabilistic framework that characterizes long-horizon success through two complementary dimensions: search efficiency and terminal precision.
  arXiv  Detail & Related papers  (2026-03-29T02:59:27Z)
• ANCHOR: Branch-Point Data Generation for GUI Agents [52.22377425487]
  End-to-end GUI agents for real desktop environments require large amounts of high-quality interaction data.<n>We present a trajectory expansion framework Anchor that bootstraps scalable desktop supervision from a small set of verified seed demonstrations.<n>Experiments on standard desktop benchmarks, OSWorld and WindowsAgentArena, show that models fine-tuned on our expanded corpus achieve consistent improvements.
  arXiv  Detail & Related papers  (2026-02-06T19:55:26Z)
• Experience-Driven Multi-Agent Systems Are Training-free Context-aware Earth Observers [27.817039954088315]
  We introduce textbfGeoEvolver, a self-evolving multi-agent system for learning tool-level expertise.<n>We show that GeoEvolver consistently improves end-to-end task success, with an average gain of 12% across multiple backbones.
  arXiv  Detail & Related papers  (2026-01-30T15:11:07Z)
• Rethinking the Value of Multi-Agent Workflow: A Strong Single Agent Baseline [38.16649115214312]
  We show that a single agent can reach the performance of homogeneous with an efficiency advantage from KV cache reuse.<n>We propose an algorithm that automatically tailors for single-agent execution, reducing inference costs.
  arXiv  Detail & Related papers  (2026-01-18T08:16:09Z)
• Do We Always Need Query-Level Workflows? Rethinking Agentic Workflow Generation for Multi-Agent Systems [72.3575737073235]
  Multi-Agent Systems (MAS) solve complex tasks by coordinating multiple agents through.<n>Existing approaches generates either at task level or query level, but their relative costs and benefits remain unclear.<n>We show that query-level workflow generation is not always necessary, since a small set of top-K best task-level together already covers equivalent or even more queries.
  arXiv  Detail & Related papers  (2026-01-16T10:05:51Z)
• M$^3$Prune: Hierarchical Communication Graph Pruning for Efficient Multi-Modal Multi-Agent Retrieval-Augmented Generation [18.091284320771006]
  We propose a novel Multi-Modal Multi-agent hierarchical communication graph PRUNING framework, termed M$3$Prune.<n>Our framework eliminates redundant edges across different modalities, achieving an optimal balance between task performance and token overhead.<n>Our method consistently outperforms both single-agent and robust multi-agent mRAG systems.
  arXiv  Detail & Related papers  (2025-11-25T06:29:13Z)
• GAP: Graph-Based Agent Planning with Parallel Tool Use and Reinforcement Learning [20.75113227786218]
  Graph-based Agent Planning (GAP) is a novel framework that explicitly models inter-task dependencies through graph-based planning.<n>Our approach trains agent foundation models to decompose complex tasks into dependency-aware sub-task graphs.<n>This dependency-aware orchestration achieves substantial improvements in both execution efficiency and task accuracy.
  arXiv  Detail & Related papers  (2025-10-29T09:35:55Z)
• AgentRouter: A Knowledge-Graph-Guided LLM Router for Collaborative Multi-Agent Question Answering [51.07491603393163]
  tAgent is a framework that formulates multi-agent QA as a knowledge-graph-guided routing problem supervised by empirical performance signals.<n>By leveraging soft supervision and weighted aggregation of agent outputs, Agent learns principled collaboration schemes that capture the complementary strengths of diverse agents.
  arXiv  Detail & Related papers  (2025-10-06T23:20:49Z)
• AgentSynth: Scalable Task Generation for Generalist Computer-Use Agents [60.881609323604685]
  Agent Synth is a scalable and cost-efficient pipeline for automatically synthesizing high-quality tasks and trajectory datasets.<n>Our pipeline achieves a low average cost of $0.60 per trajectory, orders of magnitude cheaper than human annotations.
  arXiv  Detail & Related papers  (2025-06-17T05:46:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.