These are my ongoing research notes and should be read as a draft document.

I'm interested in neural program synthesis for general task solving.

Task solving is a challenging problem because tasks are generally out-of-distribution. It's hard to develop algorithms that can examine a problem, reason about a solution, and then execute that solution -- on tasks it may never have seen before.

A neural program synthesis network is shown a task and then generates a program (ususally in a domain specific language) that can execute a solution to the problem. I believe that we can develop algorithms that are shown tasks from a previously unseen domain and through self-play learn to generate programs that operate in that domain.

As an example, consider the toy (yet difficult) challenges from the ARC-AGI problem set.

Each task in the ARC challenge is a collection of input-output pairs (input on the left, output on the right in Figure 01, above). The bottom four rows are examples that have known inputs and outputs while the top row is a test that only has an input provided. The goal is to develop a network (or algorithm) that can generate the correct output (transparent grid in the top right) for the provided test input.

There are two reasons why the ARC challenge is difficult:

1. Each task is fairly unique. There are primitive subprograms and motifs that are repeated across tasks, but even handcoded programs that perform brute force search through known primitive subprograms struggle to successfully generate more than 25% of the test outputs.
2. By design the private test set of tasks is more complex than the training set. This means that algorithms (networks) that learn to predict output grids from input grids will naturally struggle when presented with an input from the test set.

I like the ARC challenge because it's actually antithetical to the typical use of a neural network, which is to learn a distribution over inputs. If we consider a simple image recognition task, then the goal is to learn to predict a class label given an input sample. At training time we have supervised labels, but critically at test time we don't have any supervision. The ARC challenge is different: we have supervision at test time . If we write a program that solves each of the training examples (which we have at test time) then in theory that program will also solve the current test problem. This means we don't need any prior knowledge about the tasks -- it's motivation to want to treat the entire process as a sort of merged train / test cycle.

In my opinion a solution is composed of three main components:

• Masks
• Operations
• Programs

A mask is a binary pattern that selects from an input grid. Every input grid is composed of a series of masks applied iteratively. Consider the following input example with it's corresponding target solution:

The mask in column (3) selects the pink squares from the input grid, and the mask in column (4) selects the yellow squares. By shifting the masks across the output grid and changing the order of how we apply each mask we can change where the two coloured shapes are placed in the output. For this particular task a solution could be to take mask (3), shift it up and to the right one unit, then take mask (4) and shift it down and to the right one unit. This results in the final output grid as shown by the solution.

My theory is that any ARC task can be represented as a collection of masks (layers) that can be manipulated by programs which are themselves collections of operations over masks. In this hypothetical example some operations are select(mask, input), shift(mask, x, y) and draw(mask).