Out-of-Distribution Generalization in the ARC-AGI Domain: Comparing Execution-Guided Neural Program Synthesis and Test-Time Fine-Tuning

## Abstract

Abstract We run a controlled compositional generalization experiment in the ARC-AGI domain: an open-world problem domain in which the ability to generalize out-of-distribution is, by design, an essential characteristic for success. We compare neural program synthesis and test-time fine-tuning approaches on this experiment. We find that execution-guided neural program synthesis outperforms all reference algorithms in its ability to compose novel solutions. Our empirical findings also suggest that the success of TTFT on ARC-AGI lies mainly in eliciting in-distribution knowledge that the LLM otherwise fails to rely on directly.

## Introduction

ARC-AGI and, more recently, ARC-AGI-2 (Chollet et al. 2025), is a challenging open-world visual reasoning problem domain. At its core, ARC-AGI assesses whether a system can recombine primitive operations, or prior knowledge, in novel ways to solve unseen problems; a notion known as compositional generalization. Human solvers effortlessly apply compositional reasoning, but achieving this efficiently in machines has remained elusive. The ARC-AGI hidden test set enforces strict separation between training and final evaluation. While participants can refine models on the public tasks, final performance is reported on tasks with no prior examples online, guarding against overfitting and rewarding genuine generalization.

While ARC-AGI may not capture all aspects of AGI, it offers a concrete test of a critical capability: solving structurally novel reasoning tasks by recombining known primitives. This could be one of the main bottlenecks preventing us from reaching AGI in any deep or strong sense of the word. Indeed, cutting edge AI systems fail to achieve results above 29% on ARC-AGI-2 at the time of this writing. The fact that humans solve these problems while our best AI systems do not is direct, practical evidence of a fundamental missing functionality with respect to AGI.

We are interested in better understanding the performance of neural program synthesis methods, especially execution-guided, multi-step neural program synthesis, in comparison to test-time fine-tuning approaches. Since execution-guided neural program synthesis has not yet been attempted on ARC-AGI, we implement a version of it in this domain, inspired by the most recent literature.

In summary, our main contributions are:

- •
We present an implementation of an execution-guided multi-step neural program synthesis (EG-NPS) algorithm for ARC-AGI, along with a new DSL and program syntax that facilitates the latter.
- •
We present a carefully controlled out-of-distribution generalization experiment to compare EG-NPS, non-execution-guided NPS, and test-time fine-tuning (TTFT).

## Related Work

#### Neural Program Synthesis on ARC-AGI

On the 2024 ARC-AGI competition, two papers described a NPS approach: the Latent Program Network (Bonnet and Macfarlane 2024) and GridCoder (Ouellette 2024). The latter is a non-execution-guided approach based on a CNN+Transformer-architecture and a relatively high-level, specific DSL. The former differs from more traditional program synthesis in that no hand-made DSL is required at all; the algorithm implicitly learns the required primitives from the training data. On the public score board, there is a notable, high-performing NPS algorithm that was attempted (Greenblatt 2024). It uses an LLM, not even fine-tuned on ARC-AGI, to generate program candidates and refine them via trial and error.

#### Execution-guided Program Synthesis

Zohar and Wolf (2018) introduce PCCoder: at each synthesis step, a model predicts the next high-level operation, its operands, and which variables can be dropped (“garbage-collected”), based on the current program state and I/O context. The garbage collection is learned by a distinct neural network than the synthesis. They demonstrate that they are able to create programs that are more than twice as long as existing solutions, while improving the success rate for comparable lengths, and cutting the run-time by two orders of magnitude. Ellis et al. (2019) build on the latter, but use a reinforcement learning approach for the program search instead of a beam search.

Shi et al. (2024) enhance the approach by having a separate Transformer model, the subgoal network, that predicts the next goal state to reach. Doing this decomposes the larger problem in sub-problems which further improves performance on tasks. Verbruggen et al. (2025) introduce execution-guided within-prompt search, a method that iteratively generates and evaluates candidate lines of code within a single prompt. Execution feedback on each candidate is incorporated directly into the prompt as annotations, allowing the language model to refine its output in subsequent generations.

Lavon, Katz, and Wolf (2025) propose Execution‑Guided Classifier‑Free Guidance, a line‑by‑line LLM-based code generation method that integrates real‑time execution feedback into the decoding process. At each line, the model samples multiple candidate continuations via beam search, executes them against test cases, and constructs an execution‑trace prompt. Classifier‑Free Guidance then steers the next tokens by interpolating between the normal and execution‑conditioned distributions, refreshing this feedback at each line boundary.

#### Test-time fine-tuning

Akyürek et al. (2025) use an 8B Llama 3 model pretrained on synthetically generated tasks, and they evaluate on a subset of the publicly available ARC-AGI validation tasks. They show an increase in performance, as in the empirical results we will present, but contrary to their claims, it cannot be concluded that this is due to an ability to generalize to structurally novel tasks: they use a pretrained foundation model and evaluate on publicly available data. In addition, they generate tasks synthetically for training, as well as geometric transformations thereof, that can overlap with validation data. Thus, data contamination is likely, and whether their evaluation benchmarks are truly out-of-distribution is unknown.

## Background

ARC-AGI consists of solving tasks that are composed of (typically 3 to 6) pairs of grids. Each pair consists of an input grid and its associated target grid. Each grid can have a size of anywhere between $1\times 1$ to $30\times 30$ cells, each cell being one of 10 possible colors. Each task has its own logic that converts the input grid examples to their associated target grids. The solver must figure out the underlying logic or algorithm, and apply it to a test grid in order to confirm its understanding. It is evaluated on a hidden private test set, which consists of tasks that are meant to be distinct from any of the tasks that are publicly available.

Additionally, in ARC-AGI-2, submission attempts are not immediately scored on this private test set, to avoid ”data mining” or ”overfitting” this test set. This methodology encourages building solvers that can adapt to novelty, instead of simply interpolating over a predefined domain.

