ReCAP: Recursive Context-Aware Reasoning and Planning for Large Language Model Agents
Authors: Zhenyu Zhang
Tianyi Chen
Weiran Xu
Alex Pentland
Jiaxin Pei
Venue: NeurIPS 2025 poster ()
Keywords: Large Language Model
Long-Horizon Reasoning
LLM Agent
LLM Reasoning
Primary area: deep_learning
TL;DR: We introduce ReCAP, a recursive context-aware framework that enables LLMs to perform long-horizon reasoning and planning through task decomposition, execution, and backtracking, significantly improving performance in complex, multi-step environments.

Abstract: Long-horizon tasks requiring multi-step reasoning and dynamic re-planning remain challenging for large language models (LLMs). Sequential prompting methods are prone to context drift, loss of goal information, and recurrent failure cycles, while hierarchical prompting methods often weaken cross-level continuity or incur substantial runtime overhead. We introduce ReCAP (Recursive Context-Aware Reasoning and Planning), a hierarchical framework with shared context for reasoning and planning in LLMs. ReCAP combines three key mechanisms: (i) plan-ahead decomposition, in which the model generates a full subtask list, executes the first item, and refines the remainder; (ii) structured re-injection of parent plans, maintaining consistent multi-level context during recursive return; and (iii) memory-efficient execution, bounding the active prompt so costs scale linearly with task depth. Together these mechanisms align high-level goals with low-level actions, reduce redundant prompting, and preserve coherent context updates across recursion. Experiments demonstrate that ReCAP substantially improves subgoal alignment and success rates on various long-horizon reasoning benchmarks, achieving a 32\% gain on synchronous Robotouille and a 29\% improvement on asynchronous Robotouille under the strict pass@1 protocol.

RECAP: Recursive Context-Aware Reasoning and Planning for Large Language Model Agents
Zhenyu Zhang!
Tianyi Chen'* Weiran Xu
Alex Pentland Jiaxin Pei
Department of Computer Science, Stanford University
Stanford Institute for Human-Centered AI MIT Media Lab
zhenyuz50stanford edu tchen288@stanfford edu weiran@stanford edu
sandyōmedia mit. edu pedropei @stanford. edu
Abstract
Long-horizon tasks requiring multi-step reasoning and dynamic re-planning remain challenging for large language models (LLMs). Sequential prompting methods are prone context drift, loss of goal information, and recurrent failure cycles, while hierarchical prompting methods often weaken cross-level continuity or incur substantial runtime overhead. We introduce ReCAP (Recursive Context-A Reasoning and Planning). hierarchical framework with shared context for reason- ing and planning in L.LMs. ReCAP combines three key mechanisms: (i) plan-ahead decomposition, in which the model generates full subtask list, executes the first item, and refines the remainder; (ii) structured re- injecciion of parent plans, maintain- ing consistent multi-level context during recursive return; and (iii) memory-efficient execution, bounding the active prompt so costs scale linearly with task depth. To- gether these mechanisms align high-level goals with low-level actions, reduce redundant prompting, and preserve coherent context updates across recursion. Ex- periments demonstrate that ReCAP substantially improves subgoal alignment and success rates on various long- moog-horizon reasoning benchmarks, achieving 32% gain synchronous Robotouille and 29% improvement asynchronous Robotouille under the strict pass @ protocol.
Introduction
fundamental characteristic of intelligence is the smooth transition between high-level abstract reasoning and low-level task execution- something humans routinely perform in everyday activi- ties [14]. Imagine organizing a multi-day trip: one first outlines a broad plan-such as identifying destinations, transport, and accommodations. before refining it into actionable subtasks like booking tickets or arranging local travel. Real-world task execution, however, rarely follows a fixed script: resource may be unavailable, an intermediate step may fail, schedules may conflict. Such situa- tions demand long- long-horizon reasoning that both preserves the global intent and maintains coherence between different levels of detail within the plan, while flexibly revising steps feedback unfolds. Current LLM-based methods face challenges here: sequential prompting exhibits context drift and repeated cycles when early plans leave the context window, while hierarchical prompting often lose continuity across levels or incur redundant memory usage. Addressing such scenarios demands context-aware long-horizon adaptive reasoning and planning, requiring an intelligent system that can commit to a plan while remaining flexible to feedback and maintain coherence across multiple levels of reasoning [24, 5].
"gqual contribution. Project lead
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Sequontial Reasoning (RaAct/Roflection/..)
high-level thought too for from the current posttion
Context:
Thine
Act
Thikk
Taak
Recuralve Reasoning (ADePT/THREAD/...
Output
don't know happered subtask exocution in contexts 2 and
LLM Context (Depth
bae
Copied Block
LLM Context 2
Obsenvation
(Depth
Context (Depth 3)
Aet
Obe
Sun
ddnn't know the high- level gosl
(a) Limitations of pure sequential/hicraachicall prompting. sequential prompting (e.g.. ReAct/Re- flexion), early high-level thoughts drift far in sequential history, leading to loss of goal information. In hierarchical prompting (e.g., ADaPT/THREAD), subtasks run in separate local contexts, fragmenting information across depths and leading recurrent failure cycles.
Pt V2
PLIMI
PLA12
Depth
Thene
(71:122 Nolmo the provic plac)
Suptedio
Finch suttisk refine the
Depth
Contant Injccion
P1.1
Thee
Depth
Actio printee,
euwodeel the
vubiion regara (rilred)
Copled Block
One Single LLM Context:
Slidng Contact Window
(b) ReCAP. At each depth, the agent generates or refines a subtask plan, executes primitive actions as they occur, and appends new observations. After resolving each subgoal, the parent's 's remaining plan is re- re-injected into a single sliding LLM context, keeping high-level intent proximal to the current decision point and preserving coherence across multiple levels of reasoning.
Figure I: sequential/hierrrcciicl prompting vs. RECAP
Recent reasoning frameworks enable LLMs to interleave reasoning with action, improving problem solving in multi-step settings. Sequential prompting methods such as Chain-of-Thought (CoT) [25], ReAct [5], and Reflexion [19] operate in largely linear fashion: the model produces step-by-step thoughts (and optionally actions/obserrations)) along single trajectory. These approaches are simple and effective on short horizons. but in long-horizon environments. early plans often drift out of the context window or become stale, leading to loss of goal information and recurrent failure cycles even with extended contexts [11,6 6, 2]. Ada-Planner [22] extends this paradigm by editing a single global linear plan through explicit closed-loop refinement, but it remains fundamentally linear and still susceptible to divergence from planned trajectory on long horizons. response, hierarchical prompting methods explicitly organize reasoning beyond single chain: Tree of Thoughts (ToT) explores branching and backtracking over thought trees [6]; Graph of Thoughts (GoT) generalize to non-linear dependencies [1]: THREAD recursively spawns subproblems but prompts each with isolated subgoal context [18]; ADaPT alternates planner-executor prompts to refine subgoals [16];
and REPL--Plan maintains an external program state and code-execurte loop to drive planning [10]. While these methods organize reasoning in hicrarchy, they can either (i) reduce continuity between levels of reasoning when subtasks are prompted in largely isolated contexts (c.g.. THREAD, where subgoal prompts carry only partial parent information), or (ii) introduce increased runtime overhead and strong dependence prior trajectories tool-specific states (e.g., REPL-Plan, which introduces environment).
extra overhead by depending on an external
To address these limitations, we introduce ReCAP (Recursive Context-A ware Reasoning and Planning), a hierarchical prompting framework with shared context for long-horizon tasks and dynamic environments. ReCAP is built around three major mechanisms.
(1) Plan-ahead task decomposition: instead of generating one subtask at a time, ReCAP produces a complete subtask list in single pass, executes only the first item, and refines the remaining plan upon subtask com-

---

pletion preserving global intent while avoiding plan drift. (2) Consistent multi-level context with structured injection: reasoning across all recursion depths occurs within a shared LLM con- text. When returning from subgoal, the parent's ' plan (latest thoughts and remaining subtasks) is re-injected into the active context window, preserving cross-level continuity and ensuring coher- ent progression through the task hierarchy (3) Memory-efficient scalability: the active prompt remains bounded, with critical planning information reintroduced through structured injection so that truncation does not cause loss of high-level intent. This avoids unbounded context accumulation, eliminates redundant few-shot duplication across recursive calls, and makes the external state grow linearly with recursion depth. Together, these mechanisms preserve high-level intent, support coherent multi-level reasoning, and provide robustness across a wide range of long- Lang-horizon tasks and dynamic environments.
We evaluate ReCAP across embodied and knowledge-intensive tasks with different planning horizons and feedback dynamics: Robotouille [7], ALFWorld [21], FEVER [23], and SWE-bench [9]. ALFWorld features short, largely linear embodied sequences. In Robotouille, the horizon grows much longer, and subgoals must be interleaved or refined continuously under resource contention. FEVER remains a shallow, tool-mediated retrieval task with a small symbolic action API. SWE-bench expands the action space from finite to effectively unbounded: the agent must compose multi-step code edits in a space far larger than environments with a limited verb set. Importantly, we adopt a strict pass @1 protocol: each task instance is solved through a single uninterrupted reasoning execcution trajectory, without retries, self-consistency, or ensembling, and we use a one-shot demonstration per agent. This is stricter than the ReAct setting, which is frequently reported with pass 6 and multiple demonstrations, and thus better reflects realistic single-run agent deployment. To summarize, ReCAP introduces recursive, context-aware framework for long-horizon reasoning and planning with LLMs. enables structured subtask decomposition, dynamic memory tracking, and observation-driven plan adaptation without any training or fine-tuning. ReCAP outperforms strong mnslines-aachevingg up to 32% in long-horizon tasks.
2 ReCAP: Recursive Context-Aware Reasoning and Planning
2.1 Framework Overview
Algorithm 1 formalizes the overall procedure, starting from the entry point ReCAP Oinit) where D is the task description with one-shot demonstration and mini the initial observation. ReCAP frames model execution a recursive process within a shared language model context C, which can be viewed as dynamically unfolding into a context tree: each recursive call extends LLM context C with local reasoning traces and subtasks, while backtracking corresponds to returning control to the parent node. From C, the model first generates an initial thought T and an ordered subtask list S = (su, $1. 1m-1) via the LLM--ased planning function и. The node then advances by attempting the first subtask S[0]: if it is primitive, the environment dynamics & execute S(0) and return an observation O, which appended to C: if not, recursive call is invoked on the extended context C || S. 5'0)), after which the parent plan (T, S(1 :)) is re-injected into C. In either case, the updated context is passed to the L..M- refinement function p. which produces a revised thought and subtask list through prompt templates that adapt to different reasoning granularities (root, recursive, and backtracking levels; see Appendix D for full definitions). This loop continues until S is empty or & reaches end, yielding complete resolution of the original task.
2.2 Recursive Task Decomposition with Plan-Ahead
ReCAP adopts a plan-ahead strategy: given the current context C. the planning function x returns an internal thought and an ordered subtask list
(T, S (so, s1,..., 91......m-1))) 1)) + (C'.
At execution time, only the head subtask S10) is attempted; the rest S :] is preserved for later refinement.
If S'0) is itself composite task, a recursive call invoked on the extended context || (T, S, S(O). producing a fresh thought and subtask list that decomposes the task to lower level. This recursion continues until S is primitive-i.e. directly corresponds to an executable action under the current environment dynamics E-at which point the subtask becomes temporary leaf in the unfolding
3

---

