Solving ARC with non-procedural program induction
Norbert Neumann, Ádám Pintér · 2023
This paper attempts to solve the Abstraction and Reasoning Corpus (ARC) [1] which was made to measure strong generalization in artificial intelligence systems. The existing program induction solutions have the disadvantage that the program tree defined by the used Domain-Specific Language (DSL), in which the search takes place, grows exponentially with the length of the program, making the search space too large to find the appropriate program. Our program induction-based solution attempted to eliminate the need for searching in the DSL’s program tree. This requires that the induced program should not be procedural, i.e., it should not consist of a sequence of instructions built on top of each other. The induction of such programs is much simpler, as breaking down the instruction’s interdependence causes the search time to grow only linearly with the program’s length. This method successfully reduced the size of the problem’s search space. Compared to previous methods, the average task-solving time was significantly lower than in any other publications. It was able to solve 41 tasks in the training set and 10 tasks in the public test set, which is the fourth-best result among previous publications.