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

🕒 Published (v1): 2025-12-30 11:40 UTC · Source: Arxiv · Venue: AAAI 2026 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

A training-free, graph-based state-space exploration agent is proposed for ARC-AGI-3, a benchmark of game-like interactive reasoning tasks where frontier LLMs score near 0%. By combining visual frame segmentation with a directed-graph explorer that prioritizes high-salience untested actions via shortest-path navigation, the method solves a median of 30/52 levels and ranks 3rd on the private leaderboard.

Problem

ARC-AGI-3 requires agents to infer unknown game mechanics through sparse-feedback interaction (only level completion signals), adapt to progressively introduced mechanics, and operate in action spaces up to size 4,100. Frontier LLMs achieve 0% on initial preview tasks; learning-based RL methods require extensive data incompatible with the benchmark's few-shot (≤10 levels/game) structure. No existing approach provided a reliable baseline for this class of interactive reasoning tasks.

Method

The system has two modules:

Frame Processor: Segments each 64×64 RGB frame into single-color connected components, detects and masks status bars, hashes the masked frame for state identity, and assigns click targets to five priority tiers based on segment size, shape, and color salience.

Level Graph Explorer: Maintains a directed graph where nodes are hashed states and edges are (action, successor-state) pairs. Action selection follows a hierarchical policy (Algorithm 1): (1) execute an untested action in the current state at the current priority tier; (2) if none exists locally, navigate via shortest path to the nearest frontier state with untested actions at that priority; (3) if no such state is reachable, raise the priority threshold and recurse. This guarantees systematic coverage ordered by visual salience. The method is entirely training-free and deterministic given a fixed environment.

Key Contributions

• Training-free graph-based exploration baseline competitive with (and surpassing) frontier LLM agents on ARC-AGI-3.
• Priority-tiered action selection that couples visual salience with shortest-path graph traversal to manage 4,096+ action spaces.
• Incremental ablation showing each component's isolated contribution (frame segmentation, new-action prioritization, full graph exploration).
• 3rd-place finish on ARC-AGI-3 private leaderboard; open-source implementation.

Results

• At 4,000-interaction cap (fair comparison with LLM+DSL baseline): full method solves 19 levels (private + public) vs. 6 for random agent and 5 for GPT-4.1+DSL — the LLM baseline underperforms even a random policy.
• Full 8-hour run (96k steps/game budget), median over 5 runs: 16 levels solved on private games, 14 on public games (30 total across 6 games/52 levels).
• Official submission: 12 private levels solved (rank 3rd); lower than re-runs due to a reset-handling bug causing action-selection loops.
• Per-game highlights: vc33 solve rate 100% through level 7 (0.8 on levels 8–9); as66 100% through all 9 levels tested; ls20 and ft09 saturate at levels 3–4 due to state-space explosion.
• Ablation: adding frame segmentation alone lifts public-game solves from 3 to 7; adding graph exploration brings total to 19 at 4k steps.

Limitations

• Computational cost scales linearly with state-space size; fails on levels with very large state spaces (ft09 levels 6+, ls20 levels 3+).
• Assumes deterministic, fully observable environments; explicitly would fail under stochasticity or partial observability.
• Reset-handling bug caused infinite loops in official submission, depressing score by ~4 levels relative to internal re-runs.
• Visual salience heuristic may misalign with task-relevant interactive elements in games where salient pixels are decorative.
• No learning or generalization across levels; each level is explored from scratch.

Relevance to Agentic AI / LLM Agents

ARC-AGI-3 directly tests a core agentic capability: forming and testing hypotheses under sparse feedback in a novel environment — something current LLMs demonstrably cannot do reliably. This paper shows that explicit state tracking and structured exploration (a classical AI primitive) outperforms LLM-based reasoning + code generation by a wide margin in this regime, providing a concrete diagnostic of where LLM agents fail (inability to systematically enumerate and track tested hypotheses). For researchers building LLM agents, the result argues that augmenting LLMs with explicit graph-structured memory and exploration policies — rather than relying on in-context reasoning alone — is a promising hybrid direction, especially for tasks requiring multi-step probing under sparse rewards.