In theory, with unlimited compute, one could enumerate all possible programs that can be formulated in a given DSL, train a neural network to learn with perfect accuracy the entire manifold for that program space, and then use that to solve any tasks in the problem domain that is covered by this program space. In practice, of course, in an open-ended problem domain such as ARC-AGI, one can expect to face tasks at test time that are quite distinct from those seen during training. Therefore, strategies must be discovered that will allow the solver to adapt at test-time to these novel problems.

## Execution-Guided Synthesis for ARC-AGI

We implement a variant of execution-guided neural program synthesis for ARC-AGI. This implies developing our own DSL for this domain, in a way that facilitates having a tractable, tokenizable intermediate state at each step along the way.

### GridCoder 2

The execution-guided neural program synthesis implementation we propose here(^1^11https://github.com/SimonOuellette35/OODGenARC-AGI) uses a DSL and a Transformer trained from scratch, rather than an LLM with pretraining. Unlike Zohar and Wolf (2018), our memory management strategy is based around the <del> primitive. Whenever this instruction occurs, the specified state variable is removed from memory. Thus, we have one neural network, not two, and its responsibility is both to help synthesize the program and to manage memory in the same process.

The execution-guided feedback is implemented by executing the current instruction step, tokenizing its output (in our DSL, each instruction step always outputs exactly one variable), feeding it to the encoder to produce an embedding, and concatenating this embedding to the previous ones. This generated encoder memory is used as input to the decoder for the next instruction step decoding iteration (see Figure 1).

Figure: Figure 1: A diagram of the state-conditioned, execution-guided inference used. Each step consists of decoding a single instruction sequence from looking only at a concatenated accumulation of past encoded states and the encoded target state. The resulting token sequence is executed, the output is tokenized and encoded, added to encoder memory, and the procedure is repeated.
Refer to caption: figures/diagram_recursive_inference.png

Additionally, a feature we refer to as ”entropy” was added to take up the remaining time budget when the full non-zero probability space is explored well before its expiration. When that happens, it re-launches the search, but in this second iteration it adds a fixed probability value to randomly selected tokens of the root node expansion. This creates further exploration of paths that previously had a zero probability assigned to them, potentially discovering new trajectories that solve the problem. Although the impact of this mechanism on aggregate success rates was limited, it enabled the solution of three additional task instances that could not be solved without it.

Our program search algorithm is a tree search in which each node represents the application of one particular instruction step sequence. Each node that gets expanded is populated with a list of non-zero probability instruction sequences conditional on that node’s program state. Each child of this node contains an index indicating which of these instruction sequences was executed to reach that child node. Thus, each node also contains a state variable, corresponding to the output of applying its instruction step sequence.

The search through this tree continues until either a solution is found or a timeout occurs. A solution is considered found when the generated program state is exactly like the expected target grids of the demonstration set examples. Details of this algorithm can be found in Appendix A, but the high-level iterative steps are:

- 1.
Collect the currently selected node’s input state by concatenating the intermediate state of all its parents in the tree. Execute the selected node’s instruction step on this state. Save the result inside that node.
- 2.
If this result is the target grid set, a solution has been found.
- 3.
Given the selected node, the target grids, and the trained model: generate all token sequences for the next instruction step (whose probability $>$ some threshold, 0.01 in our case).
- 4.
Calculate the joint probability of each of these instruction step token sequences.
- 5.
Insert these new programs into a global queue, ordered by joint probability. The new programs are the programs represented by the tree path down to the selected node, to which each of the newly generated instruction steps are appended.
- 6.
This program queue is used to select the next program to attempt (the highest probability one), which is then dequeued. A new child node is instantiated from this next program’s last instruction step. This becomes the new selected node. Repeat from step 1.

The neural network used is a standard encoder-decoder transformer, whose hyperparameters are detailed in Appendix B. During training, each ground truth program is decomposed into its individual instruction steps. Each training sample is a token sequence of an instruction step, coupled with the tokenized sequences of intermediate states that have been generated in the previous instruction steps. This includes the initial input-output grid set.

This tokenized intermediate state is fed to the encoder, which produces the embedding that is fed to the decoder. The latter predicts a token sequence that minimizes the cross-entropy loss with respect to the ground truth instruction step. This supervised training proceeds iteratively: each iteration, the encoder embedding for subsequent steps is generated by executing the instruction steps from previous iterations and concatenating them to the current embedding.

## DSL

We introduce a custom domain-specific language(^2^22https://github.com/SimonOuellette35/AmotizedDSL) (DSL) tailored for ARC-AGI. Each program is a sequence of instruction steps, where each step executes a single primitive operation and produces exactly one output variable (e.g., a Grid, a list, or a scalar).

> [<primitive>, <SEP>, <arg1>, <ARGSEP>, <arg2>, <ARGSEP>, ..., <argN>, <EOS>]

**Table 1: DSL instruction structure. Each instruction is a token sequence of the form [<primitive>, <SEP>, <arg1>, <ARGSEP>, ..., <argN>, <EOS>].**
| Component | Description |
| --- | --- |
| <primitive> | Operation to apply (e.g., equal, set_pixels) |
| <SEP> | Separator between primitive and arguments |
| <argN> | Argument: constant, object attribute, or reference to prior variable |
| <ARGSEP> | Separator between arguments |
| <EOS> | Marks the end of the instruction step |

Each argument can be a constant or a reference to an existing variable in the current state of the program, either the initial input grid set or the output of a previous instruction step. Accessing a Grid’s attributes is done by using two consecutive argument tokens: the reference to the object, and the attribute token. There is a special del primitive that does garbage collection of specified program state variables that are no longer needed by the rest of the program. Table 2 describes the token types and their range. See Appendix D for details.

**Table 2: Token ranges in the DSL vocabulary. N is the total number of primitives (including the constants and object attributes) in the DSL. The vocabulary includes integer constants, DSL primitives, object attributes, and references to previously defined state variables.**
| Token Range | Meaning |
| --- | --- |
| 0--9 | Integer constants |
| 10--N | Primitives and object attribute tokens (e.g., .x, .c) |
| N+0 to N+max | State variable references to intermediate values (e.g., outputs of previous instruction steps) |

The example program in Table [3](https://arxiv.org/html/2507.15877v2#Sx5.T3) contains four instruction steps. Its effect is to change all non-zero pixels of the grid to the color $2$. The first instruction returns a boolean list for each pixel in the input grid set (reference: $N+0$), set to true if 0, false otherwise. Instruction $2$ is an ”if/else” statement going over each element of $N+1$. When its value is True, it outputs 0, otherwise it outputs $2$. The third instruction removes from memory the now obsolete $N+1$. The last instruction sets all pixels of the input grid set $(N+0)$, at positions determined by .x and .y attributes of $N+0$ (i.e., all pixels are modified), to the color value specified in what was previously $N+2$, but is now $N+1$ due to the previous del operation.

**Table 3: Example DSL program: recolors all non-zero pixels in the input grid to color 2.**
| #1. | [equal, <SEP>, N+0, <.c>, <ARGSEP>, 0, <EOS>]   $\rightarrow N+1$ |
| --- | --- |
| #2. | [switch, <SEP>, N+1, <ARGSEP>, 0, <ARGSEP>, 2, <EOS>]   $\rightarrow N+2$ |
| #3. | [del, <SEP>, N+1, <EOS>] |
| #4. | [set_pixels, <SEP>, N+0, <ARGSEP>, N+0, <.x>, <ARGSEP>, N+0, <.y>, <ARGSEP>, N+1, <EOS>] |

## Experiments & Results

The controlled experiment presented here is designed to clearly compare the capabilities of competing approaches. Specifically, it examines the ability of an algorithm to learn from training data in a way that generalizes to new compositions of this training data. By knowing exactly the content of the generated training and test data, we prevent any form of data contamination. We can also evaluate in controlled ways the failure and success cases of the competing approaches.

### The algorithms being compared

Five different approaches to solving these ARC-AGI-based problems are compared. First, the GridCoder implementation presented in Ouellette (2024) is evaluated. This is a neurally guided search over programs, but it does not perform state-conditioned synthesis: instead, it processes the input-output pairs and searches for the most probable program without using any feedback on the intermediate effects of its instructions. Additionally, it uses the rather specific and high-level DSL presented in that paper, rather than the lower-level, more flexible DSL used here.

GridCoder2 is the execution-guided neural program synthesis baseline, detailed in previous sections. In NN-Only, the same neural network and state-conditioned inference procedure as GridCoder 2 is used, but without the search algorithm. Only the highest probability tokens are generated at each step, instead of searching over the space of programs for a fit on the input-output examples.

Given TTFT’s popularity in ARC-AGI, we include it as a baseline. Specifically, we use the Omni-ARC algorithm (Barbadillo 2024), which won second place on the ARC-AGI 2024 competition. Because the comparisons must be on an equal footing, therefore trained on the same data, the LLM Qwen2-0.5B-Instruct is trained from scratch (i.e. without loading its pretraining weights) on the same training data as the other approaches. Additionally, because the objective of the experiments will be to evaluate out-of-distribution generalization specifically, some geometric data augmentations that can generate training data identical to the out-of-distribution tasks were removed.

Omni-ARC is a transductive approach, rather than a program synthesis approach. In other words, the inference output is not a program to execute, but rather the predicted output grid itself. It operates in essentially 4 steps:

- 1.
The LLM (Qwen2-0.5B-Instruct) is fine-tuned on a training dataset designed to learn the ARC-AGI domain itself.
- 2.
The fine-tuned LLM is then further fine-tuned on a given test task. This is the test-time fine-tuning step, which outputs a task-specific LoRA adapter.
- 3.
The fine-tuned LLM and its associated LoRA adapter are used to perform a number of different inference attempts on the test grid(s) of the task to solve.
- 4.
A voting procedure is used over the inference attempts to determine the true guess.

Finally, the AlphaEvolve algorithm was also evaluated, by using an open-source implementation of it (Sharma 2025). It is a Python-based program synthesis approach. The LLM engine used was gpt-4.1-mini, without being fine-tuned on the ARC-AGI domain. While using the pretraining goes against the idea of controlling for training data shift and preventing data contamination, in this case the performance was too low, in spite of all of its pretraining, to be an issue. A few different prompt templates were experimented with, but in all of them the LLM was given the following information in its prompts:

- 1.
a pixelwise similarity metric to improve upon: the percentage of identical pixels between input grid and target grid
- 2.
three input grids for the given task
- 3.
their three corresponding target grids
- 4.
the three grids currently returned by the program.

Comparison to a baseline brute-force search was omitted for the simple reason that the GridCoder 2 DSL search space is too vast to be tractable to such an approach under the given resource budget. All models are trained on, and experiments are run on, an A40 RunPod instance with 48Gb of VRAM, 50Gb of RAM, and 9 vCPUs (Intel(R) Xeon(R) Gold 6342 CPU @ 2.80GHz), using a three minute budget per task instance.

The training data for each task is generated by randomly sampling subgrids of ARC-AGI training tasks, and by applying the task’s ground truth program to the inputs in order to obtain the target grids. The program synthesis models are trained on $200,000$ task examples each containing exactly one input/output pair, each example designed to be non-trivial and not underdetermined. The task is considered solved if it finds a program that generates the outputs (including a test output) from the input. Five runs per task example were done to evaluate variance in results (min/max/median). The DSL for the experiments #1 and #2 contain $34$ primitives, while the experiment #3 used a DSL of $45$ primitives.

The TTFT model was pretrained on a larger amount of pair examples: $100,000$ task instances each having 8 input/output demonstration pairs, for a total of $800,000$ distinct pair examples. TTFT itself is done on task instances with 3 pairs. The voting procedure, when evaluating the test output, is done over 8 different inference attempts. The most frequent output is kept.

The comparison between TTFT and GridCoder2 is fair because they both have 3 minutes of test-time search (or gradient descent in the case of TTFT). If anything, the experiment is unfair to GridCoder2 because it is trained on only $200,000$ whereas TTFT is trained on $800,000$ tasks. The 3 minutes time budget was selected to match the average task solution time allowed per task on the ARC-AGI Kaggle competition, and is therefore not arbitrary, nor was it selected to favor GridCoder2. Qwen2-0.5B-Instruct is the LLM used by Omni-ARC to reach its performance in the 2024 competition, so it has more than enough capacity to learn what it needs to learn for these experiments.

### Experiment #1: Out-of-Distribution Tasks

In this first experiment, each neural network is trained on $14$ distinct tasks that are constructed by composing a known set of high-level operations such as recoloring non-zero pixels, horizontal grid flipping, translation of pixels, etc. They are then evaluated on a different set of $7$ tasks, each compositionally constructed from these same atomic operations (see Table [4](https://arxiv.org/html/2507.15877v2#Sx6.T4)). However, these $7$ test tasks are out-of-distribution (OOD) with respect to the training set because they are composed in ways that are not seen in the $14$ training tasks (see Appendix C for details).

In some cases, the ground truth programs of the OOD tasks are significantly longer than the longest one seen in the training set. For each of these OOD tasks, $10$ task instances are attempted. By task instance, we mean a distinct grid input-output set that implements the same underlying task pattern.

The results in Table [4](https://arxiv.org/html/2507.15877v2#Sx6.T4) indicate that AlphaEvolve is too slow and struggles to find the solution except for the most trivial examples. For OOD task #1, for example, it immediately noticed that a recoloring of the non-zero pixels was required, but no matter how much it iterated on the generated program, it would never discover that a shift to the right is subsequently required.

**Table 4: Median success rate over 10 samples for each OOD task and each algorithm, with a 3-minute budget per task sample. Total min, max and median over 5 distinct runs is shown as well.**
| OOD Task # | NN-Only | GridCoder1 | GridCoder2 | TTFT | AlphaEvolve |
| --- | --- | --- | --- | --- | --- |
| 1 | 10% | 70% | 100% | 10% | 0% |
| 2 | 0% | 90% | 80% | 10% | 0% |
| 3 | 10% | 70% | 100% | 40% | 0% |
| 4 | 40% | 60% | 100% | 0% | 0% |
| 5 | 0% | 10% | 70% | 0% | 0% |
| 6 | 0% | 0% | 60% | 10% | 0% |
| 7 | 10% | 0% | 50% | 0% | 100% |
| Min | 10% | 40.06% | 78.4% | 9.8% | 14.29% |
| Max | 10% | 43% | 82.8% | 12.3% | 14.29% |
| Median | 10% | 42.86% | 80% | 10% | 14.29% |

### Experiment #2: Analyzing TTFT

The relative performance of TTFT in the first set of experiments can seem contradictory to the high performance of TTFT on the 2024 competition. The experiment in this section focuses entirely on TTFT, in order to better understand the sources of success, and the limitations, of this approach. In particular, what component of the performance comes from the LLM pretraining, from the various data augmentations that the original implementations use, and TTFT itself (or an interaction of these components).

This experiment is performed on the same data as Experiment #1: we fine-tune on the $14$ training tasks and evaluate on the the $7$ OOD tasks. In Table [5](https://arxiv.org/html/2507.15877v2#Sx6.T5), LLM+TTFT refers to the original, intact version of the Omni-ARC implementation: the pretrained Qwen2-0.5B-Instruct weights are used, instead of being discarded, which means that all of the knowledge it benefits from is used. Additionally, all of the data augmentations are used, regardless of the fact that they convert tasks that were intended to be out-of-distribution into training distribution tasks.

LLM-no-TTFT is the full LLM, fine-tuned on the 14 training tasks, with data augmentations, but no TTFT is done. TTFT+augments refers to not using the Qwen2-0.5B-Instruct weights at all, but all of the data augmentations are kept, and TTFT is used. And finally, TTFT-no-augments is simply a repetition of the scores of the TTFT implementation used in Experiment #1, for visibility.

**Table 5: Comparison of TTFT variants on the OOD tasks.**
| OOD Task # | LLM+TTFT | LLM-no-TTFT | TTFT+augments | TTFT-no-augments |
| --- | --- | --- | --- | --- |
| 1 | 90% | 50% | 40% | 10% |
| 2 | 100% | 100% | 70% | 10% |
| 3 | 100% | 80 % | 40% | 40% |
| 4 | 70% | 20% | 0% | 0% |
| 5 | 80% | 10% | 0% | 0% |
| 6 | 90% | 0% | 10% | 10% |
| 7 | 100% | 90% | 90% | 0% |
| Total | 90% | 50% | 35.71% | 10% |

### Experiment #3: ARC-AGI Training Tasks

To demonstrate that our approach is not contrived and can apply to real ARC-AGI tasks, we present results on a subset of ARC-AGI-2 training tasks. To expand the model’s scope, $11$ new primitives and $6$ additional training tasks were added.
Only up to 18 tasks are theoretically solvable under the current DSL, in large part because it does not yet include the ability to detect and manipulate objects. GridCoder2 solves $83.33\%$ of the theoretically solvable ARC-AGI-2 training tasks, which is $1.5\%$ of the whole set. In contrast, NN-Only solved only $27.78\%$ of the theoretically solvable tasks.

## Discussion

### TTFT results

The TTFT experiments clarify why the method performs well on ARC-AGI. First and foremost, the large gap between LLM+TTFT and the other variants that do not use the LLM’s pretraining indicates that most of the performance comes from the LLM’s foundational knowledge. It is conceivable that it has already been trained on tasks that are sufficiently similar to relatively simple operations found in our OOD tasks: translating elements in a matrix, systematically replacing some values with other values, flipping the matrix elements around an axis, etc.

Yet, the performance of this same, fully pretrained LLM drops significantly when no TTFT is used (LLM-no-TTFT). This suggests that TTFT is able to extract information from this pretraining that is not available from direct, static inference. This is coherent with Sun and Dredze (2025), in which the authors fine-tuned multiple checkpoints of a large LLM and found that additional pretraining produces latent gains that only become visible after fine-tuning.

Their findings suggest that large-scale pretraining builds a core capability that fine-tuning unlocks for each downstream task. On a similar line of thinking, research on using reinforcement learning at test-time, for a purpose similar to TTFT here, indicates that it only reshapes the probability distribution of answers, as it only makes correct trajectories easier to hit (Yue et al. 2025). It does not add any reasoning paths that were not there in the base model to begin with. The original GridCoder paper made a similar observation in the discussion section.

As for the gap between TTFT+augments and TTFT-no-augments, it is easily explained by the presence of geometrical data augmentations that cause the training procedure to see task examples that are very similar to the OOD task examples. The drop in performance for Task #7 is explained by the following: some training tasks consists of shifting pixels to the right, but none consist of shifting to the left. However, when the data augmentation horizontally flips or rotates by 180 degrees both the input and output grids to create a new task, what is presented effectively becomes the task of shifting pixels to the left. Thus, Task #7 is no longer out-of-distribution when this happens, explaining its high success rate.

Task #2 performance is explained by training task #13 (see Appendix C): it consists of shifting the pixels upwards by one row, and then vertically flipping the grid. Seen differently, this is the same as vertically flipping the grid first, and then shifting the pixels down by one row. Now, if you rotate the input and output grid by 270 degrees via data augmentation, you get a new task: horizontally flip the grid, then shift the pixels to the right. This is exactly OOD Task #2.

In summary, the majority of the performance boost from using TTFT appears to come from its ability to elicit knowledge that comes from the training manifold, i.e. that is in-distribution with respect to it. We did not observe any substantial empirical evidence that TTFT is capable of learning novel tasks on-the-fly. These findings are coherent with the results from Teterwak et al. (2025), which indicate that transfer learning does not generalize to any unseen task. It improves performance when data distribution shifts are on the pretraining manifold; when shifts are orthogonal, fine-tuning is not sufficient.

### Surprising solutions

GridCoder 2 was able to derive unexpected solutions. In addition to being quite successful at discovering solutions to compositionally novel tasks (which was the expected and intended result), it also produced solutions that were surprising in two ways:

- 1.
It composed subroutines in ways that omitted unnecessary instructions from one or both of the subroutines when the input grid’s specific content allowed it.
- 2.
It corrected redundancies in ground truth programs by ignoring the redundant instructions.

#### Example #1

For the input and output grid pair presented in Figure [2](https://arxiv.org/html/2507.15877v2#Sx7.F2), it solved the problem by first flipping the grid horizontally, and then, for the subsequent steps, instead of using the ground truth program for ”shift right” tasks seen during training, it innovated a more efficient version by skipping the part that zeros out the left column. It could afford to do so because the input grid already does not contain any non-zero pixels in the leftmost column, making the step superfluous.

Figure: Figure 2: Example #1: the task consists of flipping the grid horizontally, and then shifting its pixels to the right by 1 column.
Refer to caption: figures/example1.png

#### Example #2

In this example shown in Figure [3](https://arxiv.org/html/2507.15877v2#Sx7.F3), the goal is to shift the pixels diagonally towards the upper-right corner of the grid. The given solution differs from the expected solution in two ways. First, unlike the ground truth ”shift right” and ”shift up” programs, no zeroing out of the leftmost column or the bottom row occur, because of the specificities of the input grid. This is the same principle as Example #1 above. Second, the solution did not contain a crop of the resulting grid after the ”shift up” subroutine, contrary to the related ground truths.

Investigation revealed a bug in the ground truth programs, consisting of this redundant and superfluous crop operation. Although shifting right or down extends the grid and therefore requires cropping, shifting up or left silently discards pixels pasted to negative indices because of how the primitives have been implemented. Consequently, cropping is unnecessary in such cases.

Figure: Figure 3: Example #2: the task consists of shifting the pixels diagonally towards the upper-right corner by 1 row, 1 column.
Refer to caption: figures/example2.png

#### Example #3

This task (Figure [4](https://arxiv.org/html/2507.15877v2#Sx7.F4)) was implemented as a 180-degree rotation. Mathematically, composing a vertical and horizontal flip together produces the same result, which GridCoder 2 had no issue discovering. But the more interesting aspect is the efficiency of the solution. This is another case where it found a more efficient way to implement a routine than in our ground truth programs. It starts as expected by flipping the grid vertically. However, the subsequent steps implement a horizontal grid flip in a more condensed way than our ground truth program for this task, by doing it in 1 instruction instead of 3.

These 2 implementations are logically equivalent, but this is another case where our ground truth programs were inefficient. Indeed, our ground truth program was using an instruction <colorOf> that returns a list of pixel colors, instead of directly using the object attribute <.c> when setting the output grid pixels, which is more compact.

Figure: Figure 4: Example #3: the task consists of doing a 180-degree rotation. This can be also accomplished by flipping the grid both vertically and horizontally.
Refer to caption: figures/example3.png

## Conclusion

We conduct a controlled experiment that uses ARC-AGI-like tasks, evaluating the compositional generalization capabilities of various approches. Execution-guided NPS is the approach that was most able to extract compositional knowledge and to reuse it at test-time on novel tasks. In fact, it even innovated surprising solutions, with its ability to generate more efficient solutions than the program ground truths it was trained on.

In contrast, an ablation study that consists of omitting the test-time search component by only using the argmax solution significantly underperformed. GridCoder, which can be thought of as GridCoder 2 without the state-conditioned decoding, also significantly underperformed. Finally, experiments on TTFT identified no evidence of an ability to reliably generalize to structurally novel tasks.

## Acknowledgments

Thanks to Guillermo Barbadillo for his open source Omni-ARC project and his help in answering our questions about this approach.

## References

- Akyürek et al. (2025)
Akyürek, E.; Damani, M.; Zweiger, A.; Qiu, L.; Guo, H.; Pari, J.; Kim, Y.; and Andreas, J. 2025.
The Surprising Effectiveness of Test-Time Training for Few-Shot Learning.
arXiv:2411.07279.
- Barbadillo (2024)
Barbadillo, G. 2024.
Omni-ARC.
https://github.com/ironbar/arc24.
Accessed: 2025-06-16.
- Bonnet and Macfarlane (2024)
Bonnet, C.; and Macfarlane, M. V. 2024.
Searching Latent Program Spaces.
arXiv:2411.08706.
- Chollet et al. (2025)
Chollet, F.; Knoop, M.; Kamradt, G.; Landers, B.; and Pinkard, H. 2025.
ARC-AGI-2: A New Challenge for Frontier AI Reasoning Systems.
arXiv:2505.11831.
- Ellis et al. (2019)
Ellis, K.; Nye, M.; Pu, Y.; Sosa, F.; Tenenbaum, J.; and Solar-Lezama, A. 2019.
Write, execute, assess: Program synthesis with a repl.
*Advances in Neural Information Processing Systems*, 32.
- Greenblatt (2024)
Greenblatt, R. 2024.
Getting 50
https://redwoodresearch.substack.com/p/getting-50-sota-on-arc-agi-with-gpt.
Accessed: 2025-07-12.
- Lavon, Katz, and Wolf (2025)
Lavon, B.; Katz, S.; and Wolf, L. 2025.
Execution Guided Line-by-Line Code Generation.
arXiv:2506.10948.
- Ouellette (2024)
Ouellette, S. 2024.
Towards Efficient Neurally-Guided Program Induction for ARC-AGI.
arXiv:2411.17708.
- Sharma (2025)
Sharma, A. 2025.
OpenEvolve: Open-source implementation of AlphaEvolve.
https://github.com/codelion/openevolve.
Accessed: 2025-06-16.
- Shi et al. (2024)
Shi, K.; Hong, J.; Deng, Y.; Yin, P.; Zaheer, M.; and Sutton, C. 2024.
ExeDec: Execution Decomposition for Compositional Generalization in Neural Program Synthesis.
arXiv:2307.13883.
- Sun and Dredze (2025)
Sun, K.; and Dredze, M. 2025.
Amuro and Char: Analyzing the Relationship between Pre-Training and Fine-Tuning of Large Language Models.
arXiv:2408.06663.
- Teterwak et al. (2025)
Teterwak, P.; Saito, K.; Tsiligkaridis, T.; Plummer, B. A.; and Saenko, K. 2025.
Is Large-Scale Pretraining the Secret to Good Domain Generalization?
arXiv:2412.02856.
- Verbruggen et al. (2025)
Verbruggen, G.; Tiwari, A.; Singh, M.; Le, V.; and Gulwani, S. 2025.
Execution-guided within-prompt search for programming-by-example.
In *The Thirteenth International Conference on Learning Representations*.
- Yue et al. (2025)
Yue, Y.; Chen, Z.; Lu, R.; Zhao, A.; Wang, Z.; Yue, Y.; Song, S.; and Huang, G. 2025.
Does Reinforcement Learning Really Incentivize Reasoning Capacity in LLMs Beyond the Base Model?
arXiv:2504.13837.
- Zohar and Wolf (2018)
Zohar, A.; and Wolf, L. 2018.
Automatic program synthesis of long programs with a learned garbage collector.
*Advances in neural information processing systems*, 31.

## Appendix A Appendix A. Search algorithm pseudo-code

Figure: Algorithm 1 TreeSearch

In the pseudocode, $SearchTreeNode$ is the class representing a node in the tree structure. The first argument is the state variable if we already have it, and the second argument is the parent node. The node’s state variable can be set to None and later updated from inside the $execute_program$ call. The latter executes the instruction step associated with the node, gets the resulting output, and updates the node’s internal state variable. It also returns the result to verify if the goal was reached.

The $enumerate$ function aggregates encoder output from the parent node states and the target grid $Y$, and then uses the model $M$ to recursively query token probabilities and return possible token sequences for the next instruction step whose probability is greater than some threshold. We use 0.01 in our experiments. Also, if the number of generated possible sequences exceeds a threshold k, we only keep the top k (k = 1M in our experiments). Finally, there is a maximum token sequence length of 40 tokens.

Suppose $enumerate$ generates $42$ different possible instruction steps at this stage in the program, this means that we add $42$ new programs to the program queue: each starting with the same instruction steps for the node parents trajectory, and ending with the newly generated instruction steps.

Not presented in the pseudo-code (for simplicity) are further search constraints such as maximum tree depth (20 in our experiments) and a memory limit of 5. This memory limit refers to the maximum number of intermediate state variables that can be kept in the program’s working memory at all times. When that memory limit is reached, only the del primitive is allowed to clear up some memory.

## Appendix B Appendix B. Hyperparameters

#### Execution-guided NPS

The neural network used in the experiments presented in this paper is a standard Encoder-Decoder transformer architecture (using PyTorch), with $4$ encoder and $4$ decoder layers. The feedforward layer’s dimensionality is $1024$, the embedding space (d_model) has a dimension of $256$, and $16$ attention heads were used. The input vocabulary has a size of $55$ and the target vocabulary has a size of $45$.

#### TTFT

Fine-tuning from scratch on our training data was not done using LoRA. Instead, it was a full, ”standard” training of the weights. While most of the hyperparameters used were the same ones used by Omni-ARC to reach 2nd place in the 2024 ARC-AGI competition, in an attempt to improve the performance of TTFT-no-augments we varied some hyperparameters in the test-time fine-tuning phase. In particular:

- 1.
max_steps: we tried fine-tuning a different number of steps from $10$ steps up to the maximum number of steps that took 2 minutes 30 seconds, to respect the 3-minute time budget (the subsequent LoRA merge step, inference step and voting steps took approximately $30$ seconds). This lead to trying up to about $60$ fine-tuning steps.
- 2.
learning rate: varied between 2e-4 to 1e-5 in various increments.
- 3.
batch_size: we tried the default 16, 8 and 32.
- 4.
eval_steps: we tried 10, 20, 50.

## Appendix C Appendix C. OOD Task details

The neural network is trained on generated training data that implements the following 14 simple ARC-AGI-like tasks, on grids of variable dimensions between $3\times 3$ and $30\times 30$:

- 1.
Horizontally flip the grid around the vertical axis formed by the center column.
- 2.
Vertically flip the grid around the horizontal axis formed by the center row.
- 3.
Set all non-zero, non-black pixels to the color green.
- 4.
Horizontally flip the grid and set all its foreground pixels to green.
- 5.
Vertically flip the grid and set all its foreground pixels to green.
- 6.
Shift pixels to the right by 1 column, with no wrapping; the leftmost column is left completely black.
- 7.
Shift pixels upward by 1 row (no wrapping).
- 8.
Shift pixels downward by 1 row (no wrapping).
- 9.
Shift pixels to the right by 1 column, and then horizontally flip the resulting grid around the central axis.
- 10.
Vertically flip the grid, and then shift the resulting grid to the right by 1 column.
- 11.
Horizontally flip the grid, and then shift the pixels upward by 1 row.
- 12.
Shift the pixels downward by 1 row, and horizontally flip the grid.
- 13.
Shift the pixels upward by 1 row, and then vertically flip the grid.
- 14.
Vertically flip the grid, and then shift the pixels upward by 1 row.

The OOD tasks are:

- 1.
Shift the pixels to the right by 1 column, and set all the non-zero pixels to green.
- 2.
Horizontally flip the grid, and then shift the pixels to the right by 1 column.
- 3.
Shift the pixels diagonally towards the upper-right corner by 1 cell.
- 4.
Rotate 180 degrees
- 5.
Horizontally flip the grid, shift it to the right, then vertically flip it.
- 6.
Set the non-zero pixels to green, shift diagonally the pixels towards the upper-right corner.
- 7.
Shift pixels to the left (no wrapping).

## Appendix D Appendix D. DSL details

Object attributes:

- 1.
.x: a list of all x coordinates of each grid cell from left to right, top down
- 2.
.y: a list of all y coordinates of the grid from left to right, top down
- 3.
.c: a list of all pixel colors of the grid from left to right, top down
- 4.
.width: the number of columns in the grid
- 5.
.height: the number of rows in the grid
- 6.
.max_x: width - 1 (essentially a shortcut to simplify code)
- 7.
.max_y: height - 1
- 8.
.ul_x: x coordinate of the upper left corner of this grid. Can be non-zero if this is a sub-grid representing an object in the outer grid.
- 9.
.ul_y: y coordinate of the upper left corner of this grid. Can be non-zero if this is a sub-grid representing an object in the outer grid.

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 6
presentation: 3
questions: 1. Have the authors considered training neural program synthesis from a pretrained LLM rather than from scratch? While one would expect it to not make much of a difference, it would be nice to disentangle the base architecture from the training algorithm. 

2. If I understand correctly, the other neural program synthesis approach GridCoder uses a different DSL than EG-NPS. What would happen if the DSL used between the two approaches were the same?
soundness: 3
strengths: 1. Compositional generalization is an important yet underexplored problem. The setup the authors considered in ARC-AGI will be generally useful for evaluating compositional generality of future approaches. 

2. The authors demonstrate that fine-tuning is primarily useful for unlocking latent in-distribution knowledge and not OOD generalization. This is an interesting finding as such fine-tuning approaches are very popular in practice.

3. The authors develop (to my knowledge) the first instance of execution-guided neural program synthesis for the ARC-AGI domain with its own DSL. This will be a useful baseline to compare against for this benchmark.
summary: The paper considers compositional generalization within the the ARC-AGI domain. The authors demonstrate that execution-guided program synthesis performs best, beating out other neural program synthesis approaches as well as test-time fine-tuning of LLMs. To achieve this, the authors developed a DSL for the ARC-AGI domain.
weaknesses: 1. While execution-guided program synthesis is proven to be effective at compositional generalization, its applicability seems to be limited due to the requirement of designing a DSL that covers all theoretically solvable tasks. In particular, the DSL the authors designed does not cover the full scope of ARG-AGI tasks. So it is unclear how useful such approaches will be in general. 

2. The entropy term added to search did not seem particularly effective. It is unclear if the search algorithm implemented was suboptimal.

3. Furthermore, my understanding is that neural program synthesis and fine-tuning consider very different test-time search algorithms. This makes the results a bit more difficult to parse, as it is unclear how important the choice of search algorithm was.

---

confidence: 3
contribution: 2
initial_rating: 4
presentation: 4
questions: Questions are raised in the weakness section.
soundness: 3
strengths: * The paper is well written and explains enough details to understand the distinction to prior approaches.

* The ablation study is focused and explains where EG-NPS improves over prior works evaluated.

* The gains on the programs evaluated in success rate are significant. The approach solves about 83% of the few (1.5%) of ARC-AGI-2 tasks within scope of the current DSL considered in the work.

The paper's proposed methods combines a number of pre-existing ideas, but in a systematic way. The analysis and design of experiments is performed carefully to understand where the gains are coming from.
summary: The paper target the problem of solving out-of-distribution (OOD) tasks in the ARC-AGI-2 visual reasoning benchmark. The approach extends the line of work on execution-guided program synthesis with an approach the paper calls EG-NPS. It uses a simple DSL which integrates with a standard encoder-decoder transformer as the program generator. The idea is to generate instructions and to partially evaluate them, exposing both of these as execution trace to program generator. This informs the search procedure, which is a tree search with tunable randomness, to complete the program that reaches the end goal. The system is trained on ground truth programs that successfully solve some task. The evaluation is on different tasks in the same visual domain. 

The experiments compare with other competing approaches which do not carry all the features of EG-NPS. The results show significant gains on 7 task that were evaluated during tests.
weaknesses: * The paper is relatively weak on explaining how the expressiveness of the DSL is a stumbling block to a broader evaluation. The paper briefly mentions in Section 6.4 that the DSL had to expanded to deal with just 1.5% of ARC-AGI-2 benchmarks. It is known that the search space explodes and there is work characterizing the input-output samples needed therein. Please see the work by Wang et al. [a]. It will be useful if the paper talks about the issue of DSL design, state explosion, and expected sample complexity.

* The paper is scoped to a particular benchmark. While this is a completely reasonable way to devise a better program synthesis technique, the resulting ideas are in no way restricted to visual tasks. Clearly the tree-search method, transformer for synthesis, equipped with a DSL can be targeted to other real-world tasks. Did you consider evaluating your proposed methods on any other non-ARC-AGI-2 task? For example, you could take a standard DSL (e.g. FlashFill), architectural instruction set, or any other minimal programming language and try to solve coding tasks. This kind of experiments reduce the risk of ideas being overfit to a benchmark or set of tasks.

* The paper references Lavon et al. (2025). This is execution-guided technique too. I understand that EG-NPS is targeting ARC-AGI-2, but at the technical level both are execution-guided techniques. As such, it would be useful to see a comparison on common benchmarks. To understand the advance presented by EG-NPS, it is useful to run it on Lavon et al.'s evaluated benchmarks.

[a] "SynGuar: Guaranteeing Generalization in Programming by Example", Wang et al., In ESEC/FSE 2021: Proceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering.

---

confidence: 3
contribution: 2
initial_rating: 4
presentation: 3
questions: How would you think of scaling the proposed approach? Suggesting a few directions for future work could improve the paper.
soundness: 3
strengths: The paper is overall well-written: 
- Focus on compositional and OOD generalization.
- Novel tree search algorithm for execution-guided neural program synthesis.
- Diverse empirical setups: include baselines and ablations.
summary: This paper investigates out-of-distribution (OOD) generalization on the ARC-AGI benchmark by comparing execution-guided neural program synthesis (EG-NPS) with test-time fine-tuning (TTFT). The authors introduce a novel EG-NPS algorithm alongside a custom domain-specific language (DSL). Through controlled experiments, EG-NPS significantly outperforms non-execution-guided methods and TTFT on a series of experimental setups. The results demonstrate that execution-guided synthesis enables stronger compositional reasoning and more robust OOD generalization than fine-tuning-based approaches in the ARC-AGI domain.
weaknesses: The paper’s main weaknesses include scale, scope, and generalizability of the experiments:
- Requires ground-truth programs as training data.
- Requires a DSL, and the implemented one is very limiting.
- Limited scale and empirical scope: for instance, experiments on ARC-AGI include only 18 tasks out of the 1000+ available.
- Other fully neural baselines could have been tested against: e.g., [Ouellette, 2024] or [Bonnet & Macfarlane, 2024].

---

confidence: 4
contribution: 2
initial_rating: 6
presentation: 3
questions: * What exactly is meant by “open-world” in this context? ARC-AGI seems quite closed in scope.
* What are the different DSL and training tasks?
* Could the observed advantage of EG-NPS be mostly due to its explicit search and verification loop, which the TTT baselines can’t really do?
soundness: 3
strengths: I liked that the paper carefully controlled their experiments by designing all tasks by hand, making sure test tasks involved new combinations of primitives that were not encountered at training time.

The test-time training experiment is particularly well designed, controlling for different possible factors explaining its success in prior work.

This kind of question is interesting and deserves more investigation, and ARC-AGI might be an interesting domain to conduct such experiments.
summary: The authors propose to study the ability of execution-guided program synthesis approach and transduction approaches with test-time training to generalize to new ARC-AGI-like tasks at test time. Train and test tasks are designed by hand to involve different compositions of the same set of predefined primitives. 

Overall, the paper asks an interesting and timely question about compositional generalization in ARC-like domains and provides a well-controlled experimental setup. The execution-guided synthesis results are solid and the TTFT analysis is carefully done. However, the scope of the comparison is narrow: both methods rely on hand-crafted DSLs and synthetic data, the OOD tasks are simple, and the advantage of EG-NPS may mostly reflect its explicit search and verification loop rather than deeper generalization. The study is informative within its controlled sandbox but limited in how much it says about solving the broader ARC-AGI challenge or about generalization in pretrained LLMs.
weaknesses: **Missing related work:**

The related work section (and intro) miss significant related work:
* CodeIt: Self-Improving Language Models with Prioritized Hindsight Replay: https://arxiv.org/abs/2402.04858v2
* Self-Improving Language Models for Evolutionary Program Synthesis: A Case Study on ARC-AGI: https://arxiv.org/pdf/2507.14172
* Combining Induction and Transduction for Abstract Reasoning: https://arxiv.org/abs/2411.02272

“Execution-guided, neural program synthesis has not yet been attempted”: The second paper above applies a genetic algorithm to solve ARC, with mutation operators conditioned on previous solutions and their execution feedback. In general, any LLM-based GA method (FunSearch, AlphaEvolve, etc.) is “execution-guided”. The authors seem to use a different meaning — more about search within program execution rather than post-execution feedback. Did I get this right? This should be clarified.



**Test-time training and program synthesis are orthogonal**
The third paper above already separates program synthesis (induction) from direct generation (transduction). This axis is orthogonal to test-time training. One can have a program-synthesis model that also learns at test time (as in the last two papers above), or a transductive model without any TTT. So opposing “program synthesis” and “TTT” doesn’t seem to be the key conceptual split here.
In the discussion of Akyürek et al., it says “they generate tasks synthetically … that can overlap with validation data.” I think that’s fine — if a system can imagine validation-like data and improve from it, that’s still generalization. It only becomes a problem if augmentations are designed knowing the validation set.

**Solving ARC-AGI ≠ recombining known primitives**
This paper studies recombination, but ARC-AGI itself doesn’t come with a DSL. True generalization may require inventing new operations at test time, not just reusing old ones. The DSL here can only solve ~18 ARC-AGI-2 tasks, so conclusions about full ARC-AGI generalization are limited. Moreover, the “OOD” tasks (flips, shifts, recolors) cover a narrow subset of ARC reasoning.

**Dependence on hand-crafted DSL and synthetic data**
Both methods depend on a fixed DSL and synthetic training data. The DSL defines what “generalization” means: no new primitives can be invented. The training distribution (types of transformations, grid sizes, augmentations) also determines what counts as OOD. No ablation checks sensitivity to DSL or data design. Code and primitive lists are missing, making reproduction complicated: 
* What are the DSLs with 34 and 45 primitives?
* What are the training tasks?
* What are the training tasks and primitives which were added for the ARC-AGI-2 experiment, and why?

**TTT interpretation**
The claim that TTFT only surfaces pre-existing abilities is more of an interpretation rather than demonstrated. It may simply be that pre-training + TTT together enable generalization. Without knowing the pre-training corpus of course, this can’t be verified.
For the same reason, the study can’t say much about LLM-based program-synthesis methods that rely on large pretrained models (like the ones developed in the two last papers of the above list): these would be hard to train from scratch under a controlled setup.

**Other points**
The claim that humans solve these tasks should be supported by data (e.g. http://arxiv.org/pdf/2409.01374). Can any human solve them, or at least some? I think in ARC-AGI 2 it’s more of “out of a group of N, at least 2 can solve the task”.