🤖 AI

Explore Before You Solve: The Speed--Depth Trade-off in Epistemic Agents for ARC-AGI-3

This paper critiques the ARC-AGI-3 public benchmark for being solvable by trivial non-intelligent strategies due to a speed-depth trade-off vulnerability, and proposes the AERA agent, which employs an adaptive "explore-before-solve" framework to achieve superior performance by balancing action efficiency with information gain.

Original authors: Liew Keong Han

Published 2026-05-26

📖 6 min read🧠 Deep dive

CC0 1.0

Original authors: Liew Keong Han

Original paper dedicated to the public domain under CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.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 Picture: The "Guessing Game" Problem

Imagine you walk into a room with a locked box. You don't know the combination, and you don't know what the box does. You have a limited number of tries to open it. If you guess the wrong code too many times, you lose.

This is exactly how the ARC-AGI-3 benchmark works. It puts an AI in a new, unknown game and asks it to figure out the rules and the goal just by playing. The AI is scored on efficiency: if a human takes 10 steps to solve it, and the AI takes 20, the AI gets a very low score. If the AI takes 100 steps, it gets almost zero credit.

The paper argues that current AI systems are terrible at this because they try to solve the puzzle immediately without exploring it first. They guess the answer based on a hunch, and if they are wrong, they waste all their turns.

The Core Discovery: The Public Games Were "Broken"

Before building their solution, the authors did something surprising: they tried to solve all 25 public games using the "dumbest" strategies possible.

They found that every single one of the 25 public games could be beaten without any intelligence at all.

The "Magic Button": For 18 games, simply pressing a specific button (or clicking a specific spot) that causes a computer error (a "crash") tricks the system into thinking you won.
The "Spam" Strategy: For 8 games, you just have to press the same button 50 to 200 times in a row.
The "Blind Guess": For the remaining games, a random guess or a single probe works.

The Takeaway: The public test is flawed. It cannot tell the difference between a super-intelligent robot and a robot that just got lucky or is spamming buttons. The real test is the private set of 55 games, which we can't see yet.

The Solution: AERA (The "Curious Detective")

Since the public games were too easy to trick, the authors built a new AI agent called AERA to see if it could actually learn to explore properly. They designed it to act like a human detective rather than a guessing machine.

AERA follows a three-step process, which they call the Speed–Depth Trade-off:

EXPLORE (The "Probe" Phase):
- Analogy: Imagine you are in a dark room. Instead of running blindly toward a door you think is there, you first tap the walls with a stick to see where the obstacles are.
- How it works: AERA takes a few small, safe actions just to see what happens. It asks, "If I do this, what changes?" It builds a mental map of the rules.
- The "Budget": The authors found that spending about 40% of your total allowed moves just exploring is the sweet spot. If you explore too little, you guess wrong. If you explore too much, you run out of moves before you can actually solve the puzzle.
VERIFY (The "Double-Check" Phase):
- Analogy: You think the door is behind the bookshelf. Before you run to it, you peek around the corner to make sure you aren't wrong.
- How it works: AERA tests its best guess with a few specific actions to see if it holds up. If the guess fails, it goes back to step 1.
PLAN (The "Sprint" Phase):
- Analogy: Now that you know the layout, you sprint to the door.
- How it works: Once AERA is confident, it stops exploring and executes the solution quickly to maximize its score.

The Results: Why "Dumb" AI Fails

The authors tested this "Curious Detective" (AERA) against two other types of AI:

The Random AI: Just presses buttons randomly. (Score: 0)
The "No-Explore" AI: Tries to solve the puzzle immediately without checking anything first. (Score: 0)

Why did the "No-Explore" AI fail?
Because it didn't have a map. It tried to plan a route through a maze it had never seen. It got stuck immediately.

How did AERA do?

On a small test of 5 games, AERA solved 2 of them (a huge improvement over 0).
On the full set of 25 public games, AERA solved 4 of them.
Crucially, AERA achieved a score of 0.21, while the "dumb" strategies scored 0.00.

This proves that exploration is the missing ingredient. The AI didn't need to be "smarter" in terms of raw brain power; it just needed to be more curious.

The "Speed vs. Depth" Metaphor

