ExplorationBench: Measuring AI Systems' Exploration in Verifiable Alien Worlds
Ming Zhang, Zhenghao Xiang, Peizhong Gao, Yujiong Shen, Yuhui Wang, Zhonghan Yue, Shihan Dou, Zhangyue Yin, Junjie Ye, Shichun Liu, Weihuang Zheng, Jiahao Chen, Jiayi Chen, Hongzhang Liu, Jiaqi Shao, Tao Gui, Qi Zhang, Xuanjing Huang, Suncong Zheng, Maxm Pan
cs.AI, cs.CL
2026-09-25
ExplorationBench tests exploration in executable anti-prior worlds. Best AlienCode hits 87.6% after four rounds vs ≤11% without feedback; same-system traces differ by 72.8 points.
Exploration means choosing what to test, updating beliefs, and applying new rules to held-out work. Most benchmarks either paste the new knowledge into the prompt or score the world state instead of later transfer. Genuine discoveries are hard to grade on the spot. ExplorationBench compresses the problem into two executable worlds whose rules contradict familiar priors. An interpreter or a proof checker grades every answer. No LLM judge.
AlienCode is a small calculation language with 31 hidden rules and 70 held-out tasks. Integer literals are XOR-ed with 27, so EMIT(100) prints 127. PLUCK counts from one while the manual says zero. AlienLogic is first-order natural deduction with 24 patched inference rules and 70 tasks. Unprovable items get credit only for a correct refusal.
Every system starts from the same flawed manual and ten fixed examples, then submits programs or proofs for four rounds. After each round, tools are disabled. The system answers each of 70 tasks three times and reports the rules it thinks it found. The headline score is Best@3: the best complete endpoint among three independent traces. Controls include the same number of turns without environment feedback, replaying the system's own best probes, a fixed probe sequence, and an open-book dump of every rule.
Ten frontier systems run at their highest reasoning setting, three traces per sandbox.
Before exploration, no AlienCode trace exceeds 15.7%. After four rounds, Best@3 reaches 87.6% (Claude Opus 5), and 7 of 10 systems clear 60%. The same thinking turns without feedback leave AlienCode at 0.5–11.0%. AlienLogic starts at 32.9–51.9% and reaches 58.1–83.8% Best@3 (Grok 4.6 leads).
| System | AlienCode M4 | AlienLogic M4 |
| Claude Opus 5 | 87.6 | 77.6 |
| GPT-5.6 Sol | 87.1 | 75.2 |
| Grok 4.6 | 67.6 | 83.8 |
| DeepSeek-V4-Pro | 12.9 | 73.8 |
Who designs the experiments matters. On AlienCode, autonomous exploration has median 66.0%, hindsight replay 40.7%, fixed probes 5.7%. Rank correlation across sandboxes is Spearman 0.35. When a trace states every required rule correctly, those tasks are still solved only 70.9% of the time. Same-system traces differ by up to 72.8 points (Kimi K3 on AlienCode: 4.8% versus 77.6%). Six of 30 AlienCode traces finish at least 3 points below an earlier milestone.
Few benches split "can you gather evidence" from "can you use the new rule." Static knowledge training will score near zero here. Best@3 asks whether a system can build one working trajectory, not whether it is reliable. Mean@3 and the worst trace are reported beside it.
Both worlds are deterministic toys. Real science has noise, cost, incomplete observations, and horizons much longer than four rounds. Three traces per system show variance; they do not pin down a distribution. Open-book AlienLogic already hits 93–97%, so exploration adds almost nothing there. That sandbox is a discovery bottleneck, not a use bottleneck.