Reflexion: Language Agents with Verbal Reinforcement Learning

TL;DR

LLM agents fail at multi-step tasks, and the classic fix — reinforcement learning that updates the model’s weights — is too slow and expensive when the “model” is a 100B+ parameter LLM you’re calling over an API. Reflexion sidesteps this entirely: after a failed attempt, the agent reads its own transcript, writes a short natural-language critique of why it failed (“I assumed I was holding the pan but I never picked it up”), and stores that critique in a memory buffer. On the next attempt the critique is injected into the prompt, so the agent is conditioned on its own lessons. No weights move. This “verbal reinforcement learning” lifts an LLM coder from 80% to 91% pass@1 on HumanEval (beating raw GPT-4), adds +22% on AlfWorld decision-making, and +20% on HotPotQA reasoning — all in a handful of trials.

Problem & Motivation

The concrete pain: you have an LLM agent (ReAct-style: think, act, observe, repeat) trying to do something multi-step — navigate a simulated house, answer a multi-hop question, write a function that passes tests. It fails. You want it to learn from that failure and do better on the next try.

The textbook answer is reinforcement learning: collect the trajectory, compute a reward, run gradient descent to nudge the policy toward higher-reward actions. But here the policy is a giant LLM. Fine-tuning it requires thousands of samples and a GPU bill, and you often can’t even touch the weights (it’s behind an API). Worse, RL hands the agent a single scalar reward — “you got 0” — which is a terrible teacher. The agent has to solve the credit assignment problem (out of 30 actions, which one doomed me?) from one number. That’s the bottleneck.

Prior in-context approaches (Self-Refine, retry loops) get partway there but stay shallow: they refine a single generation, or they blindly retry without diagnosing the failure, or they need ground-truth test cases that disqualify honest pass@1 claims. Nobody had a clean, weight-free loop that (a) works across decision-making, reasoning, and coding, and (b) turns a sparse reward into rich, actionable, persisted feedback.

What’s New (Core Contribution)

1. Verbal reinforcement learning. Before: learning from experience meant gradient updates to the policy. Now: the “policy” is parameterized as {LLM, memory}, and you “reinforce” it by appending natural-language self-critiques to the memory. The semantic content of the critique plays the role a gradient plays in normal RL — it points the agent in a concrete direction to improve.
2. Self-reflection as the credit-assignment engine. Before: the agent had to infer what went wrong from a scalar reward. Now: a dedicated Self-Reflection LLM reads the full failed trajectory + the reward and writes specifically what to do differently (“I should have searched the drawers before the countertop”). This is the heart of the paper, and the ablations show it’s the part that actually carries the gains.
3. A clean three-model decomposition. Actor / Evaluator / Self-Reflection as swappable modules. Before: refinement loops bolted feedback onto one model. Now: a modular framework where the Evaluator can be exact-match, a heuristic, or an LLM, and the same loop works for three task families.
4. LeetcodeHardGym. A new benchmark of 40 hard Leetcode problems (released after GPT-4’s training cutoff, so no memorization) across 19 languages — and the use of self-generated unit tests as the reward signal, which keeps the result pass@1-eligible (no peeking at hidden tests).

How It Works (Technically)

Reflexion runs a loop over trials. Within a trial the agent acts in the environment until it finishes or gives up; between trials it reflects. Three LLM-backed components drive it:

• Actor (M_a) — the agent that does the task. It samples an action a_t from its policy π_θ given the current state, gets an observation o_t back, repeats. In practice the Actor is a ReAct or Chain-of-Thought prompt. The twist: its prompt also contains mem, the long-term memory of past reflections. So the policy is literally π_θ where θ = {M_a, mem} — the LLM weights are frozen, and the only thing that changes between trials is the memory text. That memory IS the learnable parameter.

