Graphs, Constraints, and Search for the Abstraction and Reasoning Corpus


  • Yudong Xu University of Toronto
  • Elias B. Khalil University of Toronto
  • Scott Sanner University of Toronto



CSO: Search, CSO: Constraint Learning and Acquisition, SO: Heuristic Search


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.




How to Cite

Xu, Y., Khalil, E. B., & Sanner, S. (2023). Graphs, Constraints, and Search for the Abstraction and Reasoning Corpus. Proceedings of the AAAI Conference on Artificial Intelligence, 37(4), 4115-4122.



AAAI Technical Track on Constraint Satisfaction and Optimization