ARC Prize 2024 获奖算法【Daniel Franzen 与 Jan Disselhoff】

Jan and Daniel, it's amazing to have you on MLST. Welcome, both of you.

Thank you for having us here.

So you guys are the official winners of the ARC challenge. The results were finalized about a month ago or so. Why don't we just start by telling us a little bit about your solution?

1. The ARC Approach Takes Shape

It was a process with lots of ups and downs. We started with simple LLM fine-tuning and had pretty good results, but during the competition we tried to add additional computation steps outside of the LLM, which helped us increase our score substantially. Our LLM alone reached a score of 41 points, I think, but with the additional external help we could get the LLM to improve substantially, to around 56 points. That didn't count, so we ended up with 53.5 points.

Can you talk us through the overall ARC approach?

We actually started with a basic LLM that was trained on language. We started out with a rather large model: a 12-billion-parameter model. What we essentially do is take the ARC tasks, which are located on a grid with pixels of different colors, and use one token for each color. We tokenize them line by line and put them directly into an LLM.

We do no program search or other preprocessing. We just convert the tasks to text and put them into the LLM, and that worked amazingly well—better than I expected. Of course, there are quite a few tricks we need to use to make it work better on these tasks, because the reasoning capabilities of LLMs without fine-tuning on the specific test set are not so good.

We essentially did some test-time fine-tuning, so we had two training processes. We first did a long pretraining on the official ARC training set. Later, we replaced it with Re-ARC, which can generate more tasks and examples. That model did not perform as well on the evaluation tasks, so what we do is test-time training: we do another training process on the examples of the evaluation set that we get during inference, without seeing the final challenge that we then try to predict with the model. That gives a big improvement to the score.

There were quite a few other improvements that we tried during the challenge. Some worked very well, but there were also a lot that didn't turn out well.

I've learned so much. Melanie Mitchell had an interesting paper out discussing her concept of ARC and what it means for LLMs to understand all of this. The common-sense rationale was very much that language models would never be able to do this, and that the only way it could possibly work was if we generated an intermediate program, because symbolic things are better, more compositional, and generalize better.

Certainly, if you took GPT-4 and just did zero-shot solution-space prediction, you were looking at around 10%. That's nonzero, and it's certainly much better than something like GPT-3.5, but many of us, myself included, ruled out the possibility that these things could be reasoning. What did you discover on that journey?

2. LLMs Learn The Grid

We started with the same assumption, at least I did, but we quickly found that LLMs have far more computational capability than we thought.

For example, all the tasks seem like 2D vision tasks. They are on a 2D grid, and if you see them, you use your perceptual knowledge to move blocks or pixels around. My hypothesis was that an LLM is 1D: it processes text. We have a token for going to the next line, and it seemed crazy to me that the LLM could function in that space. It had to learn to infer the 2D structure of the problem without ever working in 2D.

The more we trained the networks, the more it seemed that this simply wasn't a problem. The LLMs were strong enough and had enough capability to infer this structure implicitly. We did some experiments in which we tried to help by giving them more information about the structure, such as appending dimensions or coordinates, but it wasn't needed. It rarely improved the score, and when it did, it improved it by such a small amount that it wasn't worth the additional compute time.

One of the intuitions there is that it's a 2D grid. Certainly, in Transformer models we put in positional tokens and things like that. The remarkable thing is that it generalized to different grid sizes without you needing to explicitly give it any compasses or markers.

We actually tried to use a 2D positional encoding on the data, but it didn't really improve the results. The model just learns to detect the end-of-line markings and output lines with the correct length. It worked fine, so we stopped with the positional-encoding approach because it was too complicated and didn't give us any advantage.

You did fine-tune the model. I think you ended up using an 8-billion-parameter model. Is that what you were using?

That's what we actually started with. Then we went to a 12-billion-parameter model, and because that model was too large to do many things on Kaggle, we went back to a smaller model. It was the Llama 3.2 3B model, which we found to be essentially as strong as the 8B model while being much faster to execute, so we could try a lot more things.

I'm very excited about that new Llama model. It's amazing how much they've gotten out of it. With that model out of the box, zero-shot, in solution space, what kind of accuracy were you getting?

Without training?

Without training.

I think close to zero, or zero. The model can't even predict the structure. Sometimes it just outputs end-of-sentence tokens indefinitely. Sometimes it predicts numbers, as it should with newlines, but then some lines are too long and some are too short. It hardly produces any solution that is even possible without a training process.

You trained it on Re-ARC, which is Michael Hodel's dataset. Could you talk a little bit about that?

It was very useful to have a dataset that is essentially unlimited. We have 4 tasks in the original dataset, and Re-ARC helps generate more examples for each challenge. At some point you saturate, because you don't get novel ideas in the tasks, but it was very useful to have virtually infinite generable training data.