Reasoning Subtree
Algorithm ReCAP
Require: LLM Context C'
Current Task
Ensure: Updated context C
(T.S) -- (C))
2: while S not empty do
Just Finished Subtask
First Remaining Subtask
3:
if S is primitive then
4:
O - {()())
1
5:
- C (T,
6:
else
7:
+ (e ||
Previcus Cartiet - NNw Observation
Injected Old Rleaoning ng
New Reasoning
Retine Subcases
8:
end if
9: C+ (T, :]}
11M Canserted
(T + PCC)
11: end while
Figure 2: Overview of ReCAP's backtracking and refinement
12: return C
hierarchy. Its execution may succeed or fail depending on environmental constraints. In either case, control returns to the parent context: the higher-level plan (T, S[1 :]} is re-injected into C, and the refinement function p is called revise the subtask list.
2.3 Consistent Multi-level Context and Structured Injection
ReCAP maintains a shared LLM context across all recursion depths, so that high-level goals and low-level task executions remain aligned. When non-primitive subtask S(0] is encountered, the parent's plan S is appended to the context before invoking a recursive call:
+ RCCAPPCC (T, (,)O))) After the subgoal is resolved, the parent's remaining plan S(1 is re-injected into to restore contextual awareness:
C (I
This re-injection step corresponds to backtracking: once a child subtask finishes (successfully or not), its outcome and the environmental observations appended C. prompting the LLM to refine the parent's reasoning and update the remaining plan. By doing so, ReCAP dynamically prunes or revises subtasks in response to execution feedback, and then proceeds with the next unfinished subtask in the refined list.
Overall, this structured injection and backtracking mechanism helps the LLM to keep track of how its high-level plan got executed and encourages plan refinement throughout the long-horizon task execution. By keeping all reasoning within single evolving context rather than allocating separate contexts at each level, ReCAP supports consistent context updates upon recursive return, makes use of history dialogue context-aware demonstrations, and thus ensures coherent multi-level planning. Figure illustrates the local structure of context re-injection and next subtask generation.
2.4 Sliding Window and Scalable Memory Efficiency
isCAP designed for bounded and efficient context usage. The active LLM prompt is limited by sliding window of K back-and-forth dialogue rounds (typically K 64), with each round averaging tokens. This keeps the active context size at O(K L). well within model capacities. Older rounds beyond the window are automatically removed, while critical planning information is reintroduced through structured context injection, so that truncation does not cause loss of high-level structure. Moreover, because all recursion operates within shared context, few-shot examples are placed only once at initialization rather than re- re-injected at every recursive call. This significantly increases the proportion of tokens available for LLM reasoning. In contrast, prior recursive reasoning methods duplicate isolated contexts and few-shot prompts across calls, leading to fragmented usage. Although an external tree data structure used to power ReCAP's structured injection, with each tree node holding (T, S) for subtask, once the subtask is refined, (T,S) is replaced by the refined (T", S'). Therefore, at each step, only the path from the root to the current node remains active, so both the active prompt size and the external state storage scale O(d L), where d is the depth of the tree.

---

3 Evaluation
We evaluate ReCAP on four benchmarks, spanning coding, embodied, and text-based reasoning: ALFWorld [21], Robotouille [7], FEVER [23], and SWE-bench Verified [9]. All evaluations are conducted under a pass@1 setting: each agent is allowed a single reasoning-execution trajectory per task instance, without retries, beam search, sample-level ensembling. This setup is designed to highlight the raw decision making capability of each agent to avoid any performance-enhant strategies such self- self-consistency, inner monologue [8] response ensembling. ReCAP operates using one-shot prompting, with no training, offline or multi-trial optimization (e.g., Reflexion [19)), or task-specific tuning. To ensure consistency and fairness, for Robotouille, ALFWorld, and FEVER, we use the same task from the training sets to construct the one-shot examples and apply the same step limitations across agents, and use GPT-4o (2024-08-06) conduct all the main experiments.
3.1 Benchmarks
ALFWorld is symbolic, text-only houschold simulator for embodied reasoning via natural- language actions [21]. Each task (e.g.. heat a tomato and place it on a dining table) is solved by composing short commands over small action API (navigate, open/close, pickup/put, heat/cool, etc.). Task horizons are short (typically 5-15 steps), with limited interleaving of subgoals and modest -range dependencies. We evaluate on the official unseen split with the provided symbolic interface. For few-shot construction, we pick one training task per each of the six categories (seen in prior work), adapt the narration to the agent's prompt format, and keep identical rule descriptions across agents. This setting probes whether ReCAP's structured backtracking still yields gains when horizons are shallow and the action space is small and discrete.
Robotouille is embodied cooking environment designed to evaluate LLM agents on long-horizon tasks [7]. It supports two modes: synchronous, in which each action completes immediately and subgoals can be executed in linear sequence; and asynchronous, where certain actions incur delays (e.g., cooking or waiting for water filling), allowing agents to interleave other subtasks during these waiting periods to mitigate temporal constraints and advance multiple goals concurrently. The required action sequence lengths display the complexity of the environment: synchronous tasks require between 10 and 57 steps, while asynchronous tasks range from 21 82 steps- even when measured using the minimal number of necessary actions. These lengths are substantially greater than those in ALFWorld, making Robotouille more challenging.
major challenge in Robotouille is that subtasks often require multiple atomic actions to complete. For example, slicing single vegetable requires three consecutive cut actions before the ingredient is marked as sliced. This means that even seemingly simple operations span multiple reasoning- execution steps. placing pressure the LLM's context window. As subtask accumulates, carly-stage plans and goals can be forgotten or overwritten by new observations. Additionally, the environment frequently introduces unexpected constraints: stations such cutting boards may be occupied by other ingredients, forcing the agent to regenerate valid subtasks on the fly. We evaluate 10 synchronous and 10 asynchronous recipes, each with 10 official instances. For one-shot prompting, we follow prior work and use the held-out mion-cheese sandwich demonstration, adapting its wording to ReCAP's recursive format while preserving the original execution trajectory.
FEVER tests knowledge-intensive reasoning by classifying claims as SUPPORTED. REFUTED, or NOT ENOUGH INFO via a simplified Wikipedia API. Following ReAct, the agent uses three symbolic actions: search [entity] (first five sentences), lookup [string] (next sentence with keyword), and finish [answer] (final judgment). We use FEVER [23] to probe whether ReCAP's structured context management remains beneficial when horizons are short: most instances need less than 10 actions with little hicrarchical decomposition. We evaluate 200 randomly sampled claims with a single shared demonstration from the training set adapted to each agent's prompt format.
SWE-bench is a benchmark dedicated to repository-level coding issue resolution. Agents take a GitHub issue as input and have access to Docker container containing the repository. The agent must send commands to the container terminal to modify the code and pass set of tests for each repository. In our work, we selected its human-validated subset, SWE-bench Verified, to evaluate our framework's 's ability to reliably solve real-world software issues [15].
5

---

