ExplorationBench: Benchmarking AI Exploration in Alien Worlds

Introduction

ExplorationBench is a new benchmark designed to measure how well AI systems can explore and discover rules in completely unknown environments. Developed by Fudan University, Tencent Hunyuan, and Tsinghua University, it addresses a critical gap: most existing benchmarks test static knowledge (capability stock), whereas real-world deployment requires models to acquire new capabilities through interaction (capability increment).

Background: From Static to Interactive Evaluation

The team's prior work includes EvaLearn (NeurIPS 2025), which organized 648 questions into 182 sequential task sequences, allowing models to learn from history and feedback. It revealed that static top performers do not necessarily excel at online learning, and some models suffer negative transfer from noisy history. CL-bench then placed all required knowledge directly into the context—fictional legal codes, operational procedures, hidden regularities in data. Even with perfect context, top models averaged only 17.2% accuracy (best 23.7%), showing that context ingestion ≠ learning.

ExplorationBench Design: Two Verifiable Alien Worlds

To test genuine exploration without data contamination or unverifiable ground truth, the team constructed two fully formalized "alien worlds" with deliberately altered rules:

AlienCode : A programming language with 31 rule modifications ("discovery targets"). Examples: SHATTER performs multiplication; EMIT(100) prints 127 because integer literals are XORed with 27; PLUCK uses 1-based indexing despite manual saying 0-based; addition primitive is removed, forcing models to compose other operations.

AlienLogic : A natural deduction system with 24 modified inference rules. Some classically valid steps fail; some invalid transformations succeed. 70 held-out tasks include 23 unprovable theorems where models must recognize dead ends and refuse to prove.

Together they contain 55 discovery targets and 140 held-out tasks. AlienCode programs are judged by an interpreter; AlienLogic proofs by a proof checker and bounded decision procedure—no LLM-as-judge.

Evaluation Protocol

Each system starts from the same erroneous manual and fixed examples. Over four rounds, it submits probe code or proofs via predefined tools, receiving deterministic but unexplained execution feedback. After each round, a tool-disabled copy of the session reports believed rules and answers each held-out task three times (discarded afterward). Each system runs three independent trajectories per world; the primary metric is Best@3 (best final score across three trajectories) due to high exploration stochasticity.

Experimental Setups: Isolating Exploration Components

Five conditions test what drives improvement:

Direct Answer : Answer after examples, no exploration.

No-Tool Answer : Full rounds but no environment feedback.

Fixed Probes : Randomized probes replace self-designed experiments.

Post-hoc Replay : Replay the best trajectory's probes; system only reads results.

Autonomous Exploration : Standard process—system designs every probe.

Key Findings

Feedback Is Essential

Without tools, AlienCode scores stall at 0.5%–11.0%; three AlienLogic systems even regress. Extra thinking without new evidence merely reinforces wrong priors—one system abandoned a correctly inferred rule after four thought-only rounds.

Self-Designed Experiments Outperform Fixed or Replayed Ones

In AlienCode, median accuracy drops from 67.4% (autonomous) to 41.2% (replay) to 5.7% (fixed probes). Nine of ten systems do better when choosing their own probes (median gap 17.4 pp). In AlienLogic, autonomous and replay are similar (median diff 0.2 pp), but both far exceed fixed probes.

Discovering Rules ≠ Using Rules

Open-book conditions (full rules given before/after exploration) reveal a striking divergence:

AlienLogic: Open-book yields 96%–100%; no autonomous trajectory surpasses it. Bottleneck is discovery.

AlienCode: Seven of ten systems beat pre-exploration open-book with autonomous exploration. GPT-5.6 Sol: 88.1% autonomous vs 69.5% open-book; Hy4 preview: 63.3% vs 28.6%. 26 of 30 trajectories show "explore-then-open-book" > "open-book-from-start" (median +14.5 pp). Exploration simultaneously teaches discovery and usage.

AlienCode's critical rules are two off-by-one shifts ( PLUCK index, CARVE slice). In 13 cases where accuracy jumped >30 pp in one round, 12 coincided with understanding CARVE 's offset. One GPT-5.6 Sol trajectory used a single tool call to query four indices and a slice, all contradicting the manual; its rule report jumped from 8 to 28 correct rules, accuracy from 11.0% to 81.9%.

Yet stating a rule correctly doesn't guarantee correct application: when all required rules are reported right, tasks are solved only 73.4% of the time. Kimi K3 had two trajectories that both reported the index offset correctly; one scored 79.0%, the other 5.7% because it misapplied a top-level rule inside a function causing index overflow.

Single Scores Mask Instability and Cross-World Variability

Repeated answering within a trajectory shows low variance (≤4.7 pp), but re-running exploration yields huge spreads: Kimi K3 5.7%–79.0%, Gemini 3.8 Flash 6.2%–79.0%. Ranking changes with aggregation method (Qwen3.8-Max 6th by Best@3, 3rd by mean). Token usage varies 340K–11.6M for similar tool calls. Cross-world Spearman correlation is only 0.35: Grok 4.6 5th in AlienCode but 1st in AlienLogic; Gemini 3.8 Flash tied 3rd in AlienCode but last in AlienLogic. Progress is stepwise—largest step contributes 47%–92% of total gain, occurring at different rounds. Some trajectories regress (6/30 AlienCode, 1/30 AlienLogic); Gemini 3.8 Flash correctly refused an unprovable theorem in round 1 but later adopted an invalid workaround and encoded it as a rule.

Future Directions: Consolidation

ExplorationBench measures within-session learning. The next challenge is consolidation : can agents distill exploration records into long-term memory, reusable tools, or even parameter updates—and discard outdated knowledge when the environment changes?

References

Paper: ExplorationBench: Measuring AI Systems' Exploration in Verifiable Alien Worlds (arXiv:2609.30199)

Project page: https://explorationbench.com Code repository: https://github.com/Tencent-Hunyuan/ExplorationBench Blog:

https://explorationbench.com/blog/