TL;DR
Researchers have developed a new symbolic solver that tackles the Abstraction and Reasoning Corpus (ARC) by mimicking human abductive reasoning. By converting visual grids into multi-layered knowledge graphs and using Domain-Specific Languages (DSLs), the system extracts "core knowledge" to narrow down the search space, significantly outperforming non-graph-based methods in predicting grid properties.
What Problem Does This Paper Address?
While modern AI excels at many tasks, it still struggles with the "puzzle test"—abstract visual reasoning that requires logical stability and common sense. The benchmark for this is the Abstraction and Reasoning Corpus (ARC), a collection of unique tasks where an agent must infer a transformation rule from just a few example pairs and apply it to a new test input.
Current transformer-based models often suffer from "hallucinations" or lack the ability to explain why a specific change occurred. Humans, by contrast, use abductive reasoning—forming the most likely hypothesis to explain observations. This paper aims to bridge the gap by creating a solver that represents data symbolically, making the reasoning process both logical and interpretable.
Methods
The authors propose a three-stage framework called the Abductive Symbolic Solver:
- ARC Knowledge Graph (ARCKG) Construction: Instead of treating grids as simple 2D arrays, the system converts them into a 4-layer graph:
- Pnode layer: Individual pixels.
- Onode layer: Groups of pixels forming objects.
- Gnode layer: The entire input or output grid.
-
Vnode layer: A top-level node connecting the input and output grids of a pair.
Figure 5: An example of a straightforward, and almost backbone-structured knowledge graph of the first pair of Figure 1. In practice, the ARCKG generated by Algorithm 1 can contain up to millions of edges. The graph consists of four layers, with edges freely drawn between layers as well as between input and output by the Property DSL. The yellow edges represent connections between two nodes at the same position. The other (black, blue, green) indicate edges signify that nodes in the lower layer constitute nodes in the upper layer. -
Core Knowledge Extraction (The Specifier): This module acts as a filter. It looks across all example pairs to find repeated features or relationships (e.g., "the blue pixel is always the center"). This "core knowledge" drastically reduces the number of possible solutions the AI needs to consider.
- Symbolic Solution Synthesis (The Synthesizer): Using a library of Domain-Specific Languages (DSLs)—predefined functions like
get_heightoris_symmetric—the solver performs a brute-force search to find the sequence of transformations that maps the input to the output.
Datasets
The study uses the standard Abstraction and Reasoning Corpus (ARC), consisting of 400 training tasks and 400 evaluation tasks. Each task includes multiple example pairs and one test pair. The authors specifically evaluated their solver's ability to predict the grid size and the color set of the output.
Key Insights and Ideas
- Abduction over Induction: While inductive reasoning seeks general rules from massive data, abductive reasoning is better suited for ARC's "few-shot" nature, where the AI must find the best explanation for a very limited set of observations.
- Symbolic Stability: By using DSLs, the "essence" of a task isn't lost in a high-dimensional vector space. The solution remains a human-readable sequence of logical steps.
- The Power of the Graph: Representing the grid as a graph allows the model to capture spatial and relational information (like "object A is inside object B") that is difficult for standard convolutional or transformer architectures to parse.
- Search Space Reduction: The "Specifier" is the secret sauce. By identifying what doesn't change or what is consistently present, it prevents the Synthesizer from wasting time on irrelevant transformation paths.
Key Results
The researchers compared their Knowledge Graph (KG) approach against a version that applied DSLs directly to the grid without a graph.
- Accuracy Boost: The KG-based solver achieved significantly higher accuracy across all metrics. For example, in the "HWC" category (predicting Height, Width, and Color set simultaneously), the KG approach reached 66.5% accuracy, compared to just 32.3% for the non-KG version.
- Grid Size Perfection: The solver achieved nearly perfect accuracy (over 90%) in predicting the height and width of the output grids when using the knowledge graph.
- DSL Scaling: Increasing the number of available Transformation DSLs (from 5 to 10) led to a massive performance jump, particularly in color prediction, supporting the idea that a richer symbolic vocabulary leads to better reasoning.
Limitations and Future Work
- Content Prediction: The current study focuses on predicting the size and colors of the output grid. The authors acknowledge that predicting the exact content (the specific arrangement of pixels) is the next major challenge.
- DSL Coverage: The solver's success is bound by the completeness of its DSL library. If a task requires a transformation not defined in the DSL (like a complex custom rotation), the solver will fail.
- Computational Complexity: While the Specifier narrows the search, the Synthesizer still relies on a brute-force search tree. As the depth of reasoning required for a puzzle increases, the search space could grow exponentially.
Summary updated