Michael Hodel's work is a dataset generator. Given a task, you can create a whole bunch of additional augmentations of that task. You had about 10,000 of those across all of the ARC tasks in the public set, and you fine-tuned Llama 3.2 3B on that. Zero-shot solution space, out of the gate—what were you looking at?

Let me think for a moment. With the Llama model, I think we were maybe at 10% to 20% performance. I'm not sure, because we did some multiple-inference steps and other things. You could get the zero-shot model with some tricks to perhaps 20% or 25%. That was the maximum we could get out of it on the evaluation data.

That brings us to the magical test-time inference—or test-time training. There are lots of different names for it, and people have been using different names, but tell us about that.

3. Test Time Training Takes Hold

After the model was fine-tuned the first time, we did an additional training step on the evaluation data. Not on the full evaluation data, because we only had the examples and not the challenge itself, but the examples essentially look the same as the challenge. We could just pick one output from an example as the final example and train on those inputs.

On the ARC contest, we essentially did retraining on some of these examples, and after that we did the inference step. This improved the results quite a lot.

I suppose you could argue that this is cheating, or not. In the real world, I suppose you would be doing an online prediction, and what you're doing is making your predictive model as good as it would have been at the end of a line of online prediction.

You're correct about that. We tested different versions, and it's also possible to retrain on every single task. That would essentially be a fairer version, so the model doesn't see the other evaluation tasks. That works just as well, but in our experiments it required more time to retrain than putting all the tasks in at the same time.

Because time was so limited in this challenge, we chose the option to train on multiple tasks at once.

There's this thing called transductive active fine-tuning. At test time, you have the specification, generate augmentations from the specification, fine-tune on those augmentations, and then do the prediction. Do you mean from the test—the new challenges?

Yes. We heavily use augmentation. Basically, all our inference steps also use it during training. We used it for the pretraining in Re-ARC as well, because it helps a lot to get enough data.

During retraining, or test-time training, we are heavily data-limited. Each challenge only has 3 examples, but we can use the symmetry of the problem. All the problems work on a 2D grid and have some implicit biases, so we can rotate the examples, mirror them, and even shift the colors in specific ways without changing the challenge.

Because the model is not rotation-invariant—it is a 1D LLM—we can create rotated augmentations and use them to train on the challenge. It looks like a novel task to the LLM because it is rotated differently, which helps a lot with the amount of data we have.

From the test specifications, you do symmetry augmentations and fine-tuning. Do you do any additional augmentations?

We thought about a lot of augmentation techniques. Most of our tests didn't pan out or were too time-intensive. For example, we have a selection step in which we take the generated example—our solution—and then do an augmentation again. We ask the LLM whether this solution looks correct from a different perspective as well.

Theoretically, you can do more augmentations there. You can shift into another space where the problem looks simpler, as long as there is some consistency in the solution. For example, many problems have the same solution if they are in black and white instead of in color. In theory, you could use that to filter wrong solutions very easily, but we didn't have the time to get it to work.

Other than symmetry and color-shift augmentations, we also shifted the examples because the Transformer is not invariant to the order of the examples. We shuffled the examples around a little bit.

We're getting close to putting the pin in the middle of the dartboard here, which was the main thing that you did. You use some kind of search and evaluation process as part of your test-time inference. Can you tell me about that?

4. Depth First Search Wins

There are actually different methods of sampling from an LLM. You could just do greedy sampling, which means always taking the token with the highest probability. Or you could sample stochastically by selecting tokens according to the probabilities predicted by the network.

These sampling methods didn't work very well when we wanted to generate lots of different candidates. We later implemented a selection process, which we can talk about, so the focus in this generation step was essentially to generate lots of candidates and increase the chance of finding the correct solution.

We first started with sampling, and we also tested beam search, because often there are different paths through the network that give different predictions, and one of them is correct. In the end, we settled on a depth-first search that we implemented ourselves, because we hadn't found one that worked for this purpose. It worked quite well and had some advantages over beam search.

We treat the tokens predicted by the network as a search tree. We then search through this tree to find all solutions whose sampling probability is above a certain cutoff value. For example, if we set this probability to 10%, we get a variable number of candidates—up to 10, in theory.

This search has several advantages. The first is that it is very memory-efficient: you only need to store exactly one path. It is much more efficient than beam search, which needs essentially the same memory for every beam.

The other advantage is that it gives us multiple solutions for the problem at once. We also have a cutoff, so if there are paths that are not promising, the search stops early and doesn't follow them. That gave us a big efficiency boost in generating solution candidates.

