GATS (Graph-Augmented Tree Search), a planning framework that combines systematic UCB1-based tree search with a layered world model to eliminate LLM calls during inference while achieving superior planning performance, is presented.
Abstract
Large Language Model (LLM) agents have shown promise in multi-step planning tasks, but existing approaches like LATS (Language Agent Tree Search) and ReAct rely heavily on LLM inference during planning, leading to high computational costs and stochastic behavior. We present \textbf{GATS} (Graph-Augmented Tree Search), a planning framework that combines systematic UCB1-based tree search with a layered world model to eliminate LLM calls during inference while achieving superior planning performance. Our three-layer world model integrates: (L1) exact symbolic action matching, (L2) statistics learned from execution logs, and (L3) LLM-based prediction for unknown actions. On synthetic planning tasks with branching paths and dead-ends, GATS achieves \textbf{100\% success rate} compared to 92 % for LATS and 64\% for ReAct. On a comprehensive stress test spanning 12 challenging scenarios -- including coding workflows, web navigation, and long-horizon tasks -- GATS maintains \textbf{100\% success} while LATS drops to 88.9 % and ReAct to 23.9%. GATS requires \textbf{zero LLM calls per task} during planning (vs. 37 per task for LATS) and produces deterministic plans with zero variance across runs. Our results demonstrate that systematic search with learned world models can substantially outperform LLM-guided exploration for agent planning.
This work reframe trajectory evaluation as a distance between the agent's execution graph and a set of valid solution graphs, and instantiates OTAP via an unbalanced fused Gromov-Wasserstein transport problem over attributed dependency graphs, which is a pseudo-metric that is provably invariant to dependency-preserving reorderings and has bounded sensitivity to redundant steps.
Babak Barazandeh, Subhabrata Majumdar, G. Michailidis· 0 citations
A structured taxonomy is presented that organizes existing work into three complementary paradigms that represent dominant architectural tendencies in current LLM-based embodied task planning research, and compares these paradigms along dimension of accuracy, robustness, scalability, efficiency, and sim-to-real transfer.
Zhen Zhang· Applied and Computational En...· 0 citations
Optimizing agentic workflows, such as retrieval-augmented generation (RAG) pipelines, requires navigating a combinatorial space of discrete component choices under tight evaluation budgets. Existing approaches - heuristic search, black-box optimization, and standard tree search methods - do not explicitly exploit the compositional structure of these workflows, leading to redundant computation and inefficient budget allocation. We introduce Agent-UCT (Agent-based Cost-Aware Upper Confidence Bounds Applied to Trees), a tree search algorithm that extends UCT with a reuse-aware regularization term derived from a bipartite prefix reuse graph. Agent-UCT biases selection toward branches that leverage previously materialized configuration prefixes, reducing redundant execution while maintaining effective exploration. Our framework, RAGSpace, unifies heterogeneous RAG components from LongRAG, LightRAG, and Self-RAG into a five-dimensional configuration space, enabling systematic cross-framework recombination. WTB (Workflow Test Bench) provides deterministic replay, content-addressable caching, and transactional consistency, ensuring that intermediate states are materialized once and reused across the search. Experiments on HotpotQA and UltraDomain demonstrate that Agent-UCT identifies configurations with the highest out-of-sample performance among the evaluated fixed framework presets. Under full-pool evaluation, bipartite prefix reuse reduces logical search cost by 73.6% relative to the no-prefix-sharing cost upper bound. Compared with full-pool evaluation, sampling-based evaluation further achieves a 4.2x wall-clock speedup. Agent-UCT, RAGSpace, and WTB together provide a unified framework for cost-aware, reproducible, and compositionally efficient agentic workflow optimization.
This work introduces AgentSearch, a cost-aware Monte Carlo Tree Search (MCTS) framework that constructs agentic workflows through deliberative lookahead search and attains single-episode success while reducing computational costs by up to 47%, thereby eliminating the trial-and-error exploration required by previous adaptive methods.
D. Attota, Ying Xie· Proceedings of the 15th Inte...· 0 citations
AgentWeave is introduced, a deterministic pre-inference routing layer that constructs a bounded model-visible action space using eligibility, requirement, capability, and routing signals and shows lower mean local-model latency.
Saurav Singla, A. Singla, Advik Gupta et al.· 0 citations
This work introduces tentative object pruning, an approach that leverages this property by constructing multiple simplified tasks with reduced object sets and searching them in parallel until a valid, satisficing solution is found.
Anita de Mello Koch, Naman Shah, Cameron S. Allen et al.· 0 citations