Student or educator? Sign up with your school email and get 6 months of Pro free.
CoChat
Sign Up
PreprintCited by 1

The DOI matches its DataCite record.

Towards Efficient Neurally-Guided Program Induction for ARC-AGI

Ouellette, Simon·2024·arXiv
DOI 10.48550/arxiv.2411.17708arXiv 2411.17708
Open this paper in CoChat — free account

Abstract

ARC-AGI is an open-world problem domain in which the ability to generalize out-of-distribution is a crucial quality. Under the program induction paradigm, we present a series of experiments that reveal the efficiency and generalization characteristics of various neurally-guided program induction approaches. The three paradigms we consider are Learning the grid space, Learning the program space, and Learning the transform space. We implement and experiment thoroughly on the first two, and retain the second one for ARC-AGI submission. After identifying the strengths and weaknesses of both of these approaches, we suggest the third as a potential solution, and run preliminary experiments.

Overview

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.2411.17708

Cites

Statistics

Figures

Figure 1 Architecture of VLM
Figure 1 Architecture of VLMCC-BY · From the PDF
Figure 2 Syntax tree for [ lefthalf , righthalf , <New Level> , cellwiseOR , <New Level> , set fg color3 , <End of Sentence> ]
Figure 2 Syntax tree for [ lefthalf , righthalf , <New Level> , cellwiseOR , <New Level> , set fg color3 , <End of Sentence> ]CC-BY · From the PDF
Figure 3 Syntax tree for [ topthird , hcenterthird , bottomthird , <New Level> , <Identity> , cellwiseOR , <New Level> , cellwiseOR , <End of Sentence> ]
Figure 3 Syntax tree for [ topthird , hcenterthird , bottomthird , <New Level> , <Identity> , cellwiseOR , <New Level> , cellwiseOR , <End of Sentence> ]CC-BY · From the PDF
Figure 4 Success rate on the 29-task solvable set from ARCAGI evaluation set
Figure 4 Success rate on the 29-task solvable set from ARCAGI evaluation setCC-BY · From the PDF
Figure 5 Two examples of GridCoder failures. Left: task bc4146bd. Right: task d47aa2ff.
Figure 5 Two examples of GridCoder failures. Left: task bc4146bd. Right: task d47aa2ff.CC-BY · From the PDF
Figure 6 Example of a task solution
Figure 6 Example of a task solutionCC-BY · From the PDF

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

No references could be resolved yet.

Research works printed but not linked: 11

  1. Alford, S. 2021. A Neurosymbolic Approach to Abstrac- tion and Reasoning. Ph.D. thesis, Massachusetts Institute of Technology.
  2. Chen, X.; Liu, C.; and Song, D. 2018. Execution-guided neural program synthesis. In International Conference on Learning Representations.
  3. Chen, X.; Song, D.; and Tian, Y. 2021. Latent execution for neural program synthesis beyond domain-specific lan- guages. Advances in Neural Information Processing Sys- tems, 34: 22196-22208.
  4. Devlin, J.; Uesato, J.; Bhupatiraju, S.; Singh, R.; Mohamed, A.-r.; and Kohli, P. 2017. Robustfill: Neural program learn- ing under noisy i/o. In International conference on machine learning, 990-998.
  5. PMLR.
  6. Ellis, K.; Wong, C.; Nye, M.; Sablé-Meyer, M.; Morales, L.; Hewitt, L.; Cary, L.; Solar-Lezama, A.; and Tenenbaum, J. B. 2021. DreamCoder: Bootstrapping Inductive Pro- gram Synthesis with Wake-Sleep Library Learning. In Pro- ceedings of the 42nd ACM SIGPLAN International Confer- ence on Programming Language Design and Implementa- tion, PLDI 2021, 835-850. New York, NY, USA: Associa- tion for Computing Machinery. ISBN 9781450383912.
  7. Fijalkow, N.; Lagarde, G.; Matricon, T.; Ellis, K.; Ohlmann, P.; and Potta, A. 2021. Scaling Neural Program Synthesis with Distribution-based Search. CoRR, abs/2110.12485. · arXiv
  8. Hocquette, C.; and Cropper, A. 2024. Relational de- composition for program synthesis. arXiv preprint arXiv:2408.12212. · arXiv
  9. Kapur, S.; Jenner, E.; and Russell, S. 2024. Diffusion On Syntax Trees For Program Synthesis. arXiv preprint arXiv:2405.20519. · arXiv
  10. Nye, M.; Pu, Y.; Bowers, M.; Andreas, J.; Tenenbaum, J. B.; and Solar-Lezama, A. 2020. Representing partial programs with blended abstract semantics. arXiv preprint arXiv:2012.12964. · arXiv
  11. Schrittwieser, J.; Antonoglou, I.; Hubert, T.; Simonyan, K.; Sifre, L.; Schmitt, S.; Guez, A.; Lockhart, E.; Hassabis, D.; Graepel, T.; et al. 2020. Mastering atari, go, chess and shogi by planning with a learned model. Nature, 588(7839): 604- 609.

Cited by

Metadata

Authors
Ouellette, S.
Venue
arXiv
Publisher
arXiv
Published
2024
DOI
10.48550/arxiv.2411.17708
arXiv
2411.17708
References
0
Type
Preprint
Licence
creativecommons.org/licenses/by/4.0/legalcode

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.