acceptodds
Under review as a conference paper at ICLR 2027

NLPG: Natural-Language Policy Gradients for Self-Evolving Language Agents

Abstract

Large language model agents increasingly rely on compound programs for retrieval, tool use, reasoning, and verification, yet their failures often arise from local procedural decisions. Existing reinforcement-learning and prompt-optimization approaches typically rely on scalar rewards or repeatedly modify entire prompts, making it difficult to capture and reuse procedural improvements while preserving a frozen agent. To address this problem, We propose Natural-Language Policy Gradients (NLPG), an external policy-memory method for improving a fixed agent without changing its model parameters or program structure. NLPG diagnoses execution traces, propagates downstream feedback backward through the module graph, and converts recurring failures into route-local natural-language corrections that are aggregated into bounded policy updates for subsequent executions. Across six benchmarks covering memory, reasoning, instruction following, and evidence verification, NLPG also outperforms the strongest listed baseline for each benchmark by 8.71 percentage points on average. These results provide evidence that evaluated procedural experience can be transformed into local and interpretable policy updates, enabling continual improvement of frozen agents.

Primary area:
foundation or frontier models, including LLMs
Keywords:
self-evolving agents, LLM memory, prompt optimization, large language models, compound AI systems

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_6tvgOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces Natural-Language Policy Gradients (NLPG), a method for improving compound LLM agents while keeping the model weights, program structure and base prompts frozen. Instead of rewriting prompts, NLPG keeps an external "policy memory" of short natural-language rules. Each rule is filed under a route, which is either a program module or a task family. At inference time, the top-K rules for a route are appended to that module's prompt. To build this memory, NLPG diagnoses failed runs with benchmark-specific adapters. It then passes textual feedback backward through the module dependency graph, as TextGrad does, to produce a local correction for each module. Corrections are grouped across runs and scored by how many failures support them and by the critic's confidence. They are turned into rules, and a new memory is accepted only if it improves a held-out set without regressions. The method is evaluated on memory benchmarks (LoCoMo, HaluMem, LongMemEval) against memory-agent baselines. It is also evaluated on the GEPA suite (HotpotQA, IFBench, HoVer) against MIPROv2, TextGrad, Trace and GEPA, using Qwen3-8B and GPT-4.1 Mini. It reports the best results in every comparison, for example 59.00 vs. 51.09 for GEPA with Qwen3-8B.

Critical strengths
  1. NLPG adds short rules tied to specific modules or task families and never rewrites prompts or code. This makes each change easy to inspect, attribute and roll back. It also avoids prompt drift, a risk with methods that rewrite whole instructions, such as GEPA or Meta-Harness.
  2. It joins TextGrad-style backward credit assignment, voting across runs and held-out validation into a single procedure. Together these address a known weakness of reflective optimizers: overfitting to fixes that come from a single example.
  3. NLPG outperforms GEPA, GEPA+Merge, TextGrad and MIPROv2 on all three transfer tasks with both backbones. It also outperforms memory-agent baselines on LoCoMo, HaluMem and LongMemEval. Because routing can be by task family, the same procedure works both for multi-module programs and for memory-QA tasks.
Critical weaknesses
  1. The backward credit assignment is taken directly from TextGrad, which the authors acknowledge. Module-level, reflection-driven instruction optimization with validation is the core of GEPA. Storing reusable lessons from experience resembles prior experiential-memory work such as ExpeL and Agent Workflow Memory. The main new elements are storing fixes as additive rules and support-weighted aggregation. The paper should state more clearly which part is new and isolate its effect, for example by comparing against GEPA with an add-rules-only constraint, or TextGrad with cross-run aggregation. Recent harness-optimization work such as Meta-Harness [1], which optimizes the full harness code, is neither cited nor discussed.
  2. Appendix C says that auxiliary models used for reflection and optimization are "reported separately," but I could not find them in the paper. This matters a lot. If a stronger model writes the rules, part of NLPG's gain on Qwen3-8B may come from transferring that model's knowledge. A fair comparison needs the same reflection model as GEPA, or an analysis of how sensitive the results are to this choice.
  3. The paper matches inference budgets but does not report optimization cost relative to GEPA and TextGrad: rollouts, critic calls, tokens or wall-clock time. A per-module backward pass on every failure, plus held-out validation each round, could cost much more than GEPA.
  4. The backbones (GPT-4.1 Mini, GPT-4o-mini, Qwen3-8B) are relatively old and small. It is unclear whether rule-based addenda still help stronger current models that may already follow such procedures.

