Reflexion

Full title: Reflexion: Language Agents with Verbal Reinforcement Learning Authors: Noah Shinn, Federico Cassano, Edward Berman (Northeastern University), Ashwin Gopinath (MIT), Karthik Narasimhan, Shunyu Yao (Princeton University) Venue/year: NeurIPS 2023; the local PDF is the arXiv v4 preprint (Oct 2023), marked "Preprint. Under review." arXiv: https://arxiv.org/abs/2303.11366 Local PDF: /Users/moscalej/Documents/Onep/research-papers/2303.11366-reflexion.pdf

Why this paper matters

Reflexion is the founding paper of verbal reinforcement learning: instead of updating weights with a scalar reward, the agent converts environment feedback into a written self-critique, stores it in an episodic memory, and conditions the next attempt on those stored lessons (§1, §3). The "policy" being optimized is not the LLM's parameters but its memory contents. This reframing — learning across episodes via text rather than gradients — made trial-and-error improvement practical for frozen, API-only models, and it is the ancestor of every "retry with lessons learned," self-debugging, and episodic-memory pattern in today's agents. Its headline result, 91% pass@1 on HumanEval versus GPT-4's then-SOTA 80% (abstract, Table 1), showed that a learning loop around a frozen model can beat the model itself.

The problem

LLM agents built on ReAct-style loops (ReAct, SayCan, Toolformer, WebGPT, …) act, fail, and — within a single trajectory — cannot recover from early mistakes, nor carry anything forward to the next attempt (§1). Traditional RL would fix this with policy or value learning, but that requires "extensive training samples and expensive model fine-tuning," infeasible for frozen frontier models (§1, abstract). Two sub-problems make naive retrying useless:

• Credit assignment. A sparse binary success signal at the end of a long trajectory says nothing about which action was wrong (§1: "it requires a good understanding of where the model made mistakes").
• No memory. The paper's own baselines demonstrate the ceiling: ReAct-only on ALFWorld plateaus between trials 6 and 7 and converges to a persistent 22% hallucination rate with "no signs of long-term recovery" (§4.1, Figure 3); on HotPotQA, retrying with temperature 0.7 but no memory solves zero previously-failed tasks (§4.2, Results).

The mechanism

Three models and two memories (§3)

Reflexion decomposes the agent into three LLM roles plus a memory system:

• Actor M_a — generates thoughts and actions given observations, exactly as in ReAct or CoT (both are used as Actor variants). It conditions on the trajectory so far (short-term memory) and on mem (long-term memory).
• Evaluator M_e — scores a finished trajectory tau_t into a reward r_t = M_e(tau_t). Instantiations are task-specific: exact-match grading for reasoning, hand-written heuristics for decision-making, self-generated unit tests for code, or an LLM used directly as a judge (§3 Evaluator).
• Self-Reflection model M_sr — the new part. Given the sparse signal (e.g. pass/fail), the trajectory, and the existing memory, it writes a "nuanced and specific" natural-language diagnosis: what went wrong, and what to do differently — e.g. inferring that action a_i led the episode astray and proposing the alternative a'_i (§3 Self-reflection). The paper calls this a "'semantic' gradient signal" (§1).
• Memory. Short-term = the current trajectory; long-term = mem, the list of self-reflection texts, bounded by a cap Omega, "usually set to 1-3," to respect context limits (§3 Memory, The Reflexion process). Programming uses Omega = 1; ALFWorld/HotPotQA use 3 (§4).

The policy is written pi_theta(a_t | s_t) with theta = {M_a, mem} (Algorithm 1): the learned object is the pair of frozen model and mutable memory — hence "verbal RL."

Feedback sources (§1, §4)

Three ways to produce the evaluation signal, in increasing sophistication: (1) simple binary environment feedback; (2) pre-defined heuristics for common failure cases — on ALFWorld, self-reflect if the same action gets the same response more than 3 times, or if the episode exceeds 30 actions (§4.1); (3) self-evaluation by an LLM — binary classification for decision-making, or self-written unit tests for programming (§1, §4.3). For code, tests are generated with CoT prompting, filtered for syntactic validity by AST construction, and up to n = 6 tests form the suite (§4.3) — since no hidden test is consulted, pass@1 reporting stays legitimate.

