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

arXiv: https://arxiv.org/abs/2512.24156 · HTML: https://mlsanity.com/paper/2512.24156/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Placed in Multimodal reasoning, one of 17 directions in LLM reasoning.
- Builds on 8 of its 10 references that are in the map.
- First posted on arXiv 30 Dec 2025.

## Placed in

- LLM reasoning / [Multimodal reasoning](https://mlsanity.com/lr/multimodal-reasoning/)

## Builds on (most cited first, 8 of 8)

- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Curiosity-driven Exploration by Self-supervised Prediction](https://mlsanity.com/paper/1705.05363/) (2017)
- [First return, then explore](https://mlsanity.com/paper/2004.12919/) (2020)
- [Mastering Atari Games with Limited Data](https://mlsanity.com/paper/2111.00210/) (2021)
- [Bigger, Better, Faster: Human-level Atari with human-level efficiency](https://mlsanity.com/paper/2305.19452/) (2023)
- [Training Agents Inside of Scalable World Models](https://mlsanity.com/paper/2509.24527/) (2025)
- [Assessing Adaptive World Models in Machines with Novel Games](https://mlsanity.com/paper/2507.12821/) (2025)
- [AXIOM: Learning to Play Games in Minutes with Expanding Object-Centric Models](https://mlsanity.com/paper/2505.24784/) (2025)

## Built on by (most cited first, 6 of 6)

- [OPINE-World: Programmatic World Modeling with Ontology-error-Prioritized Interactive Exploration for ARC-AGI-3](https://mlsanity.com/paper/2607.01531/) (2026)
- [Workspace Optimization: How to Train Your Agent](https://mlsanity.com/paper/2605.09650/) (2026)
- [Tycho: Active Abstraction with Programmatic World Models for ARC-AGI-3](https://mlsanity.com/paper/2607.28287/) (2026)
- [Twin: Playing an Unknown Game with a Test-Time Digital Twin](https://mlsanity.com/paper/2608.14490/) (2026)
- [Do Coding Agents Need Executable World Models, Simplification, and Verification to Solve ARC-AGI-3?](https://mlsanity.com/paper/2607.15439/) (2026)
- [Memento 3: Model-Based Recursive Self-Improvement through Reflective Rulebooks](https://mlsanity.com/paper/2610.11794/) (2026)

## Abstract (arXiv)

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.