💬 NLP

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

The paper introduces EvoTest, an evolutionary test-time learning framework that enables AI agents to self-improve during gameplay without gradients or fine-tuning by evolving their system configuration via an Evolver Agent, demonstrating superior performance on the new Jericho Test-Time Learning (J-TTL) benchmark compared to existing adaptation methods.

Original authors: Yufei He, Juncheng Liu, Yue Liu, Yibo Li, Tri Cao, Zhiyuan Hu, Xinxing Xu, Bryan Hooi

Published 2026-04-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yufei He, Juncheng Liu, Yue Liu, Yibo Li, Tri Cao, Zhiyuan Hu, Xinxing Xu, Bryan Hooi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: The "Clever but Clueless Intern"

Imagine you hire a brilliant new intern to solve a complex mystery. They are smart and can read instructions perfectly. But, if they get stuck in a hallway because they keep trying to walk through a wall, they will keep trying to walk through that wall for the next 50 days. They don't learn from their mistakes; they just repeat them.

Current AI agents are like this intern. They are "clever" (they can talk and follow rules) but "clueless" (they can't learn from a bad experience in real-time). Once they are deployed, their "brain" is frozen. They can't rewrite their own instructions to get better.

The Solution: The "Evolutionary" Approach

The authors of this paper, EvoTest, wanted to fix this. They created a system where the AI doesn't just "think" harder; it actually rewrites its own rulebook after every attempt.

Think of it like a video game character who, after dying to a boss, doesn't just try again with the same strategy. Instead, the character sits down, writes a new manual for themselves, changes their equipment settings, and then tries again.

How It Works: The Two-Actor Play

The system uses two distinct "agents" (AI personalities) working together in a loop:

The Actor (The Player):
- Role: This is the one playing the game (specifically, text-based adventure games like Zork or Detective).
- Action: It tries to solve the puzzle, gets stuck, or wins. It produces a "transcript" (a story of what happened).
- Analogy: Imagine a race car driver driving a lap. They might crash, or they might find a shortcut.
The Evolver (The Coach/Engineer):
- Role: This agent never plays the game. It only watches the transcript of the Actor's run.
- Action: It analyzes the story. "Oh, the driver crashed because they tried to turn left at a dead end. Also, they were too cautious and missed a shortcut."
- The Magic: The Evolver then rewrites the entire system for the next lap. It doesn't just tweak the driver's mind; it changes:
  - The Strategy (Prompt): "Don't turn left at the dead end; go right."
  - The Memory: "Remember that the key is in the kitchen."
  - The Settings (Hyperparameters): "Be a bit more adventurous today; take more risks."
  - The Tools: "Check your map before every turn."
- Analogy: This is the pit crew and engineer who look at the crash data, rewrite the car's manual, adjust the suspension, and tell the driver, "Next time, do exactly this."

The Benchmark: The "Jericho" Test

To prove this works, they created a new test called J-TTL (Jericho Test-Time Learning).

The Setup: The AI plays the same difficult text game over and over again (50 times).
The Goal: It must get better with every single attempt, using only the experience from the previous runs.
The Result: Most other AI methods (like simple memory or standard reinforcement learning) failed. They got stuck in loops or couldn't figure out the puzzles. EvoTest, however, kept getting smarter. In some games, it went from winning 0% of the time to winning almost every time.

Why Is This Better Than Other Methods?

The paper compares EvoTest to three other ways AI usually tries to learn:

Memory/Reflection (The "Diary" Method):
- How it works: The AI reads its old notes and says, "I failed here, so I'll try something else."
- Why it fails: It's like reading a diary but never changing your habits. You know you failed, but you don't know how to fix the specific rule that caused the failure.
- EvoTest wins: It doesn't just read the diary; it edits the rulebook.
Online Fine-Tuning (The "School" Method):
- How it works: The AI goes back to school (re-trains its neural network weights) after every game.
- Why it fails: It's too slow and expensive. It's like trying to get a PhD in 5 minutes between every lap of a race. Also, if the AI fails, it has no good data to learn from, so it can't "study."
- EvoTest wins: It learns instantly by rewriting its instructions. No heavy math or expensive hardware needed.
Prompt Optimization (The "Edit" Method):
- How it works: The AI tries to find the perfect sentence to tell itself.
- Why it fails: It's too narrow. It only changes the words, not the settings or the memory structure.
- EvoTest wins: It changes everything: the words, the memory, the settings, and the tools. It's a "whole-system" upgrade.

The Secret Sauce: "Narrative Credit Assignment"

In traditional AI learning, the AI gets a simple score: "Good job (+1)" or "Bad job (-1)."

The Problem: In complex games, you might do 100 things right and one thing wrong, and the score is still zero. The AI doesn't know which of the 100 things was good or which one was bad.
The EvoTest Solution: The Evolver reads the entire story of the game. It understands the narrative.
- Example: "The agent got stuck in a loop because it kept trying to open a locked door."
- The Fix: The Evolver writes a rule: "If a door is locked, look for a key first."
- It learns from the story, not just the score. This is much more efficient.

The Takeaway

EvoTest is a framework that allows AI agents to evolve like living organisms. Instead of being static robots that repeat mistakes, they act like a team of a Driver and a Coach. After every race, the Coach analyzes the footage, rewrites the playbook, adjusts the car's settings, and sends the Driver back out with a brand new, improved strategy.

This makes AI agents capable of learning on the fly, turning them from "clueless interns" into self-improving experts who can tackle complex, changing environments without needing to be retrained by humans.

1. Problem Statement

Current AI agents often behave like "clever but clueless interns": they can execute instructions based on a fixed policy but lack the ability to learn complex skills on the fly during test time. When deployed in novel, dynamic environments (specifically text-based adventure games with sparse rewards and irreversible consequences), existing adaptation methods fail to improve performance across consecutive episodes.

The authors identify three main limitations in current approaches:

Static Agents: Repeat the same errors without a learning mechanism.
Online Fine-Tuning (SFT/RL): Struggle with data scarcity. In sparse-reward environments, a single failed episode provides insufficient or noisy gradient signals (e.g., a reward of 0 for a wrong move is indistinguishable from a neutral move), making credit assignment difficult.
Reflection/Memory Methods: While they can recall past failures, they often fail to fundamentally alter the agent's decision-making logic, tool-use routines, or exploration strategies.

To address this, the paper introduces the Jericho Test-Time Learning (J-TTL) benchmark, designed to measure an agent's ability to progressively improve its score on the same complex game over a series of consecutive attempts within a single session.

2. Methodology: The EvoTest Framework

EvoTest is a gradient-free, evolutionary framework that improves an agent's entire configuration between episodes without updating the neural weights of the backbone Large Language Model (LLM). It operates via a two-agent loop:

A. The Agentic Configuration ( $\chi$ )

Instead of just updating a prompt, EvoTest evolves a holistic configuration $\chi = (p, M, h, u)$ :

Policy Prompt ( $p$ ): High-level strategic guidance and heuristics.
Deployment-time Memory ( $M$ ): A structured database of "Success" (state-action pairs leading to score increases) and "Failure" (patterns leading to loops or stalls) memories.
Hyperparameters ( $h$ ): Inference parameters like temperature and exploration strength.
Tool-Use Routines ( $u$ ): Python functions for state abstraction (summarizing long histories) and logic for querying memory.

B. The Two-Agent Learning Loop

Actor Agent: Plays a full episode using the current configuration $\chi^{(e)}$ . It interacts with the environment, generating a trajectory transcript $\tau^{(e)}$ and a final score.
Evolver Agent: Analyzes the full narrative transcript of the episode (not just scalar rewards) to propose a revised configuration $\chi^{(e+1)}$ $χ^{(e + 1)}$ . It performs four types of evolutionary operators:
- Prompt Mutation: Rewrites the system prompt to encode new strategies (e.g., "Always examine objects before taking them") or add "guardrails" against specific failures (e.g., "Avoid going West in the hallway").
- Memory Update: Programmatically parses the transcript to log successful state-action pairs into the success memory and identifies unproductive loops for the failure memory.
- Hyperparameter Tuning: Adjusts parameters (e.g., increasing temperature to encourage exploration if the agent is stuck in a loop).
- Tool-Use Refinement: Modifies the logic of how the agent accesses memory or abstracts states.

C. Configuration Selection (UCB)

To manage the exploration-exploitation trade-off, EvoTest uses the Upper Confidence Bound (UCB) algorithm. It selects the next configuration from a pool containing the parent configuration and newly generated "child" configurations. This prevents the system from getting stuck on a "lucky" but unstable mutation and ensures a safety net by reverting to a proven parent if a new configuration performs poorly.

3. Key Contributions

J-TTL Benchmark: A new evaluation framework using Jericho interactive fiction games to systematically measure on-the-fly learning. It highlights the failure of current methods in sparse-reward, long-horizon tasks.
EvoTest Framework: A novel evolutionary approach that decouples acting from adaptation. It evolves the entire agentic system (prompt, memory, hyperparameters, tools) via transcript-level analysis, bypassing the need for gradient-based weight updates.
Narrative Credit Assignment: The paper demonstrates that analyzing the rich, narrative feedback of an episode transcript is a more data-efficient mechanism for credit assignment than relying on sparse scalar rewards used in RL.

4. Experimental Results

The authors evaluated EvoTest on six Jericho games (Detective, Library, Zork1, Zork3, Balances, Temple) using two backbone LLMs (Gemini 2.5 Flash and Claude 4 Sonnet).

Performance: EvoTest consistently outperformed all baselines, including:
- Non-learning: Static agents.
- Memory/Reflection: RAG, Summary, Reflexion.
- Prompt Optimization: TextGrad, Promptbreeder, EvoPrompt.
- Weight-Update: Online SFT and Online GRPO (RL).
Metrics: EvoTest achieved an average Area Under the Curve (AUC) score of 0.47/0.50, significantly higher than the next best baseline (EvoPrompt at ~0.34/0.36) and online RL (GRPO at ~0.30).
Game Wins: Notably, EvoTest was the only method capable of winning the "Detective" and "Library" games, while all baselines failed to win any.
Efficiency: EvoTest is computationally practical for test-time learning. A learning step takes 20–30 seconds (one API call), whereas online fine-tuning methods require 5–10 minutes on 4 H100 GPUs per episode.
Ablation Studies: Removing any component (Prompt Evolution, UCB, Memory, Hyperparameter tuning, or Tool-Use) degraded performance, confirming the necessity of the holistic approach. The UCB selection was crucial for stability, preventing catastrophic drops in performance.

5. Significance

Data Efficiency: EvoTest proves that agents can learn complex skills from a single experience by leveraging semantic analysis of failure and success, overcoming the data inefficiency of traditional RL in sparse-reward environments.
Practicality: By avoiding gradient-based updates, EvoTest eliminates the need for expensive GPU clusters during inference, making self-improving agents feasible for real-world deployment where rapid adaptation is required.
Holistic Adaptation: The work shifts the paradigm from "prompt engineering" or "weight tuning" to whole-system evolution, demonstrating that optimizing the interplay between memory, strategy, and hyperparameters yields superior results.

In conclusion, EvoTest provides a concrete step toward truly autonomous agents that can self-improve from experience in dynamic environments, bridging the gap between static deployment and adaptive intelligence.