I interviewed some people at the University of Toronto who were talking about the reachability space of language models. They had this famous Roger Federer game, where you try to make a language model say, “Roger Federer is the greatest,” and you have to find what prompt will reach that word.

Their theorem, essentially, is that the capacity or reachability of Transformers is incredibly flexible. There is a remarkable divergence between the way we sample tokens from a language model and what those models are capable of. A clearer way of saying that is that there is a misalignment between how we sample language models and the epistemic truth, or the correctness, of the program that we are sampling.

I find that fascinating. It is also related to the creativity problem. When we do greedy sampling—taking the best token, then the best token, then the best token—we are missing all of these creative possibilities. This is something that a lot of people aren't really thinking about yet.

It is a very interesting problem, and we have to distinguish between a language context and the ARC context. There is a substantial difference: we only have 10 possible tokens that might be the next correct answer, and we know there is only 1 correct answer.

In language, you can have millions of ways of rephrasing the same idea, and all of them are valid or good continuations. In our case, there is only 1 correct continuation. That is one of the reasons why the DFS works so well. We only have one correct continuation, we have to find it, and it is very easy to evaluate and search because the set of possible continuations is much smaller.

We can even calculate how probable each solution is by taking the solution, doing a forward pass, calculating the logits, and summing them. Then we know how low the cutoff needs to be for our DFS to find the correct solution with a guarantee.

That makes the problem very tractable. Sampling algorithms are built for language, because LLMs work on language. That is also why we didn't find an existing breadth-first search implementation that worked for this setting—we had to reimplement it ourselves.

It isn't a valid way of sampling language. Language has too many possible paths, and each path, as long as it is valid, should have roughly the same probability. If you have 1 million possible continuations, each probability is 1 in 1 million, so it is very hard to use this approach in that context. Our problem is discretely small, so we can sample very efficiently.

This raises so many interesting questions. You could argue that the reason these models are misaligned between program or knowledge correctness and how we sample them is that there are too many degrees of freedom in natural language. They are dealing with this ambiguity, and their training therefore means that when we sample from them, we are not very likely to get the correct answer.

You have to be careful about that, because we have to differentiate between the probability of a path and the probability of an answer. You can have a very improbable path that leads to a specific answer, and then you can have multiple variations of it. The probability of the answer is not dependent on any single path, but on the sum of all paths that lead to that answer.

In language, you have this broad set of paths that all lead to the same solution. When you use standard sampling techniques, you sample the final answer correctly. In the ARC contest, there are no alternative intermediate steps. You don't need to marginalize over all possible paths; you simply need to get the correct path.

For normal LLMs, this is completely fine. But I think that in the age of reasoning models, such as o1 or o3, you also need the correct reasoning steps and intermediate steps to get to the right solution, especially if you use the model for code generation or answering complex mathematical questions.

This will be a much larger problem in the future. Up to now, sampling was simply the correct approach.

In your solution, the way that you traversed that sparse space is interesting. It is a bit like reinforcement learning, where you need to take several steps without knowing what the value is going to be. That is very difficult when we have some kind of traversal optimization algorithm that relies on a monotonic signal—we're getting better and better and better. In this case, the space is sparse, and we have to take several steps into the unknown.

What really interests me, though, is that even if we don't know what the reasoning steps are, Ryan Greenblatt's solution impressed and surprised me. I assumed this was an exponentially large problem, and that using a language model to guide the search would not be significantly better than exhaustively finding programs.

What he demonstrated quite succinctly is that it is tractable. We still need to generate many completions and do some search, but a reasonable amount of search gets you to the solution. Even though there is an apparent orthogonality between correctness and searching this space, the correct solution isn't that far away. That's fascinating.

The interesting thing about Ryan Greenblatt's solution, from my perspective, is that he showed that code generation can work that way. The models can see the visual problems—the 1D representation of the grids—and then produce code that works to move these 2D objects, even though they were never seen before and without fine-tuning on them.

On the other hand, code generation has a massive advantage compared with our approach, because you can test the code. You can check whether the generated code performs in the way you want it to, and if it does, then it is probably a good solution. Our approach doesn't have that. We had to find a way to select which candidate we wanted to submit without any guarantee that it was right.

This gets us to the most delicious part of all. As you just articulated, Ryan Greenblatt's solution was technically a neuro-symbolic architecture. Shahriar Khatri would have been delighted, because he loves having formal guarantees and actually knowing for sure. In this case, we don't know for sure, because many correct programs are not correct for the right reason, but at least we can run a program on a Python interpreter and get a yes-or-no answer. It might still be a false positive.

You have done something very interesting: you are using the language model to verify its own value as you traverse through this tree structure. Can you tell me about that?

5. The Model Judges Its Answers

Our generation process essentially generates multiple solution candidates—usually up to 10 or 20 in practice—and then we need to find a way to select the correct one. We used our model to judge how good these solutions are.