The paper introduces a concept called the Speed–Depth Trade-off.

Speed: How fast you finish the puzzle (fewer moves).
Depth: How much you learn about the rules with each move.

The authors argue that the scoring system (RHAE) punishes you quadratically for being slow. This means if you take twice as many steps as a human, you don't just get half the points; you get one-quarter the points.

To get a good score, you have to be on the "Pareto Frontier"—the perfect balance where you learn just enough (Depth) to stop wasting time, but not so much that you run out of moves (Speed). AERA tries to find this perfect balance automatically.

The "Model Size" Surprise

The authors found something weird about the size of the AI brain:

Small Brain (0.5B parameters): When forced to explore, it actually did better than when it tried to plan immediately. It was "dumb" enough to accidentally hit the right button by trying random things.
Big Brain (1.5B parameters): When forced to explore, it did worse than when it just guessed. It was "too smart" and confident in its wrong guesses, so it didn't try enough random things to find the lucky break.

Lesson: Being smarter doesn't always mean being better at exploring. Sometimes, a little bit of "confusion" helps you find the right answer faster in a totally new world.

Summary

The Problem: Current AI benchmarks are too easy to "cheat" on, and AI systems are too eager to guess without learning the rules first.
The Fix: Build an AI that pauses to explore (like tapping a dark room with a stick) before it commits to a solution.
The Result: This "Explore-then-Solve" approach allows even small AI models to solve puzzles that "smart" but impatient models cannot.
The Reality Check: The public test games were so simple that even a "crash bug" or "spamming a button" could win. The real test of intelligence is still the hidden, private set of games where these tricks won't work.

The paper concludes that true intelligence isn't just about knowing the answer; it's about knowing how to find the answer when you start with nothing.

Technical Summary: The Speed–Depth Trade-off in Epistemic Agents for ARC-AGI-3

1. Problem Statement

The paper addresses the challenge of interactive rule induction within the ARC-AGI-3 benchmark. Unlike static benchmarks, ARC-AGI-3 places agents in novel, turn-based environments where the rules and win conditions are hidden. Agents must discover these rules through interaction (actions and observations) without prior instructions.

The performance metric, RHAE (Ratio of Human Actions to AI Actions, squared), imposes a severe quadratic penalty for inefficiency. If an agent uses twice as many actions as the human median, it receives only 25% credit. The authors argue that current frontier models fail this benchmark not due to a lack of reasoning capability, but due to a lack of epistemic discipline: they fail to explore the environment to reduce uncertainty before committing to a plan.

Furthermore, the paper identifies a critical flaw in the public evaluation set (25 games): it fails to distinguish between intelligent exploration and trivial heuristics. The authors demonstrate that every public game is solvable via non-intelligent strategies (e.g., blind single actions, repeated actions with sufficient budget, or exploiting a library-level null-coordinate vulnerability). Consequently, the public set cannot validate whether an agent possesses genuine exploratory intelligence; only the private 55-game set serves as a valid test.

2. Methodology

Theoretical Framework: Speed–Depth Trade-off

The authors formalize the interaction between Speed (action efficiency, $1/A_E$ ) and Depth (information gain per action, $\Delta H(b)/a$ ).

Pareto Frontier: They posit that an optimal policy lies on a Pareto frontier between Speed and Depth.
Convexity Assumption (A1): Assuming the frontier is convex, the RHAE metric acts as a second-order penalty for deviating from this frontier.
Implication: Agents that skip exploration (Depth = 0) or over-explore (excessive Speed cost) incur quadratic penalties. The optimal strategy involves a "Speed–Depth" balance where exploration budget is proportional to the human baseline.

Architecture: AERA (Adaptive Epistemic Reasoning Agent)

AERA implements a three-phase architecture designed to navigate the Speed–Depth trade-off:

EXPLORE (Depth Mode): The agent performs actions to reduce belief entropy ( $H(b_t)$ $H (b_{t})$ ). Actions are selected to maximize expected information gain. The phase continues until the entropy proxy (length of the UNCERTAIN field in the LLM output) falls below a threshold $\theta$ $θ$ .
- Budget Heuristic: The exploration budget $B_{max}$ is set empirically to approximately 40% of the human median action count ( $\alpha \approx 0.4$ ).
VERIFY: The agent performs 1–3 targeted actions to falsify the current Maximum A Posteriori (MAP) hypothesis. If falsified, it re-enters the EXPLORE phase.
PLAN + EXECUTE (Speed Mode): Once uncertainty is low, the agent commits to a plan based on the verified hypothesis. Execution aborts and re-enters EXPLORE if unexpected observations occur.