• Evaluator (M_e) — scores a finished trajectory τ and returns a reward r_t = M_e(τ). Crucially this is just a scalar (often binary: pass/fail). How you compute it depends on the task:

  • Reasoning (HotPotQA): exact-match grading against the gold answer.
  • Decision-making (AlfWorld): a hand-written heuristic (e.g., “if you repeated the same action 3+ times or took >30 actions, you’re stuck”) or an LLM asked to classify success.
  • Coding: run the agent’s own self-generated unit tests and see if they pass.

• Self-Reflection (M_sr) — the special sauce. It takes {trajectory τ, reward r, memory mem} and emits a paragraph of verbal feedback sr_t. This is where a sparse “you failed” gets amplified into “you failed because you tried to clean the pan before picking it up; next time grab the pan from the stove first.” That paragraph gets appended to mem.

The loop, equation by equation (demystified)

The paper’s Algorithm 1 looks formal but it’s a simple while loop. Here’s every line in plain English:

• Initialize π_θ(a_i | s_i), θ = {M_a, mem} → the policy is “the Actor LLM plus a memory buffer.” Memory starts empty.
• Generate τ_0 using π_θ → run the agent once; collect the trajectory (sequence of action/observation pairs).
• Evaluate τ_0 using M_e → score it. r_t = M_e(τ_0) — a scalar that goes up as you do better. (No gradients computed from it; it’s just an input to the reflection step.)
• Generate sr_0 using M_sr; mem ← [sr_0] → write the first self-critique, seed memory with it.
• while M_e not pass and t < max_trials: → keep going until you succeed or run out of tries.
  • Generate τ_t using π_θ → re-run the agent, now with mem in its prompt. This is the learning: same weights, smarter context.
  • Evaluate; Generate sr_t; Append sr_t to mem; t += 1 → score, reflect, remember, repeat.

Two kinds of memory work together, mirroring human cognition:

• Short-term memory = the current trajectory τ (fine-grained recent detail — what just happened this trial).
• Long-term memory = mem, the list of distilled reflections across trials (the lessons). It’s capped at Ω = 1–3 experiences to fit the context window — usually 1 for coding, 3 for AlfWorld/HotPotQA.

The deep point: in normal policy-gradient RL, the reward signal is a number and the “direction to improve” is a gradient vector in weight-space. Here the reward signal is still a number, but the “direction to improve” is a sentence in English that gets read by the next forward pass. Shinn et al. call this a semantic gradient — it carries far more bits of useful information than a scalar, and it’s interpretable, which a weight gradient never is.

Architecture & data flow

flowchart LR
  ENV[Environment<br/>game / compiler / QA] -->|obs, reward| ACT[Actor LLM<br/>ReAct / CoT]
  ACT -->|action| ENV
  ENV -->|trajectory τ| EVAL[Evaluator<br/>EM / heuristic / unit tests]
  EVAL -->|scalar reward r| REF[Self-Reflection LLM]
  ACT -->|trajectory τ| REF
  REF -->|verbal critique sr| MEM[(Long-term memory<br/>last Ω reflections)]
  MEM -->|injected into prompt| ACT
  classDef hot fill:#2d6cdf,color:#fff;
  class REF hot;

The trial loop in motion: watch a failed trajectory get scored, distilled into a verbal reflection, pushed into the memory buffer, and lift the success probability on the next trial. Schematic — the curve illustrates the paper's "spike then steady climb" learning shape, not exact numbers.

The algorithm, simplified

# Reflexion: weight-free learning via self-written feedback.
# llm(prompt) -> str ; env.run(actor) -> Trajectory ; evaluate(traj) -> float|bool