The interesting part is that this is difficult if you do it without augmentations, because a model naturally favors its own predictions. The score we use is the sampling probability we got in the first place. What we do at this point is use a lot of augmentation for the judging step.

We use 16 different augmentations of the problem and put them through the model to calculate scores for each augmentation. Then we average the scores. We tried different algorithms: one was simply to sum the actual probabilities, and the other was to sum the logarithmic probabilities, which is essentially equivalent to multiplying the probabilities. The second approach worked much better for selecting solutions.

Our hypothesis is that the correct solution looks mostly correct from every angle. No matter how you rotate it, it might not get a very high score, but it doesn't get an extremely low score. Incorrect solutions might look good from some perspectives, but usually there are 1 or 2—or even more—perspectives where they get an extremely low probability, such as 0.01%.

Those low scores are important in the calculation. You can't get them during the generation process, because those solutions are never sampled. We need the extra scoring step to calculate the low scores and sort out the false solutions.

You generate 16 augmentations for a test specification, and you had already fine-tuned the model on symmetry permutations. That means it has some awareness of different symmetry transformations. You are saying that using it to do self-reflection on the value of those symmetry augmentations gives it different perspectives on what good looks like. You can then look at the coherence of those different symmetry perspectives to get an idea of which solution is correct.

Exactly. Ironically, it is very useful to us that the LLM does not have symmetry in its predictions. If it had the 2D symmetries, we couldn't use augmentation for scoring, because the score would be the same every time.

In a way, we abuse the fact that the LLM is not perfect at 2D tasks. It is always generating from left to right and from top to bottom, so some parts of the puzzle get generated later, with more information, while other parts get generated earlier, with less information. If we rotate it, we generate other parts of the solution first.

A lot of the score differences between the augmentations come from that. Sometimes a solution depends on previous input, and if we generate the wrong solution and then rotate it, the model sees the error much earlier. It can see, “It makes no sense that the line that goes from left to right here ends at an empty pixel. That should never happen.” Because we rotate the problem, it can see it from a new perspective and decide that it is an invalid or very improbable solution.

How much does this depend on the symmetry augmentation before test time? Before we get to any test-time computation, do you take all of the evaluation tasks, perform symmetry transformations, and then fine-tune? If you don't do that, how does it affect the evaluation?

I think we have never tested it. You mean not doing the augmentations during training?

Yes.

We have never tried that. We have always used augmentation from the beginning.

You seem to be saying that it is actually a good thing that the model doesn't know about the augmentations. Doing the augmentations seems like it would be a good thing, but perhaps it isn't.

It's a trade-off. We would lose a lot of training data, and it is also good if the model can generate the correct solution from every perspective. Some problems are simply easier from some perspectives than others.

In theory, the network should converge to a correct solution from every perspective if it is deep and strong enough. But sometimes it simply can't, and then we can use that fact by generating different augmentations and scoring them correctly.

There are different perspectives on language models. Shahriar Khatri called it jagged intelligence, I think, which is what Andrej Karpathy called it. That's the idea that they are actually very good in a probabilistic sense, but they have these islands of knowledge. You can give them an example of something they know and they can tell you whether it is good or bad, but they don't know how to get there.

There seem to be concentric circles in which they are better at discriminating than generating, and they are also capable of knowing when they don't know how to get there.

In some ways, yes. It depends so strongly on the task. There are problems where it is true that the model has a much easier time discriminating between solutions than generating them, but it depends on how you measure it.

We measure the score of a task, or of a solution, by calculating the probability that it would be generated from normal sampling. In our case, generation probability and evaluation are exactly the same. The only way we can use the discriminatory abilities of the LLM is through these transformations, because LLMs prefer their own outputs.

We have to trick the LLM into thinking that it is looking at an output it would never have produced.

Thomas Dietterich was telling me that it is interesting to look at the divergence between epistemic risk and aleatoric risk. There is a divergence between things that are true and things that a language model will give you if you stochastically sample from it.

He said that before RLHF there was much more correspondence between the likelihood of a trajectory and epistemic truthfulness—whether something was actually true—and that RLHF deranges that. I'm thinking that it doesn't really affect your situation, because you are fine-tuning on top of the model. You are either overwriting or working orthogonally to the RLHF training, deliberately saying, “Here is what good looks like.” If the model can generalize from that example of goodness, it can use the likelihood of a trajectory as a proxy for correctness.

We used both a Llama model and an uncensored model in our experiments, and we also compared them with the normal model. The uncensored model was a little bit better, so maybe that makes a difference.

Was it retrospectively uncensored, or was it simply never RLHF-trained?

It was uncensored from the beginning.