References

[1] Meta-Harness: End-to-End Optimization of Model Harnesses, 2026, Lee et al.

Questions for authors
  1. Which models serve as the critic and optimizer, and did GEPA and TextGrad use the same reflection model?
  2. What is the total optimization cost (LLM calls and tokens) of NLPG compared with GEPA?
  3. How does NLPG perform with a stronger backbone (e.g., GPT-6-class or Qwen3-32B+)?
9 comments
AuthorsOpenReview ↗

The Response to Weakness2 and Question1

We thank the reviewer for their thoughtful assessment and recognition of NLPG’s interpretable policy updates. and for raising the questions which have helped us improve the paper.

Response to Weakness2 and Question1

All auxiliary roles run on the same model as the task backbone of their block. For the Qwen3-8B block the critic and the optimizer are Qwen3-8B; for the GPT-4.1 Mini block they are GPT-4.1 Mini. The same weights that answer the task also diagnose the failure and write, score and filter the rules; no external model is introduced at any stage. GEPA and TextGrad use the same reflection model as their task backbone. GEPA instantiates each system once per model with all modules on that model, and its reflection LM is that model. TextGrad's optimizer engine is set to the same model, run in the Trace framework under GEPA's budget, metric and feedback function. We have revised the writing in the Appendix B.2

AuthorsOpenReview ↗

The Response to Weakness3 and Question2

The Response to Weakness3 and Question2

Thank you for highlighting optimization cost beyond inference. We have added the optimization rollout budgets and reflection-call counts for NLPG and GEPA,using qwen3-8b for task execution, criticism, backward reflection, and optimization.:

BenchmarkNLPG reflection callsGEPA reflection callsNLPG rolloutsGEPA rollouts
HotpotQA42 / 6269 / 644206,871
IFBench21 / 2721 / 173603,593
HoVer86 / 4792 / 504207,051

The following costs exclude preflight and final testing:

BenchmarkTask rolloutsTotal API requestsReported tokens
IFBench360580439,892
HotpotQA4201,5271,410,649
HoVer4203,2033,673,576

Auxiliary stages account for 33.9%, 25.2%, and 46.5% of these token budgets, respectively. Observed offline elapsed times were 18.7, 19.5, and 21.8 minutes, respectively.

NLPG uses approximately 16.4×, 10.0×, and 16.8× fewer optimization rollouts on HotpotQA, IFBench, and HoVer, respectively. These budgets include policy construction and parent/candidate held-out validation; final-test rollouts are excluded.

GEPA’s larger rollout count arises from repeated candidate evaluation during evolutionary search. Each reflective update is first evaluated on a training minibatch, and candidates that improve are subsequently evaluated on the larger selection set. These repeated executions accumulate rollouts even when the number of distinct training examples is small. NLPG instead constructs a candidate policy memory from batch-level feedback and uses a fixed parent–candidate validation schedule, resulting in fewer optimization rollouts in our reported experiments.

Thus, module-local feedback does not translate into a larger rollout budget in these experiments: reflection counts are broadly comparable, while NLPG requires substantially fewer agent executions.

AuthorsOpenReview ↗

The Response to Weakness4 and Question3

The Response to Weakness4 and Question3

We thank the reviewer for the suggestion. We additionally evaluated NLPG with GPT-6.1 Sol and Qwen3-32B under the same data splits and evaluation settings:

BackboneHotpotQAIFBenchHoVer
GPT-6.1 Sol83.00%82.00%73.33%
Qwen3-32B77.67%42.00%58.67%

Together with the backbone results already reported in the paper, these additional experiments show that NLPG remains effective across different model families and scales. In particular, its strong performance with GPT-6.1 Sol supports its applicability to more capable backbones.

Reviewer_hzDuOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

NLPG proposes a method for improving LLM agents without changing model weights or program structure. It analyzes execution failures, propagates feedback backward through the agent's module graph, and converts identified mistakes into reusable natural-language instructions stored in module-specific policy memory.

Across six benchmarks covering memory, reasoning, and instruction following, NLPG outperforms existing methods such as GEPA and TextGrad, achieving an average improvement of 8.71 percentage points over the strongest listed baselines. Its main contribution is module-level credit assignment and persistent procedural learning, although it relies on reliable failure diagnosis and evaluation feedback.

Critical strengths

A promising direction to make resemblance from text updates to gradients. Self-improving agents is indeed a promising direction

