ExplorationBench: Measuring AI Systems' Exploration in Verifiable Alien Worlds

AI summary

Overview

Research area: Evaluation of AI systems (large language model agents) for autonomous exploration and discovery, specifically whether agents can acquire genuinely new knowledge by experimenting in unfamiliar environments and then apply it to unseen tasks.

Technical level: Intermediate. The protocol and metrics are explained clearly, but readers benefit from familiarity with LLM agent evaluation, benchmarks, and terms like held-out accuracy and Best@n.

Scope: The paper introduces ExplorationBench, a benchmark built on two executable "alien worlds" whose hidden rules contradict the provided manual and pre-training priors, and reports results for ten frontier AI systems across four exploration rounds.

What This Paper Is About

Evaluating whether AI systems can actually explore is hard because two requirements conflict: the tasks must be genuinely new (so success cannot come from memorized pre-training knowledge), yet the answers must be exactly verifiable (so an evaluator can tell a real discovery from a confident but wrong claim). ExplorationBench resolves this by putting systems in deterministic, executable "alien worlds" whose rules are verifiable by a program checker but deliberately contradict familiar knowledge, so recall misleads rather than helps. The goal is to measure the full path from choosing experiments, to reporting discovered rules, to applying those rules on held-out tasks.

Key Contributions

1. A verifiable alien-world benchmark for exploration. ExplorationBench contains two sandboxes: AlienCode, a small programming language with hidden semantics, 31 discovery targets, and 70 held-out tasks, and AlienLogic, a natural-deduction system with 24 discovery targets and 70 held-out tasks. Together these are 55 discovery targets and 140 held-out tasks, checked by an interpreter or a proof-checker rather than an LLM judge.

2. A protocol that separates finding from using knowledge. Every system starts from the same flawed manual and worked examples, explores for four rounds with a tool-call schema, and is tested at milestones M0 through M4 with tools disabled, reporting both the rules it believes and its held-out accuracy.

3. Controlled conditions that isolate what drives gains. Five exploration conditions (autonomous, hindsight, fixed-probe, without-tool, direct) plus an open-book condition (rules supplied before exploration as O@M0, or after autonomous exploration as A4+O) vary whether environment feedback arrives and who designs the probes.

4. A system-level evaluation of ten frontier systems. Each system runs three independent trajectories per sandbox and is scored by Best@3, with answering noise, trajectory spread, and rule reports reported separately.

Main Findings

• Exploration, not recall or extra thinking, produces the required knowledge. Before exploring, no AlienCode trajectory exceeds 15.7% at M0. After four rounds, Best@3 reaches 87.6% in AlienCode and rises to 58.1–83.8% in AlienLogic (which starts higher, at 32.9–51.9%, because its altered rules leave part of standard natural deduction intact). Without-tool answering leaves AlienCode at 0.5–11.0% and in AlienLogic changes accuracy by −12.4 to +13.8 points, lowering it for three systems.