I've played with uncensored models, such as the Qwen models, and I found that they are lobotomized. For whatever reason, however they are uncensored, they seem to degrade to the performance of a model half their size. A 72-billion-parameter model will have the reasoning abilities of a 32-billion-parameter model. That's just my experience.

We're not sure whether it is at all important that we use a pretrained model. One of our experiments at the moment is to reset all the weights and then train the model, to check whether we even use the pretrained language capabilities or whether it is just the architecture.

That's very interesting. I interviewed Randall Balestriero at NeurIPS, and he made the same discovery. We are taught that we need large pretrained models and that we are leveraging the knowledge inside them. Apparently, no one had really done this experiment: you can take a very large model and train it from scratch for a discriminative task, and get better performance than frontier models with hardly any training and hardly any data.

It goes back to papers from years ago arguing that there are so many inductive biases in the architecture itself that you don't actually need that much training.

One interesting part is that we also lobotomize our LLM. At the end, we have a model with essentially only 140 tokens or so. We remove all language capabilities from the model and make sure that it can only operate in the space of ARC. It can output numbers from 0 to 9, newline tokens, and some special tokens.

We mostly did that because of computation requirements. It saves a surprising amount of memory, but we remove all language capabilities. We are often asked whether we do any prompting or chain-of-thought thinking. It can't; it's all gone.

The MindsAI team is very bullish on multimodal or cross-domain transfer. They might give English-language descriptions of ARC challenges, for example, and they are looking for as many ways as possible to leverage the base model and the language model.

There are 2 views on this. One is that these things are a form of general intelligence, and the whole point of o3, for example, is that it creates a novel skill program through compositional generalization. It is working in a novel situation.

The alternative view is that they are a jagged and specialized form of intelligence. They are mostly working on specific instances of very similar things that they have seen before, indirectly.

6. Familiar Concepts Drive Transfer

We found that the model performed much better on tasks where it had seen similar tasks. In our paper, we claimed performance of 72% on a left-out part of the evaluation dataset, but performance dropped noticeably if we never trained on any evaluation-set tasks.

We believe that this is because of what we called conceptual leakage from some tasks in the related dataset to other tasks. They are not the same, but they have similar ideas. That is probably also a reason why additional datasets, such as ConceptARC or the BARC dataset, helped. They may have introduced novel ideas in some way.

If the LLM has never seen an idea or concept during training, it is very unlikely to perform well on it. For example, if we train the LLM on ARC challenges involving flood-fill algorithms, it will not transfer those skills to a counting task. But as long as it has seen some counting tasks, it might be able to combine the ideas to form novel challenges.

It is interesting. Take multiplication, for example. Frontier models don't generalize very well. They do a little bit—3 digits, maybe 4 digits—but you can take GPT-2 and fine-tune it on multiplication of up to 20 digits, and it works better than any frontier model.

There is always this notion that fine-tuning for a specific task is architecturally better, but that doesn't work very well, because we live in a world subject to novelty all the time. We can't possibly fine-tune in every possible situation. Maybe this is where active fine-tuning and test-time computation come into play.

Increasingly, we'll build architectures that learn online and share that knowledge with other models in a clever way. It feels as though, with this new online version of prediction, we can have our cake and eat it.

For multiplication, tokenization plays a big role. The models tokenize numbers differently. The model we used had some digits as individual tokens, but sometimes it combined digits into 2-digit or 3-digit numbers.

There were digits from 0 to 9 that it could tokenize, but then there were some 2-digit and 3-digit numbers. Newer models probably do this differently and may have all 3-digit numbers integrated, but for us this was a problem in ARC. We removed all of that from the tokenizer and used only single digits, because the changing length of the outputs would have been a big problem.

So you modified the tokenizer to remove all of the compound numbers?

We essentially removed anything except numbers, end-of-line tokens, end-of-problem tokens, and the input and output prefixes.

You weren't degrading it, because you were training on top of it. You were using a higher-resolution token version of training.

Exactly.

For multiplication, I think a common problem on Twitter is that people misunderstand how complicated a problem is for LLMs. OpenAI has almost every 3-digit number as a token, so if you tell ChatGPT to multiply 2 3-digit numbers, it essentially has to remember 1 million multiplication pairs. That is a very complicated task.

Then people say, “It can't multiply 3-digit numbers,” but that is a hard task for ChatGPT. The same is true of the typical strawberry task. Imagine that every syllable is a token, or every letter is a token in a language you have never seen, and you have to remember how many r's are in each of those tokens. You have to remember that for 130,000 different things, without ever seeing the letter r. That's hard.

