Abductive Symbolic Solver on Abstraction and Reasoning Corpus

Mintaek Lim, Seokki Lee, Liyew Woletemaryam Abitew, Sundong Kim

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.

Figure 1: Example ARC task. Solvers are supposed to formulate a pattern that applies to all the given example pairs and then construct an answer with the given test input grid.

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:

  1. ARC Knowledge Graph (ARCKG) Construction: Instead of treating grids as simple 2D arrays, the system converts them into a 4-layer graph:
  2. Pnode layer: Individual pixels.
  3. Onode layer: Groups of pixels forming objects.
  4. Gnode layer: The entire input or output grid.
  5. 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.
  6. 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.

  7. Symbolic Solution Synthesis (The Synthesizer): Using a library of Domain-Specific Languages (DSLs)—predefined functions like get_height or is_symmetric—the solver performs a brute-force search to find the sequence of transformations that maps the input to the output.
Figure 2: Overall framework of Symbolic ARC Solver. To tackle ARC tasks from the symbolic perspective, the first step involves generating a corresponding knowledge graph using a construction program based on defined Domain Specific Languages (DSL). (Step 1, Chapter 3.1) Then, extract core knowledge from the knowledge graph using Specifier. (Step 2, Chapter 3.2) Since all the ARC tasks consist of multiples of example pairs and a test pair, we define Specifier to hold only the repeated conditions that appeared in all example pairs. Lastly, search solutions under given constraints using Synthesizer. (Step 3, Chapter 3.3) The information gained from the examples and proposing Transformation DSLs limits the solution search space and makes the search feasible.

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

Abstract

This paper addresses the challenge of enhancing artificial intelligence reasoning capabilities, focusing on logicality within the Abstraction and Reasoning Corpus (ARC). Humans solve such visual reasoning tasks based on their observations and hypotheses, and they can explain their solutions with a proper reason. However, many previous approaches focused only on the grid transition and it is not enough for AI to provide reasonable and human-like solutions. By considering the human process of solving visual reasoning tasks, we have concluded that the thinking process is likely the abductive reasoning process. Thus, we propose a novel framework that symbolically represents the observed data into a knowledge graph and extracts core knowledge that can be used for solution generation. This information limits the solution search space and helps provide a reasonable mid-process. Our approach holds promise for improving AI performance on ARC tasks by effectively narrowing the solution space and providing logical solutions grounded in core knowledge extraction.
BibTeX
@inproceedings{lim2024abductive,
  author = {Mintaek Lim and Seokki Lee and Liyew Woletemaryam Abitew and Sundong Kim},
  title = {{Abductive Symbolic Solver on Abstraction and Reasoning Corpus}},
  booktitle = {Workshops @ IJCAI},
  year = {2024},
  url = {https://openreview.net/forum?id=w6pxdhgxKL},
}
Figure