Graphs, Constraints, and Search for the Abstraction and Reasoning Corpus
This addresses the challenge of few-shot generalization in AI benchmarks, offering a novel approach for the ARC, though it is incremental in improving program synthesis methods.
The paper tackles the Abstraction and Reasoning Corpus (ARC) by proposing ARGA, an object-centric framework that uses graph representations and program synthesis, achieving efficient performance on complex tasks with correct and interpretable programs.
The Abstraction and Reasoning Corpus (ARC) aims at benchmarking the performance of general artificial intelligence algorithms. The ARC's focus on broad generalization and few-shot learning has made it difficult to solve using pure machine learning. A more promising approach has been to perform program synthesis within an appropriately designed Domain Specific Language (DSL). However, these too have seen limited success. We propose Abstract Reasoning with Graph Abstractions (ARGA), a new object-centric framework that first represents images using graphs and then performs a search for a correct program in a DSL that is based on the abstracted graph space. The complexity of this combinatorial search is tamed through the use of constraint acquisition, state hashing, and Tabu search. An extensive set of experiments demonstrates the promise of ARGA in tackling some of the complicated object-centric tasks of the ARC rather efficiently, producing programs that are correct and easy to understand.