ReCAP: Recursive Context-Aware Reasoning and Planning for Large Language Model Agents

AI summary

Overview

Research area: Artificial Intelligence — LLM agents, long-horizon reasoning and planning, prompting frameworks.

Technical level: Intermediate to Advanced (requires familiarity with ReAct-style prompting, hierarchical planning, and agent benchmarks, though the core ideas are explained conceptually).

Scope: The paper introduces ReCAP, a recursive, context-aware prompting framework that shares a single evolving LLM context across multiple levels of task decomposition and shows pass@1 success-rate gains over sequential and hierarchical prompting baselines on four benchmarks.

What This Paper Is About

Large language models struggle with long-horizon tasks that require planning over many steps and re-planning when the environment pushes back. Sequential prompting methods tend to lose the original goal as early thoughts drift out of the context window, while hierarchical methods often fragment information by running subtasks in isolated contexts or by adding heavy runtime overhead. ReCAP's goal is to keep high-level intent and low-level actions aligned inside one shared, bounding LLM context so the agent can decompose, execute, backtrack, and refine without losing its plan.

Key Contributions

1. Plan-ahead task decomposition. Instead of emitting one subtask at a time, the model generates a complete ordered subtask list in a single pass, executes only the head item, and refines the remaining list once that item completes — preserving global intent and reducing plan drift.
2. Consistent multi-level context with structured re-injection. All recursion depths operate inside a single shared LLM context; when a subgoal resolves, the parent's latest thought and remaining subtasks are re-injected so reasoning stays continuous across levels rather than fragmenting into isolated prompts.
3. Memory-efficient, bounded execution. A sliding window of back-and-forth dialogue rounds (typically K = 64) keeps the active prompt at O(K · L̄) tokens, while external state and re-injected planning information scale as O(d · L̄) with tree depth d, so costs grow with path depth rather than total trajectory length.
4. Training-free evaluation under a strict pass@1 protocol. ReCAP is evaluated with one-shot prompting, no training, fine-tuning, retries, self-consistency, or ensembling across ALFWorld, Robotouille, FEVER, and SWE-bench Verified, with code and data released at https://github.com/ReCAP-Stanford/ReCAP.

Main Findings

• Large gains on long-horizon embodied tasks. On synchronous Robotouille, ReCAP reaches 70.0% success versus 38.0% for ReAct (reported as a 32% gain); on asynchronous Robotouille, 53.0% versus 24.0% (a 29% improvement). Both differences are reported with p-value < 0.001.
• Shorter horizons show smaller but consistent gains. On ALFWorld, ReCAP scores 91.0 versus 84.0 for ReAct (a 7% improvement); ADaPT is reported at 71.6 using GPT-3.5, and Act at 74.0.
• Knowledge-retrieval parity. On FEVER, ReCAP and ReAct both reach 63.5%, with CoT and Act at 58.5% and Standard at 53.5% — the paper attributes the lack of separation to short horizons (most instances need fewer than 10 actions).
• Best reported result on SWE-bench Verified among GPT-4.1-based methods. ReCAP scores 44.8 versus 39.58 for the mini-SWE-agent ReAct baseline. All 500 tasks were submitted without human intervention, 498 were successfully evaluated by the SWE-bench CLI, and 224 were solved.
• Robustness across model families. On Robotouille tasks #2, #4, and #6, ReCAP beats ReAct for every model tested: GPT-4o 90.0 vs 63.0, Qwen2.5-32B 33.0 vs 10.0, Qwen2.5-72B 53.0 vs 23.0, LLaMA-4 (400B) 60.0 vs 37.0, and DeepSeek-V3 (671B) 87.0 vs 57.0.
• Failure modes differ qualitatively. ReAct frequently enters infinite loops when a station is blocked (repeatedly stacking and unstacking around the blocker), whereas ReCAP detects the loop, backtracks, and revises the plan — for example by moving the blocking lettuce before cutting.
• Ablations show reasoning traces and depth matter. On the long-horizon Robotouille task synchronous/6_lettuce_tomato_cheeseburger, success drops from 80 for the original variant to 60 (no_think), 55 (name_only), and 10 (level_3) / 0 (level_2), while think_many (70), level_5 (70), and level_4 (60) remain comparable. All structural variants used a context length of 128 messages.
• Resulting task trees are shallow and wide. Averaged over 20 runs of that same task, tree depth is 3.4 and branching factor is 12.5, which also implies smaller external state storage requirements.
• Cost is higher. On Robotouille, a complete run averages 74.95 LLM calls (SD 27.87) and 7.77 USD (SD 3.45). On ALFWorld, running all 134 test tasks costs 37.89 USD with ReAct and 118.40 USD with ReCAP — roughly three times as much, attributed mainly to extra reasoning traces in the input and extra steps for intermediate decomposition.