Critical weaknesses
  1. Bad presentation. Lots of parts are clearly AI generated and not readable. Ex. figure 2 just dumps information.
  2. Figure 3, 4 are not readable.
  3. Experiments do not have clear explanation on why the proposed method works or changes upon previous work such as text gradient by GEPA.
Questions for authors
  1. What are the figures trying to convey? They are very poorly presented though the direction is interesting.
  2. What innovation do you bring on top of previous methods in terms of novelty? I do not know how this is different from text gradient
7 comments
AuthorsOpenReview ↗

The Response to Weakness1 and Question1

We thank the reviewer for recognizing the promise of self-improving agents and for highlighting the need for clearer presentation. We have redrawn Figure 2 to make the central mechanism and its execution flow easier to follow.

Response to Weakness1 and Question1: Presentation and Figure 2

The revised figure follows a concrete multi-hop QA example and organizes NLPG into three connected stages: (A) inference with policy memory, where route-specific instructions guide module calls with the backbone frozen; (B) graph-backward feedback, where a missing bridge entity leads to a local diagnosis and a reusable correction, followed by aggregation across executions; and (C) validation and promotion, where candidate policies replace the current memory only after satisfying held-out gain and regression constraints. The revised caption explains each panel explicitly. This organization makes the link from an execution failure to a localized correction and a validated policy update visible, addressing the information overload in the original figure.

We hope the revised figure makes NLPG’s mechanism clearer and would welcome any further suggestions on its presentation.

AuthorsOpenReview ↗

The Response to Weakness2

Response to Weakness2: Readability of Figures 3 and 4

Thank you for highlighting these presentation issues. Original Figure 3 summarized the main performance comparisons: HotpotQA, IFBench, and HoVer results with Qwen3-8B and GPT-4.1 Mini, alongside category-wise LoCoMo accuracy. Since these results were already reported in the main experimental tables, we have removed the figure to reduce redundancy.

Original Figure 4 presented IFBench component ablations across instruction categories, showing both strict accuracy and changes relative to full NLPG, with low-sample categories marked explicitly. We have replaced this heatmap with a table so that readers can directly inspect the numerical results and compare each ablation.

To help us further improve the presentation, could the reviewer clarify whether “not readable” refers primarily to font size and visual density, or to insufficient explanation of the figures’ intended messages? We would appreciate this guidance and have revised both the format and accompanying explanations to address these concerns.

AuthorsOpenReview ↗

The Response to Weakness3 and Question2

Response to Weakness3 and Question2

We thank the reviewer for raising the weakness. We have revised the presentation in the Introduction 、Method and Related Work sections to distinguish the mechanisms inherited from prior work from the policy representation and update mechanism introduced here.

NLPG addresses how execution-specific feedback can become persistent, reusable procedural knowledge in a compound agent. Its central contribution is a route-indexed additive policy memory with evidence-weighted consolidation across executions: localized corrections are retained as explicit rules, accumulated according to recurring evidence, and selectively injected into subsequent module calls. This connects failure diagnosis to persistent policy evolution while keeping the agent program and backbone fixed.

The distinction from prior work lies in how execution feedback is converted into persistent policies. TextGrad provides backward textual feedback, while GEPA evolves instructions through reflection and candidate selection. NLPG addresses a complementary challenge: which local corrections should be retained, and where should they be reused?A correction useful for one failure may not generalize across examples or apply to every module. NLPG therefore groups corrections by route and failure signature, prioritizes them using evidence from distinct executions, and injects only a bounded set into the relevant calls. This design aims to reduce reliance on isolated failures and limit unrelated guidance, while keeping each rule separately inspectable and the base prompts unchanged. ExpeL and Agent Workflow Memory also reuse experience; NLPG’s specific contribution is to connect execution-level diagnosis with evidence-supported selection of reusable local rules. The IFBench ablations support the value of this design: removing route credit or failure signatures lowers accuracy by 3.3 and 4.0 percentage points, respectively.

