Graph-Based Exploration for ARC-AGI-3 Interactive Reasoning Tasks

AI summary

Overview

Research area: Artificial intelligence / interactive reasoning benchmarks, specifically the ARC-AGI-3 challenge, combining graph search, computer vision preprocessing, and exploration strategies in sparse-reward environments.

Technical level: Intermediate. The paper is readable without deep reinforcement learning expertise, but familiarity with state-space search, graph traversal, and basic RL concepts (sparse rewards, exploration vs. exploitation) helps.

Scope: The paper describes a training-free, graph-based exploration agent that solves game-like interactive reasoning tasks by systematically tracking states and prioritizing untested actions, outperforming frontier LLM-based agents on the ARC-AGI-3 benchmark.

What This Paper Is About

ARC-AGI-3 presents agents with unfamiliar game environments where the rules must be discovered through trial and error, with only one feedback signal: whether a level is completed. The paper's goal is to show that a simple, non-learning agent—one that builds an explicit map of states and actions and explores them systematically—can solve these tasks far more reliably than large language models, which currently score near zero.

Key Contributions

1. A training-free graph-based exploration method for interactive reasoning tasks that maintains a directed graph of discovered states and action transitions, without any learned policy or world model.
2. A frame processing pipeline that segments visual observations into single-color connected components, masks probable status bars, ranks candidate click targets into five priority tiers based on size, morphology, and color salience, and hashes masked frames to identify unique states.
3. A hierarchical action selection policy that exhausts high-priority untested actions at the current state, then navigates via shortest paths to frontiers (reachable states with untested actions), incrementally raising the priority threshold only when necessary.
4. Empirical evidence that structured exploration beats frontier LLMs on ARC-AGI-3, with the method ranking 3rd on the private leaderboard and substantially outperforming a GPT-4.1-based LLM+DSL baseline.

Main Findings

• Strong benchmark performance: On the ARC-AGI-3 Preview Challenge, the method solves a median of 30 out of 52 levels across six games and ranks 3rd on the private leaderboard.

• LLMs underperform even random action selection: Under a 4,000-interaction cap, a purely random agent solved 6 levels on the private games, while the GPT-4.1 + domain-specific language baseline solved only 5. The full graph-based method solved 19 under the same cap.

• Component-by-component gains are incremental but meaningful: Adding frame segmentation to random exploration solved levels that random could not (5 levels on vc33, 2 on ft09). Adding untested-action prioritization without full graph exploration slightly regressed on one game (as66), showing that the graph structure itself carries much of the benefit.

• Full-budget results: Over a full 8-hour evaluation (5 runs, 10 steps/second), the method solves a median of 16 private-game levels and 14 public-game levels.

• Performance tracks visual salience: The method excels when interactive elements are visually distinctive (vc33, as66) and degrades when state spaces become very large or partial observability is introduced (ft09 levels 6+, ls20 levels 3+).

• A reported bug caused a leaderboard discrepancy: In the official evaluation, the agent solved 12 private-game levels rather than the ~16 seen in reruns. Reset-triggering actions were not marked as tested in the graph, so the agent repeatedly reselected them, looping and resetting the game.

• Explicit limitations: Cost grows linearly with state-space size, and the method assumes deterministic, fully observable environments—it would break under stochasticity or hidden state.

Methodology in Plain English

The agent is split into two cooperating parts.

The Frame Processor looks at each 64×64 pixel game frame and simplifies it. It breaks the image into blocks of a single color, tries to identify and mask off the status bar (which is not part of the game world), and for click-based games sorts candidate click locations into five priority tiers—larger, more visually distinctive, button-like shapes get tried first. It then hashes the cleaned-up image, giving each unique game situation a short ID.

The Level Graph Explorer remembers what it has seen as a graph. Every unique game state is a node; every action taken from a state is an edge leading to the next state. Each edge is labeled with a priority, whether it has been tested, and what happened when it was tried. The agent's policy is simple: at the current state, try any untested high-priority action at random. If all high-priority actions are tested, walk along the shortest known path to a state that still has untested high-priority actions. If nothing at that priority remains anywhere reachable, raise the priority threshold and repeat.

This produces an agent that never learns a policy or a world model but still systematically sweeps the reachable state space in an order that favors likely-interactive elements first. The authors compare this against a random agent and against GPT-4.1 that writes and executes Python code to interact with the environment.

Why This Matters

Impact on research. The paper is a counterpoint to the assumption that interactive reasoning requires learning or large language models. It shows that a hand-designed exploration strategy, with no training, can be a strong baseline—and in this benchmark, a stronger one than a frontier LLM. It also highlights that explicit state tracking, not raw model capacity, may be the bottleneck in sparse-feedback settings.

Real-world applications.

• Automated software and UI testing, where an agent must discover what buttons and controls do with no documentation or reward signal.
• Robotic manipulation in novel environments, where the agent has to figure out which objects are movable and which actions are reversible.
• Digital game playtesting and QA, where levels must be explored exhaustively to detect breakages or unintended state transitions.
• Scientific or diagnostic workflows, where an agent probes an unfamiliar system with a limited budget of expensive experiments.

Industry relevance. Any product team building agents that operate in interactive environments with delayed or binary feedback—RPA, browser automation, game AI, industrial control—can treat this graph-exploration approach as a strong, cheap baseline before investing in learned policies. The open-source release makes it directly usable.

Future Directions

• Hybridizing graph exploration with learning. The 1st-place leaderboard solution used a learning-based approach without structured exploration. Combining the two—using the graph to guide training and action selection while a learned model generalizes across states—is the most obvious next step.
• Handling large or continuous state spaces. Current cost scales linearly with the number of discovered states, which caps performance on games with very large state spaces. Hierarchical or abstract graph representations could reduce this.
• Extending to stochastic and partially observable environments. The method assumes determinism and full observability, so adapting it to settings with noise, hidden state, or delayed observations is an open problem.
• Cross-level knowledge transfer. Levels progressively add mechanics while retaining earlier ones, but the paper treats them largely independently. Reusing the graph or extracted mechanics across levels could substantially reduce exploration budgets.

Target Audience

Researchers and practitioners working on interactive reasoning, agent exploration in sparse-reward environments, and benchmark evaluation of LLM agents. Also useful for engineers building autonomous agents that must operate in unfamiliar software or game environments, and for students looking for a clear, working example of how explicit state-space search can outperform end-to-end learned approaches.

Authors’ abstract

We present a training-free graph-based approach for solving interactive reasoning tasks in the ARC-AGI-3 benchmark. ARC-AGI-3 comprises game-like tasks where agents must infer task mechanics through limited interactions, and adapt to increasing complexity as levels progress. Success requires forming hypotheses, testing them, and tracking discovered mechanics. The benchmark has revealed that state-of-the-art LLMs are currently incapable of reliably solving these tasks. Our method combines vision-based frame processing with systematic state-space exploration using graph-structured representations. It segments visual frames into meaningful components, prioritizes actions based on visual salience, and maintains a directed graph of explored states and transitions. By tracking visited states and tested actions, the agent prioritizes actions that provide the shortest path to untested state-action pairs. On the ARC-AGI-3 Preview Challenge, this structured exploration strategy solves a median of 30 out of 52 levels across six games and ranks 3rd on the private leaderboard, substantially outperforming frontier LLM-based agents. These results demonstrate that explicit graph-structured exploration, even without learning, can serve as a strong baseline for interactive reasoning and underscore the importance of systematic state tracking and action prioritization in sparse-feedback environments where current LLMs fail to capture task dynamics. The code is open source and available at https://github.com/dolphin-in-a-coma/arc-agi-3-just-explore.