• Exploration works best when the system designs its own experiments — in AlienCode. In AlienCode the median falls from 66.0% under autonomous exploration to 40.7% under hindsight (replaying the system's own best probes) and 5.7% under fixed probes. Autonomous beats hindsight for 9 of 10 systems, by a median of 17.1 points, even though the replayed evidence is identical in a deterministic sandbox. Gemini 3.8 Flash is the exception (85.2% under hindsight against 77.6%).

• Who designs the probes matters less in AlienLogic. Autonomous and hindsight exploration tie (median difference 0.5 points), while hindsight exceeds fixed probes by a median of 21.7 points, so which proofs are tried matters more than who chose them.

• Exploration ability varies across settings. The Spearman correlation between the two Best@3 rankings is 0.35. Grok 4.6 ranks fifth in AlienCode and first in AlienLogic; DeepSeek-V4-Pro moves from last to sixth. AlienCode spreads Best@3 over 12.9–87.6%, whereas eight of 10 systems fall within 72.4–83.8% in AlienLogic.

• Discovering rules beats being told them in AlienCode, but not in AlienLogic. In AlienCode the Best@3 trajectory outscores O@M0 for 7 of 10 systems (GPT-5.6 Sol 87.1% against 68.1%; Hy4 preview 62.4% against 27.1%), and A4+O beats O@M0 in 26 of 30 trajectories by a median of 14.5 points. In AlienLogic, O@M0 alone reaches 93–97%, no Best@3 trajectory matches it, and exploring first adds nothing (median 0.0 points). Seed2.1 Pro even scores lower under A4+O than O@M0 (55.2% against 61.4%).

• Two keystone rules dominate AlienCode. The PLUCK index shift (R14) and CARVE slice shift (R15) together enter 51 of the 70 tasks. Of the 15 trajectories ending at or above 50%, 13 state both correctly; of the 9 ending below 25%, 6 state neither. Of the 13 jumps of at least 30 points between consecutive milestones, 12 occur in the round where the rule report newly states R15 correctly and 11 where it newly states R14. The number of rules stated correctly at M4 correlates with M4 at r = 0.85.

• Knowing a rule does not guarantee using it. When a trajectory's M4 rule report states every rule a task requires, the task is still solved only 70.9% of the time (647 task–trajectory pairs). Two trajectories state both keystone rules yet end at 4.8% and 12.9%. A task whose required rule is stated incorrectly is still solved 34.3% of the time, and in 26 of 30 trajectories a rule stated correctly later drops out of the report while accuracy on tasks requiring it rises from 11.4% to 16.8%.

• Exploration is unreliable across trajectories of the same system. Answering noise is small (standard deviation at most 4.7 points in AlienCode and 2.9 in AlienLogic), but trajectories of one system differ by up to 72.8 points in AlienCode and 21.0 in AlienLogic. Kimi K3 and Gemini 3.8 Flash each end between roughly 5–6% and 77.6%, and every AlienCode trajectory spends 45–48 of its 48 tool calls. The aggregate choice changes rankings: Qwen3.8-Max ranks sixth by Best@3 but third by Mean@3, while Kimi K3 falls from a tie for third to seventh.

• Gains arrive in leaps and can reverse. In each AlienCode Best@3 trajectory the largest single step contributes 45–92% of the retained gain, and the round in which it arrives differs by system (first round for GPT-5.6 Sol; second for Claude Opus 5, Kimi K3, and Gemini 3.8 Flash; third for Grok 4.6 and Hy4 preview). Of 30 AlienCode trajectories, 6 end at least 3 points below an earlier milestone, as do 3 of 30 AlienLogic trajectories; Gemini 3.8 Flash's AlienLogic Best@3 peaks at 63.8% after the first round and ends at 58.1%.

• A case study shows one probe can crack the world. GPT-5.6 Sol's trajectory 2, using 12 tool calls in round 1, exposed both keystone shifts with one probe; its rule report went from 8 of 31 rules correct at M0 to 28 at M1, and held-out accuracy rose from 11.0% to 81.0% (on the 51 tasks using R14 or R15, from 9.8% to 79.1%).

Methodology in Plain English

The researchers built two small, fully deterministic worlds and deliberately published the wrong instruction manual for each. AlienCode looks like a normal little programming language, but familiar operators behave differently — integer literals are silently XOR-ed with 27 so EMIT(100) prints 127, PLUCK counts from one instead of zero, and SHATTER means multiply rather than destroy. AlienLogic looks like a standard proof system, but 24 inference rules have been changed with side conditions such as duplicate-premise and use-once guards. Some rules are left unchanged as red herrings. Crucially, because the worlds are executable, every answer can be graded by running an interpreter or a proof-checker, with no LLM judge involved.

Each system receives the same flawed manual and the same worked examples (ten examples for AlienCode across five task bands, eight accepted proofs for AlienLogic). It then runs four rounds in which it submits programs or proofs as "probes," reads the deterministic output, and updates its hypotheses. Nothing else enters the context: no weight updates, no persistent memory, no scalar reward, and a fixed maximum budget B = (C, P, T) of tool calls, probe units, and exploration tokens that is recorded but not scored.

At each milestone M0 through M4 the system is tested in a fresh copy of the conversation with tools disabled. It states the rules it believes hold and answers the 70 held-out questions, each answered three times so that answering noise can be measured separately from exploration variability. The headline score is Best@3, the best final accuracy among three independent trajectories, chosen once by its complete M4 score so that no synthetic trajectory is assembled from different runs. Control conditions swap the system's probes for its own best sequence (hindsight), for a fixed model-independent sequence, or for no environment feedback at all, and open-book conditions supply the full rule set.

Why This Matters

Impact on research: ExplorationBench gives a way to measure exploration as its own capability, separate from retrieval and one-shot reasoning. Because the worlds are executable, it avoids LLM-judge grading and contamination concerns, and it separates three things that results show diverge: which probes a system picks, what rules it reports, and whether it can actually use them on unseen tasks. The finding that systems can acquire unfamiliar rules but do so unreliably, and sometimes lose progress with continued exploration, points at concrete failure modes for agent research.

Real-world applications:

• Evaluating AI agents that must diagnose unfamiliar software, systems, or configurations where documentation is wrong or outdated.
• Assessing scientific and engineering agents that must design experiments rather than only reason over provided data.
• Benchmarking tool-using assistants whose competence depends on probing an environment's actual behavior.
• Selecting and monitoring AI systems for workflows where an agent's self-reported understanding cannot be trusted without checking downstream task accuracy.

Industry relevance: Any organization deploying agents that act on unfamiliar environments — code synthesis, formal verification, data engineering, automation — needs evidence that the agent learns from feedback rather than replaying memorized patterns. The paper's controls also give a framework for testing whether a vendor's claimed gains come from real exploration or from extra inference turns without evidence.

Future Directions

• Extending the benchmark beyond two deterministic, executable worlds, whose exactness is also a limitation: real scientific exploration involves noisy or incomplete observations, costly or irreversible experiments, open-ended hypothesis spaces, and horizons far longer than four rounds.
• Improving reliability, since same-system, same-budget trajectories can end up to 72.8 points apart in AlienCode, and 6 of 30 AlienCode trajectories end at least 3 points below an earlier milestone.
• Closing the gap between stating a rule and using it, given that tasks whose rules a system reports correctly are still solved only 70.9% of the time.
• Scaling the statistical picture: three trajectories per system and three answers per question expose variability but are insufficient to estimate either distribution precisely.
• Building exploration methods that improve transfer across different task settings, given the Spearman correlation of 0.35 between the two sandbox rankings.

Target Audience

Researchers and engineers working on LLM agents, agent evaluation, and AI for scientific discovery — particularly those designing benchmarks for reasoning, tool use, or self-improvement. It is also useful for practitioners who deploy tool-using agents in unfamiliar environments and need to know whether performance reflects genuine learning from evidence or recall of already-known material. Readers mainly interested in static knowledge benchmarks may find the protocol details more relevant than the sandbox specifics.

Note: the paper's comparison table (Table 2), which positions ExplorationBench against related benchmarks such as MARS, DiscoveryWorld, NewtonBench, COLLIE, MLAgentBench, Voyager, CL-bench, EvaLearn, SWE-bench, WebArena, and tau-bench, is truncated in the available content, so its full contents are not summarized here.

Authors’ abstract

Scientific discovery begins where known problems end. There, AI systems must engage in exploration: framing hypotheses, designing experiments, and iterating on the results. However, evaluating this ability is difficult: (1) how to verify whether a genuinely new hypothesis holds, and (2) how to determine whether a system has discovered it through exploration or merely recalled related knowledge from pre-training data. To this end, we introduce ExplorationBench, which turns the wicked problem of evaluating scientific exploration into a concrete and tractable framework built on verifiable Alien Worlds: their rules are executable, so every answer can be checked exactly, and they conflict with familiar knowledge, so recall alone cannot solve the tasks. The benchmark contains two sandboxes, AlienCode (31 discovery targets, 70 tasks) and AlienLogic (24 discovery targets, 70 tasks). Each sandbox provides a flawed manual, task-specific environmental feedback, and a dedicated tool-call schema. Systems use these resources to explore the sandbox, then solve held-out tasks. We evaluate 10 AI systems and find that the strongest systems can acquire and apply unfamiliar rules, while performance varies substantially across trajectories and continued exploration can stall or reverse earlier gains. ExplorationBench represents a step towards AI systems that can acquire and apply genuinely new knowledge through exploration in unknown environments.