💬 NLP

Planning to Explore: Curiosity-Driven Planning for LLM Test Generation

The paper introduces CovQValue, a curiosity-driven planning method that treats code branch structure as an unknown environment and uses LLM-estimated Q-values to select informative test generation plans, significantly outperforming greedy approaches in achieving higher branch coverage on both existing and newly proposed benchmarks.

Original authors: Alfonso Amayuelas, Firas Laakom, Piotr Piękos, Wenyi Wang, Yifan Xu, Yuhui Wang, Jürgen Schmidhuber, William Wang

Published 2026-04-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Alfonso Amayuelas, Firas Laakom, Piotr Piękos, Wenyi Wang, Yifan Xu, Yuhui Wang, Jürgen Schmidhuber, William Wang

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 "Greedy" Explorer

Imagine you are a treasure hunter exploring a massive, unknown castle. Your goal is to find every single hidden room and secret passage.

Most current AI tools (LLMs) used for writing computer tests act like greedy explorers.

How they work: They look at the hallway right in front of them. If they see a door that leads to a room they haven't visited yet, they walk through it immediately.
The flaw: What if the most valuable treasure is in a room deep inside the castle, but to get there, you first have to walk through a long, boring hallway with no doors?
The result: The greedy explorer gets stuck in the first few rooms. They keep opening the same easy doors because they only care about finding something new right now. They never realize that walking down that boring hallway is the only way to unlock the secret vault later.

In computer terms, this is called the "Corridor Problem." To reach deep, complex code, you often need to set up a sequence of steps (like logging in, initializing a database, or importing specific files). If you don't do these steps, you get zero "coverage" (you don't see any new code). Greedy AI stops trying because it thinks it's wasting time.

The Solution: The "Curious Planner" (CovQValue)

The authors of this paper propose a smarter approach called CovQValue. Instead of just looking at the next step, this AI acts like a strategic explorer with a map.

Here is how it works, using our castle analogy:

1. The Map (The Coverage Map)

Every time the AI tries a test, it updates a "map" of the castle. This map shows exactly which rooms (code branches) have been visited and which are still dark and unknown.

Old way: The AI forgets the map after every step.
New way: The AI constantly looks at the map to see where it has been and where it needs to go.

2. The "What If" Game (Planning)

Instead of picking just one door to open, the AI imagines three different adventure plans at once:

Plan A: Try to break the front door (easy, but maybe nothing new behind it).
Plan B: Walk down the long, boring hallway to the library (boring at first, but leads to a treasure room).
Plan C: Climb the tower (risky, might fall, but offers a new view).

3. The "Curiosity Score" (Q-Value)

This is the magic sauce. The AI doesn't just ask, "Which plan finds a new room right now?"
It asks: "Which plan will teach me the most about the castle in the long run?"

It gives a score to each plan based on two things:

Immediate Gain: How many new rooms does this plan open today?
Future Potential: If I do this plan, will it unlock future doors that are currently locked?

The Analogy:

Greedy AI sees the long hallway and says, "No new rooms here! I'll skip it."
CovQValue AI sees the hallway and says, "This hallway has no doors yet, but if I walk all the way to the end, I'll find the key to the Master Bedroom. I'll take this plan!"

How They Tested It

The researchers built a new "training ground" called RepoExploreBench. Imagine a set of 93 different, complex software "castles" (Python packages like Flask, Requests, and Pydantic).

They pitted the Greedy AI against the Curious Planner (CovQValue) using three different AI models (Gemini, GPT, and Mistral).

The Results:

The Greedy AI got stuck early. It explored the easy rooms and gave up, covering only about 30–50% of the castle.
The Curious Planner kept going. It was willing to take the "boring" steps to unlock the deep secrets. It covered 40% to 77% more of the code than the greedy approach.
The Trade-off: The Curious Planner was a bit more "risky." It tried harder, stranger things, so some of its tests failed (crashed). But because it was willing to crash to find the truth, it found way more hidden code than the cautious AI.

Why This Matters

This paper proves that AI needs to be patient and strategic, not just reactive.

For Software: It means we can automatically find bugs in deep, complex parts of code that humans and current tools miss.
For the Future: This "curiosity" isn't just for code. It could help robots explore unknown environments, scientists design new experiments, or AI agents learn to navigate complex real-world systems by planning ahead rather than just reacting to the immediate moment.

In a nutshell: Don't just look at the door in front of you. Look at the map, imagine the future, and be willing to walk down the boring hallway if it means finding the treasure at the end. That is the power of Curiosity-Driven Planning.

1. Problem Statement

The paper addresses the limitations of current Large Language Model (LLM) approaches to automated test generation. While LLMs are effective at generating code and tests, existing methods typically rely on greedy strategies that maximize immediate code coverage gain.

The Core Issue: In complex codebases, reaching deep program branches often requires a sequence of "setup steps" (e.g., specific initialization chains, validation gates, or import dependencies). Individually, these steps yield zero new branch coverage.
The Consequence: Greedy agents, which only select actions that provide immediate coverage, get stuck in local optima. They fail to traverse these "corridors" of zero-gain steps, preventing them from discovering deep, critical program behaviors.
The Gap: Current methods treat test generation as a series of independent, single-step optimization problems rather than a sequential exploration of an unknown environment.