LLMs are very strong problem-solvers if you fine-tune them, but they are not the intended solution for ARC in the way that we use them. It is a hacky solution, but because of the challenge you have to use the best-performing model. You could create a very creative solution that goes further in the direction of AGI, but you wouldn't win. You win with LLMs by exploiting fine-tuning speed and things like that. LLMs are too strong for this contest to enable other solutions.

ARC was designed to be solvable by humans. One of the restrictions is that the grids shouldn't be more than about 30 by 30 cells, because otherwise humans would start making many mistakes. Coincidentally, that also seems to be the upper bound of what we can correctly do with an LLM.

If it were 50 by 50 or even 60 by 60, no one would be using LLMs to solve ARC. We would only solve the small problems.

When we look at the failure modes of o3, there is definitely a tailing-off with solution size. It starts making more and more mistakes when it gets to 30 by 30. That raises the question of the complexity of the problem.

My intuition is that ARC has a kind of exponential complexity. I would have said the same thing about language. If you think about all the ways that reference can hierarchically connect to each other, the information complexity of a book should be exponentially large, because there are all of these connections between paragraphs, sentences, and words.

Language models don't have much trouble understanding and explaining books. I want to understand what that is. There is the potential complexity of all the possible connections between terms, and then there is the actual embedded complexity of language. I think you were arguing earlier that the embedded complexity doesn't scale exponentially with problem size.

In many challenges, at least, you can see that most of the problem is trivial. There are just a few pixels where you have to make the right decisions. We measured that, and found that in an intermediate stage of our solutions—when we were still doing normal sampling and not using DFS—we had to get the model to choose the second-highest-probability token 3 times, and then we would have solved 80% of the challenges.

We had to get it to make those choices, but we don't know which of the 900 tokens the second-best token is. The space of solutions the LLM generates is much smaller than the theoretical space, because many of the pixels are trivial. The background is often trivial, for example.

Many problems involve moving an object. If you start the object at the correct position, the LLM generates the rest of the object correctly, but it has to decide where to put that object. That is the hard part. The number of decisions we have to make to generate the correct solution is surprisingly low.

Does that imply that there is no reason in principle why an LLM couldn't scale to 100 by 100, or even 1,000 by 1,000?

That is one of the reasons why Daniel's DFS solution worked so well for us. With normal sampling, each token we generate has a small probability of being selected incorrectly. There are ways to address that, such as min-p sampling and top-k sampling, but we still have a small chance of making a mistake with every token.

Our DFS solution generates all solutions above a certain probability. We are essentially guaranteed to get the most likely solutions, along with some less likely ones, which reduces many of the problems associated with the exponential nature of sampling—as long as our probability bound is low enough.

How did you decide on the depth of the search and the threshold?

We decided on the depth by testing it. How deep can we go to find the correct solution in most cases? It is a trade-off. If you search down to 1%, you can get 100 solutions in theory, although in practice you get much fewer. If you search to 10%, you can get only 10 solutions in theory, and again you get fewer in practice.

For some problems where the solution is clear, it doesn't make a difference—you simply find the solution. But when the solution is unclear, you get many samples by going down to 1%, and that would have been computationally infeasible on Kaggle.

In the end, it was a trade-off that we tested. We ended up trying different values between 10% and 1.77%. The solution was mostly in that range. Going from 10% to 1% gave an improvement from about 70% to 71% on the score, so not much.

It is still technically a variable computation budget. At 1%, if you do it 100 times, you could get a huge variance in the amount of searching. It is vaguely budgeted, but it isn't clear beforehand how many solutions you will get from the DFS. Is that correct?

It depends on the problem. Something interesting happened at the end of the contest, when we switched back to a larger model. We had fine-tuned a lot, and when you use normal sampling, switching to a larger model has a certain factor by which more compute you need. Inference is essentially N times something.

With DFS, however, the larger model got better at deciding what the correct solution was, so it could prune earlier in the DFS. It still took a little longer, but not as much longer as we expected from our previous tests. That was surprising, and it enabled us to do more within the limited compute time on Kaggle.

Did you try a 72-billion-parameter model at home, just for fun?

I tried it on the evaluation set after the contest. I don't think it was a 72-billion-parameter model, but it was a 32-billion-parameter model or something in that range. I didn't have time to fine-tune it properly, so I ran it with the same parameters. It didn't make much of a difference in that setting, but that isn't conclusive because I didn't have time to tune it.

There seems to be an interesting relationship between the strength of the base model and how much test-time computation you do. There is an argument that, if the budget allows, it may be better to do more test-time computation on a smaller model.

I think so. Increasing the size is not necessarily always better in this case. The more parameters you have, the more parameters you have to fine-tune, and for a fixed compute budget I think smaller models are much better. You can generate more, evaluate more, and filter more.

In some experiments, larger models simply didn't perform better. They converged to roughly the same score.

