Reflexion: Language Agents with Verbal Reinforcement Learning

Oct 2023 · Paper

---

1. Motivation

Reinforcement learning (RL) improves policies through gradient updates on scalar rewards, but applying RL to large language model (LLM) agents is expensive and often impractical: fine-tuning frontier models is costly or impossible via APIs, and rewards in interactive tasks (embodied environments, question answering, programming) are sparse and uninformative.¹ Reflexion asks whether the feedback signal of RL can be preserved while replacing the weight update with something an LLM already does well - reading and writing text. The hypothesis is that binary or scalar feedback, once “amplified” into a specific verbal lesson (“you kept searching the countertop, but the mug was in the cabinet”), can steer the next trial the way a policy-gradient step would.² This reframes agent improvement as a memory-engineering problem, an idea nearly every later agentic discovery system - from ReEvo to the AI Co-Scientist - reuses in some form.³

---

2. Methodology

2.1 Search Structure

Reflexion is an iterative trial-and-error loop over whole episodes, formalized as its Algorithm 1 “Reinforcement via self-reflection”:²

repeat until Evaluator pass or max trials:
    τ_t  = Actor(mem)                 # full trajectory of actions/observations
    r_t  = Evaluator(τ_t)             # scalar / binary / heuristic score
    sr_t = SelfReflection(τ_t, r_t)   # verbal lesson in first person
    mem  = mem ∪ {sr_t}               # episodic buffer, |mem| ≤ Ω

Search operates at the granularity of episodes, not tokens or steps: each iteration produces one complete trajectory, scores it, and distills one reflection. Three task families instantiate the loop: sequential decision-making (AlfWorld, ReAct Actor), single-step reasoning (HotPotQA, chain-of-thought [CoT] or ReAct Actors), and programming (HumanEval, MBPP, LeetcodeHardGym).²

2.2 State Representation

The policy is parameterized as $\pi_\theta(a_i \mid s_i)$ with $\theta = \{M_a, \text{mem}\}$: the frozen LLM $M_a$ plus memory. Two memory tiers exist: (i) short-term memory - the current trajectory history of action–observation pairs, analogous to RL state; (ii) long-term memory - stored self-reflection texts from past trials.² Long-term memory is deliberately bounded: “we bound mem by a maximum number of stored experiences, $\Omega$ (usually set to 1–3).”² The sliding window keeps the most recent 3 reflections for AlfWorld/HotPotQA and only 1 experience for programming tasks.²

2.3 Generation Mechanism

The Actor is a prompted LLM - GPT-3 for AlfWorld, GPT-4 for programming - using CoT or ReAct prompting, conditioned on observations plus the reflection buffer.² No gradients are computed anywhere; improvement is generated purely by re-prompting with accumulated verbal lessons. In the programming setting the agent additionally generates its own unit-test suite via CoT prompting (at most $n \le 6$ tests), filtered for syntactic validity by abstract-syntax-tree (AST) construction before execution.² The Self-Reflection model is itself an LLM prompted to convert the failed trajectory and its reward into a specific, actionable first-person hint.

2.4 Evaluation & Grounding

Three evaluator types are explored: (i) exact-match grading (HotPotQA binary success); (ii) hand-written heuristics for AlfWorld - reflect if the same action–response pair repeats for more than 3 cycles or the episode exceeds 30 actions (“inefficient planning”); (iii) self-generated unit tests executed against real compilers/interpreters (MultiPL-E for Rust).² The pass@1 claims for programming rest specifically on self-generated tests, not hidden ground-truth suites - a grounding choice with measured consequences (see §2.7).²

2.5 Memory / Information Flow

The information pipeline per trial is:

failed trajectory τ → scalar reward r → Self-Reflection LLM
    → verbal lesson sr ("semantic gradient")
    → append to episodic buffer (sliding window, Ω ≤ 3)
    → inject as context into next trial's Actor prompt

A HotPotQA ablation isolates the value of verbal distillation versus raw persistence: CoT(GT) plus episodic memory (raw last trajectory) versus CoT(GT) plus Reflexion - self-reflection adds an 8% absolute boost over raw episodic memory, showing that the compressed lesson, not mere trajectory replay, drives the gain.²

2.6 Selection & Propagation

There is no population and no selection operator: Reflexion is single-agent hill-climbing across trials. “Propagation” reduces to which experiences survive the sliding window - only the most recent $\Omega$ reflections persist - and the loop terminates on Evaluator pass or after 3 consecutive failed attempts per task (HotPotQA).² This makes Reflexion the minimal, non-evolutionary pole of the selection spectrum later populated by Promptbreeder’s tournaments and MAP-Elites’ archive elitism.

2.7 Anti-Slop / Anti-Hallucination Mechanisms