2. Methodology: CovQValue

The authors propose CovQValue, a method that frames iterative test generation as Bayesian Exploration. Instead of greedy selection, the method uses a "curiosity-driven" planning approach inspired by reinforcement learning and information theory.

Key Conceptual Framework

Environment: The program's branch structure is treated as an unknown environment ( $\Theta$ ).
State: The Coverage Map (the set of branches discovered so far) serves as a sufficient statistic for the agent's exploration state, acting as a proxy for the posterior distribution $p(\Theta|h)$ .
Action: Generating a Test Plan (a sequence of $S$ test scripts) rather than a single test.
Objective: Maximize cumulative information gain (branch coverage) over time, balancing immediate discovery with future reachability.

The Algorithm

The CovQValue method operates in an iterative loop:

Diverse Plan Generation: Given the current coverage map, the LLM generates $K$ diverse candidate test plans. Each plan is prompted with a different "exploration directive" (e.g., targeting error handling, main functionality, or cross-module interactions) to ensure structural diversity.
Curiosity Q-Value Estimation: The LLM acts as a heuristic estimator to score each plan. It predicts two values for each plan:
- Immediate Gain ( $\hat{g}$ ): The expected number of new branches the plan will discover immediately.
- Future Reachability ( $\hat{v}$ ): The expected number of additional branches that will become reachable in the future as a result of executing this plan (e.g., passing a validation gate).
Scoring: The Q-value is calculated using the formula:
$Q = \hat{g} + \gamma \cdot \hat{v}$
Where $\gamma$ is a discount factor (set to 0.5 in experiments) balancing immediate vs. future gains.
Selection & Execution: The plan with the highest Q-value is selected and executed. The resulting coverage map is updated, and the loop repeats.

3. Key Contributions

Formalization of Test Generation as Bayesian Exploration: The paper provides a theoretical grounding for LLM test generation, treating the coverage map as a sufficient statistic and using recursive Q-values to optimize for long-term information gain rather than short-term rewards.
RepoExploreBench: The authors introduce a new benchmark specifically designed for iterative, exploration-based test generation. It consists of 93 modules from 9 popular Python packages (e.g., Flask, Requests, Pydantic) selected for their "corridor structure" (complex setup requirements), where greedy methods typically fail.
CovQValue Method: A practical implementation that combines coverage feedback, diverse plan generation, and LLM-estimated Q-value scoring to navigate complex code structures.

4. Experimental Results

The method was evaluated on RepoExploreBench and the existing TestGenEval Lite benchmark using three LLMs: Gemini 3 Flash, GPT-5.4 Mini, and Mistral Large 3.

Performance Gains:
- RepoExploreBench: CovQValue achieved 40–74% higher branch coverage compared to greedy selection.
- TestGenEval Lite: CovQValue achieved 51–77% higher branch coverage.
- Win Rate: CovQValue outperformed greedy baselines on 77–84% of individual targets across all models.
Corridor Navigation: In case studies (e.g., flask.app), greedy methods remained stuck at low coverage (2 branches) because they could not traverse initialization sequences. CovQValue successfully navigated these "corridors," reaching 182 branches.
Trade-offs: The method achieves higher coverage by generating more ambitious tests that have a slightly lower pass rate (57–71% vs. 75–95% for greedy). This indicates the LLM is successfully targeting unexplored, risky code paths rather than just writing "safe" tests.
Ablation Studies:
- Planning Horizon: Longer plans (multi-step sequences) significantly improved coverage, confirming the value of lookahead.
- Components: Both "diverse generation hints" and "Q-value scoring" contributed independently to performance, with Q-value scoring providing the largest boost.
- Discount Factor ( $\gamma$ ): A value of 0.5 yielded the best results, suggesting a balance between immediate discovery and future potential is optimal.

5. Significance and Impact

Beyond Greedy Optimization: The paper demonstrates that treating code exploration as a sequential decision-making problem allows LLMs to overcome the "local optima" trap common in current test generation tools.
Generalizability: The framework is not limited to testing. The authors suggest it applies to any agent interacting with an unknown environment (e.g., API discovery, scientific experimentation) where "corridor structures" exist.
Theoretical Alignment: It bridges the gap between theoretical optimal exploration (Sun et al., 2011) and practical LLM application, showing that LLMs can effectively approximate complex Bayesian planning heuristics when provided with the right feedback loops (coverage maps).
Ethical Considerations: The authors note that while this autonomy is powerful, deploying such agents in live systems requires guardrails to prevent unintended harmful exploration, as the agent is driven by curiosity metrics rather than explicit human constraints.

In summary, CovQValue represents a shift from reactive, coverage-greedy test generation to proactive, curiosity-driven planning, enabling LLMs to discover deep and complex program behaviors that were previously inaccessible to automated tools.