EvoTest: Evolutionary Test-Time Learning for Self-Improving Agentic Systems

AI summary

Overview

• Research area: Artificial intelligence, specifically LLM-based agentic systems, test-time learning, and evolutionary prompt/agent optimization.
• Technical level: Intermediate. The paper assumes familiarity with LLM agents, reinforcement learning concepts (credit assignment, sparse rewards, online fine-tuning), and multi-armed bandit selection, but it is written so that the core ideas are understandable without deep math.
• Scope: The paper introduces a benchmark (J-TTL) for measuring whether an agent can improve at the same task across repeated attempts, and proposes EvoTest, a gradient-free framework that rewrites an agent's entire configuration between episodes.

What This Paper Is About

Most AI agents are deployed with a fixed policy: they can follow instructions but cannot reform their own process from experience. This paper first builds the Jericho Test-Time Learning (J-TTL) benchmark, in which an agent plays the same text-adventure game for several consecutive episodes and must raise its score from one episode to the next using only what it learned in that single session. It then proposes EvoTest, which improves an agent at test time without fine-tuning or gradients by having a second "Evolver" agent rewrite the Actor agent's prompt, memory, hyperparameters, and tool-use routines after every episode.

Key Contributions

1. A benchmark for test-time learning (J-TTL). Built on the Jericho suite of Interactive Fiction games, J-TTL measures an agent's on-the-fly learning ability across a session of K consecutive playthroughs of the same game, with the environment reset to its identical initial state before each episode. The paper reports that existing adaptation methods ("reflection, memory, or reinforcement learning") struggle on it.
2. A test-time learning algorithm (EvoTest). An evolutionary framework that evolves the entire agentic system — policy prompt, memory, tool-use routines, and hyperparameters — via transcript-level analysis, without gradients or fine-tuning.
3. State-of-the-art empirical results on J-TTL. The paper reports that EvoTest shows a 38% improvement over the strongest prompt-evolution baseline and a 57% improvement over online RL, outperforming reflection-based, memory-based, and gradient-based baselines on every game. It is described as the only method capable of winning two games (Detective and Library), while all baselines fail to win any.

Main Findings

• Test-time learning helps, across the board. Every learning-based method achieves a higher average AUC than the Static non-learning baseline (average 0.11 with Gemini, 0.12 with Claude). Learning curves trend upward for learning methods while the Static agent stays flat.
• EvoTest leads on every game and every backbone. EvoTest reaches an average AUC of 0.47 (google/gemini-2.5-flash) and 0.50 (anthropic/claude-4-sonnet-20250522), versus the next-best baseline EvoPrompt at 0.34/0.36. Per-game EvoTest AUCs are Detective 0.94/0.95, Library 0.77/0.80, Zork1 0.14/0.16, Zork3 0.35/0.38, Balances 0.32/0.35, and Temple 0.31/0.34.
• Whole-system evolution beats single-channel adaptation. Memory and RAG supply raw information with no strategic guidance; Reflexion, TextGrad, Promptbreeder, and EvoPrompt refine only the prompt. EvoTest can, for example, raise exploration temperature while simultaneously adding a new strategic heuristic, which single-channel methods cannot do.
• Evolutionary adaptation is more data-efficient than online RL at test time. EvoTest's average AUC (0.47/0.50) is substantially higher than GRPO (online) at 0.30. The paper attributes this to using the entire episode transcript as a rich narrative feedback signal instead of sparse scalar rewards — "credit assignment via narrative analysis" rather than backpropagation.
• Prompt evolution is the single most important component. In the ablation on Detective, EvoTest scores 0.94, dropping to 0.52 when prompt evolution is removed — the largest drop of any ablated component. Removing UCB drops it to 0.68; removing memory to 0.82; removing hyperparameter tuning to 0.89; removing tool-use refinement to 0.91.
• UCB selection prevents catastrophic collapses. The greedy variant without UCB is described as prone to sharp performance drops after over-committing to a lucky high-scoring mutation; UCB's exploration term lets the system fall back to the reliable parent configuration.
• The Evolver's LLM quality matters, but the loop works even with small models. On Detective/Zork1/Balances, AUC falls from 0.94/0.14/0.32 with openai/o3, to 0.90/0.12/0.29 with deepseek/r1, 0.82/0.10/0.25 with qwen3-32b, and 0.68/0.07/0.20 with qwen3-8b — all above the Static baseline of 0.21/0.03/0.11.
• The structure of the evolution prompt matters. Replacing the detailed Evolver prompt with a generic "analyze the trajectory and generate an improved prompt" instruction drops Detective AUC from 0.94 to 0.65, the same as EvoPrompt's 0.65.
• Under a matched backbone, EvoTest still wins. With qwen/qwen3-32b as the Actor for all methods, EvoTest averages 0.35 AUC versus GRPO at 0.31 and SFT at 0.24. Pairing that Actor with an openai/o3 Evolver raises the average to 0.40.
• Gradient-free updates are far cheaper. A fine-tuning pass on one episode's data took 5–10 minutes on 4 H100 GPUs. EvoTest's update is a single LLM call taking about 20–30 seconds; TextGrad takes 30–50 seconds and 2 calls, Reflexion 15–25 seconds, RAG 5–15 seconds with embeddings, and Memory under 1 second.

Methodology in Plain English