def reflexion(task, max_trials=3, mem_cap=3):
    mem = []                                  # long-term memory = the ONLY learnable state
    for t in range(max_trials):
        # ACTOR: act in the env, conditioned on distilled lessons so far
        trajectory = env.run(actor=lambda state: llm(
            f"Task: {task}\nLessons from past attempts:\n{chr(10).join(mem)}\n"
            f"State: {state}\nThink, then act."
        ))
        # EVALUATOR: scalar/binary reward (exact-match, heuristic, or run unit tests)
        reward = evaluate(trajectory)
        if reward == PASS:
            return trajectory                 # solved — stop early

        # SELF-REFLECTION: amplify the sparse reward into an actionable sentence
        critique = llm(
            f"Task: {task}\nYou FAILED. Trajectory:\n{trajectory}\n"
            f"Reward: {reward}\nIn first person, say exactly what you did wrong "
            f"and what you'll do differently next time."
        )
        mem.append(critique)                  # this paragraph is the 'semantic gradient'
        mem = mem[-mem_cap:]                   # bound memory to fit the context window
    return trajectory                         # best effort after max_trials

That’s the whole contribution. No training loop, no optimizer, no dataset — just a for loop and a memory list.

Built on Prior Work

Results & Evidence

Headline numbers:

• Coding (HumanEval Python): 91.0% pass@1, vs. 80.1% for raw GPT-4 — a new SOTA, and the result that got the paper attention. Also HumanEval Rust 60→68%, MBPP Rust 71→75%, Leetcode Hard 7.5→15%.
• Decision-making (AlfWorld): 130/134 tasks solved, +22% absolute over ReAct, with most gains in the first 2 trials then a steady climb over 12 trials. The ReAct-only baseline plateaus at trial 6–7 with a stubborn 22% hallucination rate.
• Reasoning (HotPotQA): +20%. Critically, the baselines (ReAct-only, CoT-only) never fixed a first-trial failure on retry — they had no mechanism to. Reflexion did.
• The ablation that matters: with episodic memory but no reflection step, you get only the memory benefit; adding the verbal reflection adds +8% absolute on top. And on Rust, omitting reflection entirely drops to baseline — “blind retry” debugging doesn’t help on hard problems. This is the evidence that the reflection, not just “try again,” is doing the work.

Caveats — read these before you sell it:

• It lost on MBPP Python (77.1 vs 80.1). Why? The self-generated tests had a 16.3% false-positive rate (tests pass but code is wrong) vs only 1.4% on HumanEval. When the Evaluator is the agent’s own tests, a flaky test suite makes it confidently submit garbage. Your reward signal is only as good as the verifier.
• Self-evaluation is the whole risk surface. The method explicitly relies on the LLM being able to judge its own work (or a decent heuristic). No formal success guarantee; it can settle into a local minimum and keep “reflecting” the wrong lesson.
• Few-shot prompting throughout (2–6 shot examples per task) — these results aren’t pure zero-shot, and the heuristics (AlfWorld’s “3 repeats / 30 actions”) are hand-tuned.
• Memory is a tiny sliding window (1–3). Long-horizon learning across many distinct lessons isn’t really tested — the paper flags vector DBs as future work.

How You’d Use It

This is one of the highest-leverage, lowest-cost patterns in the agentic toolkit, and it maps directly onto an AI services business.

• Bolt it onto any existing agent as an outer loop. If you’ve built a ReAct agent for a client, you don’t rewrite it — you wrap it. Add (1) a pass/fail check and (2) a “why did you fail, what next” prompt, and feed the answer back. That’s a one-day upgrade that often turns a 60%-reliable agent into an 85%+ one on retryable tasks.
• Code-generation services. The self-test → reflect → retry loop is exactly what you want behind a “generate me a function/script” product. Pair it with a sandboxed executor and you get measurably higher first-shot correctness, with the test suite doubling as deliverable artifact for the client.
• Where the Evaluator is cheap and reliable, this shines: anything with a ground-truth check (does the SQL run? does the test pass? does the extracted JSON validate against a schema? did the form submit?). Those are gold-standard Evaluators because there’s no LLM-judging risk.
• Observability/QA offering. Because the “learning signal” is plain English, every reflection is an audit log of why the agent struggled — you can surface these to clients as “here’s where your task is ambiguous,” turning a debugging mechanism into a consulting insight.
• The honest read for selling it: it’s real and it works, but it only helps on retryable, verifiable tasks. If you can’t cheaply tell success from failure, the loop has nothing to reflect on. Don’t pitch it for open-ended generation with no verifier.