Reviewer_8dogOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces Natural-Language Policy Gradients (NLPG), a parameter-free policy-evolution framework designed to improve compound language model agents without changing their underlying model parameters, base code program structures, or retrieval backends. Instead of updating global prompts or optimizing scalar parameters via reinforcement learning, NLPG maintains an external, route-indexed policy memory containing short natural-language procedural instructions. When a task fails, NLPG performs graph-backward credit assignment by propagating task-level evaluation feedback in reverse topological order through the recorded module dependency graph. A critic model converts these localized errors into natural-language corrections, which are subsequently filtered, ranked based on cross-execution support, failure weight, and critic confidence, and validated on a held-out split. The authors evaluate NLPG across six benchmarks spanning long-horizon conversational memory (LoCoMo, HaluMem, LongMemEval) and multi-task transfer (HotpotQA, IFBench, HoVer) using backbones like Qwen3-8B and GPT-4.1 Mini. Results demonstrate consistent performance gains over existing baseline methods, prompt optimizers (such as MIPROv2, TextGrad, and GEPA), and reinforcement learning approaches.

Critical strengths

Module-Local Credit Assignment via Graph-Backward Propagation: By propagating task-level feedback backward through recorded module dependencies in reverse topological order, NLPG effectively addresses the credit-assignment bottleneck in compound agents. This allows errors to be attributed precisely to responsible modules (e.g., specific retrieval or query generation steps) rather than requiring coarse, global prompt updates.

Rigorous Experimental Validation and Data Separation: The authors employ a strict, independent held-out evaluation protocol across six diverse benchmarks, ensuring that policy construction, selection, and final testing use strictly disjoint data partitions and grouping keys. This significantly strengthens the credibility and reproducibility of the reported performance gains.

Critical weaknesses

Reliance on Structured Trace Graphs and Explicit Annotations: The framework assumes that agent execution traces can be cleanly decomposed into explicit module dependencies and structured intermediate fields (e.g., query rationale, summaries, explicit outputs). While standard in modular frameworks like DSPy, applying NLPG to highly unstructured or end-to-end black-box agent workflows where intermediate module boundaries are blurry could be challenging.

Modest End-to-End Repair Rates in Constraint-Heavy Tasks: As noted in the IFBench repair analysis (Appendix C.7.1), while diagnosis F1 and constraint-family localization are strong, the actual end-to-end strict repair success rate is relatively modest (8.79%), highlighting that identifying a policy correction does not always guarantee that the underlying model can successfully execute multiple simultaneous output constraints.

Questions for authors

Dependency on Execution Graph Granularity: How sensitive is NLPG's backward propagation mechanism to the granularity of the module dependency graph? If an agent architecture merges several functional steps (e.g., combining query generation and evidence retrieval into a single un-factored module call), how severely does this degrade the precision of route-local credit assignment?

Overhead of Offline Policy Construction: Could the authors elaborate on the computational and API cost overhead associated with running the LLM-based critic and backward reflection passes during offline policy construction across multiple iterative training rounds?

5 comments
AuthorsOpenReview ↗

The Response to Weakness1 and Question1

We thank the reviewer for their feedback for recognizing NLPG’s module-local credit assignment and rigorous data separation, and for raising the question of its dependence on structured traces. We address Weakness 1 and Question 1 through controlled graph-coarsening and intermediate-information-hiding experiments.

Response to Weakness 1: Reliance on structured traces and explicit annotations.

NLPG assigns feedback at explicit module interfaces; it does not require every internal operation to be exposed as a separate node. To examine dependence on intermediate fields, We compared three trace settings: separate query-generation and retrieval modules, a merged query/retrieval module with the internal query retained, and the same merged module with the internal query hidden. The explicit view hid the internal query, exposing only the combined module’s external inputs and retrieved documents. All conditions used the same 76 controlled-fault cases and six successful critic calls per case. Fault labels were hidden from the critic and used only for evaluation.

Trace viewInternal query visibleLocalization accuracy on common routes
Separate modulesYes43.42%
Merged, query retainedYes39.47%
Merged, query hiddenNo51.32%

All conditions were evaluated on the same two attribution targets: query/retrieval versus answer. Hiding the internal query did not reduce localization accuracy in this diagnostic, suggesting that access to this structured intermediate field is not essential for assigning feedback to the combined module. These results show that merging query generation and retrieval into one module does not systematically degrade route-local credit assignment, even when the internal query is unavailable.

These results support applying NLPG at the granularity of available interfaces: when internal steps are hidden, the combined module can serve as a single feedback target, with reusable policies injected at its exposed input boundary. Thus, NLPG can accommodate partially observable workflows without reconstructing every internal dependency. The trade-off is coarser attribution rather than necessarily losing the ability to learn procedural corrections. NLPG primarily targets workflows where recurring procedural decisions can be improved through module- or task-family-specific guidance. Fully end-to-end black-box agents with unclear intermediate module boundaries are beyond this main focus. Without intermediate inputs and outputs, NLPG has less evidence to identify which internal step caused a failure. Future work will explore learning guidance for the overall task when only inputs and final outputs are available.

