Tru-POMDP: Task Planning Under Uncertainty via Tree of Hypotheses and Open-Ended POMDPs
Authors: Wenjing Tang
Xinyu He
Yongxi Huang
Yunxiao Xiao
Cewu Lu
Panpan Cai
Venue: NeurIPS 2025 poster ()
Keywords: Robotics
Planning under uncertainty
Robot task planning
Large language models
POMDPs
Primary area: reinforcement_learning
TL;DR: Tru-POMDP combines rigorous POMDP planning with structured belief generation via Large Language Models (LLMs).

Abstract: Task planning under uncertainty is essential for home-service robots operating in the real world. Tasks involve ambiguous human instructions, hidden or unknown object locations, and open-vocabulary object types, leading to significant open-ended uncertainty and a boundlessly large planning space. To address these challenges, we propose Tru-POMDP, a planner that combines structured belief generation using Large Language Models (LLMs) with principled POMDP planning. Tru-POMDP introduces a hierarchical Tree of Hypotheses (TOH), which systematically queries an LLM to construct high-quality particle beliefs over possible world states and human goals. We further formulate an open-ended POMDP model that enables rigorous Bayesian belief tracking and efficient belief-space planning over these LLM-generated hypotheses. Experiments on complex object rearrangement tasks across diverse kitchen environments show that Tru-POMDP significantly outperforms state-of-the-art LLM-based and LLM-tree-search hybrid planners, achieving higher success rates with significantly better plans, stronger robustness to ambiguity and occlusion, and greater planning efficiency.

Tru-POMDP: Task Planning Under Uncertainty via Tree of Hypotheses and Open-Ended POMDPs
Wenjing Tang 1.2 Xinyu He Yongxi Huang 128 Yunxiao Xiao Cewu Lu Panpan Cai
Shanghai Jiao Tong University
SShnngai Innovation Institute
East China Normal University
Beijing University of Posts and Telecommunications
Abstract
Task planning under uncertainty is essential for home-service robots operating in the real world. Tasks involve ambiguous human instructions, hidden un- known object locations, and open-vocabulary object types, leading to significant open-ended uncertainty and boundlessly large planning space. To address these challenges, we propose Tru-POMDP, a planner that combines structured belief generation using Large Language Models (LLMs) with principled POMDP plan- ning. Tru-POMDP introduces hierarchical Tree of Hypotheses (TOH), which systematically queries an LLM construct high-quality particle belief's over possi- ble world states and human goals. We further formulate an open-ended POMDP model that enables rigorous Bayesian belief tracking and efficient belief-space planning over these LLM-generated hypotheses. Experiments complex object rearrangement tasks across diverse kitchen environments show that Tru-POMDP significantly outperforms state-of ohtte--f-hh-arr the-art LLM- and planners, achieving higher success rates with significantly better plans, stronger robustness to ambiguity and occlusion, and greater planning efficiency!
hybrid
1 Introduction
Home-service robots are increasingly expected to perform complex tasks in unstructured household settings, such as tidying up. preparing for guests, or assisting with daily routines. Among these, object rearrangement tasks-e.g., "prepare the kitchen for party"-require robots to interpret ambiguous, open-ended instructions and manipulate open-vocabulary objects. many of which may be hidden in drawers, cabinets, or containers. The robot must infer user intent, identify relevant items, and plan long-horizon action sequences to satisfy under-specified goals in partially observable environments.
While these challenges can be positioned within the framework of planning under uncertainty-whert a robot must hedge against imperfect perception, unobservable environment states, and stochastic action outcomes the difficulties open household environments extend far beyond standard formulations. First, human instructions are inherently ambiguous and often omit crucial details (e.g.. what specific items are needed for party). Second, many objects are hidden from the robot's initial view, and the set of relevant objects is unbounded and diverse (e.g., cups, snacks, decorations). As result, robot must reason over open-ended uncertainty, where fundamental components of the planning problem-sucl
the state space (e.g., what objects exist), the action space (e.g., what objects to operate on) and task goals (c.g., what the human cantot be predefined. This setting leads to effecttvvly boundless belief space, making hong-horizon planning extremely challenging.
'Wenjing Tang and Yongxi Huang are the visiting students at Shanghai Innovation Institute. Cooresponndig author: cai _al__ppaaanjjsa edu. 'The code and demonstration video are available at: https://tru-poont pomdl.-ooppp.... gi thub. io
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

To address open-world problems, recent work has started to leverage large language models (LLMs) to bring commonsense reasoning into robot planning. One line of work treats LLMs as planners,
leveraging their implicit knowledge and ability to reflect over past failures [ 2 3 3
6
However,
such approaches often rely on implicit, unverified hypotheses about the world, and can fail catastroph-
ically when the underlying hypotheses are incorrect. Another line combines LLMs with symbolic or
probabilistic planners, for example, by prompting LLMs to generate POMDP models for informing LLM planning suggesting default actions for search 77 (89)) IO II 12] While more structured, these methods still commit to a single high-probabilityy hypothesis or operate in a closed domain, which limits robustness in the open- woold...
To overeome these limitations, we propose Tru-POMDP, a task planner built upon an open-ended POMDP formulation, that tightly integrates commonsense reasoning by LLMs with explicit belief tracking and principled POMDP planning- Tru-POMDP operates in three stages: (1) constructs a tree of hypotheses over possible world states and task goals using hierarchical LLM queries, to form a commonsense belief; (2) fuses the L..M-generated belief with Bayesian filtering to construct hybrid belief that is both diverse and consistent during updates; and (3) it solves for an optimal policy using online belief tree search with a dynamically constructed action space and guided by an LLM-generated rollout policy. This design leverages the generalization power of LLMs while maintaining rigorous, verifiable reasoning over open-ended uncertainty.
We evaluate Tru-POMDP on object rearrangement tasks across five diverse kitchen environments from RoboCasa [3] involving open- ppen-ended instructions, ambiguous user intentions, and a large number of hidden spaces. Results show that Tru- effectively tackles challenges brought by open-ended uncertainties. Through the integration of LLLM-based belief generation with POMDP planning, Tru-POMDP significantly outperforms both LLM agents and L..M-augmente tree search planners, producing higher success rates and plan qualities with lower LLM token usage. Tru-Po Tru-POMDP also benefits from structured belief modeling with LLMs and hybrid belief tracking that combines LLM belief with Bayesian updates.
In summary, our main contributions include:
The first framework to address "open-ended POMDPs", integrating LLM-based reasoning with principled POMDP planning for household tasks.
A novel hybrid belief modeling approach that integrates LLM LLM-generated hypotheses with principled Bayesian filtering.
A POMDP model for open-world object rearrangement tasks and a practical belief-tree search planner for solving such tasks efficiently under large-scale uncertainty.
2 Background and Related Work
2.1 Online POMDP Planning
Partially Observable Markov Decision Processes (POMDPs) provide principled framework for decision-making under uncertainty, where the true state of the world is only partially and noisily observed. A POMDP is formally defined as a 7-tuple (S, A, Z, I, O, R, bo). where S is the set of states, A is the set of actions, Z is the set observations, T's' s, a) is the transition model, Oz]ss' is the observation model, R(s, a) is the reward function, and bo is the initial belief over states. Online POMDP planning targets for single-query planning or even real- time planning, by computing policies via belief tree search. The agent maintains belief probability distribution over possible world states-usin Bayesian filtering. At each decision step, it constructs a belief tree by simulating future actions and observations [14, and applies Bellman's principle [15) in the
to compute the best policy given the current belief. Only the immediate action is executed, and the process is repeated at each time step, allowing the planner adapt new observations in an online fashion (e.g., replan 1 Hz). A POMDP model requires a full specification of all possible states, actions, and observations, which limits its use "closed-domain" problems.
2.2 Robot Planning with Large Language Models
Recent advances in large language models (LLMMs) have enabled robots to handle tasks expressed in open-vocabulary language and to incorporate commonsense knowledge into the planning process.

---

