ARC Prize 2024 (ARC) just announced their winners and even described the winning strategies so far, which are Deep Learning Guided Program Synthesisand Test Time Training techniques. But, there is a line in the report that caught my eye — “This suggests algorithmic improvements towards AGI hold significant power and that massive compute may not be necessary in order to beat ARC-AGI.” That seemed encouraging to me because I’ve been playing around with algorithmic approaches to solving the ARC Prize.

After being so enthusiastic about the solution I came up with last time, I am going to change track. Sorry for the whiplash. Who knows, the final solution might be some amalgamation of a bunch of methods. And it might even use an LLM!

Let me first state that I know that this method is impractical. There are combinatorial explosions that are possible at multiple steps in the process. However, this method has fascinated me for the past few days, and I thought I’d just put it out there.

The new approach that I came up with is based on the notion that we humans seem to solve the ARC puzzles with an approach that can be summed up as “IF x THEN y”. The x is a property of a component of the input grid, whether that component is a pixel, a cluster or the grid itself. The y is the state of a pixel in the output grid, or the output grid’s dimensions. An example of such a condition could be “IF there are 5 red pixels THEN this cluster is yellow.” Let’s call these “IF…THEN…” statements “conditionals”.

Now, x could well be a combination of properties of a bunch of components resulting in conditionals like “IF (X1 AND X2 AND X3) THEN Y”.

We humans rely on previously learned information when making these conditionals about each puzzle. However, how is a software system to learn these? We could program these “priors” in but then we’d be building a system that’ll break when it encounters a puzzle that doesn’t have those particular priors. The point of an AGI is that it is adaptable. Which means that you need a way to be able to generate these conditionals.

What if we generate these conditionals mechanically? We could go through all the combinations of properties of input grid’s components and relate them to the state of output grid’s components. We can quickly generate multiple conditionals like:

Of course, these mechanically produced conditionals are just hypotheses at the moment. We will next check to see if they affect the outcome.

An ARC puzzle’s examples explain a relationship between the input and output grids to us. This relationship is true of all the examples, of course. This means that we can validate the generated conditionals by testing to see if the conditional exists across all the examples.

An issue with making this check is that a conditional might be too specific. For instance, a red pixel at (4, 5) in one example might not be in the same place in all the examples. Humans adapt to this situation by checking to see if it is roughly in the same place. The system can make such an abstraction as well. We can abstract away the position of the pixel to something more general, like “the top left third of the grid”, and see if such a pixel appears in that location in all the examples.

However, we have to be careful that such an abstraction isn’t too general either because that will result in matches across all examples for all conditionals we generate! (For instance, looking for a blue pixels “anywhere in the grid” might not be too helpful.) To be useful, the abstraction should be specific enough to eliminate the chance of a 100% cross-match of all conditionals and general enough to not result in a 0% cross-match. Especially with pixel positions, this “tolerance”, if you will, can be adjusted.

Once we have a bunch of conditionals that are applicable across all examples we can try to generate the output from the test set. This will be done, again, by mechanically passing each of the components of the input grid through the set of conditionals and see what we get in the output grid.

Like I said before, this method is rife with possibilities of combinatorial explosion at multiple points in the step. (Even with a 30 x 30 grid, I’d be generating more data than there is space in the universe to store.) And, there are multiple details that I have simply not spoken about at all like the properties of components we will look for, finding relationships that are of interest, and the optimizations that one can make to make this approach a bit more practical. Still, I hope I have given you a good overview of a method that has occupied my mind for the past few days.

That complex interrelationships that can be captured by simple, rote methods is fascinating. Onwards to the next method!