Implementation Details

Models: Experiments utilize Qwen2.5-0.5B and Qwen2.5-1.5B.
Entropy Proxy: Instead of a formal particle filter, AERA uses the length of the LLM's structured UNCERTAIN output as a heuristic proxy for belief entropy.
Competition Entry: A separate submission (BFS solver with offline pre-solve cache) implements the same "EXPLORE-before-PLAN" principle without LLM APIs, achieving RHAE=0.30 on the private set.

3. Key Results

Empirical Performance on Public Games (25 Games)

AERA (0.5B, b=1): Achieves RHAE = 0.2116, solving 4/25 games (VC33, FT09, LP85, S5I5).
Baselines:
- Random: RHAE = 0.0000 (0/25 solved).
- No-Explore (B1): RHAE = 0.0000 (0/25 solved). The 0.5B model fails to generate a plan without an explicit hypothesis formed during exploration.
Model Capability Interaction:
- On a 5-game subset, the 0.5B model with exploration (b=1) achieves RHAE=0.5290, while the 1.5B model with no exploration achieves 0.2645.
- Surprisingly, the 1.5B model with forced 1-step exploration (b=1) scores 0.0000, performing worse than its no-explore counterpart. The authors hypothesize that larger models have more concentrated action distributions, making them less likely to accidentally trigger serendipitous win conditions (like FT09's single-action win) compared to the more diffuse 0.5B model.

Benchmark Validity Analysis

A systematic investigation of all 25 public games reveals:

10 games are solvable in a single blind step (5 via ACTION6, 5 via other blind actions).
5 games require ACTION6 after a single probe.
1 game requires diverse exploration.
1 game is solvable by repeated ACTION1.
8 games are solvable by repeating a single action 50–200 times (budget-constrained).
18 games can be bypassed in 1 step via a null-coordinate vulnerability (calling ACTION6 with x=None, y=None triggers a library exception misclassified as a win).
Conclusion: The public set cannot discriminate intelligent exploration from trivial heuristics. The genuine intelligence test remains the private 55-game set.

Competition Results

The linked code track entry (BFS-based implementation of the explore-first principle) achieves RHAE = 0.30 on the full 55-game private evaluation, outperforming the reported community best of ~12.58% at the time of writing.

4. Significance and Claims

The paper makes three primary contributions:

Theoretical: It interprets the quadratic RHAE metric as a Speed–Depth Pareto frontier penalty. Under a convexity assumption (proven for a class of uniform-information environments), the metric mathematically penalizes agents that fail to balance information gain with action efficiency.
Architectural: It introduces AERA, a framework that explicitly gates the transition from exploration to planning based on belief entropy. This demonstrates that exploration is necessary for smaller models (0.5B) to achieve non-zero RHAE, whereas larger models (1.5B) may rely on priors but still suffer if exploration is forced incorrectly.
Empirical/Benchmark Critique: It provides a rigorous critique of the ARC-AGI-3 public evaluation set, showing it is invalid for measuring exploration because all games are reachable via non-intelligent strategies. The authors argue that the gap between human and AI performance is not a reasoning gap but an epistemic discipline gap.

Modest Claims:

The authors do not claim AERA solves the general ARC-AGI-3 problem or reaches the 85% target.
The exploration budget heuristic ( $\alpha \approx 0.4$ ) is an empirical fit, not a derived law.
The convexity assumption (A1) is not proven for all environments, only for a specific class.
The "null-coordinate" win is reported as a benchmark vulnerability, not an intelligent strategy, and is excluded from legitimate RHAE comparisons.

The paper concludes that the "EXPLORE-before-PLAN" principle is a fundamental mechanism for first-contact behavior in novel environments, and that future progress toward AGI requires architectures that explicitly manage the trade-off between information gathering and action efficiency.