Methodology in Plain English

ReCAP treats task solving as a recursion inside one continuously updated conversation with the model. Starting from the task description and initial observation, the model produces a thought plus an ordered list of subtasks. The agent then tries only the first subtask. If that subtask is something the environment can directly execute (a primitive action), the environment runs it and the resulting observation is appended. If it is not primitive, ReCAP recurses, carrying the parent's thought, list, and current subtask along, and decomposes further until it reaches executable actions.

The distinctive step happens on the way back up. After a child subtask finishes — successfully or not — the parent's latest thought and its remaining subtasks are re-injected into the same context, and a refinement function revises the plan in light of what just happened. This is how the agent prunes dead ends and recovers from blocked or failed steps without ever discarding the global goal. An external tree structure stores per-node (thought, subtask-list) pairs and overwrites them with refined versions, so only the root-to-current-node path stays active.

To keep the prompt from growing without bound, ReCAP uses a sliding window over recent dialogue rounds (typically 64), deleting the oldest rounds while retaining the fixed initial prompt with few-shot examples. Because few-shot examples live in that single shared context, they are injected once rather than duplicated at every recursive call. A history-length cap and a fallback for context-length-exceeded errors manage truncation, and the full environment rule text is re-prepended every 10 LLM invocations to counter "rule amnesia."

Evaluation covers four benchmarks with different horizon lengths and action-space sizes: ALFWorld (symbolic household tasks, official unseen split), Robotouille (embodied cooking, 10 synchronous recipes requiring 10–57 steps and 10 asynchronous recipes requiring 21–82 steps, each with 10 official instances), FEVER (200 randomly sampled claims, seed 42, hard cap of 10 reasoning steps), and SWE-bench Verified (500 tasks). Baselines include Standard, CoT, ReAct, Act, and a re-implementation of ADaPT on Robotouille. Main experiments use GPT-4o (2024-08-06) at temperature 0.5 with a max_step_multiplier of 4 and an ALFWorld timeout of 50 steps; SWE-bench uses GPT-4.1 (2025-04-14), zero demonstrations, and temperature zero, implemented by replacing SWE-agent's ReAct memory with ReCAP.

Why This Matters

Impact on research. The paper challenges the assumption that an LLM's context must be a flat, linear dialogue history. It shows that how context is organized and selectively re-injected can matter as much as how much context is available, and it offers a training-free, prompt-only alternative to methods that depend on fine-tuning, external code interpreters, or multi-trial self-critique. Because the framework is model-agnostic, it also provides a reusable design pattern for recursive agent architectures.

Real-world applications:

• Software maintenance agents that resolve repository-level GitHub issues by composing multi-step code edits in an effectively unbounded action space.
• Robotic and embodied assistants that must interleave and re-plan subgoals under resource contention or delayed actions, such as cooking or household tasks.
• Knowledge-verification pipelines that classify claims against retrieved evidence through a small symbolic action API.
• Multi-step workflow automation where task decomposition and mid-execution revision are needed without retraining models.

Industry relevance. The paper reports transparent cost data — roughly three times ReAct's cost on ALFWorld (118.40 USD vs 37.89 USD for all 134 tasks) and 7.77 USD per Robotouille run — which is directly relevant to teams weighing accuracy gains against API spend and latency. The finding that gains grow with task length while short-horizon performance does not degrade provides a practical guide for when to deploy recursive structuring.

Future Directions

1. Modularize planning and execution. Decouple high-level decomposition from low-level action, potentially letting a large LLM handle planning while a lightweight model handles primitive actions.
2. Reduce interaction cost. Apply reasoning compression, dynamic step control, or API batching to shrink the extra overhead that ReCAP's longer trajectories introduce.
3. Structure memory beyond a dialogue history. Explore organizing memory as an executable graph for more targeted retrieval, possibly combined with reinforcement learning or memory-aware routing to optimize reasoning under context constraints.
4. Reduce sensitivity to the underlying model. Because all decomposition, execution, and backtracking decisions are delegated to the LLM without external validation, errors can propagate when the model misinterprets feedback — an open problem the paper explicitly flags.

Target Audience

This paper suits LLM agent researchers and engineers building multi-step reasoning systems, particularly those working on long-horizon planning, context management, or agent memory architectures. It is also useful to practitioners comparing prompting strategies for embodied task execution (ALFWorld, Robotouille) or automated software repair (SWE-bench Verified), and to readers interested in how context organization — rather than raw context length — affects agent reliability.

Authors’ 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.