Broadly, two directions have emerged. The first uses LLMs as planners, either generating open-loop action sequences via prompt engineering or tine-tuning loop actions through iterative feedback and reflection [2
or producing closed- While flexible, these approaches rely on implicit reasoning and often lack robustness when their internal hypotheses diverge from reality. The second direction combines LLMS with explicit planning algorithms. For example, some work uses LLMs to generate PDDL domains and problems, which are then solved by symbolic planners [25 26 27 28, 29). Others combine LLMs with Monte Carlo Tree Search (MCTS), using the LLM to hypothesize initial states or initial solutions 77 8 30, BT]. However, these methods generally assume full observability and deterministic goals, ignoring the inherent uncertainty in both human intention and world states. As a result, their solutions are often suboptimal in real-world deployments.
16
17
5
6
18
19
20
21
22
23
24
2.3 Planning under Uncertainty with Large Language Models
few recent efforts have explored combining LLM reasoning with the structure of POMDPs. Some approaches use LLMs to generate elements of POMDP model-such as belief's or observation likelihoods-wii whhch are then fed back into the LLM to improve its planning ability under uncer- tainty [0 [2]. However, these methods still rely heavily on the LLM's implicit reasoning and lack the formal guarantees provided by explicit belief tracking and tree-search planning. Other work combines LLMs with tree search. One possibility is to generate single most likely hypothesis about goals and world states, and then applies MCTS for planning [32 33]. This strategy fails when the true goal diverges from the most likely one. LLM-MCTS 7 proposed to plan with LLM-ggnerated state distributions. However, it uses a "flat" belief that only considers single aspect of uncertainty on the initial placement of objects. It operates beforehand, and incurs significant computational cost due to repeated LLM queries within the tree search (34). In contrast, Tru-POMDP offers a scalable and flexible approach to address open-ended uncertainty. It uses the LLM to construct free of plausible hypotheses representing a complex, multi-aspect, and open-ended belief over entirely unknown objects and ambiguous human goals. We combine this with Bayesian filtering to maintain consistently updatable belief. Finally, apply belief tree search over this hybrid belief, using a dynamically constructed action space and a pre-compiled, LLM-generade rollout policy to efficiently guide optimal search.
closed domain, assuming the object set is known
3 Problem Formulation
3.1 Task Specification
We study the object rearrangement task performed by dual-armed mobile robot in household environment. Given a free-form, ambiguous natural language instruction 1, the robot must arrange open- vocabbucayl objects existing in the scene into target configuration that fulfills the human's 's underlying intention, while minimizing total execution time. The robot exccutes four types of actions: MOVE navigates specific area (c.g., in front of furniture appliances); PICK picks an object from an open surface or an open container; PLACE places the held object onto a surface or into a container; and OPEN opens container drawer if it is closed. MOVE has time cost proportional to the navigation distance, while the other actions incur a fixed cost. The robot can hold at most one object in its right hand; the left hand is reserved for the OPEN operation.
The environment is represented as a structured scene graph 9 = (V, where V denotes asset nodes and E encodes spatial relationships. Nodes are organized hierarchically into four layers: a root ROOM node representing the overall scene; AREA nodes representing surfaces or containers that can hold objects; OBJECT nodes representing physical items; and ROBOT node indicating the robot's s current location. Edges encode containment and adjacency (e.g., an object is at an area, or the robot is at an area). Each AREA node has a boolean attribute indicating whether it is open or closed. The robot can observe objects in open areas without noise but cannot observe contents in closed areas. While we assume noise-free observations, the method naturally extends to stochastic cases without affecting belief tracking or planning algorithm design.
Due to the inherent ambiguity of human instructions, we model the task goal as a set of plausi- ble placement goals P = (Pi:...,Po). Each placement goal p; specifies a list of target objects {oi...., ) and their respective desired destination areas (to (tor....,to,, ). These specifications are
3

---

concise and do not constrain the locations of unrelated objects. Concrete goal representations for example tasks are provided in the appendix A.4
3.2 The POMDP Model
States. state s consists a scene graph 93 encoding the current placement of both visible and hidden objects, and hypothetical placement goal ps of target objects, representing the intended final configuration consistent with the instruction of the task.
Observations. An observation 2 E Z is partial scene graph G3 that includes only visible objects in open areas. The observation function is defined as:
1,
if Visible((g.)
O a, = Pr(g. (G.,
0, otherwise
where Visible removes all hidden objects from Gs-
The action space A is defined over parameterized operations on the scene graph. OPEN(area) opens a closed area, setting its status open. PICK(area, object) picks an object from an area, reassigning its parent to the ROBOT node. PLACE(area places the held object into the target area, making that area its new parent. These actions implicitly execute a MOVE when the robot is not in front of the specified area or object. The robot may also choose to take no action via NULL. Actions are subject feasibility constraints: for instance, only closed areas can be opened. Infeasible actions are mapped to NULL..
Parameterized Actions and State Transition.
Reward Modeling. Manipulation actions incur fixed cost of 5, and navigation costs vary from 0 to 27 depending on the distance traveled. Infeasible actions are penalized with a cost of 100. Completing subgoal yields reward of 200, with an additional 200 granted upon full task completion.
Belief Modeling. The belief is represented as weighted particle set ((5,, w:) 8; E S, w; E (0. 1]}. where each is possible world state and w, its associated probability. The initial belief is generated from the natural language instruction I and the initial observation G3 using LLMs, and updated using Bayesian filtering. Details of belief tracking are provided in Section 4.1
4 The Tru-POMDP Planner
Tru-POMDP consists of three modules (Fig. T
Tree of Hypotheses, Hybrid Belief Update, and Online POMDP Plamning. Given natural language instruction I and current observation G., the Tree Hypotheses module generates a belief over candidate world states and plausible placement goals P. The Hybrid Belief Update module filters inconsistent hypotheses and augments the belief as needed. The Online POMDP module computes the optimal next action under uncertainty via belief tree search.
4.1
Tree of Hypotheses
This module queries LLM to generate diverse belief over three sources of uncertainty: ambiguity in human instructions, open-class objects, and occluded object locations. The LLM takes as input the human instructions I and the observed scene graph Gz. transformed into textual description Tg. and constructs a tree of hypotheses (TOH) consisting of three levels:
Level 1: Hypotheses of target objects. The L.M predicts sets of objects that are potentially relevant to the task described by T. Since we do not assume known object set, the LLM has to hypothesize objects with commonsense priors, and returns a set of C₁ candidate combinations of target objects:
= {(O,, wx) i == Ci).
(2)
where each O is set of objects that can be used to accomplish the task, and w; is the LLM's confidence score for that hypothesis. These hypotheses reflect alternative interpretations of vague or underspecified instructions. The LLM also incorporates information from failed past executions (if available) to disambiguate user intent and generalize to open-class object names.
Level 2: Hypotheses of placement goals. For each combination of target objects, the LLM infers destination area for each object the set. This yields a plausible goal placement:
P goal (O,) {(o,, t2) j 1, ... [O]}
(3)

---

(a) Human Instruction & Scene Graph
(b) Tree of Hypotheses SF
Home
Prompt
Prepare for Partyl
Chowere
Related Ozjects
6
Robot
Objects
Target Areas
Action
CurrentArcaa
(d) Online POMDP Planning
Dynamic Action
Belief
(c) Hybrid Belief Update
LLM Particles
a3
Wm0.7
Palicy
Beyesian Fittering
Accios RoctAction
Eliminate
Predict
Figure 1: The architecture for Tru-POMDP. (a) Task Inpul: Human instruction and the observed scene graph. (b) Tree of Hypotheses: An LLM infers target objects, target areas, and initial locations, producing weighted particles. (c) Hybrid Belief Update: Bayesian filtering updates the belief using particle prediction and elimination, and augments the filtered belief with LLM particles. POMDP Planning: Belief tree search computes the optimal action with the help of dynamic action branching and an LLM-written rollout policy.
(d) Online
which assigns each target object 0j the combination O, to its target AREA node 1y-
Level 3: Hypotheses of current placements. To estimate the current locations of target objects that not visible in Gz, LLM is queried for each invisible target object to predict distribution over its possible locations, i.e., hidden areas:
Pon {1o, wx) k= I
where set C2 locations (1, are generated, together with a confidence score wy for each hypothesis. If o is observed in G., its location is taken directly.
Inference for each invisible target object is queried independently, enabling parallelization.
Particle belief construction. Each path from the root to a leaf of the hypothesis tree defines sampled particle: (G.,P.) where G. encodes hypothesized complete scene graph (a union of observed scene graph G2 and inferred initial placements of invisible target objects), and ps corresponds to the generated placement goal. Aggregating all such particles yields the LLM-inferred particle belief:
DLIM {(n, w.,)) n 1..... Ca
(5)
where the particle weight w, is proportional to the multiplication of all confidence scores, i.c., wa's and wa,ss 's along the top-down path. These particle weights are normalized to ensure the belief forms valid probability distribution.
4.2 Hybrid Belief Update
The Hybrid Belief Update module maintains consistent and efficient particle belief over partially observed world states and placement goals. It fulfills two objectives: (1) ensuring smooth and reliable belief updates through Bayesian filtering, and (2) reducing the frequency of expensive LLM queries by only invoking them when necessary. The algorithm monitors the total weight of the particle belief. If the belief retains sufficient nright-indicating strong agreement with the current observation is updated using a particle filter. the weight falls below a threshold (e.g., é = 0.3), new particles generated by invoking the Tree of Hypotheses module (Section 4.1 replenish the belief.
Bayesian Filtering. We employ particle filter perform principled belief updates. Each step consists of two phases:
5

---

Prediction step. For each particle = Ps.), we simulate the effect of the last action to update the scene graph Gs, according to the deterministic transition model.
Elimination step. Given the new observation 9z, particles inconsistent with it are removed. Because the observation model is deterministic (Equation []. this reduces to filtering out particles whose predicted visible scene Visible(G..) does not match G.. The result is a new filtered particle set bBF with total weight WBF - 1.
LLM Particle Supplementation. When War < 1 - 6, the belief augmented using a new set of particles generated by the Tree of Hypotheses. This new set, bLLM. is generated by conditioning on the full history of past actions and observations. The augmented belief is defined as:
by bBF + - WBBF) bLLM:
where the weights of particles in PLLM are scaled by (1-wpr² before merging. This ensures that the resulting belief remains valid probability distribution.
4.3 Online POMDP Planning
This module plans the optimal policy given the current belief over uncertain world states and goals. Our planner is built upon DESPOT [14), sampling- baaee online POMDP algorithm that provides asymptotic optimality guarantees. We extend DESPOT with two key innovations: (1) dynamic action space constructed from belief particles, and (2) an LLM-generated rollout policy that injects commonsense domain knowledge while maintaining computational efficiency. Tru-POMDP operates in an online planning setting: at each time step, it executes the optimal action for the current belief and replans after receiving new observations.
Dynamic Action Space. As discussed in Section 3.2 the robot's action space includes PICK actions over objects that may be hidden and unknown. Since the full set of possible objects is unbounded, naively enumerating all possible parameterized actions would result in an intractably large-or infinite-actio catiie-aationn space. To address this, we dynamically construct a compact action space based on the current belief. Concretely, we extract the union of all relevant entities from the particles in the belief: hypothesized target objects, open areas, and closed containers. We then construct the grounded action set consisting of: (1) OPEN for each closed area; (2) PICK for each target object that is currently visible and graspable; and (3) PLACE for placing the held object (if any) into each open area. This dynamic action set varies with the belief but remains compact and tractable, while retaining sufficient expressiveness for solving the task.
Belief Tree Search. We adapt the DESPOT algorithm to recursively explore the space of future action-observation sequences from the current belief. At each time step, a sparse belief tree is constructed: nodes represent future belief states (particle beliefs), and branches represent possible actions and the resulting observations, simulated using the POMDP transition and observation models. Each belief node also maintains value estimate, representing the expected cumulative reward that can be achieved under optimal behavior conditioned on that belief. These values are updated iteratively using Bellman's 's principle [4]. The planner leverages value estimates as tree search heuristics: it selects actions that maximize the value estimate, and expands observation branches based on excess uncertainty. This ensures targeted exploration of promising belief trajectories, ensuring efficient convergence of values and allowing planning to terminate at any time and output high-quality decisions.
L.M--Geeereed Rollout Policy. Following the DESPOT framework, leaf nodes in our belief tree require rolling-out a default policy to provide a heuristic lower bound on their value. However, unlike prior work that simply uses a random rollout policy 77. we query the LLM to synthesize a rollout policy in code. The rollout policy mapping from the current state s (Gs, to an action a, where G2 is the scene graph representing the hypothesized world state, and p. is the placement goal. This mapping is implemented as C++ function generated by an LLM. The generator LLM receives a general language description of the object rearrangement domain but is given no information about any specific task instance. The resulting policy generalizes across tasks the same domain and reused throughout the search. During rollouts, this policy is simulated for each rolled-out node to estimate cumulative rewards from the leaves. See Appendix A.2 for the generator prompt and the code of the rollout policy.

---

5 Experiments
We conduct comprehensive experiments to evaluate the effectiveness of Tru-POMDP in open-ended object rearrangement tasks under uncertainty, Our study aims to answer the following questions:
1. Is belief-space planning essential for household tasks involving partially observable environ- ments and ambiguous free-form instructions?
2. Can Tru-POMDP effectively solve household tasks with high and open-ended uncertainty?
3. What are the benefits of integrating belief-space planning with
reasoning?
4. How does combining Bayesian filtering with LLM belief generation improve performance?
5. Does the proposed Tree of Hypotheses (TOH) structure generate high-quality beliefs?
5.1 Experimental Setup
We evaluate Tru-POMDP in five kitchen environments from RoboCasa [3], which highlights large number of hidden areas: One Wall, One Wall with Island, L-Shaped, L-Shaped with Island, and Galley. Each scene contains up to AREA nodes with semantically-rich names, of which up to 29 are initially closed. Tasks are procedurally generated using an LLLM-assisted pipeline, emphasizing vague task instructions with substantial implicit information and ambiguous object references. For each task, populate up to 20 objects (including distractors) in the scene using commonsense priors, and define a goal set P containing various plausible target object combinations and goal placements grounded in the scene. This setup ensures each task is both solvable and exhibits ambiguity in human intention. Example scene with instruction and goal sets are listed in Appendix [A.3 and A.4
We categorize tasks into three difficulty levels based on the number of target objects required in the goal: easy (requiring 2 target objects), medium (3), and hard (4-8). Each additional target object in the goal leads to exponential growth of uncertainty. For each level, we generate 100 tasks, resulting in total of 300 tasks. Step limits are set 25, 30, and 35 respectively. The planning time capped at 600 seconds. A task fails if either the step time limit is exceeded.
We evaluate performance using the following metrics. (I) Cumulative reward: the total reward collected in an episode, computed using the POMDP reward function described in Section 3.2 In experiment, we remove the reward for subgoals, and adapt the reward for full task completion to 1,000. In addition, we adapt the cost of infeasible actions to 25. (2) Success rate: the percentage of episodes in which the task is successfully completed within the step and time limits. (3) Step count: the number of execution steps per episode, where failed episodes are assigned the maximum allowed steps. (4) Planning time: the total wall-clock time spent in online planning across all steps of an episode. (5) L.M token usage: the total number of input and output tokens consumed by the planner, averaged per episode.
Experiments are run on a local machine equipped with 12th Gen Intel Core 17-12700KF CPU (20 threads), without GPU acceleration. All methods consistently use GPT-4.1 as the LLM.
5.2 Comparison Results
We compare Tru-POMDP against a set of strong baselines, including both pure LLM-based planners and tree search planners integrated with LLM reasoning.
ReAct [ A closed-loop LLM-based planner that selects actions based on current observa- tions and immediate feedback from the environment.
Reflexion 2 : An extension of ReAc/ that introduces a reflection module. When repeated failures encountered, it analyzes the execution history and generates revised plan to guide subsequent decisions. For fair comparison in an online planning setup, we disable environment resets and trigger reflection after three consecutive failed actions.
ReAcr* and Reflexion Prompt-augmented variants of the above, in which the L.MM re- ceives additional structured descriptions of the task domain, including object types, action semantics, and goal structures. Detailed prompt templates are provided in Appendix AA.6]
I.LM-MTTS 7
L.M augmented closed-domain POMDP planning. Given a known object set, LLM generates object-location probability vectors as belief. It then performs Monte
7

---

Tru-POMDP
LLM-MCTS
Refiexion
Refiexion
ReAct*
ReAct
900
100
620
30-
300
0U
20
20
-600
easy
medium
hard
easy
medium
hard
easy
medium
(a) Cumulative Reward 1
(b) Success Rate (%) 1
(c) Total Step Number
Figure 2: Performance comparison of Tru-POMDD and baselines. Each bar represents the average value with standard error (SE). In (c), the dashed line indicates the maximum allowed step number.
Carlo Tree Search (MCTS), calling the LLM repeatedly to guide the action selection in simulation procedure MCTS.
As shown in Figure 2 Tru-POMDP significantly outperforms baselines, demonstrating its capabil- ity for planning under uncertainty.
Tru-POMDP LLM-based planners. ReAct and Reflexion are generally ineffective in environments with partial observabil- ity. When tasks involve three or more unknown target objects, these methods achieve success rates below 20% and accumulate negative rewards. The prompt-augmented versions ReAcr* and Reflexion R offer some improvement by providing clearer task semantics the LLM, increasing success rates to around 40% and achieving marginally positive rewards. However, their purely reactive nature and lack of principled reasoning over uncertainty limit their performance. In contrast, Tru-POMDP explicitly rea- sons over uncertain goals and occluded states using belief-space planning, leading to consistently higher success rates and cumu- lative rewards.
Tru TrUPPMMP LUM-MCTS
Reflex Heflex
Refctt Rerict
400
200
medium
hard
Figure Total tokens (k) used by Tru-POMDP and comparison baselines per episode.
Tru-POMDP vs. Tree Search planners. L.LM-MCTS struggles with planning efficiency due to frequent L.LM calls during sim- ulation, exceeding the 10-minute time limit in all tasks. Tru-POMDP mitigates this using offline LLM-generated policy, expressed as C++ code. LLM-MCTS also operates on closed object set, and can never accomplish a task when the true targets fall outside of the set. Tru-POMDP addresses this by constructing open-ended beliefs and dynamic action spaces. Tru-POMDP also integrates LLM reasoning with rigorous belief-space planning and performs tree search over structured particle belief, enabling to solve ambiguous tasks more effectively than all baselines. Note that Tru-POMDP achieved this using minimum consumption of LLM tokens (Figure 3). See Appendix A.7 for visualization the planned results.
5.3 Ablation Study
To understand the contributions of key components Tru-POMDP, we conduct an ablation study using the following variants:
w/o Belief: Removes explicit belief modeling, using only the single most-likely hypothesis generated by the LLM. This variant effectively reduces to MCTS planner.
w/o HBU: Removes the Hybrid Belief Update (HBU), generating an entirely new particle belief from TOH at every step, without Bayesian filtering.
w/o TOH:: Eliminates the Tree of Hypotheses (TOH) structure, instead querying the LLM once to directly generate flat set of particle hypotheses, with each particle including a target object set, goal placement, and an initial placement.
w/o LRP: Removes the I.LM -.Geerrrtteddd Rollout Policy(LRPP) in the Belief Tree Search, instead uses a simple policy that randomly selects legal action.

---

Tru-POMDP
w/o Belief
w/o HBU
w/o TOH
w/o LRP
w/o BTS
800
100
30-
400
60
20
20
easy
medium
hard
easy
medium
hard
easy
medium
hard
(a) Cumulative Reward f
Success Rate (%)
Total Step Number
Figure 4: Results for Ablation Study, Each bar shows average values with standard error (SE).
w/o BTS: Removes explicit Belief Tree Search (BTS), directly inputting the particle belief to the LLM and asking it to output the next action.
As shown Figure 4 the full Tru-POMDP method consistently outperforms all ablated variants, demonstrating that each proposed module is critical to the overall performance under uncertainty.
Comparing Tru-POMDP w/o Belief, observe that explicit belief modeling is essential. Relying hypothesis leads to substantial performance degradation. In these
solely on a maxxmum--lkeelibee scenarios, the level of uncertainty is significant but manageable by proper belief tracking. Without explicit belief representation, the planner fails to recover from errors when the hypotheses diverge from reality.
The comparison against w/o HBU highlights the benefit of com- bining Bayesian filtering with LLM belief generation. Without Bayesian filtering, the performance significantly decreases for tasks with high difficulty where stable belief updates are critical. Moreover, Figure shows that removing Bayesian filtering dra- matically increases total planning time, up three times higher, due to frequent, expensive LLM belief regeneration at every step. In contrast, Tru-POMDP efficiently maintains and updates beliefs by reusing reliable information from previous steps.
PONDP Belief
HBU
TOH
500
300
200
100
Comparing Tru- Tru-POMDP with w/o TOH highlights the effective- ness of our hicrarchical TOH structure. Asking the LLM to generate flat set of particle hypotheses in single degrades belief quality due to hallucination, resulting in worse performance than the hinlle-hypotheiis variant. This underscores the im- portance of structured querying for reliable belief generation.
easy
Figure 5: Total planning time + used by Tru-POMDP and its ab- lated variants per episode.
Comparing Tru-POMDP with w/o LRP shows that the LLM-generated rollout policy offers effective heuristic guidance for tree search. Replacing it with a random policy greatly degrades performance.
Comparing with w/o BTS confirms the importance of belief-space planning. Removing explicit POMDP planning leads to the lowest rewards and success rates, and the second-longest planning time. This suggests that Tru-POMDD benefits from integration with principled POMDP planning.
6 Conclusion and Limitations
In this work, we introduced Tru-POMDP, a principled approach that integrates belief-space POMDP planning with structured LLM reasoning address uncertainties from ambiguous human instructions, open-class objects, and hidden placements. Tru-POMDP generates explicit particle beliefs via a hierarchical Tree of Hypotheses, refines them through hybrid Bayesian-LLM, updates, and plans efficiently with online belief-tree search. Experiments show that this integration significantly out- performs pure LLM and LLM-enhancedd tree-search planners complex household rearrangement tasks, confirming the benefits of explicitly modeling uncertainty and combining POMDP planning with L.LM reasoning.
Nevertheless, our approach currently has several limitations. The Tree of Hypotheses incurs compu- tational overhead due to multiple LLM calls, which could be mitigated by fine-tuning LLM for

---

faster belief generation. Furthermore, Tru-POMDP leverages conditional independence between the placement of different objects to achieve scalable belief modeling, as this property naively supports factorization. When more complex dependency exists, systematic factorization is required to deter- mine the belief structure. Next, our experiments also assumed noise-free perception and deterministic actions. However, the general POMDP formulation naturally accommodates perception noise and stochastic outcomes by adding appropriate probabilistic models. Finally, our evaluation focused on object rearrangement tasks, Extending the approach to larger action spaces and reasoning over additional unknown object attributes remains an important direction for future work.
Acknowledgment
This work was supported in part by the National Key R&D Program of China (Grant No. 2024YFB4707600) and the National Natural Science Foundation of China (Grant No. 62303304).
We used generative AI to improve self-written texts to enhance readability. None of the presented methods and results (figures, equations, numbers, etc.) are generated by Al.
References
[1] Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models, arXiv preprint arXiv:22/0.03629, 2022.
[2] Noah Shinn, Federico Cassano, Edward Berman, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: Language agents with verbal reinforcement learning, 2023.
[3] Wenlong Huang, Fei Xia, Ted Xiao, Harris Chan, Jacky Liang, Pete Florence, Andy Zeng Jonathan Tompson, Igor Mordatch, Yevgen Chehotar, Pierre Sermanet, Noah Brown, Tomas Jackson, Linda Luu, Sergey Levine, Karol Hausman, and Brian Tehter. Inner monologue: Emhodied reasoning through planning with language models. In arXiv preprint arXiv:2207.05600 2022.
[4] Wenlong Huang, Picter Abhcel, Deepak Pathak, and Igor Mordatch. Language models as zero-shot planners: Extracting actionable knowledge for embodied agents, arXiv preprint arXiv:2201.07207 2022.
[5] Michael Ahn, Authony Brohan, Noah Brown, Yevgen Chebotar, Omar Cortes, Byron David, Chelsea Finn, Chuyuan Fu, Keerthana Gopalakrishnan, Karol Hausman, et al. Do as i can, not as say: Grounding language in robotic affordances. arXiv preprint 2rXiv:2204.01691, 2022.
[6] Jacky Liang, Wenlong Huang. Fei Xia, Peng Xu, Karol Hausman, Brian lchter, Pete Florence, and Andy Zeng. Code as policies: Language model programs embodied control. In 2023 IEEE International Conference on Robotics and Automation (ICRA), pages 9493-9500. IEFF, 2023.
[7] Zirui Zhao, Wee Sun Lee, and David Hsu. Large language models as commonsense knowledge for large-scale task planning. In Thinty-seentth Conference on Neural Information Processing Systems, 2023.
[8] Dongryung Lee, Sejune Joo, Kimin Lee, and Beomjoon Kim. Prime the search: Using large language models for guiding geometric task and motion planning by warm-starting tree search, 2024.
[9] Lingfeng Sun, Devesh K. Jha, Chiori Hori, Siddarth Jain, Radu Corcodel, Xinghao Zhu, Masayoshi Tomizuka, and Diego Romeres. Interactive planning using large language models for partially observable rohotic tasks. 2024 IEEE International Conference on Robotics and Automation (ICRA), pages 14054- 14061, 2024.
[10] Weimin Xiong, Yifan Song. Xiutian Zhao, Wenhao Wu, Xun Wang. Ke Wang, Cheng Li, Wei Peng, and Sujian Li. Watch every step! LLM agent learning via iterative step-level process refinement. In Yaser Al-Onaizan, Mohit Bansal, and Yun-Nung Chen, editors, Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pages 1556-1572, Miami, Florida, USA, November 2024. Association for Computational Linguistics.
[11] Aidan Curtis, Hao Tang, Thiago Veloso, Kevin Ellis, Tomás Lozeno-Pérez, and Leslic Pack Kaelbling. Lim-guided probabilistic program induction for pomdp model estimation, 2025.
[12] Zixuan Chen, Jing Huo, Yangtao Chen, and Yang Gao. Robohorizon: An 1lm assisted multi-view world model for long horizon robotic manipulation, 2025.
10

---

[13] Soroush Nasiriany. Abhiram Maddukuri, Lance Zhang. Adeet Parikh, Aaron Lo. Abhishek Joshi, Ajay Mandlekar, and Yuke Zhu. Robocasa: Large-scale simulation of everyday tasks for generalist robots. arXiv preprint arXiv:2406.00 02523,, 2024.
[14] Nan Ye, Adhiraj Somani, David Hsu, and Wee Sun Lee. Despot: Online pomdp planning with regularization. volume 58, page 231-266. AT Access Foundation, January 2017.
[15] Leslie Pack Kaelbling, Michael L Littman, and Authony Cassandra. Planning and acting in partially observable stochastic domains, Artificial intelligence, 101(1-2):99 134, 1998.
[16] Ishika Singh. Valts Blukis, Arsalan Mousavian, Ankit Goyal, Danfei Xu, Jonathan Tremblay, Dieter Fox, Jesse Thomason, and Animesh Garg. Progprompt: Generating situated robot task plans using large language models. In 2023 IEEE International Conference on Robotics and Automation (ICRA), pages 11523- 11530. IEEE, 2023.
[17] Zehui Chen, Kuikun Liu, Qiuchen Wang, Wenwei Zhang, Jiangning Liu, Dahua Lin, Kai Chen, and Feng Zhao. Agent-flan: Designing data and methods of effective agent tuning for large language models. arXiv preprint arXiv:2403. 12881, 2024.
[18] Zhchua Zhou, Jiayang Song, Kumpeng Yao, Zhan Shu, and Lei Ma. Isr-Ilm: Itcrative self-refined large language model for long-horizon horizon sequential task planning. In 2024 IEEE International Conference on Robotics and Automation (ICRA), pages 208 1-88- IEEE, 2024.
[19] Haotian Sun, Yuchen Zhuang, Lingkai Kong, Bo Dai, and Chao Zhang. Adaplanner: adaptive planning from feedback with language models. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS '23, Red Hook, NY, USA, 2023. Curran Associates Inc.
[20] Renxi Wang, Haonan Li, Xudong Han, Yixuan Zhang, and Timothy Baldwin. Learning from failure: Integrating negative examples when fine-tuning large language models agents, 2024.
[21] Yifan Song, Da Yin, Xiang Yue, Jie Huang, Sujian Li, and Bill Yuchen Lin. Trial and error: Exploration- based trajectory optimization for Ilm agents, 2024.
[22] Ruihan Yang, Jiangjic Chen, Yikai Zhang. Siyu Yuan, Aili Chen, Kyle Richardson, Yanghua Xiao, and Deqing Yang. Selfgoal: Your language agents already know how to achieve high-level goals. Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume I: Long Papers), pages 799-819, 2025.
[23] Shreyas Sundara Raman, Vanya Cohen, Eric Rosen, Ifrah Idrees, David Paulius, and Stefanie Tellex. Planning with large language models via corrective re-prompting. In NeurlPS 2022 Foundation Models for Decision Making Workshop, 2022.
[24] Vineet Bhat, Ali Umut Kaypak, Prashanth Krishnamurthy, Ramesh Karri, and Farshad Khorrami. Ground- ing Ilms for robot task planning using closed-loop state feedback. arXiv preprint arXiv:2402.08546. 2024.
[25] Bo Liu, Yuqian Jiang, Xiaohan Zhang. Qiang Liu, Shiqi Zhang, Joydeep Biswas, and Peter Stone. Llm+p: Empowering large language models with optimal planning proficiency. arXiv preprint arXiv:2304.1 14477, 2023.
[26] Muzhi Han, Yifeng Zhu, Song- Chun Zhu, Ying Nian Wu, and Yuke Zhu. Interpret: Interactive predicate lcarning from language feodback for generalizable task planning. In Robotics: Science and Systems (RSS), 2024.
[27] Timo Birr, Christoph Pohl, AbdeIrahman Younes, and Tamim Asfour. Autogpt+p: Affordance-basd based task planning using large language models. In Robotics: Science and Systems (RSS). Robotics: Science and Systems Foundation, July 2024.
[28] Gautier Dagan, Frank Keller, and Alex Lascarides. Dynamic planning with Ilm. arXiv preprint arXiv:2308.0m 06391, 2023.
[29] Lin Guan, Karthik Valmeekam, Sarath Sreedharan, and Subbarao Kambhampati. Leveraging pre-trained large language models to construct and utilize world models for model-based task planning. Advances in Newral Information Processing Systems, 36:79081-7999 199094, 2023.
[30] Shuofei Qiao, Runnan Fang. Ningyu Zhang. Yuqi Zhu, Xiang Chen, Shumin Deng. Yong Jiang, Pengjun Xie, Fei Huang, and Huajun Chen. Agent planning with world knowledge model. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
11

---

[31] Zijing Shi, Meng Fang, and Ling Chen. Monte carlo planning with large language model for text-based games. In The Thirteenth International Conference Learning Representations.
[32] Rishi Hazra, Pedro Zuidherg Dos Martires, and Luc De Raedt. Saycanpay: Heuristic planning with large language models using learnable domain knowledge. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38. pages 20123-20133, 2024.
[33] Allen Z. Ren, Anushri Dixit, Alexandra Bodrova, Sumeet Singh, Stephen Tu, Noah Brown, Peng Xu, Leila Takayama, Fei Xia, Jake Varley, Zhenjia Xu, Dorsa Sadigh, Andy Zeng, and Anirudha Majumdar. Robots that ask for help: Uncertainty alignment for large language model planners, 2023.
[34] Jianliang He. Siyu Chen, Fengzhuo Zhang, and Zhuoran Yang. From words to actions: Unveiling theoretical underpinnings of llm-driven autonomous systems, 2024.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and Introduction (Section clearly state the main contributions, which consistently supported by the methods and experiments described in Sections [nd
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the
contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: A dedicated Limitations section (Sec. 6 is provided discussing generalization
unseen environments, reliance LLM accuracy, and computational cost.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
13

---

Answer: [NA]
Justification: The paper focuses on an algorithmic framework and empirical evaluation; does not contain formal theorems proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The paper describes the algorithm design (Sec. experimental setup (Sec. p. and baselines and evaluation protocol (Sec. 5.2) in sufficient detail to support reproduction of key results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
14

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [Yes]
Justification: We will release anonymized code and usage instructions in the supplemental material to ensure faithful reproduction of all main results. The code is availble at: https
//tru //tru-pomdp. powdp.ommppp.e wwt.gg.thhu.... io
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to rum to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips.ce ttt.cc//pbbb. muullc//guddee tttpggdde//oeeuubbmsmiicese wttp///oddesissiiiooao wommissssoooiccy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The main paper (Sec. 5 describes datasets, task setups, and evaluation proto- cols; additional hyperparameter details are included in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
We report standard error in all bar plots (Figures 25
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
15

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Hardware and runtime details are provided in the experimental setup (Sec. 5.1 Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics htttp:://eeuri: hcc/ppbbic//thiiiiiiieeeieeeeeee
Answer: [Yes]
Justification: We have reviewed the NeurIPS Code of Ethics, and our research complies with its guidelines; ethical concerns identified in this work.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: The paper does not explicitly discuss broader societal impacts; its focus is on algorithmic design and empirical evaluation for robot planning under uncertainty.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
16

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper does not release any pretrained models or scraped datasets that pose high risk for misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We use RoboCasa environment in experiments, and is properly cited in Section 5.T with licenses and usage terms respected as per their official releases.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
17

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com/ com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's ' creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets such as datasets or models; only algorithm code will be open-sourced.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve any crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve research with human subjects and therefore does not require IRB approval.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
18

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [Yes]
Justification: LLMs play central role in our approach, powering both the Tree-of- Hypotheses generator and the rollout policy (Sections 4.1 and 4.3): they also used in an LLM-assisted pipeline to construct experimental tasks (Section 5.1 Further usage details are provided in the Appendix.
Guidelines:
The answer NA means that the core method development in this research does not non Please refer to our LLM policy (https: /ttpri:///eurps... http///uwpppppcoooeeeeeeeeeeeeee cc/conoeeencce//2222222222 for what should or should not be described.
involve L.MMs as any important, original, non- son-standard components.
19

---

A Technical Appendices
A.1 Prompt Design for the Tree of Hypotheses
Textual Description of the Observation. The textual description T: of the observation includes: (I) description of the scene graph 9= : (2) objects that have already reached their respective target areas; and (3) goal states that have been attempted but failed to satisfy the task requirements. Below, we provide an example of such a textual observation.
Current Ubservation:
clcaed
Cleaning Swwpugs_ppppp_____ Cabinet, Cookvaro_ Cosivaar_CCainet, Bakoware_ DiebHasber, laser_ apace. @ridge_Cooler.cc
Cabinee, Cutlery
Fridge, Freezer,
Nicrovavo, inner -pace_
Innor__pc___
The open areas are: Buzaa, Hand, Surp_Surface, Saffee_Tea_Surreee
Snack, Bnatk, Faatry_ Cabinet, Sookbook.Sbell. Pantry, Shelf, spice_Shelf, Appliance applaanse_burtaee Cabinet, Dseplay.Surface
Appiianeo_Cabiiet. Cabinet, Drop_ Surface
Stperago_Storggo.caa
Prilsty.Cabinet
The observed objects and their isitial areas are: decorative
is Diaplay_ Burface, egg_tiner is in Coffee. Tea, Surface, glutes, cereal i5 Hunan, Hladd, granola,bar i5 Pantzy, Sheelf regeiar_cereal
Pantzy_Shelf,,
Buack_Pantry.Ce Patt__aatty_Cabbieet rice_jar is in Pantry, Pantry_Bhelf, Bhelf, rolling.pia Display_ Surface, sheat_bread is Pasty_ Cabinet, wine glass is Bororage_Storag Cabinet, vinc_ it in Beverago_Btorsge Cabisee,,
is
glaten,
fasten_free_ceeeeee in Hanas_ regelar_coren cereel in Paack,Parzy_.abbiee
3. oatmeal in Human, Hand.
Hinssn,llnd, ostneal Band.
Objects already in target areas: gluten_free_ tree__ereall, oatmeal.
System Prompt for Level 1 & 2.
The prompt consists of five main parts: role, task, guidelines, requirements, and output example. In the requirements section, design reasoning chain for the LLM comprising five stages: object of interest identification, target area identification, validation loop, combination generation, and final output certification. The object of interest and target area identification stages extract all target-related objects and their corresponding destination areas. The validation loop checks whether any target-related objects are already in their target and can thus be excluded from further consideration. The combination generation stage pairs target objects with target areas to form multiple plausible goal states. Finally, the output certification verifies the legality of the generated results.
Role
sulve object rearrangezent
household kitchen anvironment.
You receive:
the langsage instruction of the task, iscluding the objacts_of of interent and their areea. observation of
listing all open closed obsorved objects with their placoments. If object visible.
description
area, it nor
3. list of previeusly attenpted goal states, each contaising conbinations of objects and target. that failed achiave the goal.
objects
been already placed
target areas.
Task
You need to:
instructios observation. Osly 2. Select. valid target areas for those chjacts basad an the task instruction, using areas explicitly aestioned the observation.
objects of solect objacta can hely complete task.
strictly
up possible
objects
target
Guidelines
#$ For objects of interest:
The instruction is anbiguous. You need infer the intent of the language instruction and
visual objects and, sore inportantly, unseen objects intereat the areas. 3. Use 1_' to consect sulti -oord objact nanes (e.g., 'hell
Cocsider
not tbell t)pprrt..
4. For the cbaerved objects, ita full appeared the observation.
For target The instruction is anbiguous. You need infer the intent of the language instruction and use common sanse.
The
selected
the explicitly zestioned
observation.
objecta already targes
Theae objecta are checked by husan that have been already placed the target arens.
2. You should tatally ignore these objecte!!!!!
For the final
gire your reasoning procese first. Then, you nust give your tinal anever goon sane an the ezanple jeon anever.
* fritica) Rulea (Nuat Raad Firat)
Ignore (Elaborsted already
Stepl. object's dexignated target. area, diacard from considaration..) 2. Cycle Control Vhen
equale
Section for re-processing, reconsider objects that have already been blacklisted discarded.
20

---

Requirononts:
rollowing (Bection steps step. you should explicitly givw nut your reasaning and the phaxed reaulta, and give out your finel J308 ausver at last.
each ssction. reasoning process
#t Section I: lobjaede3 OF ENTEREST IDENTIPICATIO?
Stepl: \ohjaode8
INTEREST IDENTIPICATION
Cenerate up to objecta of interest.
Focus en "fresh" objects not in the blacalist.
leza actention objects in
attention you should pay and sore probabiiity you should add it the blacklist.
object appeared
gosl
Ezasple: vrong geal atales ars: 1. chanonile_la Lea in Siacca,,trrrgeDraaee Than, pay laza attention to chanonile_ten tee, and cozsider adding it the blacklist.
Tatally ignara
already placed targat areas: chasonila,tes chasonile_tes, and zore it to the blacklist.
objects
target you tatally ignore
Erasple: Objacia already
Object Deficit Resolution Proteenl:
objects issufficient Conerate hypothetical (usseen) objecta that:
instruction requirementa),
1. Pit. the isstructian consest and pattarns.
2. Pazs sumantic cchereace checks.
Cosply
4. not duplicate blackliased propertiea.
5, Fulfill nissing capabilities is the current abject peal.
Section TARGET Varea IDEVTIPICATION
Stepl:
TARGETING
-Seleds nost probable targei_
object.
Target_area Identification Protocol:
Pit the instrustion's castext and patterns.
Reject
(e.g., placing trach refrigerator)
Consider Human_Hand first if the instruction is aaked for easy access objacts or sixilar intentions.
Brample intentions:
reach,
Stept: TARGET, Vares CHECK
For each candidate object vieible in the observation:
is liat that have been already placed the
Discard this objact antiraly
currest area in observation treget_ares Discard this object entirely. Otharvine, keep it in warking nezory.
Step2: COMPLSTENESS TEST discarding
remsiming objects current datdidatas Return to Section 1 but exclude blacklieted objecte in the next iteratios. Section CONBIRATION GENERATION
blacklist
Stepl: Nobjaode pepect-onlyy only conbinatione from the pool of valid objects. Generate up to & object
CONBINATION
Ne target_area assignrente yet.
prune duplicates redundant patterne. *** Step2: POST HOS TARGET_Varen ASSIGNMENT
Prioritize logical groupinge
For each combication fron Stapl:
Per-object resolution
higheet-validity targ option (per 2. Cross combication lecking
The first assignment chosen for object -> sarget_ares locke that napping. the zapping.
Step3: CROSS
YALIDATION
Conciesency Andit
Check that every object consistently the came targot_aros in all genorated conbinatioas.
Faslure Rodes
any target_area
detected,
confiicting
1f an object conflict arises, revisit Section step with penalty zeighting.
#e*n Final Sareguards (Section 4)
Locking valid cosbination's object Starget,
ney coabinations zust objoct->targes area assiguzeate oubsequent conbinations. Combination Quarantine
Retroactive Conctetency
existing locked mappings.
Conbinations 12volving any
object target pair kops
#u*$ Exasple (Section 4)
Expocted combinations:
combination
target_aree: Coffen_Station Burfacee; chesae.rrater. trea: Floo_Norkspace
combination 2: object: blender, treaot_area: Sttiee_Stationnaatte Surface; object: potaro_pccler, Disll
target_
Explanation: the object conbinations (blender)
objecte conbinstions are
cheuse grater, blender and potato.povier)
Unexpected conbisations:
combination
target_ares: Goffee_Station Burfacee;
chesan_grater,
target_area: Flaz,Korkpacce
combination 2: object: blender. targot_area: Dichy_Dich_Bnl Shoif; object: choese_grater, targot_ares: Flek_par
Explanation: the Surface
object Diihy_Dioh,Sholl.
corbinations (blander) different
combination objects conbinations
zase (blender and chenas_graser)
#t Section 5: FIEAL AKSHER
VALIDATION Conbins validated conbinationa.
Stept:
Esplicitly presen: the finel set of object >> target, area nappings.
Enaure 103% targat-arm, conxiatancy with the locked paira.
Step2: FIVAL. OUTFUT CERTIPICATIOS
21

---

daly
validation
Output
J80N anaver
1. All rules is sections 1-4 are satisfied.
2. Rescurce allocations rensin vithis bounds.
final
should
Ezanpla output JSON
your jacn betveen jjao
Exexple output J802 data:
"** jaon
"ubjects";
"objact;; "apple",
"target_azea"; Baud"
"object"; "banens", atargat_aran': "rabot"
b, "prabability":
"abjacta":
"objact"; *orange", "sarget_aren's "Euzan_Band"
"objact": "hanans", "target.area"" "robot"
"probability"; 0.3
System Prompt for Level 3. The prompt adopts the same structure as that used for Levels and The reasoning chain comprises four steps: object visibility check, initial area prediction, consistency verification, and final answer. The object visibility check determines whether the object is observable in the current scene graph 9.. The initial area prediction and consistency verification steps infer likely initial areas for the target object and ensure that all hypothesized locations for invisible objects are closed areas. The final answer formats the result into the required JSON output schema.
Role You receive:
expert assistant apecialized object relocation
the langsage instruction of the task. description
observation of envirementt, all open clased placoments.
obsorved objects visible.
object
area, it
3. the nane of the object of intereat should now focus
Taak
need idantify up to prabable initial areas wvnry sixsing object probability
# duidelinex
Initial_arane
The object's placesent consistent comsos aesse.
2. The mnitial_araas can only be selacted from the areas asplicitly sentioned is the obaervation. geon
#$ For the final ansser:
your reasoning process
you give your
жавa the azanple jaon ansver.
Now, carsfully read the folloving requiresanta, then step by atep give your iaszoning, and fisally, in J8ON forast.
generate your
Requiresenta:
rensoning process should include follawing staps.
step, you should
esplicitly give your ressoning
phased resulta.
" Step 1: Object Vinibility Check Check vhether the currant abject of intereat vixible in the ohservation. object placed
object
probabslity
1.0, junp
step and give out final ansver.
If the object's currant area la rabot ls hand, the sslected area should be 'robat."
Guess
Reasen/ Guwza up to pazzible initial_arma for current abject intereat
areas the observation and corresponcing probability ssing connon sense.
s* Step Object Initinl_Ares Double Check
areaial,areas you propoced:
1. closed arean in the observation.
2. The probability sun for all candidate атннв rust auT to 1.0 for each objact.
2 if double check faile.
out your #inal J808 anzver the zame forzat Ezampla Anaver.
Exanple Jeoz Anever:
22

---

"initial_ inw.. aurface." "probability"; 0.7
"initial, aree"; "cooier_layer", "probability"; 0.3
A.2 LLM-Generated Rollout Policy in Online POMDP Planning
Prompt Design. The prompt consists of six main components: role, objective, function signature, available methods, requirements, and final task. The function signature specifies the structure of the policy function, including its name, input parameters, and return type. The available methods section enumerates the callable functions along with detailed usage descriptions, including each method's name, input arguments, return values, and functionality.
You are helping a robot perfors an object rearrangenent tack in a simulated environsent. The r robots state described SconeGraphšinplc object, which tracks:
Which
pareat child relarionchips betsees
objects.
3. The open/closed status of any given area.
4. Which object, if
currently being held by the robet.
also nove each apecified object into apecified area.
vhere
indicates pairing [goal_area,1d, object.jc)
Your Dbjective
Write function nazed MextAction
deteraines
action should
toward completing any renaining goals. After perforsing the returned actios, function may be called again until all goals are net.
Function Signature
ActionSiaple Mextiction(
coast atd: set.eooorrd::::rrre array 2>>2 uzreached.goals, coast EceneGraphstaplck curreat_
unreached.goall
(ares_id, object_id] pairo descriding objecta noved to which areas.
2. current_
duscribes the atate of the enviroanent.
Available Methoda ScameGraphSipple:
You can azaune that the folloving nuthods eziat for querying the acens: int SetObjectIaBand() const;
Returss ID
object currestly
hand.
bool GettzeadpeaFroadd(inn area_id) const:
/1 Returna true If the specified area
false otherwize.
ChockAreaIsScene area_id) const; // Returss true if the apecified area is known and preaent in the acens.
baol ChackObjeetTaSeenn abject_id) Returea true the apecified object
preaent the acane.
int ManObjeetParanttti (inE object_id) canst:
that currently costaina object, object parent.
ActionSisple Class and Baage:
snen clazs ActiorTyps
ACTIDN_PLACE PLACE
possibly
class ActionSinple
public:
Actionšinple(); CettienSinlll(Acttinnn action_typ,, int area_id, int objest__id); // ...
aet.ioniiniiiaccttoo//ie :CCTON__OPEE
open spacified area_id, objact_id) instructa robot pick up as abject.
from an area.
ActionSingle (areiiiiii(ctttoyyynaaaa AAAACCCOOPACCEEE aren_id, -1) instructs the robot to place itx currestly hald
sbject into specified axea.
An empty constructor ActionSixple() indicates no actione de there are no rezsining
tasks.
Requirenents:
exactly
function muxt compile in standard asvironment.
You may use any logic you see fit decide shich action to returs next. But pay attensions to: firet. You generate looped object
Betore
closed you
at саmо Generate repeated
23

---

target object with objacta are observed. nust generate If there is no seasingful action to take, you must return ActionSinple() with so arguzenta (the so-op action).
You
actions.
dive out your thinking process, and genorate a pacudocedo. Check whather logic is write.
Inplezent fuaction body Rexidction volid paendneade. function should use the provided paranetara ScenaGraphSivple nathoda.. ahould return an ActionSinpla that ancodes the aingle, noat appropriate action to help achieve the rensining goala.
include explanations
L.MM-Generated Code for Rollout Policy. We send the prompt to the OpenAl model and directly adopt the generated code without further modification.
ActionBimple MextAction
const atd: :at::: :arra 2>58 unreached.goslt,,
const SceneGraphStnpl.. currans_acene,_e
no goaln remain. return no-og
if (sareached, capte.
ActionStmpie();
11 Check each goal
(const autok upreached_gonle)
int gosl_area go);
int goal_object goll
(heurreat.eceno_graa
area)
(current_scene wrwpe_graph........eoo.o.....eee CaceeetcecctDeetttteeeee (goa__ continue; }
If goal is already satisfied, skip it Int pareat_of_goa areeett htt..aacaa........ccceeeaaaaaaaa (ot.neeeeearraattoooo...ee.e
sparest_of_gose gosl_aros)
continue;
Chock
currently bolding
object_in,haae acese_
() tag..
(object,in, ha, - gosl_ {
Reed place
cuureea sesszeat_scezo_coo sccsc_scc___aaa graph. oedres@peaFrool((ggaa.roa)))
// Open the goal area first
return (atiosaappetccciotttp:::::
lopez, goal_area, -1);
elce
Place object return ActionSinple (Atpsappeeaccioa7p:::::: \place, grea, -1);
(object_in_Ban
// Holding different object; place it back in ita parent
int parent_of held
www.:es.eeeeeeee..oooo JetobjectPareat (objuct, band) (parent_of soreettof_belddeeeooeeeee -1) {
Na known place put. it; do nothing return ActionSisple();
}
(fourrent_ graph www.reeeeeraaarraao.t..... (faretdddppartt.fe.eedeee
return Aciiosslagl
Yopez, parest_of_ -1);
alas rsturn AetionSinple (Aciilooppeccciotyypppee.s:
Aplace, pareat.af_beld, -1)
wlaw {
1/ Holding nothing: pick the goal object (parest_nf-
No parent knows; nothing return (ctionSimple();
(fcurrent grapph. aew.eeee........eeaeaaaaaaaoaee oet.reaaauurrrttttrrrrr.o..oooo // Open the parent area first
return aetiaaSsppaaacciiotyy:::::TTT Lopan, parent_af_ggol, -1);
else {
return Aet
Apick, parmst_of_goal, goal_object);
1/ Ef all goala are antixfied or no action can be deduced, raborn na-op return (ction8ispl4())
24

---

A.3 Kitchen Environments and Area Naming
RoboCasa Kitchen Environments. We select five kitchen environments from RoboCasa [13. The layouts are illustrated in Figure We remove sufface-mounted furniture items (e.g.. sinks) while retaining furniture with internal storage spaces (e.g.. ovens).
One Wall
(b) One Wall with Island
(c) L--Shaped
(d) L-Shaped with Island
(c) Galley
Figure 6: Kitchen Environments from RoboCasa
13
Area Naming Scheme. We categorize areas in each scene into three types of initially closed areas areas-furee furniture internal spaces, cabinets, and drawers- and two types of initially open areas: surfaces and shelves. Below, we list the specific area names for each kitchen environment.
One Wall:
Category
Number
Area Names
Furniture Inner spaces
Fridge_Coolet Cooler Layer, Fridge Freezer Layer, Microwave Inner Inner_Spacee Space, Oven_Inner_Sppp
5
Dish WashWrrsn__nee Space
Dishware Cabinet, Jashware_Cabinet, Snack Snack_Pantry Pantrr_nnaaaaaaeee Cabinet, Cleaning Supply_Cabinec Cabinet, Likewarre_Cabinee Cookware Cabinee, Utility Cabinet, Appliance Cabinett,
Cabinets
8
StaerrageSSttrggeeeee Cabinet
Drawers
Cutlery Brawer
Prep_Surface Coffee
Aapliance_Surfaaee Display Surface, Drop Lone__Surface
Surfaces
Shelves
3
Cookbook_Shhe Spice_Sheii Pantry_Shelf
One Wall with Island:
25

---

Category
Number
Area Names
Furniture
Fridge Freezer Layer, Fridge Cooler Layer, Oven Inner Space.
Inner spaces
Microwave Inner Spacee
Dry_ Srood_Sttrag__aaaee Cangge_,,,ie,,,,, Appliance_ Sttrcee__ttrag_____ Ceorage_Cabinet,
Cabinets
Laking_Suuplicee Cabinet, Beverage_ Service Cabinet,,, Cleaning Serraiinnntttooeeeee Cabineta SttrSttoeCaaaeeeeeeee
Bulk Storage Cabinet, Snack Rotation Cabinet
Utensil Organizer Drawer, Knife Tool Drawer, Spice Storage Drawer,
Drawers
Vraap_Containe__Da Drawer, Sowee_Storrag Drawer, Utility_ Junk Drawer,
Trash Bag Drawer, Quick_Snack Drawer
Seffee_Station_Stte Surface, Prep_ Station__Strteeeee Appliance _ase Sarfacer Breakfast_Bar Barr_Barrrrriie BBar_Surface, Flex_ See__WoooossWsuteeeeee Surface
Surfaces
Shelves
2
Daily_Dish Shelf, Cookhook Beaikhook__ssply__SSe Display_Sheif
L-Shaped:
Category
Number
Area Names
Furniture
Frndge_Freezer Layer, Fridge_Cooles Cooler_Layer DishWasher_Inner Tven_Inner_Speen Spance, Microwave_ Baaeivee__eee____ee SpaceS
Inner spaces
Cookware Sookware_Storage__ Storaat__aaiineee Cabinet, Small Apppliacc_eaabliiiiiaaea
Backup_ Dishes Dishes_Cabinet, Baking_ Tool ihoo__Cainet,,,, Cleaning SwapniinnnSupli_e_aeeeee
SeppSSuuCppppeettttttteeeeeaeeee Cabinet,
Cabinets
Frod_Fod__ LatdFFoooaat_____eeee Centtr_Cabinnt,, Beverage Storage_Cabinett
Lunchbox Thermos Cabinet, Plastic Container Cabinet,
Food Tool Cabinet, Seasonal Item Cabinet
Item,
Cutlery_ Organizer
Drraani Drawer, Cooking Sooking_Tool____ Tool_
Srap__oil_Deeeee
Drawers
7
Spice_RackDDee Drawer, Trash Trash_Bag___ Bac__Bag_eelllleee Cecyclc_Drawed Charging_
Recycling Sorting Surface
Coffee Station Surface, Meal Prep_ Surface, Small Appliance Station Surface, Breakfast Zone Surface,
Surfaces
Herb Garden_Surface, Flcx_ Workspace_Surfaite Surffce
Shelves
Soily_Spice_Shefe Cookbook_Display_S5t
L--haped with Island:
Category
Number
Area Names
Furniture Inner spaces
Inner Space, Microwave Inner Space, Dishwasher Inner Inner_Space, Fridg__rrezer_Layee, Fridge_Cooler_Layee
5
Supply_Cabinel Cabinett, Dishware Dishware_Cabinet, Cookware Cabinet, Cookware_Cabinet, Cleaning Serening_SSpplyy Cabinet, Baking Tool Cabinet, Pet_Food T Cabinet, Waste Maaagemmn Cabinet, Appliance Storage Cabinet, Beverage_Cabinnn Spice Jar Cabinet
Cabinets
10
Elorage_CCbiiet,,
Utensil Drawer, FoodwrappDraavee Drawer, Condiment Conckn _raket_Drawer. Block Drawer, Baking Drawer TeafCoffee Drawer
Drawers
Knife Knife_Block
Small ApppallAppiiance____
SurrhiannceSSffae,,,,, Surface, Pur_fSurface, Coffee Coffce_Station, Shation_Surfaan
Surfaces
Shily_Scasoning Surface, Fruit Basket, Basket_Surface,, Kitchen_ Baaieee_TToo_Surreeie (trof_SSrface,
Decorative_Surface
Shelves
Cookbook Shelf, Display Dhell
* Galley:
26

---

Category
Number
Area Names
Furniture
Fridge Freezer Layer, Fridge Cooler Layer, Dishwasher Inner Space, Oven Inner Space, Microwave Inner Space
Inner spaces
Dry_Food, Soy_Foo__Storgeee___ ChorageCCabinet, Small Appliincee Cabinet, CappiinnceCCainet,,,
Liquor_Storage Cabinet, Sreaning_Supple Supply_Cabinet, Cabinet, Backup_ Dishes__________eee Cabinet, Baking Ingredients Cabinet, Bulk Food Cabinet, Seasonal Items Cabinet,
Cabinets
Cookware Saarare_tttree_aaeee Cabinet, Servingware Lisee_Dispp___a Display_Cabinee Cabinet, Pet_ Se___Suppp____iiie Cabinet, Medicine Saarinee_ttorrraaaae
Utensil Utensil_Organizer Drawer, Cooking_Towe Sfool_Drawer Spice_Rack Drawer,
Foip_Wrap Brawer, Snack Storage_ Drawer, Knife Block Drawer,
Drawers
11
Kitchen Linen_ Drawer, Recycling Bin Drawer, Lunch Container Drawer,
Tea Lee_Cooff_DDaweee
drawer
Prep_Surface Rice Cooker Surface, Mixing Station Surface, Baking Prep Surface.
Leffee_Staaion_Surrfeee Chopping Sropppin__Statio___ Station_SSrracee Surface, Breakfast_ BreeakaattPPrp_SSie
Surfaces
10
Fruit Basket Surface, Microwave Station Surface, Knife Magnet Surface,
Cocrowave_SStaiion
Herb Garden Surface
Shelves
2
Cookbook Ccokbooo_Disspaa_SShehe Salll_Dishee_Sheee
A.4 LLM-Assisted Task Generation
We generate object rearrangement tasks with the assistance of an LLM (GPT-4o). Each task comprises four components: natural language instruction; target-related objects with their initial placements; disturbance objects with their initial placements; and set of goal states that fulfill the instruction's s requirements.
First, we sample a background context for the task from predefined set of character and temporal settings. The LLM is then prompted generate ambiguous language instruction that human might provide, along with 6-8 target-related objects and their imitial areas. These initial placements are deliberately chosen not to satisfy the instruction's requirements directly, ensuring that rearrangement is necessary.
Next, query the LLM generate additional disturbance objects unrelated the task, increasing the total number of objects the scene to 20. For each disturbance object, the LLM is asked to propose four plausible initial areas based commonsense priors, from which we uniformly sample one as its placement.
Finally, prompt the LLM to generate up to four plausible target areas for each target-related object and to enumerate valid combinations of target-related objects that satisfy the task requirements. We then compute all potential goal states, each comprising the target objects and their corresponding target areas.
An example ISON file of generated task is shown below.
"placesent":
"aren": "Plastin, Cecaatii_Containerr Contwiner_Caaiine Cabinat",
objjcct" Costten_fee_ffluee _1""
"area': "Seasonel_ Ctw.mmeed__ue.etbiieeeee "placed_abjactt; vngar_cookieennddd..00 b.
"area': Caaetic_Contatneer.Coe "plased_cbject"; "dinser_plate_15-
"aren': "Lanchbax, Bearcchby__hhrrsscc. Charsox_Cabinet. objec"" "Jottover
"area': "Cookuare, "Cookvaro_Sterage Sttrrrtttttrrrrraeeeeeee "plassd_nbject": "rica_cnnker_14
"aren': "Gooking_Tool, Draver', objec"" "sorving, 5po0t,3"
27

---

"Breakfast, _euee_Burface', "plassd,abjsct": mesxuring.cup..
"area"; "Seal1. hap.aapppp..aaaaaeeeeee "placad, "aug,
"area"; "terarage.Bteragee Cabinet', "plased_ahjact"; opane_e
"Breakfaxt, Zenn_Brrfaca', "plased "agg_timer_
>,
"area"; "Cookbook_ Ditppoo...aalll.h.1.l... Sbelly,, "placed, caadetd
{
Saaveragg.Storagg.cooe
"plased, "harb.prass_5"
>,
"area": "Senaannl_Ttee.aabeee
"placed, "candle_3"
},
"area"; Prep..uteeer "placed_ "nrett,
h,
Saakkaox_DDaalay..Beee "placed, "decorative, vase_""
"area": Sereraage_tterag..oo Cabines', "bjece" 'vise_glase_13"
"bjac"" "mattiralllsgg.nnt.122
b,
"area": "Seall Appiiappppllaceettea Station, Surface", "bjacod raree
},
"area": Apaall_Applsance,Cae "pbaced "vine_opaner_""
b,
"area": "Breakfast Beteett_ooe__a_aeeeeeee Burface", "bjos"" "coffec_aug.5"
b.
"area": "Bpice_Rack,Drapee "bjestt" cardlensicck.blderr.33
1.
"nazo": "Feich", "location": Cooktoor.Dieepay.Bat
"object_in_haadd"
tack":
"instruction": "As the evening wind-dova begins and focusing allergen safety, please ezsure organizing any supplies accessible separate uteaeils for tomorzov'e lunch.',
_cal_set";
"tazgot_area"; "Baking, Fool__obbiee"" "pieced,object""; freefo_.tre.f
"rarget_area"; "Bridge_ Cocler, Layer", "bject" "leftorer,contsisees
"target "Baking, Foel, Cebinste,,"'', objecet "gluto__tte__couu_.
J.
"target_area": "Doy_Food_ Pantey_ objeced "elatee_freeefeeeee
28

---

"target_area",
"placad, "Iafbaver.comiaiinee:
1.
[
"target_area "Dry, Fooy_.ooo_P_ata Paasry_Cabineet" Cabinet", objecs' "gluten,fren flour_115
A.5
Hyperparameters in Tru-POMDP
Parameter
Description
Value
C1 C2
Number of candidates for Levels and in the Tree of Hypotheses
3
T
Temperature for the LLM in the Tree of Hypotheses
0.1
Threshold in Hybrid Belief Update
0.7
k
Number of scenarios in Belief Tree Search
30
d,
Maximum search depth in Belief Tree Search
20
d,
Rollout policy execution depth
10
A.6 Baseline Modifications
Online Planning Reflexion. Reflexion was originally designed for offline planning. We therefore introduce the following modifications for the online planning setting, First, we revise the activation mechanism of the reflection module: when the LLM either produces thinking process three times consecutively or generates three infeasible actions in row, we consider the LLM unable provide valid outputs. At that point, the reflection module is triggered to generate new plan for guidance. Additionally, we restrict the history record to the last 10 time steps to reduce input token length and LLM query latency.
System Prompt for ReAct and Reflexion*. In the original implementation, ReAct and Reflexion used GPT-3.5 for simple tasks, guiding the LLM solely via multiple demonstrations. In our evaluation. we observe that this approach performs poorly when switching to the GPT-4.1 and applying to more observations and stricter action
complex tasks. We attribute this to the increased complexity constraints. To address this, we design ReAct* and Reflexion* which incorporate additional system prompt specifying the role, task, action constraints, and other relevant details.
Role:
zobot complte xitchenvare household taska. firat, you current observation of the eavirenaent. 2. the task you need to complete. step, you'l1 receive current observation of eavirenacnt.
* Task:
an cluzed Pick(area, object): pick the observed object from as open area
(pen(a)))): open
3. Place(ares): place the object in zobet 's hand in/o2 open area
Note:
If an ares is opez, it's fuily observable, don't try to explore the open areas.
2. If you're still been asked complete the task (receive action fuedback), it neans haven?t ether solutions. yet. given fornat, appeared is the obaervation.
complete
The action muxt
area object paranstara
action must
You can generate 2 kinds of azskers.
atep, you should begin you thinking proceza: process, you don't seed generate
you
think
beat (e)t best action: Hf you received tok.? at the last of the interaction history, it zeazs that Therwfore, plaase ansver one action directly. your
have thought. about the currest please don't geserate 12' asything
29

---

A.7 Visualization of Planned Results
We visualize an example of the planned results in Figure 7 In this task, the instruction is: "I'm preparing for my big housewarming gathering this afternoon. Could you help me sort out items to ensure that snacks are clearly visible?" The robot identifies target objects (chips, croissant, apple, and iced _ea_ within 4 steps and completes the rearrangement by placing all target objects onto surfaces within steps.
fwv, pert chips
apple
Open/Snack, Cubinet)
OpentQuick Drawer)
Cabincd)
Open(Bulk, Cubincd
iced tea
iced tee crobeant
PicktBulk_ttoo wwwp:ll.tttteeeeeooo Moorage_Cabble Cabinet, leed
Prack:Breakfast Surfaee
7. Pick(Dry_Food Seroo_itrageeaaaaaa croissant)
PlacegBreakfart, Bartttrrrt_BBBBBrrtroa
apole chips
Pick[Bulk PockBBlkkStorogg Storoge. Cablnet spolc)
10, PlocepPrpp Station Surface)
11. Pick/Snack, Rotation, Cabnnet, chips)
12 Placo/Prop. PlacoPPrppSttttin Station, Surfoo
Figure Visualization of planned results.
30


Reviews:
[{"review_id": "03U58Gs4b2", "reviewer": "Reviewer_CHEj", "summary": "This paper presents Tru-POMDP, a framework that integrates LLM-based commonsense reasoning with principled POMDP belief-space planning to address robotic task execution under open-ended uncertainty. The system introduces a hierarchical Tree of Hypotheses to generate particle-based beliefs over scene graphs and task goals, applies Bayesian filtering for belief tracking, and uses an online POMDP planner (based on DESPOT) for action selection. While the overall framework is well-structured and practically relevant, the core technical novelty is concentrated mainly on the problem formulation. The paper relies heavily on existing solvers and standard belief tracking methods, with limited innovation in planning algorithms or inference techniques.", "questions": "Suggestions:\n1. Incorporate action execution monitoring and failure recovery, such as retrying, replanning, or reasoning over failure causes within the belief update process.\n2. Add experiments in noisy or stochastic environments, and potentially test tasks beyond object rearrangement to validate generality.", "limitations": "Yes", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1. Structured belief generation: The Tree of Hypotheses (TOH) effectively organizes LLM queries into object, goal, and placement hypotheses, providing interpretable and diverse particles.\n2. Belief-space planning: The use of online POMDP solvers like DESPOT allows the agent to reason over uncertainty instead of relying on brittle single-hypothesis planning.\n3. Hybrid belief update: Combining Bayesian filtering with LLM-generated particles improves update efficiency and robustness, reducing token cost and planning time.\n4. Efficient rollout policy: Using an LLM-generated C++ policy for DESPOT rollouts balances commonsense reasoning and computational tractability.\n\nWeaknesses:\n1. Limited algorithmic novelty and theoretical analysis:  The work does not contribute new theoretical insights or generalizable planning methods. Its scope is limited to a specific task domain. Most components, like particle filtering and DESPOT, are standard. The contribution lies primarily in their integration with LLMs.\n2. Heuristic hypothesis generation: The TOH process is prompt-based and manually structured, lacking learning or adaptation mechanisms to optimize hypothesis quality.\n3. Execution failure not modeled: The framework assumes deterministic action execution (e.g., always successful picks or opens). In practice, such actions may fail due to perception or actuation errors. The absence of failure detection and recovery mechanisms limits the system's real-world robustness.\n4. Limited task diversity despite general task planning title: Although the paper presents itself as addressing general task planning under uncertainty, the evaluation is focused solely on object rearrangement tasks in kitchen environments. It remains unclear how well the proposed method generalizes to other types of tasks, such as tool use, multi-agent collaboration, or dynamic goal adjustment, or how it handles real-world challenges like sensor noise, stochastic transitions, or action failures. A broader task set would be needed to support the generality implied by the title.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive feedback and for acknowledging the strengths of our work, including the structured belief generation via the Tree of Hypotheses, the principled use of belief-space planning, the hybrid belief update mechanism, and the efficient LLM-generated rollout policy. We appreciate the opportunity to clarify our contributions and address your concerns regarding algorithmic novelty, generalizability, and the handling of execution failures. We believe our responses will demonstrate the significance of our contributions.\n\n***\n\n**Q:** Limited algorithmic novelty and theoretical analysis: The work does not contribute new theoretical insights or generalizable planning methods. Most components, like particle filtering and DESPOT, are standard. The contribution lies primarily in their integration with LLMs.\n\n**A:** We respectfully disagree that the contribution is limited to a simple integration. While we build upon established methods, our primary contribution lies in creating the first framework that enables principled, belief-space POMDP planning in **open-ended** domains, a challenge that neither LLMs nor traditional POMDPs can solve alone. This synthesis offers significant conceptual and technical novelty:\n\n1.  **Bridging Open-Ended and Principled Planning:** Traditional POMDPs are confined to \"closed-world\" problems with predefined state, action, and observation spaces. Conversely, LLMs, while capable of handling open vocabularies, often produce suboptimal or deficient policies under uncertainty (as shown in our experiments in Figure 2). Our work is the first to bridge this gap, empowering POMDPs to tackle open-ended uncertainty while grounding LLM reasoning in a rigorous probabilistic framework for long-horizon, near-optimal planning.\n\n2.  **Novel Belief Generation for Uncertainty:** To our knowledge, prior work has used LLMs to generate only a single, most-likely hypothesis about the world state [1, 2, 3, 4]. A core insight of our work is to leverage LLMs to construct a complete **belief**, or a probability distribution over states, represented as a set of weighted particles. This is non-trivial; a naive extension from generating one hypothesis to many performs poorly, leading to a performance drop of 26%, as shown by the \"w/o TOH\" ablation in Figure 4. Our structured Tree of Hypotheses (TOH) is a novel and critical mechanism for generating a high-quality, diverse particle belief. Furthermore, the particle representation seamlessly integrates rigorous Bayesian filtering with LLM inference, a key aspect of our hybrid update module. We believe these insights will be valuable for future research in probabilistic planning with LLMs.\n\n3.  **Novel POMDP Planner Components:** Our planner includes novel adaptations crucial for efficiency in open-ended domains. \n    - The **dynamic action space grounding**, which instantiates actions based on hypothesized objects relevant to the task, prevents the action space from becoming intractably large. \n    - The **LLM-generated rollout policy**, where a code-based policy is integrated into the tree search, significantly boosts planning performance by 22%, as demonstrated by the \"w/o LRP\" ablation in Figure 4.\n\n***\n\n**Q:** Heuristic hypothesis generation: The TOH process is prompt-based and manually structured, lacking learning or adaptation mechanisms to optimize hypothesis quality.\n\n**A:** This is an excellent suggestion. Dynamically adapting the TOH structure is an important direction for future research. The current manually-structured TOH serves as a strong, interpretable baseline that demonstrates the viability of the approach. It reflects the factorization structure of the hidden state space of object rearrangement tasks. For future work, we envision two potential avenues for adaptation:\n1.  One could introduce a meta-level agent that learns to determine the optimal factorization of the hidden state space, and thus the structure of the TOH, before generating hypotheses.\n2.  Another promising direction is to treat the TOH structure as a parameter to be optimized via closed-loop learning, drawing inspiration from recent work on planner optimization [5].\n\n***\n\n**Q:** Execution failure not modeled... The framework assumes deterministic action execution... The absence of failure detection and recovery mechanisms limits the system's real-world robustness.\n\n**A:** We agree that modeling execution failures is crucial for real-world robustness. A key strength of our framework is its inherent extensibility to such scenarios without requiring fundamental algorithmic changes. The POMDP formulation readily models perception noise and stochastic action outcomes via probabilistic observation ($O(z|s',a)$) and transition ($T(s'|s,a)$) functions.\n\nWhile our current implementation uses a deterministic version of these models for clarity and to focus on the core contribution of handling open-ended uncertainty, the belief-space planning algorithm (DESPOT) and the particle filter-based belief tracking are designed to handle probabilistic models. Extending our system would involve learning the POMDP transition and observation models from data (which has been demonstrated in [6]). The resulting optimal policy under uncertainty would naturally exhibit robust behaviors, such as retrying failed actions or choosing information-gathering actions when uncertainty is high. Online replanning, which is already implemented, allows the agent to adapt its plan based on unexpected outcomes.\n\n***\n\n**Q:** Limited task diversity... the evaluation is focused solely on object rearrangement tasks... It remains unclear how well the proposed method generalizes to other types of tasks... A broader task set would be needed to support the generality implied by the title.\n\n**A:** We appreciate the feedback on task diversity. While our experiments focus on complex object rearrangement, the core technical contributions of Tru-POMDP are domain-agnostic and provide a foundation for general task planning under uncertainty.\n* **LLM-generated particle beliefs** can be applied to any domain where uncertain states can be described with semantic hypotheses.\n* The **open-ended POMDP framework** can be extended to tasks beyond object rearrangement, such as navigation, tool use, or multi-agent coordination, where the set of relevant states, objects, or goals is not known beforehand.\n* The **semantic-level POMDP model** can be applied to any domain where such a model can be formulated, for instance, by learning it from human demonstrations and interactions [6].\n* The **hybrid belief update** and the novel planner components (**dynamic action space** and **LLM rollout policy**) are general-purpose enhancements.\n\nWe acknowledge that demonstrating this generality on a broader set of tasks is an important next step. However, implementing and evaluating these extensions is substantial work that falls beyond the scope of a single paper. Our current work establishes the essential principles and demonstrates their effectiveness in a challenging, representative domain.\n\n***\n\n**Suggestion:** Incorporate action execution monitoring and failure recovery, such as retrying, replanning, or reasoning over failure causes within the belief update process.\n\n**A:** This is an excellent suggestion. As discussed in our response regarding action failures, the Tru-POMDP framework already has replanning capability and can incorporate failure-recovery and retrying behaviors at the face of uncertainty, once equipped with stochastic transition and observation models. Implementing these extensions is a key part of our future research plan.\n\n***\n\n**Suggestion:** Add experiments in noisy or stochastic environments, and potentially test tasks beyond object rearrangement to validate generality.\n\n**A:** As we outlined in our previous responses on generalizability and robustness, there are no fundamental barriers to applying Tru-POMDP more broadly. Our core technical designs—LLM-generated particle beliefs for semantic uncertainties, a hybrid belief update, a dynamic action space, and an LLM-generated rollout policy—are general. The POMDP formulation itself naturally supports noisy sensors and stochastic actions. While we believe these extensions would further strengthen our claims, implementing and thoroughly evaluating them in new domains and under noisy conditions is not feasible within the rebuttal period but remains a high-priority direction for future work.\n\n***\n\n### References\n[1] R. Hazra, P. Z. Dos Martires, and L. De Raedt. Saycanpay: Heuristic planning with large language models using learnable domain knowledge. In *Proceedings of the AAAI Conference on Artificial Intelligence*, 38, 20123–20133, 2024. \\\n[2] A. Z. Ren, A. Dixit, A. Bodrova, et al. Robots that ask for help: Uncertainty alignment for large language model planners. *arXiv preprint arXiv:2307.03046*, 2023. \\\n[3] B. Liu, Y. Jiang, X. Zhang, et al. Llm+p: Empowering large language models with optimal planning proficiency. *arXiv preprint arXiv:2304.11477*, 2023. \\\n[4] T. Silver, S. Dan, K. Srinivas, et al. Generalized planning in pddl domains with pretrained large language models. In *Proceedings of the AAAI Conference on Artificial Intelligence*, 38(18), 20256-20264, 2024. \\\n[5] Y. Lee, K. Lee, P. Cai, et al. The Planner Optimization Problem: Formulations and Frameworks. *arXiv preprint arXiv:2303.06768*, 2023. \\\n[6] Curtis, A., Tang, H., Veloso, T., Ellis, K., Tenenbaum, J., Lozano-Pérez, T., & Kaelbling, L. P. (2025). LLM-Guided Probabilistic Program Induction for POMDP Model Estimation. arXiv preprint arXiv:2505.02216."}, {"review_id": "rcY0WSSzT5", "reviewer": "Reviewer_XZFL", "summary": "This paper proposes Tru-POMDP, a task planning framework that integrates Large Language Models (LLMs) with belief-space POMDP planning for robot manipulation tasks under uncertainty. The core idea is to build a Tree of Hypotheses using LLM queries, representing multiple plausible goals and hidden object placements. These hypotheses are filtered via a hybrid Bayesian mechanism and fed into an online planner, allowing for robust and efficient planning under ambiguity and partial observability. Experiments in diverse simulated household environments demonstrate significant performance gains over strong baselines, including ReAct, Reflexion, and LLM-MCTS.", "questions": "Does the Bayesian filter in this paper involve an actual Bayesian update process, or does it primarily rely on the LLM to combine prior information with new observations?\n\nWhat is the computational cost of the proposed approach, in comparison with other works in the literature?", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nThis paper addresses a critical and underexplored research gap in robot task planning under uncertainty. The proposed integration of structured LLM reasoning with POMDP-based decision-making is both novel and timely.\n\nThe core insight of the paper has strong real-world applicability, particularly for household service robots dealing with ambiguous instructions and hidden object states.\n\nWeaknesses:\n\n- The computational analysis of the method could be stronger. Figure 5 presents a comparison against ablation variants, but the performance in comparison to other works in the literature (e.g., the ones shown in Figure 2) is still unclear.\n\n- Although five different kitchen environments were used, the work could show more generality if experiments are performed in other types of environments, beyond only kitchen-related tasks.\n\n- Although the paper is well-written, the text could be made more accessible. For instance, abbreviations such as POMDP and Tru-POMDP are not being defined when they are first mentioned. Other technical terms could also be made more clear in the introduction (such as \"open-ended uncertainty\"), in order to communicate more clearly the motivation and the significance of the work to a wider audience.", "was_revised": true, "final_justification": "I am happy with the authors rebuttal, and the additional experiments provided.\n\nOn the other hand, I agree with reviewer CHEj that the paper would be stronger if it was demonstrated in another domain. Therefore, I decided to keep my current score.", "rebuttal": "Thank you for your supportive assessment and for recognizing that our work addresses a critical research gap with a novel and timely approach. We are grateful for your constructive feedback on strengthening the computational analysis, demonstrating generality, and improving clarity. We will address each of these points below.\n\n***\n\n**Q:** The computational analysis of the method could be stronger. Figure 5 presents a comparison against ablation variants, but the performance in comparison to other works in the literature (e.g., the ones shown in Figure 2) is still unclear.\n\n**A:** Thank you for this suggestion. To clarify the computational cost relative to the baselines from Figure 2, we provide the detailed average planning times (in seconds) per episode across all difficulty levels below.\n\n| Method | Easy | Medium | Hard |\n| :--- | :---: | :---: | :---: |\n| **Tru-POMDP (Ours)** | **135.8 ± 14.6** | **188.4 ± 25.1** | **245.9 ± 29.5** |\n| LLM-MCTS | 600.8 ± 0.1 | 600.8 ± 0.1 | 601.8 ± 0.7 |\n| Reflexion* | 114.7 ± 15.1 | 161.4 ± 16.5 | 181.8 ± 16.5 |\n| Reflexion | 100.2 ± 10.9 | 155.6 ± 16.6 | 181.7 ± 16.8 |\n| ReAct* | 102.5 ± 11.0 | 150.3 ± 15.6 | 167.3 ± 14.4 |\n| ReAct | 97.3 ± 11.2 | 148.8 ± 12.0 | 165.7 ± 13.1 |\n\nAs the table shows, Tru-POMDP is significantly faster than **LLM-MCTS**, which also performs explicit reasoning but timed out on all tasks due to excessive LLM calls within its search loop. While Tru-POMDP is slower than purely reactive LLM planners (ReAct/Reflexion), this overhead is a direct result of the comprehensive belief generation, which is crucial for robust planning under uncertainty and achieving the high success rates shown in Figure 2. This cost is a worthwhile trade-off for principled decision-making. We also note that this overhead could be substantially reduced in future work by fine-tuning a specialized belief-generation LLM.\n\n***\n\n**Q:** Although five different kitchen environments were used, the work could show more generality if experiments are performed in other types of environments, beyond only kitchen-related tasks.\n\n**A:** We agree that demonstrating generality is important. While our experiments are situated in kitchen environments, the underlying algorithmic components—factored belief generation with TOH, representing hypotheses as a particle belief, and POMDP planning with dynamic action spaces and LLM rollout policies—are fully generalizable.\n\nAdapting our framework to a new domain would require redesigning the semantic POMDP model and the specific factorization structure of the TOH. However, we argue that this is no longer a significant barrier. With the advent of powerful LLMs and Vision-Language Models (VLMs), semantic or symbolic models for robotics domains (e.g., table-top manipulation, assembly, in-factory logistics) can now be effectively learned from human demonstrations and interactions [1]. Furthermore, the factorization structure of the TOH, essentially reflecting the factorization structure of the hidden state space of a domain, could itself be determined by an additional LLM layer that analyzes a language description of the new domain, further automating adaptation.\n\n***\n\n**Q:** Although the paper is well-written, the text could be made more accessible. For instance, abbreviations such as POMDP and Tru-POMDP are not being defined when they are first mentioned. Other technical terms could also be made more clear in the introduction...\n\n**A:** Thank you for this valuable feedback. We agree that improving accessibility is crucial. We will revise the introduction in the final version to define all abbreviations and technical terms clearly. To clarify for this rebuttal, here are our definitions for the central concepts:\n* **Planning under uncertainty:** In the real world, robots face numerous uncertainties: perception is imperfect and incomplete (e.g., occlusions), human intentions are unobservable, and actions can have stochastic effects (e.g., execution failures). To achieve safety and efficiency, robots must plan in a way that hedges against these uncertainties.\n* **POMDP (Partially Observable Markov Decision Process):** This is a principled mathematical framework for planning under the uncertainties mentioned above. A POMDP model requires a full specification of all possible states, actions, and observations, which limits its use to \"closed-domain\" problems.\n* **Open-ended Uncertainty:** This refers to planning problems where one or more fundamental factors of the POMDP model, e.g., state, action, or observation space, cannot be fully predefined, possibly induced by an unknown set of possible objects, an unknown set of potential goals, or even an unknown set of available skills.\n* **Open-ended POMDP:** Our work introduces this concept, where we integrate the commonsense reasoning of LLMs with the rigorous planning of POMDPs. This allows us to address open-ended problems by dynamically constructing states, actions, and observations from LLM-generated hypotheses.\n\n***\n\n**Q:** Does the Bayesian filter in this paper involve an actual Bayesian update process, or does it primarily rely on the LLM to combine prior information with new observations?\n\n**A:** Our framework uses an actual **Bayesian update process**. The Hybrid Belief Update module (see Section 4.2) executes a principled particle filter update in every planning cycle. This filter refines the existing belief by eliminating particles inconsistent with the latest observation, ensuring the belief remains grounded in reality. The LLM, via the Tree of Hypotheses, is invoked **only when necessary**—specifically, when \"particle depletion\" occurs (i.e., the total weight of consistent particles drops below a threshold), indicating that the current belief no longer explains the observations well. This hybrid mechanism significantly reduces the number of expensive LLM queries by 61% while ensuring stable and accurate belief tracking, which contributes to the superior planning performance shown in our ablation study (Figure 4).\n\n***\n\nWe thank you again for your insightful review and positive recommendation. We hope our responses have fully addressed your questions.\n\n### References\n[1] Curtis, A., Tang, H., Veloso, T., Ellis, K., Tenenbaum, J., Lozano-Pérez, T., & Kaelbling, L. P. (2025). LLM-Guided Probabilistic Program Induction for POMDP Model Estimation. arXiv preprint arXiv:2505.02216."}, {"review_id": "vXiovNOXr9", "reviewer": "Reviewer_xjTo", "summary": "The paper introduces Tru-POMDP, a novel approach designed to extend POMDP planners to more open-ended and uncertain scenarios. Specifically, the method uses LLMs to construct a structured hierarchical Tree of Hypotheses (TOH), forming an initial belief distribution and generating rollout policies. Tru-POMDP integrates this with a modified DESPOT algorithm, featuring a dynamically updated action space derived from current beliefs. Bayesian belief updates manage the belief distributions, supplemented by LLM queries to replenish particle sets when necessary. Experiments conducted on kitchen rearrangement tasks demonstrate Tru-POMDP’s performance against baseline methods, particularly highlighting robustness and efficiency in scenarios involving ambiguity and partial observability.", "questions": "1. Could the authors clarify their considerations or measures for handling the potential combinatorial explosion in the hypothesis space as the complexity of target objects and placement goals increases?\n2. When generating hypotheses for current object placements, is independence between hypotheses assumed and/or required? If so, are there anticipated challenges associated with managing the significantly increased parameters of conditional distributions?\n3. Regarding particle replenishment via the LLM, are these particles newly generated from the existing Tree of Hypotheses, or is a completely new tree constructed? \n4. Can the authors provide more explicit details on how often the LLM-generated rollout policy is updated during action selection? Is it generated once per action or less frequently? Is there refinement of the policy or any issues with the policy/code being valid?\n5. Does the reported token count in the experiments include the tokens necessary for generating the LLM rollout policy?", "limitations": "Yes", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths:\nThe primary strengths of the paper include an innovative integration of LLMs with rigorous POMDP planning frameworks, effectively combining common-sense reasoning and probabilistic planning. The authors clearly contextualize their contributions within existing literature, emphasizing both novelty and practical applicability. I also appreciated the thoughtful use of belief-based action space restriction, significantly enhancing planning efficiency. The provided ablation studies offer a thorough analysis of each component's impact, clearly detailing improvements in terms of performance metrics, including computational efficiency.\n\nWeaknesses:\nThe paper exhibits several areas requiring clarification or enhancement. Primarily, the LLM-generated rollout policy, which is a crucial element for online tree-based algorithms, receives insufficient attention regarding its precise formulation and implementation details. Additionally, the experimental evaluation lacks a clear upper bound or optimal baseline, which would enable readers to better contextualize the performance results. Another weakness is a discussion of scalability is somewhat neglected; particularly, the practical limitations associated with generating hypotheses via LLMs as the complexity of the scenario increases and how to generate reasonable beliefs from parties as this hypothesis space grows.\n\nQuality: Technically sound with well-supported claims, though more detail on rollout policies and scalability would improve completeness.\nClarity: Clearly written and organized, but additional clarification on the rollout policy would enhance reproducibility.\nSignificance: Integrates LLM and POMDP planning effectively, addressing challenging uncertainty issues and likely impacting future research.\nOriginality: Novel combination and use of existing methods (LLMs and POMDP) differentiated it from prior work.", "was_revised": true, "final_justification": "The paper presents a novel and well-executed integration of LLM-based structured reasoning with principled belief-space POMDP planning, addressing open-ended uncertainty in a way that is both sound and relevant. While the evaluation is limited to kitchen rearrangement tasks and adapting to new domains will require some engineering, the conceptual contributions are strong enough to merit acceptance. The authors have addressed all of my questions in the rebuttal, adding valuable details on rollout policy design, providing an upper-bound baseline, and assessing the independence assumption. I recommend acceptance, with tempered generality claims in the final version.", "rebuttal": "Thank you for your very supportive and thorough review. We are delighted that you found our integration of LLMs with POMDPs to be innovative, significant, and original. We appreciate your insightful questions, which give us the opportunity to provide more detail on the rollout policy, present new results with an upper-bound baseline, and clarify our approach to scalability.\n\n***\n\n### **Responses to Weaknesses**\n\n**Q:** The LLM-generated rollout policy, which is a crucial element for online tree-based algorithms, receives insufficient attention regarding its precise formulation and implementation details.\n\n**A:** Thank you for pointing this out. We are happy to provide more detail.\n* **Formulation:** The rollout policy is a mapping from the current state $s = (G_s, p_s)$ to an action $a$. Here, $G_s$ is the scene graph representing the hypothesized world state, and $p_s$ is the placement goal. This mapping is implemented as a C++ function generated by an LLM. The generator LLM receives a general language description of the object rearrangement domain but is given no information about any specific task instance.\n* **Implementation:** The prompt used to generate this C++ policy code conveys four key aspects of knowledge to the LLM: (1) the objective (e.g., find and rearrange objects to reach the goal), (2) action constraints and semantics, (3) required input/output formats for the function, and (4) the API for accessing the state from within the policy code. The full prompt is provided in Appendix A.2. We will incorporate these details into Section 4.3 in the final version to improve reproducibility.\n\n***\n\n**Q:** The experimental evaluation lacks a clear upper bound or optimal baseline, which would enable readers to better contextualize the performance results.\n\n**A:** This is an excellent suggestion. We have run a new experiment with an omniscient agent that serves as an oracle upper bound. This agent has full knowledge of the true world state (all hidden objects and the true goal) and plans optimally using MCTS. The results are shown below, integrated with the original results from Figure 2.\n\n**Table 1: Cumulative Reward Comparison**\n| Method | Easy | Medium | Hard |\n| :--- | :---: | :---: | :---: |\n| Oracle (Upper Bound) | 958.3 ± 1.6 | 937.5 ± 2.2 | 906.5 ± 3.5 |\n| **Tru-POMDP (Ours)** | **737.9 ± 33.8** | **547.9 ± 47.3** | **381.6 ± 52.9** |\n| LLM-MCTS | -53.6 ± 2.0 | -48.1 ± 1.7 | -46.0 ± 1.6 |\n| Reflexion | 126.0 ± 64.5 | -295.8 ± 49.8 | -425.2 ± 49.6 |\n| ReAct | 26.1 ± 65.6 | -472.2 ± 36.6 | -578.1 ± 35.9 |\n\n**Table 2: Total Step Number Comparison**\n| Method | Easy | Medium | Hard |\n| :--- | :---: | :---: | :---: |\n| Oracle (Upper Bound) | 4.9 ± 0.2 | 7.3 ± 0.2 | 10.6 ± 0.3 |\n| **Tru-POMDP (Ours)** | **13.2 ± 0.6** | **19.4 ± 0.7** | **25.7 ± 0.8** |\n| LLM-MCTS | 25.0 ± 0.0 | 30.0 ± 0.0 | 35.0 ± 0.0 |\n| Reflexion | 18.9 ± 0.8 | 27.6 ± 0.6 | 32.7 ± 0.6 |\n| ReAct | 19.1 ± 0.9 | 28.8 ± 0.5 | 33.8 ± 0.5 |\n\nThe significant performance gap between the oracle and Tru-POMDP highlights the cost of uncertainty. The oracle, knowing the precise world state, never needs to explore or reason about hypotheses, thus taking far fewer steps and always succeeding. Tru-POMDP's ability to close a substantial portion of this gap demonstrates its effectiveness in managing and resolving uncertainty.\n\n***\n\n**Q:** A discussion of scalability is somewhat neglected; particularly, the practical limitations associated with generating hypotheses via LLMs as the complexity of the scenario increases and how to generate reasonable beliefs... as this hypothesis space grows.\n\n**A:** We appreciate this important point. Our primary strategy for tackling scalability is through **factorization**. The Tree of Hypotheses (TOH) explicitly encodes a factored belief over the state space, decomposing it into (1) target objects, (2) goal placements, and (3) current placements, with dependencies between them. The benefit of this design is empirically validated in our ablation study (Figure 4), where the \"w/o TOH\" variant, which generates an unfactored belief, is highly ineffective, leading to a performance drop of 26%. As long as a problem's state space can be decomposed into smaller factors, our approach remains effective.\n\n***\n\n### **Responses to Questions**\n\n**Q:** Could the authors clarify their considerations or measures for handling the potential combinatorial explosion in the hypothesis space as the complexity of target objects and placement goals increases?\n\n**A:** We manage this combinatorial growth through a multi-faceted approach. Let $C_1$ be the constant number of hypothesized target object sets, $C_2$ be the constant number of location hypotheses per object, and $N$ be the number of objects per set.\n1.  **Linear Growth in LLM Calls:** By assuming conditional independence of object locations (see next point), the number of LLM calls scales linearly with the number of hidden objects ($1 + C_1 \\times N$), not exponentially.\n2.  **Bounded Particle Set:** While the number of possible hypothesis combinations (particles) grows exponentially ($C_1 \\times C_2^N$), we resample the belief down to a constant number of particles ($k=30$ in our experiments) before feeding it to the POMDP planner. This keeps the online planning cost manageable. For even larger problems, our framework could be integrated with highly parallelized POMDP solvers that support thousands of particles online [1].\n3.  **Hierarchical Decomposition:** For tasks with a very large number of target objects, a hierarchical approach could be used, where the task is first decomposed into subtasks with a manageable number of objects, and Tru-POMDP is then applied to each subtask.\n\n***\n\n**Q:** When generating hypotheses for current object placements, is independence between hypotheses assumed and/or required? If so, are there anticipated challenges associated with managing the significantly increased parameters of conditional distributions?\n\n**A:** Yes, in our proposed method we assume the initial locations of different hidden objects are conditionally independent to reduce the number of required LLM calls. We ran a new ablation study to test the impact of this assumption. In the \"w/o independence\" variant, we query the LLM to generate a joint placement hypothesis for the entire set of target objects. The results show that our original approach (with the independence assumption) performs significantly better across all metrics.\n\n**Table 3: Ablation on Independence Assumption (Hard Difficulty)**\n| Method | Cumulative Reward | Success Rate (%) | Total Planning Time |\n| :--- | :---: | :---: | :---: |\n| **Tru-POMDP (with independence)** | **381.6 ± 52.9** | **71 ± 5** | **321.3 ± 19.7** |\n| w/o independence | 39.9 ± 49.9 | 36 ± 5 | 493.1 ± 16.5 |\n\nThis suggests that prompting for independent locations reduces the cognitive load of LLMs and allows it to generate a more diverse sets of hypotheses, which outweighs the benefit of capturing potential correlations. The variant without independence also required significantly more planning time, due to more serialized LLM queries.\n\n***\n\n**Q:** Regarding particle replenishment via the LLM, are these particles newly generated from the existing Tree of Hypotheses, or is a completely new tree constructed?\n\n**A:** A completely **new** Tree of Hypotheses is constructed. This is necessary because new hypotheses must be conditioned on the most up-to-date observations. Any particles generated by the old TOH that remain consistent with all historical observations are already preserved in the belief via the Bayesian filter, so their information is fully leveraged.\n\n***\n\n**Q:** Can the authors provide more explicit details on how often the LLM-generated rollout policy is updated during action selection? Is it generated once per action or less frequently? Is there refinement of the policy or any issues with the policy/code being valid?\n\n**A:** The LLM-generated rollout policy is generated only **once** for the entire object-rearrangement domain in an offline stage. It is task-agnostic and scene-agnostic and is reused across all experiments without any updates or refinement. The generated C++ code was valid and required no manual correction. \n\n***\n\n**Q:** Does the reported token count in the experiments include the tokens necessary for generating the LLM rollout policy?\n\n**A:** No, the reported token counts reflect the online planning costs only. The rollout policy generation is a one-time, offline cost for the entire domain, that is negligible in comparison. For completeness, this offline pass consumed only 1,353 tokens.\n\n***\n\nThank you again for your careful reading and strong support of our paper. We hope our answers and new results have satisfactorily addressed your questions.\n\n### References\n[1] P. Cai, Y. Luo, D. Hsu, et al. HyP-DESPOT: A hybrid parallel algorithm for online planning under uncertainty. *The International Journal of Robotics Research*, 40(2-3), 558-573, 2021."}, {"review_id": "V2PHI10qgw", "reviewer": "Reviewer_qLq6", "summary": "The paper proposes to do task planning in the open world by combining LLM for world modelling with a POMDP planner. A Tree-of-Hypothesis method is introduced to query LLMs in order to generate particle beliefs over world states and human goals. Experiments on object rearrangement in kitchen environments show better performance compared to LLM prompting methods.", "questions": "The paper mentions that LLM-MCTS uses a single maximum likelihood hypothesis for task goal and hidden object placements (line 293-294). This is true for task goal, but LLM-MCTS uses a distribution for object placements, although the set of objects are known in advance. The authors should more carefully explain how this work makes progress beyond what LLM-MCTS does.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- Extends robot planning to the open world while handling uncertainty in a principled manner. Before the success of LLMs, methods based on POMDP solvers operate on the closed world assumption where the domain is limited in order to make construction of the POMDP models feasible. LLM-MCTS initiated the combination of LLMs and POMDP solvers by using LLMs as world model and search heuristic but still operates in the closed world where where objects and areas are known. This paper proposes a method for generating open world beliefs that do not require these to be known through its Tree of Hypothesis method, making progress on the important problem of operating in the open world.\n- The proposed method outperforms LLM methods that are not based on POMDP solvers, namely ReAct and Reflexion.\n- The method is relatively clean and simple, hence others are likely able to build on it.\n\nWeaknesses:\n- Novelty is not particularly high. LLMs are trained on very large amounts of data, hence it is not surprising that they are able to generate reasonable distribution of open world objects.", "was_revised": true, "final_justification": "In rebuttal discussion, the authors provided analysis of errors made by the methods and identified cognitive shift as a source of errors that is not handled by current methods. I think this is useful and adds novelty to their paper. As a result, I have increased my rating.", "rebuttal": "Thank you for your valuable feedback and for recognizing our work's key strengths, particularly in extending principled POMDP planning to the open world. We appreciate your assessment that the method is clean, simple, and likely to be built upon by others. We are grateful for the opportunity to address your comments on novelty and to clarify the specific advancements our work makes over LLM-MCTS.\n\n***\n\n**Q:** Novelty is not particularly high. LLMs are trained on very large amounts of data, hence it is not surprising that they are able to generate reasonable distribution of open world objects.\n\n**A:** We respectfully argue that while using an LLM to generate hypotheses may seem intuitive in retrospect, making this concept work for principled planning is a significant and novel contribution. We ask the reviewer to consider the novelty from two perspectives:\n\n**From the LLM Perspective:**\nOur work addresses fundamental limitations of LLMs for probabilistic planning tasks.\n* First, LLMs have limited probabilistic reasoning capabilities on their own, often leading to suboptimal policies when faced with uncertainty, as shown by the performance of strong LLM-based baselines in our experiments (see Figure 2).\n* Second, naively asking an LLM to generate a flat distribution of open-ended world states is ineffective for complex planning. Our ablation study (\"w/o TOH\" in Figure 4) demonstrates that without the structured, factored approach of our novel **Tree of Hypotheses (TOH)**, the generated belief is of poor quality and leads to low performance (dropping 26% success).\n* Third, our **Hybrid Belief Update** module is the first to seamlessly integrate principled Bayesian filtering with on-demand LLM inference, allowing both to function simultaneously to maintain a robust and efficient belief.\n\n**From the POMDP Planning Perspective:**\nOur work expands the entire scope of what POMDPs can solve.\n* Traditionally, POMDP planning has been confined to **closed-world problems**, where the state, action, and observation spaces are fully predefined.\n* We introduce and solve the open-ended POMDP problem, where core elements are not predefined due to unknown objects and ambiguous human intentions. Our open-ended belief tracker and POMDP planner are the first to address this formulation, dynamically constructing the state, action, and observation spaces from LLM hypotheses. This framework could potentially be extended to handle unknown actions or action consequences in the future.\n* We developed a novel open-ended planner with two key contributions:     \n\n    * A **dynamically constructed action space:** A naive action space would be intractably large or infinite due to the unbounded set of possible objects. Our planner dynamically grounds a compact, relevant set of actions based on the current particle belief. This is essential for making online planning tractable in an open-ended world.     \n\n    * An **LLM-generated rollout policy integrated into tree search:** Unlike prior work using random rollouts or expensive LLM rollouts, we leverage an LLM to generate a coded heuristic policy that provides strong, commonsense guidance from the leaf nodes of the belief tree search. This novel integration of a code-based LLM policy within a principled planner significantly improves performance (by 22%), as shown in our ablation study (Figure 4, \"w/o LRP\"). \n***\n\n**Q:** The paper mentions that LLM-MCTS uses a single maximum likelihood hypothesis for task goal and hidden object placements (line 293-294). This is true for task goal, but LLM-MCTS uses a distribution for object placements, although the set of objects are known in advance. The authors should more carefully explain how this work makes progress beyond what LLM-MCTS does.\n\n**A:** Thank you for this important correction. You are right that LLM-MCTS uses a distribution for initial object placements. We will correct this in the final manuscript. Tru-POMDP makes several fundamental advances beyond LLM-MCTS, enabling planning in truly open-ended scenarios:\n\n* **Open-Ended vs. Closed-Domain Planning:** This is the most critical distinction. LLM-MCTS operates in a **closed domain** where the set of all possible objects is known in advance. In contrast, Tru-POMDP is designed for **open-ended** environments where the robot must reason about entirely unknown objects and ambiguous human goals. Our framework dynamically constructs its state, observation, and action spaces from LLM-generated hypotheses, a significant step towards real-world open-ended planning.\n\n* **Factored Multi-Aspect Belief vs. Flat Single-Aspect Belief:** Tru-POMDP explicitly models multiple, interacting sources of uncertainty (ambiguous goals, unknown target objects, and hidden placements) using the structured Tree of Hypotheses. This factored approach is key to generating high-quality beliefs scalably. LLM-MCTS uses a \"flat\" belief that only considers a single aspect of uncertainty: the placement of *known* objects.\n\n* **Generalizable Belief Representation:** Our use of a particle-based belief is inherently more flexible and generalizable to other domains beyond object rearrangement compared to the object-receptacle probability vectors used in LLM-MCTS.\n\n* **Computational Efficiency and Weaker Priors:** The LLM-MCTS planner is computationally intensive, as it requires querying the LLM to provide a search heuristic at each node during tree expansion. As seen in our experiments, this becomes intractable for complex tasks. Tru-POMDP is far more efficient because it does not call the LLM inside the belief tree search. Instead, it uses a pre-compiled, LLM-generated rollout policy that requires only weak prior knowledge (a language description of the domain).\n\nWe will incorporate these points to more clearly position our work relative to LLM-MCTS in the final version. Thank you again for your constructive feedback and your support for our paper."}]

Author rebuttal:

Meta-review: This paper presents a novel and interesting approach to combining POMDP planning with LLMs for abstract planning. The formulation is well justified and the experimental results are promising, though they are currently demonstrated only in the setting of object rearrangement tasks. The work makes a valuable contribution by showing how symbolic reasoning and language-based hypothesis generation can be integrated into robot planning.

The main concerns raised during review centered on the generality of the approach. In particular, while the framework itself is domain-agnostic, adapting it to a new domain appears to require significant engineering effort, such as redesigning the semantic POMDP model and task-specific structures. The authors argued that LLMs and VLMs could automate much of this, but the AC did not find this to be a productive line of argumentation. Relying on future automation is a weaker justification than demonstrating generality directly. The reviewers generally agreed that the work stands on its novelty and promise, but that claims of generality should be tempered.

For the final version, it would be valuable to lessen the claims of generality and to consider a less general title.
Decision: Accept (poster)