The setup is a text adventure game played through a standard loop: the agent reads a textual observation, types a natural-language command, and gets a score change. The games (Detective, Library, Zork1, Zork3, Balances, Temple) are hard because of long-range planning, sparse rewards, and irreversible mistakes — a single wrong move can make the game unwinnable. Episodes are capped at T = 110 steps unless stated otherwise.

Performance is measured two ways: a learning curve plotting each episode's final return, and an Area Under the Curve (AUC) defined as the sum of episode scores divided by K times R_max (the maximum achievable score in a single episode), giving a value between 0 and 1.

EvoTest splits the work between two roles. The Actor Agent plays a whole episode with one fixed configuration. The Evolver Agent then reads the full transcript plus the previous configuration and proposes new candidate configurations, mutating four things: the policy prompt (new strategies and rules against observed failures), the deployment-time memory (logging state-action pairs that preceded score increases in a "success" table and no-progress patterns in a "failure" table), the hyperparameters (such as temperature and exploration strength), and the tool-use routines (when to consult memory, and an evolvable Python "state extractor" that condenses verbose history into short milestone strings).

Choosing which configuration to run next — the parent or one of the children — is framed as an exploration-versus-exploitation problem and solved with the Upper Confidence Bound rule, which scores each candidate as its average past score plus a bonus that shrinks with the number of times it has been tried. The parent always stays in the pool, acting as a safety net.

Baselines span four groups: non-learning Static; memory-based (Memory, RAG); reflection-based (Summary, Reflexion); automated prompt optimization (TextGrad, Promptbreeder, EvoPrompt); and weight-update methods (SFT online, GRPO online). All methods use the same step budget and the same backbone LLMs for their respective roles.

Why This Matters

Impact on research. The paper argues that progress on self-improving agents has been hampered by the lack of standardized testbeds for rapid, in-session improvement. J-TTL provides one, and the paper positions EvoTest as generalizing prompt evolution (APE, OPRO, TextGrad, Promptbreeder, EvoPrompt, AlphaEvolve) into whole-system evolution, in the same spirit as EvoAgent and MASS.

Real-world applications:

• Customer-service or IT agents that must improve within a session on a repeated task type without a retraining pipeline.
• Software and web-navigation agents facing novel interfaces, where a failed attempt should inform the next one immediately.
• Scientific or data-analysis copilots that refine their own tool-use routines and heuristics after each run.
• Any deployment where retraining is impractical because the task is long-horizon, rewards are sparse, and labeled data is scarce.

Industry relevance. The efficiency comparison is the practical argument: online fine-tuning needs multiple H100 GPUs and 5–10 minutes per update, while EvoTest needs roughly one 20–30 second API call on a fixed, non-trainable backbone. The ablation showing that even qwen3-8b as the Evolver beats the Static baseline suggests the framework is deployable without the largest available models.

Future Directions

• Scaling to extremely long-horizon tasks. The conclusion explicitly names building self-evolving agents for extremely long-horizon tasks as worthwhile future work.
• Extending the benchmark. J-TTL currently covers six Jericho games with a 110-step cap; evaluating across a broader and harder set of games, and testing how the framework behaves over longer sessions, is an open question.
• Rethinking credit assignment. The claim that narrative analysis is more data-efficient than backpropagation from sparse rewards invites direct comparison against better-tuned RL or hybrid approaches on the same data budget.
• Richer whole-system evolution. Only four configuration channels (prompt, memory, hyperparameters, tool-use routines) are evolved here; the paper frames holistic optimization as an ongoing direction, and the component ablation shows several channels contribute only small individual gains, leaving room to improve how they are jointly optimized.

Target Audience

Researchers and engineers working on LLM agents, agent self-improvement, and test-time adaptation will get the most from this paper, along with practitioners who need agents that adapt in-session without a fine-tuning budget. It is also relevant to reinforcement learning researchers interested in the data-efficiency argument for gradient-free methods, and to benchmark designers looking for a template for measuring in-session learning. Readers need basic familiarity with LLM prompting, agent memory, and RL terminology; the paper's own algorithms are presented with plain-language explanations alongside their equations.

Authors’ abstract

A fundamental limitation of current AI agents is their inability to learn complex skills on the fly at test time, often behaving like "clever but clueless interns" in novel environments. This severely limits their practical utility. To systematically measure and drive progress on this challenge, we first introduce the Jericho Test-Time Learning (J-TTL) benchmark. J-TTL is a new evaluation setup where an agent must play the same game for several consecutive episodes, attempting to improve its performance from one episode to the next. On J-TTL, we find that existing adaptation methods like reflection, memory, or reinforcement learning struggle. To address the challenges posed by our benchmark, we present EvoTest, an evolutionary test-time learning framework that improves an agent without any fine-tuning or gradients-by evolving the entire agentic system after every episode. EvoTest has two roles: the Actor Agent, which plays the game, and the Evolver Agent, which analyzes the episode transcript to propose a revised configuration for the next run. This configuration rewrites the prompt, updates memory by logging effective state-action choices, tunes hyperparameters, and learns the tool-use routines. On our J-TTL benchmark, EvoTest consistently increases performance, outperforming not only reflection and memory-only baselines but also more complex online fine-tuning methods. Notably, our method is the only one capable of winning two games (Detective and Library), while all baselines fail to win any.