Imagine that you deployed a web service called ARC Solver. If you persisted the LLM and continuously fine-tuned and adapted it, I imagine you would notice that its knowledge was improving because it would do less tree-searching. It would find solutions more quickly.

Do you think it would simply get generally better at ARC and know the solutions more quickly, or would you get strange behavior where it learned distractors on some tasks and got better at some things while getting worse at others?

That's a good question. I have an interesting fact to share. For fine-tuning, we tried different numbers of tasks to train on at the same time for the second fine-tuning. We trained on a single task, 50 tasks from Kaggle, and the full 400 tasks from the evaluation set.

Training on the full set led to much worse performance. Up to 50 tasks was fine, but with more tasks it simply didn't work. Maybe it was too much for the model to store at the same time. We also used LoRA, which has a limited number of parameters, so if we did online training and started with new examples, it might have to forget the old ones to solve the new ones.

We are always taught in the theory of neural networks that there is a problem with catastrophic forgetting, continual learning, and all the rest of it. François Chollet wrote in his book that when you fine-tune, you have to be careful and turn the learning rate right down, because otherwise you'll destroy anything the model already knows and it will learn only the thing you're teaching it.

We are becoming quite red-pilled on OpenAI now, because we believe these things are magical memory machines. They suck in all this knowledge, and the more knowledge you give them, the better they get. That seems to fly in the face of practical experience.

Transformers are very good at learning facts. It is frankly incredible what they can store. There is also a slightly different thing that I find interesting.

In our fine-tuning, we use LoRA, obviously, because fine-tuning the whole network is very expensive. There is a subtle thing with LoRA: if you use weight decay on a LoRA network, it degrades the weights of the LoRA, but you always have the base network below it. You can't fall below the performance of the full base network; you are always around the correct base network and simply move a little in another direction.

If you do test-time training or fine-tuning with LoRA, you can have the safety blanket of the base model below it. That can be very useful. In our challenge, we merged the first LoRA from pretraining into the weights and then did test-time training on another LoRA. In the worst case, it would degrade to the base model from pretraining.

For the audience, LoRA is low-order rank approximation, if I remember correctly. Can you explain how it works? Is it approximation or adaptation?

Adaptation, yes. It is a very simple and elegant idea. You have all these square weight matrices in the attention layers. Instead of fine-tuning all the weights, you fine-tune 2 smaller matrices that you can multiply to get a full-size matrix.

If you have a 1,000-by-1,000 matrix, instead of fine-tuning 1 million parameters, you use a 1,000-by-1 matrix and a 1-by-1,000 matrix. That would be rank 1. You fine-tune those 2 small vectors, and because you reduce the problem to a smaller one, with a simpler problem to learn, that is enough to get the network to move in the right direction.

We used a surprisingly high rank. We tried different ranks from 64 to 256, and the original model has a rank of 4,096. Anything above 128 didn't make a difference to the final performance. We also tried full fine-tuning once, but it was very memory-intensive and didn't make a difference for us. This low-rank approach was probably enough for the problem.

How long did it take? At the beginning, when you were fine-tuning the model, were we talking about half an hour, 2 hours, or a day?

At the beginning we had smaller models and shorter training times, especially when we were still working on the original training set. We couldn't use it too often without overfitting, so it took a few hours—maybe 2 to 4 hours.

It got longer and longer during the challenge. At one point we were at 2 days on an NVIDIA H100, and the final model took essentially 8 days on an NVIDIA H100.

The hard ARC dataset appeared when there were only about 4 days left until the end of the contest. We started multi-GPU training to do 8 days of work in 4 days, or 2 days. Fortunately, Lambda Labs offered us a machine with 8 H100 GPUs, so we could still train the model in time and submit it on the last day.

That was the model with the 56.5 score, which sadly didn't finish in time.

They say necessity is the mother of invention. I'm one of these people who thinks that what you're supposed to do when coding is add 1 feature at a time, check it, commit it, and so on. I have so many things I want to do, though, and I want to stick them all in there. Where do you fall on that spectrum?

7. The Contest Becomes A Mad Dash

Normally I would be similar to you, but in the setting of the contest we simply didn't have time. We had to push new solutions and experiment quickly. Trying to write clean code or refactor it to make it more flexible would have taken 1 or 2 days, and that was too long.

We had so many ideas that we wanted to experiment with that we had to use the code base we already had. If we added new features, we would have had to refactor it again, because we didn't know what we would try during the contest. It was probably pointless to refactor everything constantly.

It felt a little bit like a mad dash. We did some refactoring when things became too complicated—there were 2 or 3 points where I completely refactored the code during the challenge—but between those refactorings we just used it repeatedly and kept adding things.