Response to Question 1: Sensitivity to execution-graph granularity.

We merged HotpotQA’s retrieval, summarization, and query-generation steps into a single retrieval-pipeline node, keeping the forward program, calibration trajectories, backbone, and held-out examples fixed.

Attribution graphQwen-Flash EM on 300 examplesChange
Fine-grained75.33% (226/300)—
Coarse retrieval pipeline + answer73.67% (221/300)−1.67 pp

Merging retrieval, summarization, and query generation into a single attribution node reduced accuracy by only 1.67 percentage points, from 75.33% to 73.67% (paired McNemar p=0.332p=0.332). This suggests that route-local feedback remains effective when several functional steps share one module: corrections target the combined retrieval pipeline rather than individual internal steps. Thus, the tested merging caused only a modest change in task performance.

AuthorsOpenReview ↗

The Response to Weakness2

Response to Weakness 2: Modest end-to-end repair rates

We thank the reviewer for raising the weakness. The reported 8.79% strict repair rate measures whether the regenerated response satisfies all IFBench constraints simultaneously. It is therefore stricter than diagnosis or constraint-family localization: a correction can identify the relevant failure and still fail if the frozen backbone misses another constraint during regeneration.

Evaluation stageWhat it measuresInterpretation
DiagnosisWhether the violated requirement is identifiedFeedback quality
Constraint-family localizationWhether the error is assigned to the correct constraint familyRoute-specific attribution
Strict end-to-end repairWhether the regenerated answer satisfies every constraintJoint diagnosis-and-execution success

Thus, the 8.79% rate does not imply that NLPG fails to identify useful corrections. It shows that correct feedback does not always translate into fully compliant generation under multiple simultaneous constraints. This gap is expected in our parameter-free setting because NLPG changes the external policy instruction while keeping the backbone and program fixed; it does not directly improve the model’s underlying constraint-following capability.

We hace revised Appendix C.7.1 to state explicitly that diagnosis quality and repair execution are separate outcomes, and will avoid interpreting the strict repair rate as a direct measure of feedback quality.

AuthorsOpenReview ↗

The Response to Question2

We thank the reviewer for raising this point. We profiled two offline construction-and-selection rounds, using qwen3-8b for task execution, criticism, backward reflection, and optimization. The following costs exclude preflight and final testing:

Response to Question2: Overhead of Offline Policy Construction

BenchmarkTask rolloutsTotal API requestsReported tokens
IFBench360580439,892
HotpotQA4201,5271,410,649
HoVer4203,2033,673,576

Auxiliary stages account for 33.9%, 25.2%, and 46.5% of these token budgets, respectively. Observed offline elapsed times were 18.7, 19.5, and 21.8 minutes, respectively. The additional cost is concentrated in offline adaptation and amortized over subsequent executions, keeping the recurring inference overhead low. NLPG learns short, reusable, module-specific instructions while keeping model parameters and the agent program fixed. Held-out validation screens candidate updates before activation. During final testing, frozen policies are injected into existing module contexts, requiring no additional critic, optimizer, or backward-reflection calls; the remaining overhead comes from the added policy tokens.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Rebuttal and Revisions

Dear Area Chair and Reviewers,

Thank you for your constructive feedback. We summarize the main clarifications and additional evidence below:

  1. Novelty and effectiveness. We clarified NLPG’s mechanism of consolidating localized corrections into route-indexed procedural policy memory. In controlled comparisons, NLPG outperforms both GEPA with add-only rules and TextGrad with cross-run aggregation across three benchmarks, exceeding the stronger control by 5.67–16.00 pp.

  2. Stronger backbones. Same-backbone comparisons on GPT-6.1 Sol and Qwen3-32B show that NLPG outperforms GEPA in five of six settings, with a mean advantage of 4.28 pp.

  3. Fairness and efficiency. We clarified that reflection and optimization use the same backbone as task execution. NLPG requires approximately 10–17× fewer rollouts than GEPA’s reported total optimization budgets, with broadly comparable reflection-call counts.

  4. Analysis and presentation. We revised Figures 2–4 and added paired ablations, feedback-quality and repair analyses, and a controlled policy-intervention case. The additional comparisons and cost results are included in Appendix C.

We hope this evidence addresses the reviewers’ concerns and respectfully invite its consideration in the final assessment. Thank you again for your time.

Best regards, The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.