{"id":"16aa3220-2e05-4c39-ac46-d12706d27fb2","arxiv_id":"2412.06162","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A language model that proposes full plans and revises them after feedback queries the world model fewer times than one used as a search heuristic, across Blocksworld, Logistics, Grippers, and Robotouille.","lead":"This paper compares two ways of using large language models for planning: asking the model to act as a search heuristic versus asking it to propose entire action sequences and then adjust them after feedback. On logic and robot cooking benchmarks, the whole-plan approach, called Boomerang, reached higher success rates while making fewer world model queries.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Boomerang's adaptivity advantage is confounded with its exclusive access to interaction history: ToI-BFS/DFS use a history-free state evaluator, so the \"LLM heuristic\" baseline cannot adapt to feedback by design.","rationale":"The reader's caching/cost-metric concern is legitimate but not the most load-bearing: under the paper's deterministic-world-model definition, caching a queried transition is a valid implementation choice, and the central claim is about interactions, not directly about wall-clock time. The sharper issue is that the LLM-heuristic baseline is deliberately memoryless while the generative baseline is not; the paper's own Appendix A.7 admits that ToI's lack of history is a cause of its failures. Since the authors do not test a history-augmented heuristic, the abstract's key finding about rapid adaptation is not established by the reported experiments. This does not overturn the results, but it should be a stated condition: the authors should add a history-augmented ToI baseline before generalizing the adaptivity claim. The existing CONDITIONAL verdict already captures this need for correction, so no verdict change is required.","tokens_in":22183,"tokens_out":8954,"duration_ms":92762,"concrete_test":"Re-run ToI-BFS and ToI-DFS on the same 600 Blocksworld and 100-each Logistics/Grippers/Robotouille instances with one modification: maintain a global transcript of every queried (s,a,s′) and error message and include it in the prompts for both action proposal and state evaluation, keeping k, b, T, the 20-query budget, gpt-4-turbo, and temperature fixed. Compare success rates and mean WMQs to Boomerang. If ToI-History reaches or exceeds Boomerang's 78/82/89/57% successes, the adaptivity claim is unsupported; if Boomerang still dominates by the same margin, the claim survives.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that an LLM generative planner \"can more rapidly adapt its planning strategies based on immediate feedback than LLM as a heuristic.\" As implemented, the comparison makes this nearly true by construction. ToI-BFS (Alg. 1) and ToI-DFS (Alg. 3) use an LLM state evaluator Vθ(s,ϕ) that receives only the current state and problem context; the action proposer is likewise given no prior trajectory or error feedback. Boomerang (Alg. 2) explicitly maintains Ht = Ht−1 ∪ (ξ,error) and conditions each new plan on the entire history of world-model feedback. The paper's own Appendix A.7 attributes ToI failures to \"the lack of history in Tree of Interaction (ToI).\" A heuristic search framework is not inherently memoryless: one can append the transcript of queried (s,a,s′) triples and error messages to the LLM prompts while keeping the same beam-search/DFS outer loop. Because that condition was never tested, the headline adaptivity result conflates the planning paradigm (generative vs heuristic) with memory access (full transcript vs none). If a history-augmented ToI closes the gap, the \"fewer interactions\" conclusion is an artifact of an asymmetric baseline, not a property of generative planning.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes two ways of using LLMs for planning under a limited budget of world-model queries: Tree of Interaction (ToI), where an LLM acts as an action proposer and state evaluator inside BFS/DFS search, and Boomerang, where an LLM generates complete action sequences and replans from world-model feedback. Experiments on 600 PlanBench Blocksworld problems and 100-problem Logistics, Grippers, and Robotouille suites report that Boomerang attains the highest success rates under a 20-query cap, with 78% on Blocksworld, and that ReAct and ToI variants are less successful. The paper also presents ablations on prompting variants and Reflexion, plus an appendix connecting Boomerang to lazy search and posterior sampling.","tokens_in":22430,"tokens_out":7239,"duration_ms":64651,"significance":"The main empirical result, if it survives a controlled comparison, would be practically relevant: Boomerang is simple, cheap in LLM calls, and substantially better than the tested baselines on several domains, and the per-domain tables and released code are useful assets. The weakness is that the central claim about adaptivity is currently confounded with history access, and the numeric inconsistency in the Blocksworld result makes the headline hard to trust as stated. The theoretical appendix does not provide an independent guarantee for Boomerang. With a history-augmented ToI baseline and corrected reporting, the paper could make a solid contribution; in its present form the significance of the adaptivity finding is uncertain.","major_comments":[{"comment":"The comparison conflates the planning paradigm with access to interaction history. ToI-BFS (Alg. 1) and ToI-DFS (Alg. 3) call the action proposer πθ(s,ϕ,k) and state evaluator Vθ(s,ϕ) on the current state only, whereas Boomerang (Alg. 2) maintains Ht and conditions each new plan on the full history of world-model feedback. Appendix A.7 itself states that ToI makes minimal progress because 'the lack of history in Tree of Interaction (ToI)' discards information. Since a heuristic search framework is not inherently memoryless—one can append the transcript of queried transitions and error messages to the LLM prompts while keeping the same beam/DFS outer loop—the abstract's claim that 'the LLM as a planner can more rapidly adapt its planning strategies based on immediate feedback than LLM as a heuristic' is not established by the current experiments. Please add a history-augmented ToI baseline or restrict the conclusion to the implemented memory-free heuristic.","section":"§3.1–3.2, Alg. 1–3, Appendix A.7"},{"comment":"There is an unexplained discrepancy in the flagship Blocksworld success rate. The main text reports 0.78 for Boomerang on the 600 PlanBench problems (Fig. 2 and §4.2.1), while Table 3 in Appendix A.10 reports 0.85±0.015 for Boomerang on Blocksworld with average WMQ 10.67. If Table 3 uses a different query budget, seed, or subset, this must be stated; otherwise the headline number is internally inconsistent.","section":"§4.2.1–4.2.2 vs. Table 3"},{"comment":"Theorem 1 is not a bound for Boomerang as implemented. The proof 'follows from Osband et al. (2013)' applies to posterior sampling in reinforcement learning, but §3.2 only conjectures that Boomerang's plan generation approximates posterior sampling from Pθ(M⋆|ϕ,Ht). Without stating that approximation as an explicit assumption (or providing evidence for it), the theorem overclaims a formal guarantee. Please either state the posterior-sampling property as an unproved assumption and label the result conditional, or remove the theorem and treat the connection as intuition.","section":"Appendix A.2, Theorem 1"},{"comment":"The query-cost metric assumes free reuse of previously verified transitions. Boomerang re-uses previous queries during verification, so reported WMQ counts unique transitions rather than actual world-model invocations. If the motivating setting is an expensive, non-cacheable world model, the advantage may shrink or reverse. The statement in §4.1 that query efficiency 'directly correlates with time spent in such environments' is not demonstrated. Please report an experiment with an expensive or non-cacheable oracle, or clearly qualify the claim to the cached-query setting.","section":"§3.2 and §4.1"}],"minor_comments":[{"comment":"The sentence 'Classical uses best-first-search which implies its heuristic does not underestimate the true cost, guaranteeing it finds an optimal path' is incorrect: best-first search does not guarantee optimality, and A* with an admissible heuristic is the usual optimal variant. Given Table 3's configuration, the optimality claim should be corrected.","section":"§4.2.2"},{"comment":"The cross-reference 'see Appendix 3' does not correspond to any appendix section; it should refer to Appendix A.10.","section":"§4.2.2"},{"comment":"The abstract's phrase 'significantly fewer interactions' is not accompanied by statistical tests or confidence intervals for the main 0.78 vs. 0.52/0.63 comparisons; adding error bars or significance tests would strengthen the claim.","section":"§4.2.2 and Table 1"}],"recommendation":"major_revision","confidential_remarks":"The central adaptivity claim is the main point that needs to be clean before publication; the history-augmented ToI experiment is the key missing control. I would also verify the 78% vs. 85% discrepancy and correct the optimality claim about best-first search. If the authors can address these points, the paper would be a reasonable candidate for the journal."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is worth reading if you work on LLM planning with expensive world models. It gives a clean empirical comparison of two paradigms: LLM-as-heuristic (ToI-BFS/DFS) versus LLM-as-generative-planner (Boomerang), under a fixed world-model query budget. The four-domain evaluation, the ablations, and the released code make this a solid contribution to a subfield where comparisons are often ad hoc. I genuinely think the core finding—that generating whole plans and replanning from feedback can be more query-efficient than heuristic-guided search—is plausible and worth testing further.\n\nBut the headline claim has a load-bearing confound that the paper itself half-admits. ToI-BFS and ToI-DFS use a state evaluator and action proposer that receive only the current state and problem context; they do not see the transcript of previous queries or errors. Boomerang explicitly conditions on the full history of world-model feedback. Appendix A.7 attributes ToI's failures to \"the lack of history in Tree of Interaction.\" The paper then concludes that generative planners adapt more rapidly to feedback. That conclusion is nearly built into the setup. A history-augmented ToI—same beam-search/DFS loop, but with the query transcript appended to the prompts—is the missing control. Without it, the advantage could be memory access, not the planning paradigm. This is the main thing I'd want fixed before taking the headline at face value.\n\nOther soft spots are smaller but real. The Blocksworld success rate for Boomerang appears as 0.78 in the main text and 0.85 in Appendix Table 3; no explanation is given. The claim that best-first search with landmark-cut \"guarantees\" an optimal path is simply incorrect as stated. The regret bound in Theorem 1 follows from Osband et al. only through a mapping that the paper labels a conjecture, so the theory section is suggestive, not load-bearing. And the cost model assumes world-model queries are the bottleneck and that re-querying cached transitions is free; that is an assumption, not a demonstrated result.\n\nTo be clear, none of this sinks the paper. The empirical comparison is new, the methods are described precisely enough to reimplement, and the authors are honest about several limitations. For someone building LLM planners against a costly simulator, this is a useful data point—if they treat the central comparison as provisional until the history confound is resolved.\n\nMy recommendation: send it to peer review. The question is important, the code is there, and a revision that adds the history-augmented ToI control would turn a suggestive result into a genuine one.","headline":"A useful empirical comparison with a real confound: Boomerang gets full interaction history while ToI does not, so the headline adaptivity claim is only as strong as that asymmetry.","tokens_in":23006,"tokens_out":1941,"would_cite":true,"duration_ms":20140,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Generative LLM planners that propose full plans and replan from world-model feedback beat LLM-guided heuristic search, reaching 78-89% success under a 20-query budget.","keywords":["query-efficient planning","large language models","generative planning","LLM as heuristic","world-model queries","lazy search","replanning with feedback","PlanBench"],"falsifier":"Re-run the same planners on a domain where each world-model query is genuinely expensive, for example collision-checking a robot arm or running a local motion optimizer, charge the budget for every transition accessed from cache, and compare wall-clock time or paid queries instead of unique transition counts; if Boomerang's margin over Classical and ToI shrinks or reverses under that accounting, the query-efficiency claim rests on the free-cache assumption rather than on generative adaptivity.","tokens_in":21943,"feed_emoji":"🎯","tokens_out":18728,"duration_ms":144617,"temperature":0.7,"pith_summary":"When a planner's dominant cost is checking transitions against a world model, the paper claims, how the LLM is attached matters more than raw LLM reasoning power. It proposes two competing designs: Tree of Interaction, which uses the LLM as a heuristic that proposes actions and ranks states inside a BFS/DFS search, and Boomerang, which uses the LLM as a generative planner that emits a full start-to-goal action sequence, verifies it against the world model, and replans from the error feedback. The paper's central finding is that the generative design is more query-efficient: it reaches 78% success on 600 Blocksworld problems, 82% on Logistics, 89% on Grippers, and 57% on Robotouille within a 20-query budget, versus 63% for the best classical planner and 37% for the best LLM-heuristic variant on Blocksworld. The explanation offered is adaptivity: a generative planner resets to the start and can route around a dead end in its next whole plan, while a heuristic can only pick among nodes the search tree happens to offer. The result matters because in robotics and task-and-motion planning, world-model queries are often the expensive step, so a planner that reaches the goal in fewer queries could translate directly into faster real-time planning.","feed_headline":"78% success: whole-plan LLM replanning beats LLM-guided search","feed_subtitle":"When world-model queries are the bottleneck, generating whole plans and replanning on feedback wins under a 20-query budget.","key_machinery":"The central mechanism is the Boomerang loop: generate a complete action sequence with the LLM, verify it by querying the world model on every transition, feed back the partial trajectory and error, then regenerate, with all previously verified transitions cached so each iteration costs only the newly revealed states. This is the paper's instantiation of lazy search, where the planner reasons over a cheap internal model and only pays for edges on promising paths; the paper formalizes the LLM as a posterior sampler over world models $P_\\theta(M^\\star \\mid \\phi, H_t)$ and adapts a Bayesian regret bound of $O(\\tau\\sqrt{SAT\\log(SAT)})$ on the infeasible edges queried before a feasible path is found. The contrasting object is ToI, which embeds the LLM as an action proposer and a three-class state evaluator inside beam search or DFS, so the LLM's influence is filtered through the search tree and its state rankings, which the paper notes are inadmissible and inconsistent because states are ranked independently and history is discarded each iteration.","core_discovery":"The paper's central claim, stated in its abstract, is that using an LLM as a generative planner results in significantly fewer world-model interactions than using an LLM as a heuristic, and that the generative planner can more rapidly adapt its planning strategies based on immediate feedback. Boomerang operationalizes this by prompting the LLM to produce an entire plan from the initial state to the goal, rolling that plan out through a deterministic world model, and appending the verified prefix plus the error message to the LLM's context before generating the next plan; ToI instead confines the LLM to proposing actions and rating states as impossible/maybe/sure within a beam or depth-first search. Under a 20-world-model-query budget on 600 PlanBench Blocksworld problems and 100 problems each in Logistics, Grippers, and Robotouille, Boomerang solves them at rates of 78%, 82%, 89%, and 57%, respectively, while the strongest classical planner configuration reaches 63% on Blocksworld and 5-13% on the other PDDL domains, and the best ToI variant reaches 37% on Blocksworld. The paper also reports that Boomerang uses fewer LLM calls (5.69 per problem versus 13.69 for ReAct and 28-40 for the ToI variants) and achieves an optimality rate of 0.69, second only to the optimality-guaranteed classical planner at 0.63. The authors connect this performance to lazy search and posterior sampling, adapting a Bayesian regret bound of $O(\\tau\\sqrt{SAT\\log(SAT)})$ on the number of infeasible transitions queried before a feasible plan is found.","pith_inferences":["If the adaptivity story is right, then compressing the LLM's history, replacing raw trajectory dumps with a distilled summary of what failed and why, should extend Boomerang's advantage to long-horizon problems, where the paper's own limitations section concedes it begins reproposing failed sequences through context forgetting.","The free-cache accounting is testable: a deployment that charges for every world-model access, including re-verifying a cached transition, or one whose bottleneck is LLM API latency rather than world-model queries, could erase or reverse Boomerang's margin, since the paper asserts rather than measures the claimed correlation between query count and wall-clock time.","A natural hybrid suggested by the comparison is to seed a classical beam search with Boomerang's generated plans, giving the tree-based framework the cul-de-sac escape it currently lacks while preserving search structure; the paper does not explore this direction.","Re-running the comparison under a budget of plan length or total LLM tokens rather than verified transitions would separate the value of whole-plan generation from the value of start-state resets, which the paper treats as a single design."],"forward_implications":["In planning domains where world-model queries dominate cost, the generative-planner interface should be the default: Boomerang needs only 5.69 LLM calls per Blocksworld problem versus 13.69 for ReAct and 28-40 for ToI variants, and it reaches the goal in fewer queries on average (12.15) than both ReAct (13.06) and the best classical planner (14.67).","The gap should grow with a domain's branching factor: the paper's lazy-search analysis shows that even a perfect heuristic run as A* pays $k$ times more edge queries than a lazy planner over the optimal path, which is consistent with Grippers, the domain with the largest action space, showing Boomerang's widest margin (89% versus 31% for ToI-DFS and 13% for Classical).","The adaptivity explanation predicts that any method that resets to the start but still acts one step at a time will underperform whole-plan regeneration, which is exactly the appendix finding that Reflexion outperforms ReAct but not Boomerang.","Success within a fixed query budget and solution optimality are partly independent: the I/O + CoT + P ablation, which repeats the goal after every step, beats ReAct by 14.8% without any interaction loop, showing that prompt design and interaction design are separate levers."],"supporting_citations":[{"why":"Supplies ReAct, the action-at-a-time interactive baseline whose cul-de-sac failures Boomerang is designed to overcome and against which query efficiency is measured.","marker":"Yao et al., 2022"},{"why":"Tree of Thoughts, the LLM-guided search approach that Tree of Interaction extends into an interactive world-model loop.","marker":"Yao et al., 2024"},{"why":"Supplies the lazy-best-first-search formalism and the argument that lazy search is strictly more query-efficient than A*, the theoretical basis for Boomerang's design.","marker":"Dellin & Srinivasa, 2016b"},{"why":"Source of the posterior-sampling framework for querying expensive edges that the paper maps onto Boomerang's replan loop.","marker":"Hou et al., 2020"},{"why":"Provides the PSRL Bayesian regret bound that Theorem 1 adapts to bound Boomerang's expected infeasible queries.","marker":"Osband et al., 2013"},{"why":"PlanBench, the 600-problem Blocksworld benchmark on which the main comparison is run.","marker":"Valmeekam et al., 2024"},{"why":"PDDLGym, used as the world-model oracle for the PDDL environments.","marker":"Silver & Chitnis, 2020"},{"why":"Fast Downward, the classical planner whose best heuristic-search configuration forms the Classical baseline.","marker":"Helmert, 2006"},{"why":"Robotouille, the robot cooking simulator that serves as the non-PDDL world-model benchmark.","marker":"Wang et al., 2023"}],"fun_headline_variants":["Whole-plan LLM replanning beats LLM-guided search in query efficiency","LLM as generative planner: fewer world queries, higher success","78% on Blocksworld: whole-plan replanning trumps LLM heuristic search","Plan-then-replan beats LLM-guided search under 20-query budget"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The comparison prices a world-model query as the scarce resource and lets Boomerang reuse every previously verified transition for free, so the finding holds only if re-checking a cached transition costs nothing and if world-model queries, not LLM API calls or other computation, are the true bottleneck; the paper asserts but does not demonstrate this on an actually expensive world model.","fun_headline_variants_meta":{"raw":{"variants":["Whole-plan LLM replanning beats LLM-guided search in query efficiency","LLM as generative planner: fewer world queries, higher success","78% on Blocksworld: whole-plan replanning trumps LLM heuristic search","Plan-then-replan beats LLM-guided search under 20-query budget"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000408,"raw_usage":{"total_tokens":2200,"prompt_tokens":1106,"completion_tokens":1094,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":722,"completion_tokens_details":{"reasoning_tokens":1011}},"tokens_in":722,"tokens_out":1094,"duration_ms":10566,"temperature":1.0,"reasoning_tokens":1011,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T19:57:35.945989+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Re-run the same planners on a domain where each world-model query is genuinely expensive, for example collision-checking a robot arm or running a local motion optimizer, charge the budget for every transition accessed from cache, and compare wall-clock time or paid queries instead of unique transition counts; if Boomerang's margin over Classical and ToI shrinks or reverses under that accounting, the query-efficiency claim rests on the free-cache assumption rather than on generative adaptivity.","supporting_citations":[{"cited_title":"Posterior sampling for anytime motion planning on graphs with expensive-to-evaluate edges","cited_arxiv_id":null,"evidence_quote":"Source of the posterior-sampling framework for querying expensive edges that the paper maps onto Boomerang's replan loop."},{"cited_title":"(more) efficient reinforcement learning via posterior sampling, 2013","cited_arxiv_id":null,"evidence_quote":"Provides the PSRL Bayesian regret bound that Theorem 1 adapts to bound Boomerang's expected infeasible queries."},{"cited_title":"Pddlgym: Gym environments from pddl problems","cited_arxiv_id":null,"evidence_quote":"PDDLGym, used as the world-model oracle for the PDDL environments."},{"cited_title":"Demo2code: From summarizing demonstrations to synthesizing code via extended chain-of-thought, 2023","cited_arxiv_id":null,"evidence_quote":"Robotouille, the robot cooking simulator that serves as the non-PDDL world-model benchmark."}],"review_version":1}