AtomTree: A Hierarchical Framework for State-Aware Embodied Instruction Following with LLMs

Haotian Zhai; Tianming Sha; Junnan Li

cs.ROOct 28, 2026

AtomTree: A Hierarchical Framework for State-Aware Embodied Instruction Following with LLMs

Authors: Haotian Zhai, Tianming Sha, Junnan Li

Organizations: University of Minnesota · Stony Brook University · University of Wisconsin–Madison

Abstract

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

m_{t}=(S_{t},H_{t})

. “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.

Large Language Model-Based Robot Planning

Large language model-based robot planning turns natural-language goals and sensory observations into grounded, executable actions for robots.

See all 235 papers

RePlan-Bot: Multi-Level Replanning for Embodied Instruction Following
May 25, 2026Xicheng Gong, Guozheng Sun, Peiran Xu +1Large Language Model-Based Robot Planning Robot Task Planning
1Peking University · 2Tsinghua University
GATS: Graph-Augmented Tree Search with Layered World Models for Efficient Agent Planning
Jul 9, 2026Maureese Williams, Dymitr NowickiTree Search World Model-Based Planning
Institute for Cybernetics of NAS of Ukraine
TESS: LLM-guided Translation, Exploration, Simulation, and Search for Embodied Task Planning
Oct 19, 2026Peiran Xu, Yixiang Yang, Jinghan Li +4Robot Task Planning LLM Planning
Peking University · China Tower

May 25, 2026J/K move · Enter open · S save

RePlan-Bot: Multi-Level Replanning for Embodied Instruction Following

Xicheng Gong, Guozheng Sun, Peiran Xu, Yadong Mu

1Peking University · 2Tsinghua University

Large Language Model-Based Robot Planning Robot Task Planning Embodied AI Robot Motion Planning

Open paper AskPDF arXiv

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.

Abstract

Large Language Model-Based Robot Planning

Explore similar work

RePlan-Bot: Multi-Level Replanning for Embodied Instruction Following

GATS: Graph-Augmented Tree Search with Layered World Models for Efficient Agent Planning

TESS: LLM-guided Translation, Exploration, Simulation, and Search for Embodied Task Planning