Unlike embodied reasoning benchmarks such as ALFWorld [21], where the action space is concrete given the state of the environment, the action space of code editing is unbounded, since one can append, delete, execute arbitrary code within the repository. Therefore, in ReCAP's evaluation on SWE-bench, there is no predefined list of valid actions. Instead, actions are interpreted solely from the language model's 's tool outputs, and any tool call accepted by the environment is considered valid. Furthermore, Since text outputs and tool-call outputs are separated in language model APIs, making the number of tool calls depend on the number of subtasks cannot be implemented without manipulating the probability space during decoding. In cases where a tool call is necessary to prioritize tool execution over subtask decomposition. ReCAP
interact with the environment, triggers a refinement once the tool call is executed and environment feedback has been received. To evaluate ReCAP, modified SWE-agent's ' [26] memory from ReAct to ReCAP, added ISON schema and prompts for ReCAP output (see Appendix C.4, D.2), while keeping the tool execution and error handling the same. The LLM used is GPT-4.1 (2025-04-14) 14), with no demonstrations and temperature set to zero.
3.2 Baselines
Sequential prompting baseline We retain the four sequential prompting baselines used in prior work: (1) Standard: directly output the full action sequence without intermediate thoughts/actions: (2) CoT [25]: add chain-of-thought to Standard; (3) ReAct [5]: interleave thoughts, actions, and observations: (4) Act (act-only prompting): remove thoughts from ReAct, akin to WebGPT's API- call style [13]. Their applicability follows the environment's 's interface: Robotouille exposes both the complete environment description and the currently executable actions, we evaluate all four baselines. contrast, ALFWorld provides only a partial environment description and the currently executable actions, so evaluate Act and ReAct (Standard and CoT cannot bootstrap); FEVER follows the "search-lookup-fnnii prompt only the final verdict). For SWE-bench Verified, used mini-SWF-ageen [26] with GPT-4.1 (2025-04-144 14) as the ReAct baseline, which performance is publicly available.
protocol from [5], so we evaluate all four (for Standard/CoT we
Hierarchical prompting baseline To complement missing embodied evaluations in the original papers, additionally include the hierarchical prompting framework ADaPT [16] Robotouille. We adapt its public prompting template to Robotouille's 's observation/action format while keeping its core control flow unchanged. As the method lacks official Robotouille implementation, we follow its paper's prescribed prompts and heuristics, reporting our re-implementation under the same budget and limits other agents. This addition allows direct embodied comparison between sequential prompting Acc/ReAct/CoT//tandrrd hierarchical prompting (ADaPT), and our multi-level context with localized backtracking (ReCAP).
Excluded baselines We do not include THREAD [18], Reflexion [20], Ada-Planner [22], or REPL-PPaa [10] in our main embodied comparisons for the following reasons. (i) THREAD's uncontrollable recursion and its requirement for fine-grained, few-shot demonstrations for each subtask made it difficult to achieve reliable results within our experimental setup. (ii) Reflexion relies on muiti-trial self-critique with an experience memory improve over attempts; is designed for pass @k or repeated episodes and is not well-aligned with our pass @ single-trajectory protocol. (iii) Ada-Planner edits a single global linear plan and depends heavily on code generation and an external interpreterrrnntime. In our embodied settings, this introduces a toolchain mismatch; in practice, we observed frequent formatting and syntax errors that prevented stable execution under the same budget, making results non-comparable. (iv) REPL-Plan similarly depends on an external code- exee-exeettion environment to maintain L.LM-ggnertted program states, adding substantial system complexity and biasing behavior toward reusing prior snippets, which makes it directly applicable to our prompt-only, tool-agnostic embodied setup. For fairness and reproducibility, we therefore focus on methods that operate within comparable interfaces and budgets.

---

Table 1: Pass @ task success rates (%) across methods.
Step Range
Task
ReCAP
ADaPT
ReAct
CoT
Act
Standard
ALFWorld
4-25
91.0
71.6*
84.0
74.0
Robotouille (Sync)
10-57
70.0
40.0
38.0
14,0
31.0
12.0
Robotouille (Async)
21-82
53.0
14.0
24.0
5.0
8.0
2.0
FEVER
1-10
63.5
63.5
58.5
58.5
53.5
SWE-bench Verified
5-257
44.8
39.58
4 Results
4.1
Main Results
Table shows that ReCAP performs better than ReAct long-horizon tasks by large margin. On synchronous Robotouille, it achieves a 32% gain, and on asynchronous Robotouille, a 29% improvement, representing its strength in long-horizon environments where early goals are prone to being overwritten in flat prompting setups. In these cooking tasks, high-level objectives often span multiple atomic actions and require multi-phase coordination. While ReAct performs all reasoning sequentially and suffers from context overflow, ReCAP maintains a dynamic task hierarchy and supports explicit backtracking, enabling the agent to preserve global goals and revise local decisions when needed. These features allow ReCAP to better handle the challenges of concurrent subgoals, delayed dependencies, and evolving observations, all of which are common in Robotouille.
We further perform a detailed failure case analysis to understand the nature of errors across different task difficulties in Robotouille. On easy to medium tasks (synchronous #1-5, asynchronous #1 #1-3), ReCAP achieves near-perfect success, with failures mostly due to minor errors like missing the final cut in a sandwich or misplacing the completed item. In contrast, ReAct exhibits more fundamental mistakes even on simple recipes. On long-chain or multi-dish tasks (synchronous #8-10, asynchronous #4, #5, #8-10), ReCAP may occasionally make imperfect subtask choices, but it never enters an infinite loop. It consistently detects failure signals and backtracks to generate revised plan. ReAct, on the other hand, frequently enters infinite loops when encountering blocked stations. For instance, if lettucel is occupying board2, ReAct will repeatedly attempt to cut onion1 by stacking and unstacking on the blocking item without resolving the underlying issue. ReCAP avoids such failure by leveraging its multi-level context to identify the blockage and generate a corrected e.n- moving lettuce1 to an empty table before proceeding with the cut-thus maintaining task progress and preventing infinite loops. Figure 3 illustrates a detailed dialogue trace in which ReAct becomes trapped in an infinite unstack/stack loop, whereas ReCAP detects the looping behavior via backtracking, refines its plan to clear the blocked station, and then successfully resumes execution.
In shorter tasks, ReCAP's advantage becomes more nuanced. In ALFWorld, it improves over ReAct by 7%, smaller but consistent gain. Although the reasoning horizon is shallower, we find that ReCAP is still able to recover from local errors. On FEVER, both methods perform similarly, achieving 63.5% accuracy. This result aligns with our expectation: when the number of reasoning steps is small, the benefits of explicit hierarchical structure and backtracking diminish. Nonetheless, the fact that ReCAP remains competitive without degrading performance demonstrates that our recursive architecture does not introduce overhead in short-horizon knowledge-retrieval tasks while delivering increasing gains as task complexity and step length grow.
In real-world coding tasks, ReCAP achieves the highest success rate on SWE-bench Verified among all methods using GPT-4.1 as the LLM. All of the 500 tasks were successfully submitted without human intervention, of which 498 were successfully evaluated by the SWE-bench CLI and 224 tasks were solved. The horizon length and cost distributions are rieht-skewed, as shown in Figure 4. However, Figure 5 shows that the resolve rate does not drop entirely to zero for tasks involving
? ADaPT (ALFWorld) uses GPT-3.5. The ADaPT paper also reports GPT-4 runs, but the best accuracy with GPT-3.5; we thus report GPT-3.5 here. hhttps://wwi http::::/wwwwswwbbeeee swwbench. com/ retrieved Sept 17, 2025
7

---

ReAct
ReCAP (Ours)
In omtt..
ort
Reascring:: The goal to propare cheese dhicun sandlish on takee Gumertyy ctac prepore the sandwicd, cricien! neesh sooked Assertile sanbbichh placing chicien't of beiween breadf and breac2.
Taxte: Out onion!
Bubbtanke iPik onient from Move robott sabre? boand?
orient using robot),
Took Decompontiing tionn & Recursion
Faedbacko Sueeees New
cheesel using
Taski Movs robutt from sub ol boand)
Act: Move robont from baie? scort?
Reasoninng gool propare
on sandwigh
that
Task: Cut oniont on board? using robott using
Baoktracking Refline
cooked propents.
Feedback: fisdt
using
(. daing uratack and stace tolta
Faedbackc Suecees New
Think leeen loop
Since boardil already lettuser ioard make space onlont...
Reasoningg: ohresent
cody stocked togothor saavot,
lettucel
searcif for curting.
bubtesks: (Hrr istuoet from parsi, Place omiot on boore using robott.....
Ast Cook chickent on stowet using robott
Task: Removo inttuet
Replan
Reasoning: eg condw should be stasked wi broad, cheose, chicken, and onother bread añce chacken1 stacked on top cheesal stovel imiitakenty artempted cookit
boarsi tabriu
Subteshor (Maace
tazkel robolt),
setuort irom boantz using riboct, Place lattuoe on lat vaing robert)
Auti Unstack chaikent from cheesot using sobott
Think: Orian! now placed on tabled move back to boarst to pidk ietuue! ican to tatkel,
Taal: Place onioni boerch using robot!
culling sowerd for
Reascrinng
Infinite Loop! No Replan
Move Move robott from board? sabred,
Act chickent top cheeae! uxting noboot
C.. omit...
Rassoning:
X
Teaks Pick up Intucel trom bosid using reboet
Back to track
Peodback: Succena,.. New
Task Plaze ontent board? using robont been placed pick
have space cutling onion
J.. one
Figure 3: Detailed comparison between ReAct and ReCAP's behaviors when encountering blocked stations in Robotouille. Left: ReAct repeatedly alternates between stacking and unstacking the same item, resulting an infinite loop. Right: ReCAP detects the loop, backtracks to clear the board by moving the blocking lettuce, and then proceeds with the correct sequence of actions.
(5)
20
40
50
994
Tool Collo Cost
Uvraaceo
140
120
Frequency
Frequeecyy 07
100
200
80
150-
100
20
50
100
160
200
253
Tool Calls
Figure 4: Tool call and cost distributions for ReCAP on SWE-bench Verified.
Figure 5: Task resolve rate of ReCAP on SWE- bench Verified, by number of tool calls.
more than 100 tool calls, implying that ReCAP indeed remains strong on tasks where decides to run longer.
4.2 Task Tree Analysis
To understand the extent to which ReCAP decomposes a task before taking an action, we conducted an analysis on 20 runs of the Robotouille task synchronous/6 $__ettuce tomato. cheeseburger. On average, the tree depth is 3.4 and the branching factor 12.5, suggesting that ReCAP tends to produce shallow trees with moderate fan-out in embodied tasks, where each subtask often requires
8

---

multiple atomic actions to complete. For SWE-bench Verified, since the model's tool use takes higher priority than subtask decomposition, and each tool call incurs return to the parent task for refinement, the resulting tree structure is similar to that of embodied tasks. A shallower tree also implies smaller external state storage requirement.
4.3
Performance on Different Models
Table 2: Success rates (%) between ReAct and ReCAP across models, Robotouille tasks #2, 4, and 6.
Method
GPT-4o
Qwen2.5-32B
Qwen2.5-72B
LLaMA-4 (400B)
DeepSeck- (671B)
ReAct 63.0
10.0
23.0
37.0
57.0
ReCAP
90.0
33.0
53.0
60.0
87.0
To assess how our ReCAP generalizes across models compared to the standard ReAct setup, we evaluated both architectures three representative synchronous Robotouille tasks (IDs 2, 4, and 6). To control API costs, we limited our experiments to these three tasks and imposed hard cap of 64 context messages per (any excess truncated). We benchmarked four open-source and proprietary LLMs- Qwen2.5-32B [17]. Qwen2.5-72B, LLaMA-4 (400B) [12], and DeepSeek- V3 (671B) alonssiee GPT-4o. Table reports average success rates (%) for each model under both ReAct and ReCAP. ReCAP consistently outperforms ReAct across all evaluated models, demonstrating strong robustness and broad applicability. These results highlight the compatibility and reliability of our recursive framework across diverse model families, without requiring any model-specific tuning or code modification.
4.4 Ablation Studies
To further investigate the effectiivneess of our structure, conducted extended ablation studies on the Robotouille task synchronous/6 waw.noouuuoleettteeeeeeeeeeeeeee towattttttoooomoom cheeseburger, which requires 23 (theoretical optimal) to 40 (average) rounds of agent-environment interaction complete. We also evaluate the statistical significance of differences success rates between the structural variants and the original version. Table 3 reports the success rates and p-values for various ReCAP struc- tural variants, including alterations to the maximum reasoning depth (Level 2/3/4/5), omission of reasoning traces during backtracking (Name Only), and modifying the output format to generate only decomposition//ctiio outputs without the "think" reasoning (No Think), as well as passing all think history instead just the most recent (Think Many). All structural variants were evaluated with context length of 128, where context length refers to the number of messages stored in the LLM history during the conversation. For the No Think and Name Only variants, we adapted the one-shot prompt to match their structure.
Table Success rates (%) between different ReCAP structural variants, Robotouille task 6.
Original
think_mang
nh_think
name_only
level_5
level 4
level_3
level_2
80
70
60
55
70
60
10 0
For the long-horizon task synchronous/6. l__ee_tteeeee_eeeee tomato, to cheessebreeerr, the success rate degrades significantly when reasoning traces are removed or when the maximum reasoning depth is restricted (Level 2/3). This suggests that the explicit reasoning traces produced by ReCAP help the LLM perform better by allowing it to recall previous subtasks and lines of reasoning. With restricted reasoning depth, the LLM is limited in its ability to recursively decompose higher-level tasks into atomic, directly executable actions, forcing it to generate actions from insufficiently decomposed subtasks and thus reducing accuracy.
the other hand, the Think Many and No Think variants achieve success rates comparable to the original, indicating that ReCAP is robust even when the LLM is provided with either excessive reasoning history or only decomposition/action outputs without the intermediate "think" reasoning. This robustness is also observed in the context length variants: significant performance degradation

---

occurs when limiting the number of messages stored in the LLM history during the conversation, implying that ReCAP remains effective under sontext-eensitvve scenarios.
4.5
Cost Estimate
We
conducted cost estimation on Robotouille for ReCAP, and cost compar- between ReCAP and ReAct on ALFWorld.
For the Robotouille task Settrroooousb_etttueee _oncctttttttt_oo certtoeehheeeerrr...eeeeee the average number of LLM calls is 74.95 with a standard deviation of 27.87, and the average cumulative cost for one complete run is 7.77 USD with standard deviation of 3.45 USD. For ALFWorld. the total cost of running all 134 tasks in the test set is 37. 87.89 USD using ReAct, and 118.40 USD using ReCAP-approste approxiaaii three times the cost of ReAct. We identified that the extra cost mainly comes from the additional reasoning traces in the input and the extra steps required for intermediate task decomposition.
ison
Discussion
Despite its strong performance, ReCAP has several limitations. The framework delegates all decom- position, execution, and backtracking decisions to the underlying language model, without external validation grounding. As result, the system remains sensitive model quality and may propa- gate errors if the LLM fails to follow instructions or misinterprets feedback. In addition, ReCAP's recursive design design-While enhancing robustness and planning accuracy-ineee inneurs longer interaction trajectories compared to flat prompting. This leads to increased API overhead and slower end-to-end latency, which may pose challenges in deployment scenarios with strict efficiency cost constraints.
Several promising directions remain for improving ReCAP. One is to modularize the architecture by decoupling high-level planning and low-level execution, allowing different models (e.g.. large LLM for decomposition and a lightweight model for primitive actions) to collaborate more efficiently, Another avenue is to reduce interaction costs through reasoning compression, dynamic step control, or API batching strategies. More broadly, ReCAP's recursive context tree challenges the default assumption that LLM context must be linear dialogue history. Future work may explore structuring memory as an executable graph, enabling more targeted retrieval and potentially allowing rein- forcement learning or memory-aware routing to optimize reasoning under context constraints. This perspective points toward a more scalable alternative to simply expanding context length--mmrroinn how context is organized and used, rather than how much is stored.
Conclusion
agents both coherent and adaptive by combining three simple but complementary ideas: (i) plan-ahead task decomposition, where the model proposes full ordered subtask list, commits to the head item, and then refines the remainder using new observations to prevent myopic drift; (ii) consistent multi-level context with structured injection, which executes all recursion in single LLM session and selectively re-inserts the parent's s description, latest thoughts, and remaining subtasks on backtracking, preserving cross-level continuity without fragmenting context; and (iii) sliding-windor and re-surfaces only the essentials, so latency and memory scale with path depth rather than with total trajectory length. Across embodied cooking (Robotouille), symbolic interaction IALFWorld/FEVEE EEER), and repository-Iewe code editing (SWE-bench Verified), ReCAP improves success rates under pass@ @ I protocol without training, fine-tune fine-tuning, tool-specific engineering, showing that how organize and reinject context can matter as much as how much context we have.
We introduce RECAP, framework that makes
scalability, which bounds the active prompt
10

---

References
[1] Maciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger, Michal Podstawski, Lukas Gianinazzi, Joanna Gajda, Tomasz Lehmann, Hubert Niewiadomski, Piotr Nyczyk, and Torsten Hoefler. Graph of thoughts: Solving elaborate problems with large language models. In Proceedings of the AAAI Conference Artificial Intelligence, volume 38, pages 17682-17690, 2024.
[2] Gautier Dagan, Frank Keller, and Alex Lascarides. Dynamic planning with a Ilm, 2023.
[3] DeepSeek-Al et al. Deepseek-v3 technical report, 2025.
[4] OpenAI et al. Gpt-4o system card, 2024.
[5] Yao et al. React: Synergizing reasoning and acting in language models. In International Conference on Learning Representations (ICLR). 2023.
[6] Yao et al. Tree of thoughts: Deliberate problem solving with large language models. In Conference on Neural Information Processing Systems (NeurIPS), 2023.
[7] Gonzalo Gonzalez-Pumariegea Leong Su Yean, Neha Sunkara, and Sanjihan Choudhury. Robotouille: An asynchronous planning benchmark for Ilm agents, 2025.
[8] Wenlong Huang. Fei Xia, Ted Xiao, Harris Chan, Jacky Liang, Pete Florence, Andy Zeng. Jonathan Tompson, Igor Mordatch, Yevgen Chebotar, Pierre Sermanet, Noah Brown, Tomas Jackson, Linda Luu, Sergey Levine, Karol Hausman, and Brian Ichter. Inner monologue: Embodied reasoning through planning with language models, 2022.
[9] Carlos E Jimenez, John Yang, Alexander Wettig, Shunyu Yao, Kexin Pei, Ofir Press, and Karthik R Narasimhan. SWE-bench: Can language models resolve real-world github issues? In The Twelfth International Conference on Learning Representations, 2024.
[10] Anthony Z. Liu, Xinhe Wang, Jacob Sansom, Yao Fu, Jongwook Choi, Sungryull Sohn, Jaekyeom Kim, and Honglak Lee. Interactive and expressive code-augmented planning with large language models, 2024.
[11] Nelson F Liu, Kevin Lin Yu, Nora Kassner, Fan Du, Daniel Khashabi, Ashish Sabharwal, and Noah Smith. Lost the middle: How language models use long contexts. arXiv preprint M:Xiv:237..33122 2023. Computer Science > Computation and Language, arXiv:2307.03172.
[12] Meta AI. LLaMA 4 Scout and Maverick Models. https://githur httt::://gtttub..ccmmmmaaaall
11 moamalmoeels// tttee/reeeeeeeeeee httpr//e/mmii/moomem/eleaaaaaa
2025.
[13] Reiichiro Nakano, Jacob Hilton, Suchir Balaji, Jeff Wu, Long Ouyang, Christina Kim, Christo- pher Hesse, Shantanu Jain, Vineet Kosaraju, William Saunders, Xu Jiang, Karl Cobbe, Tyna Eloundou, Gretchen Krueger, Kevin Button, Matthew Knight, Benjamin Chess, and John Schulman. Webgpt: Browser-assisted question-answering with human feedback. 2022.
[14] Allen Newell and Herbert A. Simon. Human Problem Solving. Prentice-Hall, Englewood Cliffs,
NJ, 1972.
[15] OpenAI.
Introducing swe-hench verified.
https://openai. com/index/ August 2024. Accessed: 2025-09-16.
[16] Archiki Prasad, Alexander Koller, Mareike Hartmann. Peter Clark, Ashish Sabharwal, Mohit Bansal, and Tushar Khot. Adapt: As-needed decomposition and planning with language models, 2024.
[17] Qwen, :, An Yang, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chengyuan Li, Dayiheng Liu, Fei Huang, Haoran Wei, Huan Lin, Jian Yang, Jianhong Tu, Jianwei Zhang. Jianxin Yang, Jiaxi Yang. Jingren Zhou, Junyang Lin. Kai Dang, Keming Lu, Keqin Bao, Kexin Yang, Le Yu, Mei Li, Mingfeng Xue, Pei Zhang, Qin Zhu, Rui Men, Runji Lin, Tianhao Li, Tianyi Tang, Tingyu Xia, Xingzhang Ren, Xuancheng Ren, Yang Fan, Yang Su, Yichang Zhang, Yu Wan, Yuqiong Liu, Zeyu Cui, Zhenru Zhang, and Zihan Qiu. Qwen2.5 technical report, 2025.

---

[18] Philip Schroeder, Nathaniel Morgan, Hongyin Luo, and James Glass. Thread: with recursive spawning, 2025.
Thinking deeper
[19] Noah Shinn, Federico Cassano, Edward Berman, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: Language agents with verbal reinforcement learning, 2023.
[20] Noah Shinn, Federico Cassano, Edward Berman, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: Language agents with verbal reinforcement learning, 2023.
[21] Mohit Shridhar, Xingdi Yuan, Marc-Alexandre Côté, Yonatan Bisk, Adam Trischler, and Matthew Hausknecht. Alfworld: Aligning text and embodied environments for interactive learning, 2021.
[22] Haotian Sun, Yuchen Zhuang, Lingkai Kong, Bo Dai, and Chao Zhang. Adaplanner: Adap- tive planning from feedback with language models. In A. Oh, T. Naumann, Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 19202-58245 Curran Associates, Inc., 2023.
[23] James Thome, Andreas Vlachos, Christos Christodoulopoulls, and Arpit Mittal. FEVER: a large-scale dataset for fact extraction and VERification. In NAACL-HLT, 2018.
[24] Guanzhi Wang, Yuqi Xie, Yunfan Jiang, Ajay Mandlekar, Chaowei Xiao, Yuke Zhu, Linxi Fan, and Anima Anandkumar. Voyager: An open-ended embodied agent with large language models, 2023.
[25] Jason Wei, Xuezhi Wang. Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed Chi, Quoc Le, and Denny Zhou. Clain-of-thoughh prompting elicits reasoning in large language models, 2023.
[26] John Yang, Carlos E Jimenez, Alexander Wettig, Kilian Lieret, Shunyu Yao, Karthik R Narasimhan, and Ofir Press. SWE-agent: Agent-computer interfaces enable automated soft- ware engineering. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
12

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No] or [NA]. .
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justificatin right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]" ", is perfectly acceptable to answer "[No] "provided proper justification is given (c.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
general, answering
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only the provided macros for your answers.
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 clearly state the core contributions of the paper:
(1) the proposal of recursive, context-aware reasoning and planning framework (ReCAP); (2) the introduction of dynamic context tree for hicrarchical memory and adaptive control; (3) experimental validation across diverse benchmarks including Robotouille, ALFWorld, and FEVER; and (4) significant improvements over prior methods like ReAct. These claims are faithfully aligned with the detailed methodology and empirical results presented later in the paper.
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 be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long clear that these goals not attained by the paper.
13

---

2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
The paper discusses key limitations in the discussion section, including the heavy reliance the underlying language model for all reasoning and pecision-making steps without external validation, which makes the system sensitive to model quality. also notes that the recursive design introduces longer interaction trajectories and higher API costs, potentially limiting practical deployment in latency- or cost-sensitive scenarios. These limitations acknowiedged and contextualized, and the paper suggests directions for future work to mitigate them.
Justification:
Guidelines:
The answer NA means that the paper has no 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 "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 how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on 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 is low 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 be 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 an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
Answer: [NA]
Justification: The paper does not include any formal theoretical results, assumptions, or proofs. The contributions primarily empirical and methodological.
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 short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
14

---

Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
The paper describes all task setups, evaluation protocols, and prompt configura- tions in detail, allowing others to reproduce the experiments. We also plan to release our code, prompts, and model configurations upon publication to further facilitate reproducibility.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to 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.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a 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 to the model. In general. releasing code and data is often good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
also be provided via detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily new 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 access this model for reproducing the results 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 to deseribe the particular way they provide for reproducibility. In the case of closed-souree source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: 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?
Answer: [Yes]
Justification: We will release anonymized code, prompt templates, environment setup in- structions, and evaluation scripts in the supplemental material to enable faithful reproduction of all main results. Public access the code and documentation will be provided upon publication.
Guidelines:
The answer NA means that paper does not include experiments requiring code. Please see the NeurlPS code and data submission guidelines (https://nips.co cc/ for more details.
15

---

While we encourage the release of code and data, we understand that this might not be possible, so "No" 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 run to reproduce the results. See the NeurlPS code and data submission guidelines (https: /nipp..c. wwtpccccppppcc..eeeeee.ee.ccccle gtdiiiiggdd///////eee httgg//ddeeooeduumiieeeeeeeeee "oodeeobmissss onnoiicy) 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 as possible supplemental material (appended to paper) recommended, but including URLs to data and code is 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 Evaluation section provides full details of the experimental setup, including task specifications, dataset splits, few-shot prompt configurations, environment settings, and evaluation criteria. All relevant implementation and experimental design choices are documented to ensure transparency and reproducibility.
Guidelines:
The answer NA means that the paper does not include experiments. The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We follow strict pass I evaluation protocol without retries, consistent across benchmarks. While we do not report error bars in the main paper, we include details on statistical significance and evaluation stability in the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
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).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It 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.
16

---

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 enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the 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: All experiments were conducted via commercial API calls to proprietary and open-source language models (e.g.. OpenAI [4], Llama [12], DeepSeek(3)). We report total token usage and corresponding cost estimates for each benchmark in Appendix. Since no local training GPU inference performed, compute resources quantified in terms API usage rather than hardware.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: htt////nurripppppe htc/ppplcc/cccccsuueeeeeeeeeeell
Answer: [Yes]
Justification: The research adheres to the NeurIPS Code of Ethics. All experiments are conducted publicly available benchmarks open-source environments. No human subjects, private data, or sensitive demographic information are involved. The proposed method aims improve planning transparency and agent robustness in general-purpose reasoning tasks, without foresceable risk of misuse.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS 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: [Yes]
Justification: The paper includes a discussion of broader impacts the appendix. As foundational method for improving long-horizon reasoning in LLM agents, ReCAP has potential positive impact in areas such as education, assistive robotics, and scientific support tools. We do not identify any immediate negative socictal impacts, as the method does not introduce new content generation capabilities or decision- makonn autonomy beyond existing LLM frameworks.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
17

---

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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 that a generic algorithm for optimizing neural networks could enable people to 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 as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g.. gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
This paper does not introduce or release any new models or datasets that pose high risk for misuse. All evaluations conducted using existing, commercially available APIs or public benchmarks, and the proposed method is a prompting based framework without any training or data collection components.
Justification:
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.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All third-party assets used in this work-iicluding the Robotouille [7], ALF- World [21]. and FEVER [23] datasets- are properly cited in the paper. The language models (e.g., GPT-4o[4], Llama4[ [12], DeepSeek DeepSeek-V3(3) V3[3)) are accessed via their respective APIs under terms of service provided by the vendors. No redistribution or modification of datasets or models performed.
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 dataset.
18

---

The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. 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 package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We introduce new recursive prompting framework and associated implemen- tation, which are thoroughly documented in both the main paper and appendix. We describe usage instructions, input/output formats, and prompt templates. The code will be released upon publication with clear documentation and examples to support reproducibility.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model 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 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 crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing 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
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?
Question:
Answer: [NA]
19

---

Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending 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.
recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it 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, or originality the research, declaration is not required.
Answer: [Yes]
Justification; ReCAP framework is built to help LLM tackle long-horizon tasks, thus it is described in the paper that LLM an important component of the core method this research.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy pectp::/neuuriie http://ewwrr.s.eeeooeeeeeeeeeeee / for what should or should not be described.
20

---

A Additional Framework Details
A.1 LLM-call retry and history truncation
Our core API wrapper (call_ enforces complementary safeguards:
History-length eap: Before each call, if the in-memory history exceeds certain configurable entries, we delete the 2nd and 3rd elements (the oldest user-assistant exchange) while retaining the first entry (the fixed prompt containing few-shot examples and rules). Deletions always start from the second element to preserve the initial prompt (few-shot rules).
Model context-length cap: If the LLM returns context, context_length. www.ggtheeceeeeeeeeeeeeeeeeeeeee exceeded error, we delete and retry the same user
entries 2 through 33 (i.e. the oldest 32 messages after the fixed prompt) prompt. In practice, with the history-length cap, it is exceedingly rare to hit the 128K-token limit; this branch exists as fallback for extraordinarily long dialogues.
A.2 Periodic rule reminder injection
To prevent "rule amnesia" over long trajectories, we prepend the full environment rule text every 10 LLM invocations. This ensures that the rules are reintroduced regularly, bolstering stability on multi-step tasks.
A.3 Leaf-failure and nonleaf-failure prompt triggers
When the agent proposes an invalid primitive action (not the current valid_action list), we invoke generate _eleeffl______eeeeeeeeeeeeeleeee _aaaf_u____ sp__fail_prrott (See Section D.1.6), which supplies diagnostic hints and asks the model to repair its remaining subtasks. a non-leaf node exhausts all subtasks without completion, have the model either confirm task completion or generate additional subtasks. These failure-driven backtracking prompts enable recovery from both execution errors and planning dead-ends.
call generate Senerate_nonleaf_... _uugee______eeeeee wwwpjjjuudd________e___eee _ooe_ _one_pprompt (See Section D.1.4) to
B Per-task Result on Robotouille
Tables 4 and 5 report the per-task success rates for ReCAP and our five baselines on the 10 syn- chronous and 10 asynchronous Robotouille tasks. In the synchronous setting (Table 4), ReCAP achieves an overall average of 70%, compared to 38% for ReAct, with p-value < 0.001.
In the asynchronous setting (Table 5), ReCAP yields even larger gains. It improves average task success from 24% (ReAct) to 53%, with p-value < 0.001. These improvements imply ReCAP's strength in managing concurrent subtasks and adapting plans the fly. Despite the inherent difficulty of tasks 9 and 10, where both methods struggle, ReCAP still achieves a non-zero success rate, while none of the baselines succeeded, underscoring the ability of recursive context tracking in long- nogghhrizoon environments.
C Additional Experiment Details
C.1 Robotouille Experiment Details
All Robotouille experiments use the same hyperparameters and evaluation protocol for both ReAct and other baselines. For each of the 10 synchronous and asynchronous test tasks, we run 10 random seeds under pass @1 setting. We use the "onion cheese sandwich" recipe our one-shot demonstration. The baseline agents employ the original few-shot prompt provided by the benchmark unchanged, while ReCAP uses that same example, adapted to emit a CONNffrmatted output that contains its updated thinking and generated subtask list. Both methods share identical LLM settings (temperature 0.5, default max tokens -Pkeno-GPT-40's 128 K window- and no additional sampling penalties) and the same max step_ aatep_multiie multiplier=4 (up to four times the theoretical optimal step count per task) to allow room for error recovery. No other model-specific tuning is performed.
GPT-40's
21

---

Table Performance comparison between ReCAP and baselines on Robotouille synchronous tasks
using GPT-4o.
Task
ReCAP
ReAct
ADaPT
Act
CoT (%)
Std
(%)
(%)
(%)
(%)
(%)
100
60
70
90
40
50
80
30
70
30
30
20
80
40
50
10
10
10
80
50
30
10
90
80
70
10
10
70
60
60
30
30
30
70
50
20
20
0
60
0
0
0
50
0
10
10
0
20
0
20
0
Average
70
38
40
31
14
12
Table Performance comparison between ReCAP and baselines on Robotouille asynchronous tasks
using GPT-4o.
Task
ReCAP
ReAct
ADaPT
Act
Co'T (%)
Std
(%)
(%)
(%)
(%)
(%)
50
20
20
20
10
10
80
40
40
20
10
10
90
10
10
0
20
0
40
40
20
20
50
0
0
10
80
60
50
10
70
30
0
0
40
30
0
10
0
20
0
0
0
10
0
0
0
Average
53
14
8
5
22

---

C.2 ALFWorld Experiment Details
All ALFWorld experiments follow the same LLM settings and evaluation protocol for both ReCAP and other baselines. We use the same model hyperparameters described in Section C.I. The timeout action step is set to 50.
The original ReAct baseline employs a two-shot prompt for each task. For fairness, we only use the first example from the two-shot prompt for ReAct and modify it accordingly for ReCAP. The thinking and action traces are aligned between ReAct and ReCAP.
C.3 FEVER Experiment Details
All FEVER experiments follow the same LLM settings and evaluation protocol for both ReCAP and other baselines. We use the same model hyperparameters as described in Section C.I, and we fix the random seed to 42 to shuffle the FEVER test set. From the shuffled pool, sample 200 claims per run and evaluate under a hard cap of 10 reasoning steps (each agent may invoke at most 10 API calls-search, lookup, finish). This configuration is applied both ReAct and other baselines.
The original ReAct baseline employs three-shot prompt; to isolate the effect of our recursive architecture, ReCAP uses only one-shot prompt. When re-running the published baseline, discovered a typo in its few-shot examples: the label "NOT ENOUGH INFORMATION" was used instead of the official "NOT ENOUGH INFO," causing misclassification and artificial drop in accuracy. We corrected this label in our reproduced baseline to ensure a fair comparison.
C.4 SWE-bench Verified Experiment Details
All SWE-bench experiments were conducted on 500 tasks under the pass@) setting using GPT-4.1 1, with the temperature fixed 0 and demonstrations provided. We modified the original SWE-agent code, which uses LiteLLM to call the OpenAI API. All experiments were run without any human intervention (c.g., terminating runs that took too long). To encourage proper task submission, we added an extra parent node to the task tree. When the ReCAP agent successfully solves a task, it returns this parent node (named "review and submit") to trigger submission.
Since no few-shot demonstrations were used, we employed a JSON schema to constrain the LLM's output the fields "think" and "subtasks." The JSON schema is provided below:
"schema":
"type": "object", "properties"; {
"think" {
"type": "string",
"description". "Your reasoning and thought process for the current task."
},
" "subtasks": { "type": "array", " "items": { "type": "string"
},
"description": "A list of subtasks to complete the task. Empty if you determine the task has been completed. Do not generate any subtasks beyond the scope of the current task,"
},
"required": ["think", "subtasks"], "additiionaPPopertiie":: False }
23

---

For the baseline comparison, we used the accuracy reported by mini-SWE-agent on the benchmark'. Upon examining both their code and paper [26], we confirmed that mini-SWE-agen adopts the ReAct framework.
D Prompts
Here we list all of the prompts used our framework, such as those driving the recursive decom- position, backtracking refinement, and subtask execution, well as the rule templates for each of the three benchmarks. Due to their length, we have omitted the few-shot demonstration prompts for each benchmark from this Appendix; readers refer to our public code repository for the complete examples.
D.1
Core Framework Prompts
Below we list all of the prompt templates used by ReCAP in the recursive decomposition and backtracking loop. Variable placeholders (e.g. (taasknnmme"") indicate where runtime values are substituted.
D.1.1 Initial Decomposition Prompt
This prompt starts the process by providing system instructions, environment rules, initial observation, and the high-level goal.
leystem_promph
Here's the rule of the environment: {rule)
(init_obs}
Now you need to find the answer for the following question using the actions I provide.
Here is the description:
(task_name)
Now, start the task. Please firstly generate a list of general subtasks to accomplish the task.
D.1.2 Recursive (Downward) Prompt
Used when descending into newly created subtask node to request its own subtasks.
OK.
Your current task: {task_name)
We wish you to generate a list subtasks the current task.
D.1.3 Leaf Backtracking Prompt
Triggered after successfully executing a leaf subtask when the parent still has remaining subtasks.
You completed the task: taane_task_nnne
Here result:
{obs}
Now, you return to the parent task:
retrieved Sept 17, 2025

---

Your current task:
Your previous think: fprevious_stage_etee
Your remaining subtasks:
"remaining__ubbaskkstt"
We wish you to refine your list of subtasks based on the latest observation to achieve your goal.
If there are no remaining subtasks, check if the goal is achieved. If yes, return empty list; otherwise, return the required subtasks. Do not generate subtasks beyond the current task.
D.1.4 Non-Leaf Completion Prompt
Fires when a non-leaf node has no subtasks left and needs to decide it's fully done or generate more.
You have successfully completed the task: {done_ @dske_task.o_ name}
Now, you return to the previous stage.
Your current task: pprevious_stage_taie sttage_task_name)
Your previous think: (previous_stage_tiie
There are no remaining subtasks. Determine the task is complete. If it is, set subtasks to an empty list; if not, generate necessary subtasks.
D.1.5 Leaf Completion Prompt
Used when leaf node ends with subtasks remaining perform the final completion check. You have completed the task: Blone_task_nante
Here is the result: {obs}
Now, you return to the previous stage.
Your current task: swwrious_stage_taaskk. name)
Your previous think: (previous_stage_thiine
There are no remaining subtasks. Determine if the task is complete. If it is, set subtasks to an empty list; if not, generate necessary subtasks.
D.1.6 Leaf Failure Prompt
Triggered when leaf action fails validity, requiring the parent to fix the subtasks.
You fail to complete the task: [fail_task_naml Because the action is not among the valid options.
{obs}
Now, you return to the previous stage. Your current task: {previous_stape staooessssttee__eee task name]
Your previous think: (previous_stage_thinn
25

---

Your remaining subtasks: Beemaining_uuttskk.ooo
We wish you to modify your subtasks to fix the error.
D.1.7 Non-Leaf Backtracking Prompt
Issued after any non-leaf child finishes, to refine the parent's remaining subtasks. You completed the task: clone_tasknnang
The result shows in the previous context.
Now, you return to the parent task: Your current task: pprevious_stage_tae Battge_task_nan name]
Your previous think: (previous_stage_thinnk
Your remaining subtasks: sremanning.subrask_st))
We wish you to refine your list of subtasks based on the latest observation to achieve your goal.
Do not generate subtasks beyond the current task.
D.2 Tool Call Prioritized Prompt for SWE-bench
D.2.1 Action (Tool Call) Taken
Latest observation:
{obs}
Your current task: {task_name)
Your previously proposed subtasks: (remaining.eubraak.sst)
You can refine the subtasks based on the latest observation, empty list if you think your current task is done, further decompose the first subtask by not calling any tool, and/or make tool calls to make progress.
D.2.2 Recursive (Downward) Prompt
OK.
Your current task: {task_name)
You can decompose the task if it is too complex, empty list if you think your current task is done, further decompose the subtask by not calling any tool, and/or or make tool calls to make progress.
D.2.3 Backtracking (Upward) Prompt
You determined that the task {done_tast taskt_aak_)) has been completed.
Now, you return to the parent task. Your current task: steevous_sttae____
sttpaiussstttt_ets__aaeeeeeee name]
Your previous think: sarrriuussttae__ee
26

---

Your remaining subtasks: Beemaining_subtas....
You can refine the subtasks based on the latest observation, empty list if you think your current task is done, further decompose the first subtask by not calling any tool, and/or make tool calls to make progress.
D.3 Rule Templates
D.3.1 Robotouille
You are agent exploring a game environment with goal to achieve. You will propose series of task decomposition or an action state to make progress towards the goal. Follow the rules carefully since the environment may constraints that do not align with real world.
current
You must propose a series of task decomposition or an action given the current observation and valid actions. I will help you keep track of your progress by providing your previous thoughts and remaining subtasks.
You will receive the initial state and the goal as follows: Optional [Error Feedback: ...]
Observation:
Valid Actions:
where
'Observation' contains state information about objects in the environment and the goal
'Valid Actions' is the list of actions you can take in the current state 'Error Feedback' includes feedback about an invalid action taken previous interaction (not included in the history)
This feedback is automated and shows if the action either syntactically incorrect or does not exist in the valid actions list This feedback does not check for semantic correctness and should neither reinforce nor discourage the current strategy
Always format your response in json format:
"think"; "", // str: Your thought
"subtasks"; [...], // [ist[str]: The updated subtask list for completing the task. If your current task be executed directly from valid actions, the list should include only that action. If the task is done, i.e. no remaining subtasks, the updated subtask list should be empty. }
Below is description of the environment:
You robot in kitchen environment. The objects in the kitchen and your goal are described
in the Observation. The various types of objects in the kitchen include
Station: A location in the kitchen where can perform special actions, e.g. cooking or cutting
Item: An object that can be picked up and potentially used in Station kitchen Container: An object that can hold meals, e.g. a pot or pan
Player: Robots, including you, that are present
Meal: mixture ingredients contained within a Container
The rules of the environment are as follows:
A Player can only hold single Item at time
27

---

An Item must be placed on Station to perform an action on it Station must contain single Item to perform action
Items can only be stacked on top of one another, but not underneath Container must contain a Meal have items added to A Meal can be transferred between Containers
When you cut an item, you must cut 3 times in succession, not immediate Station/Board when it's occupied
You can't place object directly by another object. It's impossible to stack two items side by side on the same Station/Board. Otherwise you will stack on it. You might want to remove the object underneath first.
If you cook item, it is fully cooked after timesteps, not immediate. This is asynchronous (only consumes one action)
If you fry item, it is fully fried after 3 timesteps, not immediate. This is asynchronous (only consumes one action)
If you boil an item, it is fully boiled after timesteps, not immediate. This is asynchronous (only consumes one action)
there's nothing else you can while waiting for an item finish cooking / frying / boiling, you have to generate n 'Do Nothing' actions,
the number of timesteps remaining until the item is finished cooking / frying / boiling
Follow this recipe guide to learn to make food Robotouille:
Sandwich On a empty table, put a slice of bread, stacked on prepared ingredients, stacked on another slice bread. The bread must directly touch the table.
Hamburger On a empty table, A bottom bun, stacked on prepared ingredients, stacked a top bun. The bottom bun must directly touch the table.
Soup A pot is first filled with water, then boiled while ingredients are added, then served in bowl when ready.
D.3.2 ALFWorld
You can only pick up one item at a time. Always use Inventory to check what you have in possession when you are not sure plan to pick up item.
D.3.3 FEVER
You must propose series of task decomposition current observation and valid actions. will help you keep track of your progress by providing your previous thoughts and remaining subtasks.
action given the
You will receive the initial state and the goal as follows: Observation:
Claim: <some factual statement verify>
Solve clain-verification task with interleaving Thought, Action, Observation steps. Thought can reason about what you know so far and what you need check next.
Action must be one of:
1. Search [Entity] searches exactly that Wikipedia entry and returns the first paragraph if found; if not, returns a list of similar titles try.
2. Lookup[string] returns the next sentence in the current passage containing that exact string.
3. Finish(answer) ends the task by outputting one of: SUPPORTS, REFUTES, or NOT ENOUGH INFO.
28

---

Some important reminders: Only use Finish(answen when you ree confident no further lookup or search can change your decision.
Always format your response in json format:
"think": "", "subtasks": [...],
}
E
Social Impacts
ReCAP is a general-purpose framework designed to enhance the long-horizon reasoning and planning capabilities of language model agents. Its potential positive societal impacts span multiple domains: in education, ReCAP can enable tutoring agents that adaptively break down complex learning goals into structured steps; assistive robotics. may support more reliable household or caregiving robots that execute long-horizon tasks with contextual awareness; and in scientific discovery, it could help automate complex experimental or literature-bast based reasoning pipelines.
While ReCAP introduces no new content generation capabilities, it enhances the decision-making structure of existing language models. As such, it does not pose significant new risks related to misin- formation, bias, or autonomy beyond those already present in the underlying LLMs. Nevertheless, any increase in agent autonomy warrants careful consideration. In applications with safety-critical consequences--uuch as healthcare, law, or finance-explicit validation, oversight, and transparency mechanisms should be incorporated before deployment.
We encourage future work to explore safeguards, such as interpretable reasoning trees and confidence- aware action proposals, ensure that recursive planning frameworks like ReCAP remain aligned with human oversight and accountability. Overall, we believe ReCAP promotes safer long-term reasoning in LLM agents and opens promising directions for building trustworthy Al systems.
29


Reviews:
[{"review_id": "bSUOQ1CQpU", "reviewer": "Reviewer_5RPg", "summary": "The authors suggest the limitations of prior LLM agents, such as ReAct and Reflexion, that tasks that require long-horizon interactions would make it challenging for their contexts to fit in LLMs' context windows, which can harm their capabilities in complex scenarios. As a solution, the authors propose Recursive Context-Aware reasoning and Planning (ReCAP). With ReCAP, LLM agents can recursively create and execute subtasks where the execution contexts are managed in a tree. Also, it is capable of updating the rest of the plan (which consists of subtasks). Empirically, they perform evaluation of ReCAP agent on Robotouille, ALFWorld, and FEVER and demonstrate that it outperforms the baseline approaches including ReAct, Act, and CoT.", "questions": "Please take a look at the weaknesses above. I may update my score based on the author response to the weaknesses mentioned (both the originality and empirical justification).", "limitations": "Yes, they discuss the proposed method's limitations.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 1, "strengths_and_weaknesses": "Strengths\n- A sequential execution of some earlier LLM agents has clear limitations in their abilities to solve complex tasks, and tackling such limitations by introducing a hierarchical execution structure with recursion is a reasonable direction. Often, complex tasks can be decomposed into smaller subtasks, where solving such smaller tasks is easier in general.\n- The authors provide multiple analyses of how the design of the proposed method, ReCAP, is helpful in solving the tasks from the benchmarks in different aspects, including horizons, recursion depths, and context lengths.\n\nWeaknesses\n- One of my major concerns about this work is that there exist similar prior approaches with even some overlap in the target benchmarks, which are not mentioned in this submission: THREAD (\"THREAD: Thinking Deeper with Recursive Spawning\", appeared online on May 27th, 2024) and REPL-Plan (\"Interactive and Expressive Code-Augmented Planning with Large Language Models\", appeared online on Nov 21st, 2024). These methods have the ability to create and spawn subtasks and adaptively plan next steps based on the execution results and observations, with the managed contexts. There could be differences to make this submission unique by its own, but in order to make this a case, such existing work should be discussed and compared. Please note that the NeurIPS FAQ (https://neurips.cc/Conferences/2025/PaperInformation/NeurIPS-FAQ) suggests \"we do not distinguish arxiv papers and other published (conference & journal) papers, and the Contemporaneous-Work rule applies in the same way.\"\n- In addition to the concern about the originality and methodological comparison with existing work, empirically, the existing papers mentioned above report >95% performance on ALFWorld with GPT-3.5 whereas this work reports 91% with GPT-4o on ALFWorld, which gives the existing work an empirical edge. While I'm not suggesting that this tendency would necessarily hold for other benchmarks, I'm rather suggesting that given the existing methods with similarities, including those would help to provide empirical justifications of how well this method performs.", "was_revised": true, "final_justification": "I appreciate the authors' response to my review.\n\nWhile I don't fully agree with some of the points and the claim that the proposed approach is \"fundamentally different\" from the prior work given the current response, I think the suggested comparison can be a fair starting point for updating the manuscript.\n\nBased on that, I am increasing my score, but as acknowledged by the authors, the empirical comparison with the prior work may need some more work.", "rebuttal": "Thank you for your thoughtful comments. We address the two concerns raised as follows:\n\n## Comparison with THREAD and REPL-Plan\n\n- We appreciate the reviewer pointing out THREAD and REPL-Plan. While these works also explore subtask decomposition and recursive planning, they are fundamentally different from our method in key aspects:\n    - **THREAD** executes recursive subtasks by **creating new prompts with isolated subgoal descriptions**, discarding the broader context in each recursive call. This leads to a **lack of contextual continuity**, which can often cause infinite recursion or duplicated goal generation (e.g., repeatedly suggesting \"make breakfast\" at different levels of the same task). \n    - **REPL-Plan** depends on an **external code execution environment** to run and maintain LLM-generated program states, which adds system complexity. It also encourages the reuse of previously generated functions, which can lead to **over-reliance on prior trajectories** and reduce the agent’s ability to react to recent changes in the environment.\n    - In contrast, **ReCAP maintains a dynamic context tree**, where **all steps share a bounded, global memory window** (64-turn sliding context). When backtracking, we **inject structured context from the tree** back into the prompt to resume reasoning with full awareness of the hierarchical state, greatly reducing repeated errors and enabling effective few-shot prompting.\n    - Empirically, we re-implemented the THREAD prompting strategy and evaluated it on Robotouille. It achieves only ~33% success rate on high-difficulty tasks, while ReCAP achieves over 60%, underscoring the advantage of using a persistent, structured memory across planning levels. As for REPL-Plan, we would have liked to test it on Robotouille; however, implementation details are not publicly available.\n- We will revise the paper to explicitly cite and discuss these works in Section 2.2, and we thank the reviewer for encouraging this clarification.\n\n## Clarification on ALFWorld Empirical Results and ReAct Comparison\n\n- We would like to clarify that our evaluation methodology is more stringent than prior work, including ReAct:\n    - While **ReAct reports pass@6** (i.e., selecting the best result from 6 independent runs), our paper reports **pass@1**, which reflects a stricter and more realistic single-shot success rate.\n    - Additionally, in the ReAct experiments, they used **three** example trajectories for few-shot demonstrations, whereas we use only **one**.\n    - Despite this stricter setting, our method achieves 91% accuracy on ALFWorld, demonstrating the **efficiency and reliability** of our hierarchical reasoning approach.\n\n- These differences in evaluation setup mean that direct comparisons with ReAct and related baselines may underestimate our gains. We will explicitly clarify this in the updated version.\n- Furthermore, our contributions focus on long-horizon tasks with recursive recovery, which go beyond the settings optimized by ReAct and demonstrate improvements in failure-prone environments such as Robotouille and FEVER."}, {"review_id": "mG08PNIp6V", "reviewer": "Reviewer_q8CA", "summary": "ReCAP introduces a hierarchical prompting framework that equips LLM agents with a dynamic context tree to record recursive subtask decompositions, intermediate observations, and reasoning traces, enabling robust long-horizon planning with adaptive backtracking. Without any additional model training, it achieves substantial zero-shot gains—up to a 32 pp absolute improvement on Robotouille. It consistently outperforms sequential prompting baselines across embodied and symbolic benchmarks (ALFWorld, FEVER), demonstrating both improved context management and failure recovery in multi-step tasks.", "questions": "- The paper reports overall success‐rate improvements, but does not break down failure modes: could the authors provide a taxonomy of errors and their relative frequencies?\n- Can the authors quantify the additional latency and memory overhead introduced by maintaining and updating the context tree, perhaps with empirical measurements as task depth increases?", "limitations": "yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Pros\n- Extends an LLM’s effective reasoning horizon by integrating a dynamic context tree directly into the prompting loop, keeping high-level intentions tightly coupled with ongoing decisions.\n- Demonstrates substantial zero-shot performance gains (e.g. +32 pp absolute on Robotouille) without any additional model training or fine-tuning.\n- Employs adaptive backtracking to recover from low-level failures by revisiting and refining higher-level goals, improving robustness in long-horizon tasks.\n- Remains model-agnostic and broadly applicable across different benchmarks and LLM families, thanks to its purely prompt-based design.\n\nCons\n- Performance improvements can be modest on shorter or less structured tasks, making the added complexity feel disproportionate in those scenarios.\n- Validations are limited to simulated and symbolic benchmarks; real-world applicability under noisy, partially observable conditions remains untested.\n- Relies on the underlying LLM’s token capacity to store the context tree—extremely long or deeply branched tasks may still exceed limits despite hierarchical structuring.", "was_revised": true, "final_justification": "While the authors have fully addressed the computation overhead concern by clarifying their bounded context‐tree design, key weaknesses, including modest gains in certain tasks, and lack of real-world validation, remain unaddressed. These unresolved issues continue to cap the paper’s overall impact.", "rebuttal": "We sincerely thank the reviewer for the constructive feedback and helpful questions. Below, we address the specific concerns in detail:\n\n---\n\n### Q1: Breakdown of Failure Modes\n\nWe appreciate the suggestion to provide a taxonomy of failure modes. In our extended analysis (Appendix B.2), we include subtask-level performance across Robotouille. Notably, in the most complex tasks—where baseline methods (e.g., ReAct) often fail entirely—ReCAP achieves up to 60% accuracy, demonstrating that our improvements become more pronounced in high-difficulty settings.\n\nRegarding failure types, we have observed two dominant patterns:\n- First, **ReAct-style methods** frequently enter infinite loops due to incorrect planning decisions encoded in the prompt. Once a faulty trajectory is added to the context, the model tends to repeat it indefinitely. This behavior is particularly difficult to recover from without external resets.\n- Second, since ReAct does not \"inject\" or compress its history when generating new thoughts and actions, it sometimes loses track of its earlier plans and ceases to make progress.\n- In contrast, **ReCAP rarely loops**, as our dynamic context tree enables backtracking and pruning of failed subtrees. Our errors are instead often due to task horizons exceeding the current maximum depth, which can be gracefully handled with bounded memory and prompt reuse.\n\n---\n\n### Q2: Latency and Memory Overhead of the Context Tree\n\nOur system is explicitly designed for bounded and efficient memory use:\n- The context is capped at 64 dialogue turns, and each turn averages approximately 200 tokens, amounting to only ~10% of GPT-4o’s maximum context length. This ensures ample headroom and avoids overflow in nearly all practical scenarios. Older turns beyond the window are automatically removed, ensuring that memory usage remains within safe bounds.\n- At each reasoning step, only the path from the root to the current node is used for prompting, so memory and compute costs scale with path depth, not with the entire tree size.\n- Non-active paths in the tree are retained for offline retrieval or debugging purposes, but do not participate in inference, contributing negligible overhead at runtime.\n\nAs a result, our method consistently maintains fixed-length active prompts during execution. This leads to stable latency and memory usage even as task depth increases and avoids the degradation typically seen in passive context accumulation strategies.\n\nWe will clarify these memory and latency design considerations in the main paper and include empirical measurements and profiling in the supplemental material."}, {"review_id": "xwqzltBsY8", "reviewer": "Reviewer_cwmR", "summary": "In the vein of ReAct, Reflexion and similar works, the authors introduce ReCAP, a new LLM-based online planning methodology. The authors state that what separates ReCAP from previous work is that it autonomously and dynamically generates sub-tasks which are placed in a sequential dependency tree, meaning that coupled tasks appear closely together. Additionally, the dynamic nature allows ReCAP to adapt when subtasks or actions fail.\n\nReCAP is evaluated on three domains and compared to several common baseline LLM-planning strategies. ReCAP outperforms the baselines, especially in the tasks with more steps and longer dependencies.", "questions": "1. What does it mean if a completed subtask is \"pruned\"? (line 111)\n2. What are some \"fundamental mistakes\" exhibited by ReACT? (line 218)\n3. How is the one-shot prompt designed? Does it exemplify high-level subtask decomposition, selection of an atomic leaf action or both?\n4. What \"Level\", if any, was used for the base experiments? Additionally, how is the LLM informed about the level limit?\n5. How does ReCAP compare with e.g. ReAct regarding token usage?\n6. What information is propagated up from a completed subtask? As discussed in the ablation study, it's not just the status thereof.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The introduced approach of ReCAP is reasonable and motivated. Additionally, the experimental results showcase performance increases, likely without introducing overly much overhead. While some details on the prompting are unclear, it is also generally easy to follow and it would be possible to re-implement based on this.\n\nAn ablation study is also performed. While the results therein are mixed, there are some interesting results such as showing that further limiting the maximum depth might be preferable (Level 3 never performed worse than the original, usually outperforming it).\n\nThe discussion on related works is somewhat limited and could be expanded with other works which for example use LLMs to explicitly decompose tasks, e.g., MLDT (https://www.springerprofessional.de/en/mldt-multi-level-decomposition-for-complex-long-horizon-robotic-/50350624) and Compositional Foundation Models for Hierarchical Planning (https://openreview.net/forum?id=dyXNh5HLq3), or perform tree-based search, e.g., RAP (https://openreview.net/forum?id=VTWWvYtF1R). There's also concurrent work, e.g., Hierarchical Planning for Complex Tasks (https://arxiv.org/abs/2504.04578) and HyperTree (https://openreview.net/forum?id=45he3Ri6JP&noteId=a53sNTHN6D), published closer to the NeurIPS submission deadlines. Discussing these or other related works in relation to ReCAP would further strengthen the paper.", "was_revised": true, "final_justification": "The authors provided detailed answers to my questions and patiently addressed my concerns, going so far as to run additional experiments.", "rebuttal": "We sincerely appreciate the reviewer’s thoughtful questions and engagement with our work. Please find detailed answers below:\n\n---\n\n**Q: What does it mean if a completed subtask is \"pruned\"? (line 111)**  \n“Pruned” simply means that the subtask is removed from the list of remaining subtasks after successful execution. This is done by the LLM when it receives the updated observation and its previous subtask list, and then removes those that have already been completed.\n\n---\n\n**Q: What are some \"fundamental mistakes\" exhibited by ReAct? (line 218)**  \nBy “fundamental mistakes,” we refer to errors such as executing subtasks in the wrong order, failing to verify preconditions, or forgetting multi-step atomic operations (e.g., slicing requires three cut actions in Robotouille). These issues often arise from ReAct’s lack of explicit backtracking or environment re-checking mechanisms, as well as context overflow in long-horizon tasks. See Figure 3 and Section 4.1 for an example.\n\n---\n\n**Q: How is the one-shot prompt designed? Does it exemplify high-level subtask decomposition, selection of an atomic leaf action, or both?**  \nThe one-shot prompt is a compressed trace of a full task trajectory, including both high-level subtask decomposition and leaf-level atomic actions. Repeated patterns (e.g., “cut three times”) are abbreviated for space, but both planning and execution aspects are covered.\n\n---\n\n**Q: What \"Level,\" if any, was used for the base experiments? Additionally, how is the LLM informed about the level limit?**  \nWe did not impose any level limit in our base experiments. The LLM is not explicitly constrained to a maximum recursion depth; rather, recursion is guided by task structure and typically stabilizes at depth 3–5 in practice.\n\n---\n\n**Q: How does ReCAP compare with, e.g., ReAct regarding token usage?**  \nAs stated in Section C of the appendix:  \nFor ALFWorld, the total cost of running all 134 tasks in the test set is 37.89 USD using ReAct, and 118.40 USD using ReCAP—approximately three times the cost and token usage of ReAct. We identified that the extra cost mainly comes from the additional reasoning traces in the input and the extra steps required for intermediate task decomposition.\n\n---\n\n**Q: What information is propagated up from a completed subtask? As discussed in the ablation study, it's not just the status thereof.**  \nWhen a subtask completes (successfully or not), the following information is passed to the parent node:\n- The completed subtask name\n- The latest environmental observation\n- The parent task name\n- The parent's previous thought trace (`think_list`)\n- The parent's previous subtask list\n\nThis information is used to construct a new prompt for the parent node, enabling the LLM to revise its plan and reasoning. See Appendix E.1.3 (Leaf Completion Prompt) and E.1.7 (Non-Leaf Backtracking Prompt) for examples."}, {"review_id": "pl4G5ovu7R", "reviewer": "Reviewer_qEKq", "summary": "This paper presents a novel approach for real-time planning with LLMs. The novelty relies on the use of an LLM to decompose problems into subtasks recursively until reaching primitive actions, while maintaining the decomposition tree with contextual information to interleave planning and execution.\n\nThe approach is tested over three problems, Robotouille, ALFworld and FEVER, and it is shown to improve performance over problems with long planning requirements and a concurrent goals.", "questions": "Is there any problem that requires interleaving tasks, where completing one task would make it impossible to complete the other? This can be illustrated by the Sussman Anomaly problem.\n\nIs there any problem in the experiments where a deadlock can occur, as in, the problem becomes unsolvable due to the execution of an action?\n\nCan you give insights into the size of the context tree and number of backtracks?\n\nCan you give insights into the runtime overhead and the increased number of LLM calls with respect to the baselines?\n\nGiven that the aim is to have real-time reasoning, how long does it take to return an action? What is the impact of different recursion levels in terms of time?", "limitations": "N/A", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "# Quality\n\nThe paper provides a sound algorithm describing the high level procedure followed to recursively decompose the problem and maintain the relevant data in each node. The experimental design is clearly presented, and the results are discussed in detail. \n\nThat said, a few experiments were missing in order to understand the complexity of the tasks and the context tree. No results are provided in terms of the number of backtracks, the number of LLM calls, or the size of the resulting context trees as a function of plan legth. See questions below.\n\n# Clarity\n\nThe paper is accessible and easy to follow at a high level. Certain sections would require more formal or precise definitions. For example, the setup for interleaving planning and execution is not clearly defined. I couldn’t understand how much time is allowed for each phase, or if this depends on the duration of the action execution. I couldn’t tell either if backtracking meant real backtracking in the environment, or backtracking  as in changing the chosen subtask or planned next action. This became clear in the experimental section, but not while reading about the method. In general, I would recommend adding text about how the problems are described and how prompts are designed. \n\nIn general, superlatives can be misleading. Stating that the results of LLMs using ReAct are “impressive” (line 26), over complex sequential reasoning is not well defined and contradictory. It is contradictory because the experimental results in this paper show that ReAct is not impressive over tasks with more than 10 actions. It is not clear either with respect to which measure or other computational approaches is the performance impressive. The adjective “complex” is ambiguous at this stage of the paper. What makes a problem to be “complex” is not a trivial statement. \n\nMinor comments:\n\n- Figure 1 is not referenced in the text, and it is not self-explainable. I don’t understand what the colours mean.\n- Add reference to the algorithm lines when describing it in section 2.3 and 2.4.\n- One shot example is referenced for the first time in line 128, but no context is provided to understand how is it used. This is partially due to the fact that the prompt structure is not provided.\n- extra dot (line 171)\n- Line 197-198 is repeated (see line 131)\n- Figure 3 does not add much with respect to the textual explanation, which does a great job already. It can be removed to make space for some of the experiments needed to answer the questions below.\n- It is unclear what does stale reasoning means (line 264).\n\n# Significance\n\nThe results are significantly better than baselines over long horizon planning, clearly showing the potential of representing the context as a recursive tree, as well as providing the right level of detailed context.\n\n# Originality\n\nThe paper provides a valuable insight of treating context as a non-linear data-structure and showing how it can improve the reasoning ability for long-term planning that interleaves reasoning and execution. The only caveat is that the paper needs better positioning with respect to work on hierarchical task decomposition in planning, e.g. Hierarchical Task Networks (HTN), and clarify how it differs from HTNs. The first claim of novelty should be clarified that it is in the context of ReAct, but that recursive hierarchical decompositions has a large body of research. The problem of interleaving reasoning and acting could also be placed in the broader context beyond the approaches used by LLMs (line 286). See work in “Ghallab, Malik, Dana Nau, and Paolo Traverso. Automated planning and acting. Cambridge University Press, 2016.”", "was_revised": true, "final_justification": "After the discussion with authors I'm confident that they can address the issues in the discussion, hence I raise my rating to 4.", "rebuttal": "We thank the reviewer for the valuable feedback and thoughtful suggestions. Please find our detailed responses below:\n\n---\n\n### Terminology Clarifications: “Complex” and “Impressive”\n\nWe agree that certain terms (e.g., “complex” and “impressive”) could benefit from more precise framing.\n\n- **On “impressive” (line 26):**  \n  Our intention was to acknowledge prior work such as ReAct and Reflexion, which have demonstrated strong performance on short-horizon tasks. However, we agree that this adjective can be misleading in light of our results. We will revise this statement to focus on specific capabilities (e.g., short-term planning, interleaving reasoning with action) rather than making broad claims about performance.\n\n- **On “complex” tasks:**  \n  We recognize that “complex” is a context-dependent term. In our paper, we primarily refer to long-horizon, multi-stage, and feedback-driven tasks—particularly those requiring more than 10 interleaved reasoning–execution steps—as “complex.” We will clarify this definition in the introduction. To support this empirically, we provide per-task breakdowns of ReAct’s failure modes in Appendix B, demonstrating that its success rate drops significantly on Robotouille tasks with longer step ranges or asynchronous subgoals.\n\n- **On the planning/execution interface and backtracking:**  \n  Thank you for highlighting this point. Backtracking in ReCAP is not a physical rollback in the environment, but rather refers to revisiting the parent subtask with updated observations and regenerating the remaining plan. The environment only evolves forward. We will clarify this distinction in Section 3.2 and explicitly define the interleaving behavior in our setup description.\n\n- **On prompt construction and task goal encoding:**  \n  We appreciate the suggestion to improve our description of prompt construction and goal encoding. We include concrete prompt templates and examples in Appendix E, and will reference these earlier in the main text to aid clarity.\n\n---\n\n### Interleaving and Conflicting Subgoals (Sussman Anomaly)\n\n**Q: Is there any problem that requires interleaving tasks, where completing one task would make it impossible to complete the other?**\n\nYes, interleaving tasks is necessary in problems where subgoal interactions can lead to conflicts if executed in isolation. ReCAP handles such cases via recursive execution and its dynamic context tree. After each subtask execution, ReCAP backtracks to the parent node, which re-evaluates the subgoal structure using updated environment observations and prior reasoning stored in the context tree. This mechanism allows the system to detect when earlier decisions may hinder future progress and refine the subtask plan accordingly—enabling the interleaving of dependent tasks without redundant trial-and-error.\n\n---\n\n### Deadlocks and Irreversible Actions\n\n**Q: Is there any problem in the experiments where a deadlock can occur, i.e., the problem becomes unsolvable due to the execution of an action?**\n\nYes, this can occur in Robotouille, particularly in asynchronous tasks where certain resources (e.g., cutting boards, tools, ingredients) can be occupied or transformed in ways that block progress. For instance, placing an ingredient on an already-occupied tool or prematurely modifying an item (e.g., slicing before transferring) can make it temporarily unusable or incompatible with later subgoals, potentially leading to deadlocks in ReAct planners. Such failure modes are frequently observed in ReAct (see Figure 3 and Section 4.1), where agents enter infinite action loops when failing to account for dynamic environment constraints.\n\nReCAP avoids such deadlocks by continually re-evaluating the plan via backtracking. After each subtask execution, it revisits the parent node with updated observations and reasoning, allowing it to detect unintended consequences and revise the subtask tree accordingly. This mechanism enables ReCAP to recover from potential deadlock situations that would otherwise halt sequential planners.\n\n---\n\n### Context Tree Size and Backtracking\n\n**Q: Can you give insights into the size of the context tree and number of backtracks?**\n\nThe size of the context tree varies with task complexity and execution dynamics. For medium-complexity Robotouille tasks (e.g., asynchronous task #7), we observe an average of 100–120 nodes per trajectory, with approximately 40 leaf nodes (i.e., primitive executable actions). The remaining nodes correspond to higher-level subtasks generated via recursive decomposition. As ReCAP traverses the context tree in a depth-first fashion, the number of backtracks is equal to the number of nodes minus one. We appreciate the suggestion and will consider including more detailed statistics on tree structure and backtracking dynamics in future revisions.\n\n---\n\n### Runtime Overhead and LLM Call Volume\n\n**Q: Can you give insights into the runtime overhead and increased number of LLM calls compared to the baselines? What is the impact of recursion levels in terms of time?**\n\nReCAP introduces additional LLM calls due to its recursive decomposition and backtracking mechanism, but this overhead is necessary to support context-aware reasoning in long-horizon settings.\n\n- For a representative Robotouille task (e.g., synchronous/6_lettuce_tomato_cheeseburger), ReCAP issues an average of ~75 LLM calls per episode (std ≈ 28), compared to ~20–25 for ReAct. The increased call volume arises from ReCAP's subgoal-level prompts and backtracking updates, which improve execution reliability and success rates.\n\n- **Latency:** Each LLM call takes 1–2 seconds on GPT-4o, depending on prompt length and model load. Thus, the time to return a single action is typically 2–3 seconds in practice. With ~75 LLM calls, this translates to a total runtime of approximately 2.5–4 minutes per episode.\n\n- **Recursion Depth:** Tasks with recursion depth up to 3–4 (which is sufficient for most cases) complete within reasonable real-time latency bounds. Deeper recursions (5+) offer marginal performance gains but increase delay, suggesting that shallow recursion achieves a good balance between speed and performance.\n\nTo further support real-time applications, we plan to explore:\n- Batching multiple subtasks per call when possible\n- Model specialization, where a small, fast model executes leaf nodes\n- Prompt compression and dynamic context pruning to reduce token-level latency\n\n---"}]

Author rebuttal:

Meta-review: ### (a) Summary of Claims
The paper introduces `Recursive Context-Aware reasoning and Planning (ReCAP)`, a novel framework for LLM agents designed to tackle complex, long-horizon tasks. The core innovation is the use of a dynamic context tree, which allows the agent to recursively decompose problems into subtasks while maintaining a structured memory of the overall plan and execution history. The authors claim that this hierarchical approach enables robust failure recovery and context management, leading to significant performance improvements over sequential agent frameworks like ReAct, particularly in tasks with long dependencies.

### (b) Strengths
* Well-Motivated and Sound Approach: Reviewers consistently agreed that tackling the limitations of sequential LLM agents via a hierarchical, recursive structure is a reasonable and well-motivated direction. The core idea of using a context tree is a valuable insight for improving long-term planning.
* Strong Empirical Gains: The paper demonstrates significant performance improvements over baselines on several benchmarks, especially in tasks with long planning horizons, clearly showing the method's effectiveness.

### (c) Weaknesses and Rebuttal Summary
* Reviewer 5RPg initially questions the paper's originality and empirical justification. The reviewer pointed out two similar prior works, THREAD and REPL-Plan, which were not discussed or compared in the submission.
    * The authors responded with a detailed rebuttal addressing these concerns in two main parts:
        * Conceptual differences between ReCAP and THREAD and REPL-Plan.
        * Stricter evaluation is considered in this manuscript than in prior work.
    * Reviewer cwmR also asked for additional experimental comparison with THREAD on ALFWorld, given its high reported success rate. Authors then claimed that under standard, constrained evaluation settings, THREAD failed to solve any of the tested ALFWorld tasks.
    * Reviewer 5RPg acknowledged authors' detailed rebuttals and new experimental findings: While not fully agreeing that ReCAP was "fundamentally different" from prior work, the reviewer found the suggested comparisons and new results to be a "fair starting point for updating the manuscript." 
* Reviewer q8CA initially identified key weaknesses, including (1) modest performance on shorter tasks and a lack of real-world validation, (2) a breakdown of the common failure modes, and (3) quantification of the latency and memory overhead introduced by the context tree. 
    * The authors provided a direct and comprehensive rebuttal in terms of failure modes and overhead.
    * The reviewer was satisfied with the authors' response, but still criticized the modest gains in certain tasks and the lack of real-world validation. 
* Reviewer cwmR initially asked for more discussion of related work, as well as the experimental results for THREAD. During the rebuttal, the authors provided detailed answers, and the reviewer recommended acceptance.
* Reviewer qEKq initially raised concerns regarding clarity, missing experiments, and positioning. The authors provided a detailed rebuttal where they clarified ambiguous terminology, provided concrete system statistics, and explained deadlocks and irreversible actions. 
    * The reviewer engaged in a follow-up discussion, asking for more detailed information to better understand the system's behavior.
    * The authors responded promptly and thoroughly. They provided the requested tree statistics, gave a more precise definition of a "backtrack" event, and presented a detailed, step-by-step trace of ReCAP solving a "burger anomaly" task.
    * The reviewer was highly satisfied with the authors' detailed and insightful responses during the discussion.

### (e) Reasons for Acceptance
Given the strengths, rebuttal summary, and the positive consensus that emerged from the review process, AC would like to recommend the acceptance of this manuscript.
Decision: Accept (poster)