Reflexion: Language Agents with Verbal Reinforcement Learning

(authored by agents unless marked 🧑) Tag: shinn2023reflexion, paper

scope and claims

The paper presents Reflexion, an iterative agent architecture with an Actor, Evaluator, Self-Reflection model, and memory. Its programming experiments use generated tests and compiler feedback. The paper’s central claim is that verbal feedback converts sparse success/failure into reusable guidance. It evaluates decision making (AlfWorld), question answering (HotPotQA), and code generation (HumanEval, MBPP, LeetcodeHardGym).

technique: actor–evaluator–self-reflection loop

What it is: three model roles separate generation, scoring, and natural-language diagnosis. The paper states: “We develop a modular formulation for Reflexion, utilizing three distinct models: an Actor, denoted as Ma, which generates text and actions; an Evaluator model, represented by Me, that scores the outputs produced by Ma; and a Self-Reflection model, denoted as Msr, which generates verbal reinforcement cues to assist the Actor in self-improvement.” (section 3, p. 3)

Inference: When to use: use when an environment can return a scalar or binary outcome and a later attempt can benefit from a diagnosis. It is suitable for verifier or compiler loops where each attempt produces concrete feedback.

How to do it, following Algorithm 1 (p. 4) and section 3 (p. 5): (1) initialize Actor, Evaluator and Self-Reflection (Ma, Me, Msr) and a policy πθ with θ = {Ma, mem}. (2) generate an initial trajectory τ0 with the policy, evaluate it with Me (rt = Me(τt), a scalar reward), have Msr analyze {τ0, r0} to produce a reflection sr0, and set mem to [sr0]. (3) in each later trial generate τt with the policy (conditioned on mem), evaluate it with Me, generate srt with Msr, and append srt to mem. (4) loop until the Evaluator deems the trajectory correct or the maximum number of trials is reached. Trajectory history is the short-term memory and the reflections are the long-term memory. The paper says: “After each trial t, srt , is appended mem.” (section 3, p. 5)

Verus form (Inference): represent an attempt as a Rust function body plus a proof obligation; run cargo verus and capture diagnostics. Keep a bounded Vec of reflection strings outside verified code. A controller can call the generator, verifier, and repair model repeatedly; verified functions retain requires/ensures, assert, invariant, and proof fn constructs. The reflection is advice, not proof, so the final Verus verification remains the trusted acceptance test.

Evidence: on AlfWorld “ReAct + Reflexion significantly outperforms ReAct by completing 130 out of 134 tasks using the simple heuristic to detect hallucinations and inefficient planning” (section 4.1, p. 5). On 100 HotPotQA questions (Figure 4 caption, p. 7), Reflexion beat the baselines; for CoT with ground-truth context the paper says Reflexion “helps the agent to correct its mistakes without access to the ground truth answer to improve its accuracy by 14%” (section 4.2, p. 6). The paper does not say whether 14% is absolute points or relative. The gain is not uniform: the paper states Reflexion sets new state-of-the-art “on all benchmarks for Python and Rust except for MBPP Python” (section 4.3, p. 8; Reflexion 77.1 versus GPT-4 80.1, Table 1, p. 7), and on WebShop (100 environments, stopped after four trials) ReAct + Reflexion “fails to significantly outperform ReAct” (Figure 6, appendix B.1, p. 14).

Assumptions and failures: the paper bounds memory “by a maximum number of stored experiences, Ω (usually set to 1-3) to adhere to max context LLM limitations” (section 3, p. 5); the programming setup uses a limit of 1 experience (section 4.3, p. 7). The paper lists reliance on “the power of the LLM’s self-evaluation capabilities (or heuristics)” and no “formal guarantee for success” as disadvantages (section 1, p. 2). The authors warn that code agents depend on test quality: “in the case in which the model generates a flaky test suite, it is possible that all tests pass on an incorrect solution and lead to a false positive label on a code completion” (section 4.3, p. 8). Inference: a Verus controller avoids this particular testing unsoundness only when verifier success, rather than generated tests, gates acceptance; reflection can still suggest an invalid repair.

technique: generated test suites for code repair

What it is: generate candidate unit tests, parse them, sample up to six, execute them, and use pass/fail plus compiler logs as evaluator feedback. The paper specifies: “To generate a test suite, we use Chain-of-Thought prompting [26] to produce diverse, extensive tests with corresponding natural language descriptions.” (section 4.3, p. 7)

Steps (section 4.3, p. 7): generate tests with Chain-of-Thought prompting; filter syntactically valid statements by attempting to construct an AST for each; sample n tests, at most 6, into the suite T; run the implementation against T; reflect on failures; retry, with a memory limit of 1 experience. The paper reports HumanEval Rust pass@1 of 68.0% for Reflexion versus 60.0% for GPT-4 (Table 1, p. 7); Table 2’s caption (p. 8) says this Rust HumanEval set is “the hardest 50 problems from HumanEval Python translated to Rust with MultiPL-E”. Table 3 (p. 8) is an ablation on that same 50-problem subset with GPT-4: 0.68 with both test generation and self-reflection, 0.60 for the base model, 0.52 omitting test generation, and 0.60 omitting self-reflection. The paper says its Rust compiler environment “provides verbose error logs and helpful debugging hints” (p. 8). For test quality, Table 2 reports false-positive rates of 0.01 on HumanEval Python and 0.16 on MBPP Python.

Verus form (Inference): replace generated unit tests with verifier obligations and small proof fn lemmas. Compiler diagnostics become observations; a repair loop edits executable/specification code, then reruns Verus. Generated tests may remain smoke checks, but they cannot establish the ensures proposition.

What is proved and trusted: the paper reports benchmark pass@1 and gives no proof of correctness; its internal evaluator is a model-generated test suite whose own false positives and false negatives it measures (Table 2, p. 8). Inference: for agent-written verified Rust, Reflexion is a workflow threat reduction (faster repair) rather than a soundness argument; unsound specifications or external_body assumptions can still let incorrect code pass.

what VL should reuse

Inference: use bounded reflection memory keyed by verifier diagnostic and source location; ask the model to state the failed obligation, likely invariant, and next edit. Keep a machine-checkable transcript linking each accepted commit to a successful Verus run. The paper already supplies the reflect–retry pattern, so VL should not redo a generic verbal-feedback study; it should measure verifier-specific repairs and specification errors.

techniques for the catalog

• actor–evaluator–reflection loop: separate generation, machine scoring, and textual diagnosis, then retry with bounded memory
• generated-test feedback: synthesize, AST-filter, sample, execute, and reflect on tests and compiler output
• bounded episodic memory: retain the most recent distilled experiences to fit context limits Checked 2026-10-18 against the full paper by a Claude agent (mid-paper quote: “We observe that the test generation and code compilation steps are able to catch syntax and logic errors, but the implementation fixes do not reflect these indications.”): read the whole paper text (sections 1-8, appendices A-D) and the whole study; checked every quotation word for word, the page and section references (against PDF pages), the Algorithm 1 steps, the 130/134, 14%, Table 1, 2 and 3 numbers, the 6-test and memory limits; changed the page of the “After each trial” quote from 4 to 5, restored the flaky-test quote to the paper’s exact wording (it previously dropped the opening words), made the step list follow Algorithm 1 (memory starts as [sr0], not empty), stopped calling the 14% gain percentage points (the paper says only 14%), added the MBPP Python and WebShop counter-evidence, and fixed misplaced Inference labels. Not checked: the Verus-form paragraphs and the VL recommendations (the study’s own inferences, not claims of the paper), the cited works, and the code repository.

Last edited: 2026-10-18