ReCAP: Recursive Context-Aware Reasoning and Planning for Large Language Model Agents
Problem Statement
LLM agents on long-horizon tasks lose track of goals. Sequential methods such as ReAct-style prompting accumulate context drift and fall into repeated failure loops. Existing hierarchical methods split reasoning across levels, which either breaks continuity between parent and child plans or adds large runtime and token overhead. A method that is both coherent across levels and cheap to run would make agents more reliable at multi-step planning and re-planning in dynamic environments.
Key Novelty
- Plan-ahead decomposition: the model generates a full subtask list, executes only the first item, then refines the remaining items using new observations. This combines upfront planning with online re-planning.
- Structured re-injection of parent plans when a recursive call returns, so the model resumes with consistent multi-level context instead of a fragmented or summarized history.
- Memory-efficient execution that bounds the active prompt, so cost grows linearly with recursion depth rather than with the full interaction history.
Evaluation Highlights
- 32% gain on synchronous Robotouille under the strict pass@1 protocol
- 29% improvement on asynchronous Robotouille under pass@1, plus reported gains in subgoal alignment and success rate across several other long-horizon reasoning benchmarks (not named in the abstract)
Signal Assessment
Methodology
- Given a task, the LLM generates a complete ordered list of subtasks (plan-ahead decomposition) within a shared context.
- The first subtask is executed. If it is still complex, it is recursively decomposed the same way; if it is primitive, it is mapped to an environment action.
- When a subtask finishes, the parent's plan and goal are re-injected into the prompt in a structured form, and the model refines the remaining subtasks based on the new observations.
- Throughout recursion, the active prompt is bounded to the relevant multi-level context rather than the full trajectory, so token cost scales linearly with depth.
- The approach is evaluated on long-horizon benchmarks, including synchronous and asynchronous Robotouille, using strict pass@1 and comparing against sequential and hierarchical prompting baselines.
System Components
Generates a full subtask list for the current goal, commits only to the first step, and revises the remainder after execution feedback.
Recursively expands complex subtasks into sub-plans until primitive actions are reached, forming a dynamic task tree.
When control returns from a child subtask, restores the parent's goal and remaining plan in structured form so context stays coherent across levels.
Keeps the active prompt limited to the relevant hierarchical context, preventing unbounded history growth so cost scales linearly with task depth.
Results
| Metric/Benchmark | Baseline | This Paper | Delta |
|---|---|---|---|
| Synchronous Robotouille success (pass@1) | Prior prompting baseline (value not given in abstract) | ReCAP (value not given in abstract) | +32% |
| Asynchronous Robotouille success (pass@1) | Prior prompting baseline (value not given in abstract) | ReCAP (value not given in abstract) | +29% |
| Subgoal alignment (multiple long-horizon benchmarks) | Sequential/hierarchical prompting baselines | Substantially improved | Qualitative gain |
| Prompt cost scaling | Grows with interaction history (sequential) or high overhead (hierarchical) | Linear in recursion depth | Improved efficiency (qualitative) |
Key Takeaways
- For long-horizon agents, generating a full plan but committing only to its first step, then re-planning, is a cheap and effective middle ground between rigid upfront planning and purely reactive ReAct loops.
- Explicitly re-injecting the parent goal and remaining plan when a subtask returns is a simple, drop-in technique to reduce goal drift and repeated failure cycles in hierarchical agents.
- Bounding the active context to the current recursion path, instead of the full trajectory, can improve both reliability and token cost. This matters for production agents with deep task trees.
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.