Embodied instruction following in interactive environments requires agents to interpret natural language commands and complete long-horizon tasks. Existing planners either rely on large labeled trajectories, or use few-shot and zero-shot LLM prompting that produces a whole plan in a single serial reasoning process. These approaches depend on linguistic common sense, commit to a plan from the initial instruction, and only update after failures, which weakens robustness and state awareness. We present AtomTree, a hierarchical framework for state-aware task planning with LLMs. AtomTree incrementally builds a tree of subgoals and actions, where the LLM decides at each step, from the current symbolic state, whether to further decompose or to output a grounded low-level action. A lightweight memory module summarizes past outcomes for reuse in later decisions. When a low-level action stalls, AtomTree triggers hierarchical backtracking replanning to return to the parent node and regenerate the subtree plan from the latest state, preventing continued drift along an incorrect trajectory. In zero-shot evaluation on the ALFRED benchmark, AtomTree outperforms prior LLM-based planners. Project page: https://zhaihaotian.github.io/atomtree-website/.
Figures & tables
Fig. 1 : Error analysis on the Valid Seen split of the ALFRED benchmark with respect to ground-truth PDDL plan length, showing that for FLARE, a state-of-the-art few-shot method, incorrect-plan errors dominate overall and become the primary failure mode for long-horizon tasks (PDDL length >7 ).
Fig. 2 : Overview of our hierarchical planning framework for embodied instruction following. Given a task instruction and the current visual state, our method recursively decides whether to decompose the current goal into finer-grained subgoals or execute it directly. This process incrementally builds an explicit hierarchical goal tree, shown in the upper-right panel, where higher-level goals are progressively refined into executable actions. In contrast, we compare against two representative paradigms: (1) a fully supervised end-to-end EIF model trained on the full dataset, and (2) an LLM-based method using retrieved few-shot examples. While these baselines may produce incorrect action sequences, our method maintains a structured tree-based plan and performs step-by-step decomposition conditioned on the current state and memory, enabling more accurate long-horizon reasoning and execution.
Fig. 3 : Overview of our state-aware decision prompt. The prompt summarizes the role and mission, decision options, input information, available atomic actions, global rules, output format, and a small set of decision-guiding examples. Given the current subgoal together with the current state and memory, the LLM predicts whether to decompose the goal into subtasks or execute it directly.
Valid Seen
Valid Unseen
Test Seen
Test Unseen
Method
Venue
Setting
State&History-Aware
SR
GC
SR
GC
SR
GC
SR
GC
Trained with large-scale instruction–trajectory pairs
FILM [ 10 ]
ICLR’22
Supervised
✘
N/A
N/A
N/A
N/A
25.77
36.15
24.46
34.75
CAPEAM [ 16 ]
ICCV’23
Supervised
✘
N/A
N/A
N/A
N/A
47.36
54.38
43.69
54.66
MCR-Agent [ 35 ]
AAAI’23
Supervised
✘
N/A
N/A
N/A
N/A
30.13
N/A
17.04
N/A
Prompter [ 11 ]
IROS’23
Supervised
✘
N/A
N/A
N/A
N/A
47.95
56.98
41.53
53.69
TABLE I : Quantitative comparison on ALFRED [ 1 ] . We report SR and GC on four splits: Valid Seen, Valid Unseen, Test Seen, and Test Unseen. We annotate each method by its evaluation setting, publication venue, and whether it is explicitly state- and history-aware. For methods that do not report results on certain splits or metrics, we mark them as “ N/A ”. Results marked with an asterisk (*) are produced by [ 13 ] .
#
Hier.
Memory
Replan
Valid Seen SR
Valid Unseen SR
(a)
✘
✘
✘
15.24
14.01
(b)
✔
✘
✘
27.20
24.73
(c)
✔
✔
✘
38.78
40.19
(d)
✔
✔
✔
40.98
42.39
TABLE II : Ablation of AtomTree on ALFRED validation splits. “Hier.” enables hierarchical planning with Decompose and a subgoal tree. “Memory” adds the state&history memory mt=(St,Ht) . “Replan” enables hierarchical backtracking replanning. We report SR on Valid Seen and Valid Unseen.
Fig. 4 : Qualitative comparison with and without memory. Without memory, the model predicts an incorrect subgoal after picking up the cleaned lettuce, whereas AtomTree correctly predicts the next subgoal as navigating to the fridge.
Fig. 5 : Comparison between a few-shot baseline and AtomTree on a multi-instance task.
Embodied instruction following (EIF) requires agents to understand and execute complex natural language commands within interactive 3D environments. Despite recent advances, existing methods often fail in long-horizon planning and handling irreversible state changes, resulting in low task success rates. To address these challenges, we introduce RePlan-Bot, a novel EIF agent that performs multi-level, continuous replanning throughout task execution. RePlan-Bot integrates a high-level LLM-based auditor for dynamic sub-goal adjustments guided by environmental feedback, a commonsense-guided search mechanism based on a multi-layered instance map for precise and structured object localization, and a lightweight ViT-based corrector to preemptively fix risky low-level actions. Evaluated on the ALFRED benchmark, RePlan-Bot achieves state-of-the-art performance in both seen and unseen environments, demonstrating superior adaptability and reliability.
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 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 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 100% success while LATS drops to 88.9 % and ReAct to 23.9%. GATS requires 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.
In this work we focus on the problem of embodied task planning, which requires an agent to accomplish a complex task by separating it into atomic actions. Recent studies have developed LLM-based methods to address this problem. However, the executability and correctness of the generated plans remain suboptimal in complex environments and tasks. On the other hand, classical search algorithms have the potential to solve the planning problems perfectly, yet they require fully observable environments, known state transitions and goal state, which are often unattainable in general task domains. Therefore, we propose to implement an LLM-guided search algorithm that makes the search process possible and efficient by incorporating LLMs' commonsense knowledge. Our method leverages LLMs to (1) translate natural language instructions into formatted goal conditions, (2) facilitate efficient exploration in partially observable environments, (3) implement a rule-based world simulator, and (4) prune the space of candidate actions to improve search efficiency. Experimental results on VirtualHome and ALFWorld demonstrate its superior performance.