Would you say your intuitions were fairly correct throughout? We get superstitious about things and think, “That thing is really important; we need to keep it in there.” Were there situations where you realized, to your horror later on, that something you thought was good was actually not good?

That happened sometimes. We were constantly testing different things, leaving some things out and putting others in. We also used many of our submissions for testing: what happens if we remove this feature, or that feature?

Often our favorite ideas didn't pan out. Then we had to decide whether to invest more time in making them work or simply say, “We don't have time to investigate this more deeply. We have to push the things that work.”

Often it was the right decision to ignore our crazy, fun ideas and just do the thing that worked better.

What were the top 2 things out of everything you did that moved the needle the most?

The most important parts of our implementation were, first, the scoring process—scoring with augmentations—which allowed us to select solutions reliably. That gave us a big jump, I think from 30 to 37, when we implemented it.

The other thing was the depth-first-search algorithm. It gave us such a performance gain that we could change many other things afterward, such as using a larger model and doing more augmentations. We couldn't have done those things without DFS.

Part of experimentation is having a useful signal. You're saying that certain features actually unlocked a signal for other things you could try.

The DFS was a natural extension of the scoring process. After we had a good working scoring and selection algorithm, the challenge became generating good candidates. We tried many things to do that, including some LLM-based approaches and some external approaches, such as combining snippets from different solutions to generate new ones.

What worked well was Daniel's DFS algorithm. It was very fast and gave us many different candidates, with very few bad candidates. The 2 approaches worked very well together. It was a synergistic approach.

Did you ever see catastrophic failure modes with the DFS, where it would search for an unreasonable amount of time before hitting the threshold?

Not really, because we limited the search to 10%. It did sometimes search through quite a lot of solutions, but we set the limit so that it didn't lead to a major problem. The probability mass has to be distributed over all paths, so if the lower limit is 10%, there can't be more than 10 valid paths at the same time.

Do you think it would be possible, before doing the depth-first search, to predict the computational budget or predict what the search tree might look like?

That is an interesting question. It might be quite difficult, because you don't know until you have actually done some searching. You could probably estimate it after searching part of the tree, or use iterative deepening: first go to 10%, then to 5%, and so on, if you want to search more deeply while limiting the compute.

You could prompt the model with that solution and then use a classifier trained on the different topologies of trees you had found previously. You might be able to predict beforehand how much computation you should invest in a problem.

If we have the solution, that works. You can check the logits for every pixel and measure the entropy—how distributed the probability is. If the probability is distributed enough, that is a branch in the tree. But then you have only 1 path through the tree, with branches from there.

Predicting the whole tree is probably equivalent to predicting the correct solution in some ways. You have to know the solution to know what the tree looks like.

You were doing a minimum-entropy search, or something like Monte Carlo tree search. It wasn't exactly minimum entropy, but if you look at the entropy distribution, you were searching the space of low entropy.

We aren't doing exactly a minimum-entropy search. We have a rank order for each pixel's next prediction. Pixel color 1 might be the most probable, followed by pixel color 0.

For basically every problem, there are never more than 3 possible continuations. You have to be careful that you don't try the 7 things that are essentially impossible. For many problems, there are only 3 colors, and a broad search would produce colors that are simply impossible.

In the end, every smart algorithmic improvement we tried performed worse. The LLMs were simply smarter than us.

There must be some relationship between sticking a candidate solution in the model and getting an entropy distribution. In some circumstances it is quite pointed—the model says, “I want to go in this direction,” and no other direction—and sometimes it is spread out. What can you infer from that in general?

The pointed distributions are usually correct. The model has a good idea of how the problem is structured. When there are several candidates, it is usually because there is some missing link in the model's understanding of the problem, or because it doesn't understand the problem at all.

We did a lot of testing, and the problems that were hardest for the models were often counting or size-estimation problems. Flood fill worked very well, but counting and size estimation were difficult.

When there are few candidates, they are almost always correct. When the model is unsure, it often predicts a large number of possible candidates.

How did you deal with false positives? You found solutions, and the sum of the log probabilities told you that one was the solution, but it might not have been the solution. It might have been a false positive—the right solution for the wrong reason, or something like that. What did those failure cases look like?

There was one strange problem, I think. You have 4 colors in the upper-left corner, and the goal is to shift the colors in an object in a clockwise direction. The model solves that problem, but the second-best solution is also a color shift, just in the wrong direction.

I found that fascinating, because it means that the model conceptually understands the problem. Even the second-best solution is conceptually correct; it simply goes in the wrong direction.

In cases where the model has a false positive or doesn't solve the problem, it is almost always still moving in the right conceptual direction. It understands that it should fill the space with something, or that it has to generate an object in a particular place, but sometimes it doesn't assess which object. Sometimes it fills the wrong space or makes a similar mistake.