Program synthesis for analogical reasoning
A key hypothesis of our research is that an analogy holds if there exists a program synthesizing the problem and the solution efficiently. A simple particular case is when the program maps the input to the output. Since infinitely many such programs might exist, we introduce some complexity criteria, imposing that the program is of minimal length.
The ARC-AGI challenge is an important benchmark for analogical reasoning. It consists of a number of 2D grid tasks similar to intelligence tests. Each problem of the ARC-AGI challenge consists in a few examples of (problem, solution) pairs, and the goal is to find the solution to a new problem. Our approach consists in investigating approaches where the solution is found by encoding solutions as a program made up of simple elementary instructions. Our research aims to adapt existing reinforcement learning architectures to such problems, with a specific focus on encoding prior knowledge and intuitive physics.