Why it works (paper's analysis)

On ALFWorld, failed baseline trajectories are dominated by the agent believing it holds an item it does not have, then compounding the error for dozens of steps; self-reflection "distill[s] long, failed trajectories into relevant experiences that can be used as 'self-hints'" — either pinpointing the early mistake or planning a more systematic search of the environment (§4.1, Analysis). On HotPotQA, an ablation isolates the writing from the remembering: giving the agent its last trajectory verbatim (episodic memory only) helps, but adding the self-reflection step on top improves learning by a further 8% absolute (§4.2 Analysis, Figure 4c) — "refinement- only approaches are not as effective as self-reflection-guided refinement approaches."

The algorithm

Direct reconstruction of Algorithm 1, "Reinforcement via self-reflection" (§3, Figure 2b):

# Reflexion(task, M_a, M_e, M_sr, Omega, max_trials)
mem ← []                                    # long-term episodic memory (verbal)
tau_0 ← rollout(pi_theta)                   # pi_theta: Actor M_a conditioned on mem
r_0   ← M_e(tau_0)                          # scalar/binary reward for trial 0
sr_0  ← M_sr(tau_0, r_0, mem)               # verbal self-reflection on the failure
mem   ← [sr_0]
t ← 0
while not pass(r_t) and t < max_trials:
    t ← t + 1
    tau_t ← rollout(pi_theta)               # Actor now sees task + mem in its prompt
    r_t   ← M_e(tau_t)
    sr_t  ← M_sr(tau_t, r_t, mem)
    mem   ← append(mem, sr_t)               # in practice: keep only last Omega (1-3)
return tau_t

Walkthrough, line by line:

1. mem ← [] — the mutable half of the policy. Everything Reflexion "learns" lives here as plain text; delete it and the agent is back to trial 0.
2. rollout(pi_theta) — one full episode. The Actor is any generation strategy (ReAct for ALFWorld/HotPotQA action choice, CoT for pure reasoning, direct generation for code); its prompt is few-shot exemplars + task + the reflections in mem.
3. r_t ← M_e(tau_t) — evaluation. Binary exact-match (HotPotQA), heuristic or LLM classification (ALFWorld), or the self-generated test suite verdict (code). r_t is deliberately sparse — "a scalar reward for trial t" (§3, The Reflexion process).
4. sr_t ← M_sr(...) — amplification. The self-reflection model turns {tau_t, r_t} into actionable prose. This is the credit-assignment step: it names the wrong action/assumption and prescribes a correction, information a bare 0/1 reward cannot carry.
5. mem ← append(...), bounded by Omega — sliding-window episodic memory. The bound is both a context-length necessity and an implicit recency prior.
6. Loop until pass or budget. The trio (Actor, Evaluator, Self-Reflection) "work together through trials in a loop until the Evaluator deems tau_t to be correct" (§3).

No gradient step exists anywhere; the fixed point is a memory whose contents make the Actor succeed. That is the whole formal content of "verbal RL," and the paper is candid that it inherits RL's weaknesses in exchange (local minima — §5).

Results that matter

Ablation (Table 3, 50 hardest HumanEval Rust problems, GPT-4): base 0.60; test generation without self-reflection 0.60 (no gain); self-reflection without test execution 0.52 (worse than base); full Reflexion 0.68. Neither component works alone — grounded signal plus verbal credit assignment is the combination.

Limitations & how to defend the findings

• "The agent is grading its own homework — flaky self-tests can mislead it." The paper measures exactly this (Table 2, §4.3 Analysis): the false-positive rate of internal test suites is 1.4% on HumanEval Python but 16.3% on MBPP Python, and that gap is the stated explanation for the one benchmark Reflexion loses (77.1 vs 80.1). False negatives are tolerable (the agent can re-inspect and keep its solution); false positives cause premature submission of wrong code. Honest answer: the method is bounded by evaluator quality, and the paper says so.
• "Is self-reflection actually needed, or is any retry loop enough?" Two ablations answer: (a) HotPotQA baselines with retries but no memory solve zero new tasks (§4.2); (b) episodic memory of raw trajectories helps, but self-reflection adds +8% on top (Figure 4c). Table 3 shows self-reflection without grounded tests is actively harmful (0.52) — "blind trial and error debugging techniques without self-reflection are ineffective on harder tasks" (§4.3/§5 transition).
• "Verbal policy optimization can get stuck." Conceded in §5: it "may still succumb to non-optimal local minima," and memory is a crude sliding window (Omega ≤ 3); the authors point to vector databases / SQL as future memory structures.
• "No formal guarantee." Conceded in §1: Reflexion relies on the LLM's self-evaluation ability and "does not have a formal guarantee for success"; the bet is that the paradigm improves as base models improve.
• "Test-driven evaluation doesn't cover all code." §5 lists the practical limits: non-deterministic functions, impure/API-touching functions, hardware-dependent outputs, parallel behavior.
• Safety note: §8 advises isolated execution environments — generated code runs unvalidated.

Connections

• ReAct — Reflexion's Actor for decision-making and QA is literally ReAct (§4.1, §4.2); the paper is best read as "ReAct + across-episode learning," fixing ReAct's documented plateau and repetitive-failure modes (see react.md).
• Episodic memory in agents — mem is the minimal episodic store: append-on-failure, bounded window, injected into the prompt. Modern agent memory systems (vector-store recall, reflection distillation) are elaborations the paper itself anticipates in §5.
• Verbal RL vs classic RL — policy = {frozen LM, memory}; reward stays sparse; the self-reflection is the credit-assignment mechanism replacing backprop ("semantic gradient," §1). Interpretability is the bonus: the "policy update" is human-readable (§6).
• Self-consistency — orthogonal axes of test-time compute: self-consistency spends samples in parallel within one attempt and votes; Reflexion spends attempts sequentially and carries information between them (see self-consistency.md).
• Tree of Thoughts — ToT searches within a single episode with lookahead/backtracking; Reflexion learns across episodes. A search loop can sit inside a Reflexion loop (see tree-of-thoughts.md).
• Self-Refine (Madaan et al.) — closest prior (§2): iterative self-improvement, but single-episode, no memory, no decision-making — the Figure-vs-related-work table on p.3 positions Reflexion as adding hidden constraints, decision-making, binary reward, and memory.

Reading guide

• Read first: abstract + §1 (the verbal-RL framing and the three feedback types), then §3 end-to-end — it is short and contains the whole method (Actor/Evaluator/Self-Reflection/Memory and Algorithm 1).
• Then: §4.3 Programming with Tables 1–3 — the strongest results and the most honest failure analysis (MBPP false positives, component ablation).
• Then: §4.1 Analysis and §4.2 Analysis — the two paragraphs that explain why memory + reflection beats retrying, with Figure 3 and Figure 4.
• Skim: §2 Related work (the two comparison tables are efficient), §6 Broader impact.
• Don't skip: §5 Limitations — unusually candid, and the source of your best skeptical answers.
• The one figure to study: Figure 2 (architecture + Algorithm 1 side by side) — plus Table 3 if you only have time for one table: it proves both components are necessary.