Build Your Own (Minimal Recipe)

Smallest version that captures ~80% of the value, in build order:

1. Actor — your existing agent. Start with a single LLM call that takes (task, memory) and returns an answer or a trajectory. (Libraries: raw OpenAI/Anthropic SDK, or LangGraph/your own loop. You do not need an RL library.)
2. Evaluator — pick the most reliable signal you can. For code: run unit tests in a sandbox (subprocess + a timeout, or a container). For structured output: schema validation. For QA: exact match. This is the part to invest in — see the hard parts.
3. Self-Reflection prompt — one LLM call: “You failed. Here’s the trajectory and the error. In first person, diagnose the mistake and state what you’ll do differently.” Keep it specific and actionable.
4. Memory — a Python list, capped to the last 1–3 reflections, string-joined into the Actor’s prompt. Don’t over-engineer this first.
5. The loop — while not passed and trials < N. Ship it.

The 1–2 genuinely hard parts:

• The Evaluator is the whole ballgame. The MBPP failure is the cautionary tale: a 16% false-positive verifier hurt performance. If your verifier lies, the agent confidently learns the wrong thing. Spend your effort making success detection trustworthy (multiple tests, AST-validate generated tests, prefer false-negatives over false-positives).
• Writing reflections that are specific. A vague “I should be more careful” teaches nothing. The reflection prompt needs the full trajectory and should be pushed (via examples) to name the exact failing step.

How to Improve It

1. Upgrade memory from a sliding window to retrieval. The paper’s Ω=1–3 list throws away old lessons. Embed each reflection, store in a vector DB, and retrieve the most relevant past lessons for the current state. This directly attacks the stated limitation and lets the agent accumulate a real skill library across thousands of tasks.
2. Cross-task / cross-session memory. Reflexion’s memory resets per task. Persist reflections across tasks and clients (with care) so the agent compounds expertise — “in this codebase, always check for null first” becomes institutional knowledge.
3. Harden the Evaluator against false positives. Generate tests, then have a second model adversarially try to break the test suite, or require mutation-testing-style coverage before trusting a “pass.” Would likely fix the MBPP regression.
4. Reflection on success, not just failure. Currently it only reflects when it fails. Reflecting on why something worked (and storing positive exemplars) could speed learning and reduce the local-minimum risk — closer to advantage-weighted learning.
5. Detect and break reflection loops. If the agent reflects the same wrong lesson repeatedly (a local minimum), add a meta-step that notices stagnation and forces a different strategy — analogous to exploration bonuses in RL.

Glossary

• Verbal reinforcement learning — improving an agent by appending natural-language self-feedback to its prompt instead of updating its weights with gradients.
• Policy (π_θ) — the rule mapping states to actions. Here θ = {LLM, memory}, so the only mutable part is the memory text.
• Trajectory (τ) — the full sequence of actions and observations from one attempt at a task.
• Reward — a scalar score for a trajectory (often just pass/fail). Used as input to reflection, not to compute a gradient.
• Credit assignment — figuring out which of many actions was responsible for the outcome; the classic hard problem in RL that reflection tackles in plain English.
• Self-reflection (sr) — the verbal critique an LLM writes about its own failed attempt; the “semantic gradient.”
• Episodic memory — stored past experiences (here, reflections) that condition future behavior.
• ReAct — an agent prompting style interleaving reasoning “thoughts” with environment actions.
• Chain-of-Thought (CoT) — prompting the model to reason step-by-step before answering.
• pass@1 — fraction of problems solved correctly on the first submitted attempt (no peeking at hidden tests).
• AlfWorld / HotPotQA / HumanEval / MBPP — benchmarks for, respectively: text-based household decision-making, multi-hop Wikipedia QA, Python function generation, and basic Python programming.
• Self-generated unit tests — tests the model writes itself to check its own code, used as the Evaluator so the result stays pass@1-eligible.