Controls are structural, not prompt-level. The AlfWorld heuristic explicitly targets hallucination (the agent believes it holds an item it does not) and looping; ReAct-only converges with a 22% hallucination failure rate that Reflexion largely eliminates via distilled self-hints.² For code, AST syntax filtering rejects malformed self-tests, and the paper honestly reports a false-positive analysis of its test suites: MBPP-Python’s false-positive rate of 16.3% versus HumanEval-Python’s 1.4% explains Reflexion’s underperformance on MBPP (Table 2).²

---

3. Results

• AlfWorld (134 tasks): ReAct+Reflexion solves 130/134 (97%), an absolute +22% over the ReAct baseline within 12 trials; ReAct-only plateaus at trials 6–7.²
• HotPotQA (100 questions): +20% over CoT/ReAct baselines; baselines show zero probabilistic recovery of failed tasks at temperature 0.7.²
• Programming pass@1 (GPT-4 Actor, Table 1): HumanEval-Python 91.0 vs GPT-4 base 80.1; HumanEval-Rust 68.0 vs 60.0; MBPP-Rust 75.4 vs 70.9; LeetcodeHardGym 15.0 vs 7.5; MBPP-Python 77.1 vs 80.1 - the one loss, attributed to test-suite false positives.²
• Ablation (HumanEval-Rust 50 hardest): full Reflexion 68%; removing self-reflection → 60% (no gain over base); removing test generation → 52% (worse than base - the agent makes harmful edits without grounding).²

Baselines were re-run by the authors under the same Actor models; independent evidence on other tasks (multiple-choice QA across 9 LLMs) found statistically significant gains for self-reflection generally ($p < 0.001$).⁴

---

4. Limitations & Assumptions

The authors concede Reflexion “may still succumb to non-optimal local minima” and depends entirely on the LLM’s self-evaluation ability - a weak reflector yields useless lessons.² Memory is a short sliding window; the authors suggest vector/SQL stores as future work.² Test-driven grounding fails for non-deterministic, impure, hardware-dependent, or concurrent code.² Most importantly, the headline 91% HumanEval figure is conditioned on self-generated tests with nonzero false-positive rates, so it should be read as “pass@1 against a self-authored oracle,” not hidden-test SOTA.²

---

5. Critical Analysis

• Distinctive strength: Reflexion isolates and quantifies the value of verbal memory - the +8% HotPotQA ablation over raw episodic memory is rare causal evidence that distilled natural-language lessons beat replay, and the omission ablations (reflection → no gain; tests → harmful) cleanly attribute gains to each component.²
• Structural weakness / trade-off: a single-agent, single-trajectory loop with $\Omega \le 3$ memory cannot accumulate population-level diversity; it trades exploration breadth for cheap, API-compatible improvement and inherits the reflector’s blind spots (MBPP’s false-positive tests silently certified wrong programs).²
• Connections: ReEvo directly extends Reflexion from binary rewards to comparative reflection over parent heuristics inside an evolutionary loop.³ FunSearch and AlphaEvolve replace the verbal buffer with an execution-grounded program database - the same “learn from evaluated history without weight updates” principle, grounded by compilers rather than self-report.⁵⁶ The MLE agents (AIDE, ML-Master, MARS, FM-Agent) inherit Reflexion’s reflect-on-failure debug loop and its self-test machinery, including the false-positive accounting problem.

---

6. References

Footnotes

1. Shinn et al., Reflexion (arXiv abstract): https://arxiv.org/abs/2303.11366 ↩

2. Shinn et al., Reflexion, NeurIPS 2023 (PDF v4): https://arxiv.org/pdf/2303.11366.pdf · proceedings: https://papers.nips.cc/paper_files/paper/2023/hash/1b44b878bb782e6954cd888628510e90-Abstract-Conference.html · code: https://github.com/noahshinn/reflexion ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷ ↩⁸ ↩⁹ ↩¹⁰ ↩¹¹ ↩¹² ↩¹³ ↩¹⁴ ↩¹⁵ ↩¹⁶ ↩¹⁷ ↩¹⁸ ↩¹⁹ ↩²⁰ ↩²¹ ↩²² ↩²³ ↩²⁴

3. Ye et al., ReEvo, NeurIPS 2024: https://arxiv.org/abs/2402.01145 ↩ ↩²

4. Renze & Guven, Self-Reflection in LLM Agents (2024): https://arxiv.org/abs/2405.06682 ↩

5. Romera-Paredes et al., FunSearch, Nature 625:468–475: https://www.nature.com/articles/s41586-023-06924-6 ↩

6. Novikov et al., AlphaEvolve: https://arxiv.org/abs/2506.13131 ↩