Communicating Natural Programs to Humans and Machines
Authors: Sam Acquaviva
Yewen Pu
Marta Kryven
Catherine Wong
Theodoros Sechopoulos
Gabrielle Ecanow
Maxwell Nye
Michael Henry Tessler
Joshua B. Tenenbaum
Venue: ICLR 2022 Submitted (2022)
Keywords: program synthesis
communication
cognition

Abstract: The Abstraction and Reasoning Corpus (ARC) is a set of procedural tasks that tests an agent's ability to flexibly solve novel problems. While most ARC tasks are easy for humans, they are challenging for state-of-the-art AI. What makes building intelligent systems that can generalize to novel situations such as ARC difficult?
We posit that the answer might be found by studying the difference of \emph{language}: While humans readily generate and interpret instructions in a general language, computer systems are shackled to a narrow domain-specific language that they can precisely execute.
We present LARC, the \textit{Language-complete ARC}: a collection of natural language descriptions by a group of human participants  who instruct each other on how to solve ARC tasks using language alone, which contains successful instructions for 88\% of the ARC tasks.
We analyze the collected instructions as `natural programs', finding that while they resemble computer programs, they are distinct in two ways: First, they contain a wide range of primitives; Second, they frequently leverage communicative strategies beyond directly executable codes. We demonstrate that these two distinctions prevent current program synthesis techniques from leveraging LARC to its full potential, and give concrete suggestions on how to build the next-generation program synthesizers.

Under review as a conference paper at ICLR 2022
COMMUNICATING NATURAL PROGRAMS TO HUMANS AND MACHINES
Anonymous authors Paper under double-blind review
ABSTRACT
The Abstraction and Reasoning Corpus (ARC) is a set of procedural tasks that tests agent's ability to flexibly solve novel problems. While most ARC tasks are easy for humans, they are challenging for state-of-the-art AL. What makes building intelligent systems that can generalize to novel situations such ARC difficult? We posit that the answer might be found by studying the difference language: While humans readily generate and interpret instructions in general language, computer systems are shackled to a narrow domain-specific language that they can precisely execute. We present LARC, the cenguagge-omplees ARC: a collection of natural language descriptions by group of human participants who instruct each other how solve ARC tasks using language alone, which con- tains successful instructions for 88% of the ARC tasks. We analyze the collected instructions as 'natural programs', finding that while they resemble computer pro- grams, they are distinct in two ways: First, they contain a wide range of primi- tives; Second, they frequently leverage communicative strategies beyond directly executable codes. We demonstrate that these two distinctions prevent current pro- gram synthesis techniques from leveraging LARC to its full potential, and give concrete suggestions on how to build the next-generation program synthesizers.
INTRODUCTION
Humans solve range of procedural tasks such as cooking, tying shoes, and programming Although current AI systems achieve super-human proficiency at certain narrowly specified tasks (Silver et al.] 2017 Lerer al.) 2020), their reasoning domain-specific and fails generalize novel situations Laake et al. 2017). The Abstraction and Reasoning Corpus (ARC) introduced by [Chollet (2019) presents set of procedural tasks constructed expressly to benchmark fundamental capacities asso- ciated with human general intelligence, including abstraction, generalization, object categories, and the capacity to communicate (Chi al., 20144] [Hallww] 1949 Lake et al.) [2017] Lake & Piantadosi]
2020 Bartlett 1932 Tian et al. 22200) Lombrozo| (2006). Specifically, ARC requires one to infer
procedure consistent with small number abstract input-output examples and apply new
input to generate unseen answer, see Figure]
268
?
?
?
?
Figure 1: Four ARC tasks, the goal is to correctly infer the unseen output from the given examples.
How do we build systems that are capable solving general, procedural tasks such as ARC? Tradi- tional approaches of program synthesis (Parisotto al. 2016 Ellis et al. 2019 Solla-L-eaaann al.

---

Under review as a conference paper at ICLR 2022
2006
Devlin et al.] 2017b) and semantic parsing (Artzi & Zettlemoyer 2013 Ye et al.
2020 Wang
et al. 2015; Marzoev et al. 2020; Guu et al. 2017; Kulal et al. 2019) assume the tasks are DSL- closed aor any task, there exists program, written in predefined Domain Specific Language (DSL.) that solves the task. The ARC henchmark is uniquely designed to be DSI.-open - it does not come with predefined DSL capable of solving all the tasks. This is both reasonable most real life tasks, such as cooking and assembling furniture, are DSL-open - and challenging how can one build an intelligent system that can solve tasks from few examples without DSL? To illustrate, what might a DSL that would allow one to program all the ARC tasks in Figure | look like? This question is difficult answer; a recent Kaggle competition found that the best Al systems solve at most 20% of the tasks, while Johnson et al. (2021) found that most humans easily solve over 80%
Given that humans greatly outperform the best AI systems in solving ARC tasks, studying the hu- man's cognitive processes (for instance, which set of concepts do human use to represent these tasks?) can shed light on how to build similarly intelligent systems. As these thought processes are not observable directly, as a window into these latent cognitive processes. Like computer programs, these instructions can be reliably interpreted (by another human) to produce the intended output. Unlike computer programs, which must be stated a specific style, natural programs can be stated in any form such as verbal instructions or input-output examples as long as another human can execute them. In this work, we study particular form of natural programs, that of natural language instructions. We show that analyzing these natural programs with explicit comparisons to computer programs can both shed light on how humans communicate and interpret procedures (Spelke et al. 1992, McCarthy et al., 202T Clark et al. 1983 Clark & Wilkes- Gibbs 1986) and inform how one may build Al systems for challenging, DSL-open domains such as ARC.
study natural programs instructions that humans give to each other,
task 94
taak 23
task 288
task 227
You shoutd non tntetic grid number
You chould now grid with not blue, and
should nee moneor partern photle
You should god repaon inese on the inaide comers of aquare
The oulpul gndd siee is the rumber of colors heigh
outuu god size is sanc input
The ouspur grd
suree input
pattonn
buth wich
The gri saee the same j-11
Buround coch of the gray boxos with blue
Drow a veriical ed line equaree though glven limes this ug grewn equares and let to right blee though aquarea. Do baffow.
pPool hoconing cry agaero with clime arigh
connrr the orgone and move them the
commaporcing to the number of ealers
opponits ouside zeree the squaess tneale botoon lult correr move to oussce top right squa
Intrusse the rosciu fon of the ripul by the
?
?
?
Four LARC tasks, corresponding to those of Figure [ The goal is to produce the correct output given only the language instructions. 88% of the ARC tasks can be communicated this way.
Figure 2:
We present the Language-complete Abstraction and Reasoning Corpus (LARC) of natural lan- guage instructions elicited from two-player communication game, where 88% of the ARC tasks can be successfully communicated. LARC tasks are language-complete: The successful instruc- tions contain all the relevant information, even in absence of the original input-output examples (see Figure 2 This is important in several ways: First, one can use LARC to study how humans use language to communicate abstract procedures, as humans clearly have the capacity to both generate and execute these natural programs; Second, one can directly see what concepts an intelligent system must be aware of (such as colors and numbers); Third, as people readily generate natural programs, studying them will provide insights on building interactive systems.
We perform linguistic analysis on LARC, finding that humans readily leverage algorithmic concepts without being explicitly instructed to do so. These concepts range from domain general ones, such as loops, to domain-specing concepts such flood-fill. However, natural programs in LARC distinct from typical computer programs in two ways: (1) They contain a wide range of concepts, in contrast the few primitives in typical DSL; (2) The majority of effort is spent on providing clarifications and validations, as opposed to stating the procedure verbatim. We apply standard program synthesis algorithms on LARC, finding that while existing approaches can benefit from the additional language annotations, the two aforementioned distinctions pose significant challenges
Humans were evaluated subset of the training tasks; the Kaggle competition used a private test
2

---

Under review as a conference paper at ICLR 2022
task
person
person
person
natural program
computer program
0000
Interproter
instruction
programming
task
O O
task
7D 75
person
natural program
computer program
0000 interpreter
synthesizer
synthesis
Figure 3: Three ways humans and machines communicate with each other: instruction (top-left), programming (top-right), synthesis (bot).
to standard program synthesis approaches. We conclude by providing concrete suggestions on how build the next generation program synthesizers.
COMMUNICATING AND INTERPRETING PROGRAMS
In communicating procedures, a programmer constructs program in a suitable language, which is then executed an interpreter, producing desirable behaviour. For instance, person can instruct another person to carry out certain task (Fig. 3 top-left), or directly program a machine to solve tasks using code (Fig. 3 top-right). Program synthesis takes in an instruction, and reformulates it as executable code, insulating the person from the programming process (Fig. bot).
How do we build machines that are capable solving challenging tasks given in natural way? Typ- ically, one follows a "DSL-first" approach. In the DSL-ffrst approach, one first defines program- ming language and builds a corresponding interpreter, so that skilled programmer may express the tasks as programs. Then, one naturalizes the initial DSL with synthesizer, allowing end-users to describe tasks using language (Artzi Zettlemoyer 2013 Artzi al.) 20144) Ye et al. 2020 Wang et al. 2015 2016, Marzoev et al.] (020)) or by giving examples (Ellis et al. 2019 Solar- Pu et al.) 2020). While this DSL-first workflow has yielded impressive results, the DSL itself is also single point of failure. It is difficult to design DSL with the right scope, that is easy to write programs for the domain, without bloating the language with redundant concepts (Gulwani al. 2015 Bruce et al., 2020; Soto- Valero et al.) 2021). For synthesis systems, one must ensure that the DSL aligns reasonably to human instructions (Liang 2016 Shin et al (02I). while simuitaneously being efficient when used by the synthesizer (Ellis al. 2019 2020). These chal- lenges may explain why ARC, and other DSL-open domains, pose significant challenges in building intelligent systems using the DSL-first approach.
et al. 2006
In this work, we suggest that starting with human instructions (Fig top-left) can yield insights for building systems on challenging. DSL--open domains and highlight deficiencies in firs-first approaches. We define a natural program as instructions constructed by a person that can be inter- preted by another person to produce specific output. This program natural-it can be understood by speakers of the language without a prior consensus-but behaves as program, in that it produces a definitive output, which can be unambiguously checked for correctness. For instance, the origi- nal ARC (Chollet 2019) tasks natural programs: Given program consisting of input-output examples, a fellow human can readily interpret this program to produce an output on a new input, which be checked for correctness. Contrary the DSL-ffrrt approach, by starting with (linguistic) natural programs, one can directly observe the set of concepts and strategies necessary to master a domain (such as ARC), without having to first build interpreter.
language here be understood loosely any medium of communication between people
3

---

Under review as a conference paper at ICLR 2022
Describer
Builder
"Move each colored square covers the closest 2x2 light blue square."
Figure 4: describer instructs builder how to solve an ARC task using natural program
3 LARC: LANGUAGE-COMPIA
ABSTRACTION AND REASONING CORPUS
We present a dataset that augments the original ARC tasks from Chollet (019) with language- complete instructions: they can demonstrably interpreted by other human users to correctly produce the intended outputs without any additional contexts (including the original input-output examples). Thus, LARC tasks (Fig 2) like their counterparts in ARC, meet the definition of natural program while containing only natural language descriptions. To collect this dataset, introduce communication game were human describers produce linguistic instructions for unseen downstream human builders asked to solve the same tasks; and deploy this experiment using novel bandit al- gorithm to efficiently collect verifiable natural programs. The final dataset augments 88% of the original ARC tasks (354/400) with least verifiable natural program description that could be successfully interpreted by another human participant to solve the task. Fig. C-D) shows the distribution of success rates for participants acting as describers and builders over time.
3.1 HUMAN ANNOTATION DETAILS
We recruited 373 subjects via Amazon Mechanical Turk who were paid for 45 minutes of work. Fifty individuals were excluded for failing to complete the task, the final analysis included 323 subjects. The study was approved by our institution's Institutional Review Board, did not collect personally identifiable information, and did not pose risks to participants. Subjects were paid $6.00 and a $0.25 bonus for every successful communication. Subjects averaged 5.5 communications, bringing their expected hourly wage to $9.83. For interface and consent form see Appendix A.2
3.2 TWO-PLAYER PLAYEL COMMUNICATION GAME
For each task, a participant may be assigned one of two roles: a describer or a builder. The describer plays the role of human synthesizer, who reformulates input-output examples (of ARC) to natural language descriptions. The builder plays a role of human interpreter, who must construct the correct output on new input without access to the original examples (Fig The description is structured into three sections to incentivize consistency: (1) what the builder should expect to see in the input, (2) the output grid size, and (3) what the builder should do to create the output (Fig 2) After the description was submitted, we verify the describer's 's own understanding by asking them to build it, and discarding the submission the describer fails. The describer was shown all previous verified descriptions for a task, alleviating challenge of solving the task from scratch. Participants construct the output using actions defined in ARC, such as paint (color, x, y), copy ropy/paste, and floodf 11. All action sequences recorded.
3.3 THE BANDIT ALGORITHM FOR DATA COLLECTION
Collecting valid linguistic natural programs requires significant human efforts: For each task (of varying difficulties), natural programs must first be proposed by a number of describers, and then validated by number builders, where both can make mistakes. Thus, A naive data-collection process that simply collects fixed number of descriptions and builds per task will be expensive. To address this challenge, we formulate the following bandit problem: ARC tasks is different bandit; infinite-am given task, each natural language description (there are infinitely many) a different arm; best-arm identification - once a natural program is proposed, must validate it. We develop novel bandit algorithm (Appendix B to solve this problem, to
bandi- each the 400
4

---

Under review as a conference paper at ICLR 2022
A.
1.0-
Bulld task SLpDISS
0.8-
8.7-
2001 1205 esserroaaii
Prior Describu bakka completed
Comp
Descrioe
Buldd
Figure 5: A. Describer improves verifying their descriptions they describe tasks. Builders do not improve at constructing the correct outputs as they build more tasks (likely due to having no control over the qualities of their given descriptions). C. Rate of deseribers verifying their descriptions (avg 75%). D. The rate of builders constructing the correct output, (avg 50%).
1500
count
1000
500
0
COLOUR NAME
square
grd
NUMBER
color
same
with
and
call
patter NyM
is.are color
line
that
PRONOUR
shape
size
blook
you
should
each
then
top
left.
copy.
right.
make
fill
change
or
background
output
all
different
N-hh
from other comer
row bottom
words Figure 6: Words used successfully built descriptions, sorted by their frequency corpus (total 642 unique words). The words were singularized. Colors names, numbers, and pronouns were grouped together.
our best knowledge, no known algorithm can be directly applied. For each MTurk participant, our bandit algorithm dynamically allocates set of describing and building efforts for their session. As result, the LARC dataset was annotated for $3667, whereas naively collecting 20 annotations per task would cost least $10,800.
4 LINGUISTIC ANALYSIS OF NATURAL PROGRAM PHRASES
How do people actually use language in LARC to produce robustly interpretable descriptions for each task? this section, we describe results from a manual linguistic analysis verified natural program phrases phrases contained in descriptions that resulted in successful build. We analyse the verified phrases under the lens of computer programs, highlighting certain aspects that are shared between computer and natural programs, and other aspects that are distinct. Our analysis codes individual phrases with manual lags corresponding to general concepts from computer programs and concepts from knowledge (Spelke & Kinzler 2007). In total, manually label 532 randomly sampled phrases (22% of the phrase corpus) using 17 conceptual tags (in which multiple tags can be applied to each phrase); Figure 7A. shows a frequency these tags. For details Appendix A.3
4.1 SIMILARITIES OF COMPUTER AND NATURAL PROGRAMS
General Algorithmic Concepts We find LARC contains algorithmic concepts similar to those that can be found in typical programming language (i.e. python, javascript). For instance, tag logic details specific condition (i.e. "the box is blue"), tag references a group of similar objects (i.e. "you should see four red shapes"), and laglloop is similar to while loops ("keep going until ..."). Note that humans readily generate and execute these concepts without being directly instructed do so, suggesting that humans reason about ARC tasks algorithmically.
Domain Specific Concepts Like computer programs written in specific library, find that LARC contains concepts that distinguish it from other domains. We focus on concepts based on core knowledge (Spelke & Kinzler 2007), specifically, the object system defined by the principles
5

---

Under review as a conference paper at ICLR 2022
A.
B.
object_cetecttoo
object, cittectionnn
Viisual_graphaie graphical_transffrm transform
frequency
0.4
object 9000c
logto
mitiion
ama
donfico
C.
D.
phrase
operations
suge
ofnc for alore
ufice
map
Figure 7: A. The frequencies of all tags occurring in human phrases. Each phrase have multiple tags. B. More than half of the phrases described objects, of which, 75% described spatial relations. C. Relative froquencies of code (procedures) against non-code (example, framing, clarification, validation). D. Relative frequencies of core knowledge topics in phrases that referenced objects.
cohesion, persistence, and influence via contact, which the ARC corpus was designed leverage " TThe ARC priors are designed to be as close possible to Core Knowledge priors, fair ground for comparing human intelligence and artificial intelligence (47).". We found that about half of the phrases referenced objects, and three quarters of them described spatial relations of one object to another (Fig BB. Fig shows the relative frequencies of operations performed on objects. While objects prevalent in LARC. most operations objects were of the category aisual-grapice
traaaaacaaa.aaanssforrm transform such as recolouring and creating new objects. In contrast, only 5% of phrases could also be read influence via physical interaction. This suggests that objects behaviours ARC are rooted more in abstract graphical operations, possibly because is difficult represent realistic physical interactions in the input-output format.
4.2 DIFFERENCES OF COMPUTER AND NATURAL PROGRAMS
While natural programs in LARC are algorithmic, certain aspects remain markedly different from computer programs. We outline two (related) ways natural programs differ from computer programs. First, instead of using narrow DSL with few primitives, natural programs use large, diverse set of primitive functions. Second, instead of stating a precise procedure verbatim, natural programs rely on range of additional strategies to ensure that they can be interpreted precisely.
Natural Programs Invoke a Large Number of Concepts Since LARC is language-compler analyzing the words used in LARC serves as a good proxy for the underlying concepts present in the ARC domain. Similar to the finding of Johnson et al.] (2021), we find that humans use wide range of concepts (Fig (6. This testament the general capabilities of the human interpreter: the builders readily execute these concepts, and the describers confidently invoke these concepts to a stranger (the builder). LARC also suggests that, to engage with an interpreter capable of executing wide range of concepts, the task of recalling the right concept at the right time will be nontrivial. While it is sufficient to recall concept by a unique name such as 'block' for a narrow DSL, is evident from LARC that even the same concept will have range of different names such 'square' or 'box' or 'pixel', all of which can be correctly interpreted under the right context.
Natural Programs Communicate Information Beyond Procedures We study the relative fre- quencies of directly executable commands tag procedure, in contrast to "meta information". which can be analogized roughly as: tag. framing comments and setting up which library to use, validatiit checks and assertions, to ensure correct execution, and bag.clarifiiations restating the same procedure in different words. Notably, only about a third of the LARC phrases are procedures, while the framings and validations occur roughly the same frequency (see Fig C). In contrast, 86% of the executables in computer programs are not commented (Huang et al. 2020).
The high frequency of framing tags in LARC suggests that describers carefully establish context to resolve uncertainty over which programmatic concepts may be relevant, anticipating the large num- ber of concepts that the builder may have in mind. We also find that the describer often assumes

---

Under review as a conference paper at ICLR 2022
the directly executable portion of natural program (i.e. tag-procedure) as inherently ambignous, as suggested by frequent use of vug-vaiittioons and fag_clarifications following these procedures. Specifically, validation is meant to actively help the interpreter in choosing correct interpretation among multiple plausible interpretations. Clarification amends the initial ambiguous explanation, with another, also ambiguous explanation, resulting in narrowing the distribution of possible in- terpretations. We posit that better analogy to natural programs are not computer programs, but program synthesis/inference, where intelligent agent actively searches for the right interpretation among many alternatives given the natural program (of any form) provided by the describer.
5 EXECUTING NATURAL PROGRAMS
We evaluate whether DSL-first program synthesis methods (Fig 3 bot) can execute natural programs as well humans do. We consider three kinds of natural programs: (1) Input-output examples from the original ARC corpus (IO); (2) IO in conjunction with successful language instructions in LARC (IO+NI);; And (3) language alone (NI.-only) same as the MTurk builder task.
5.1 PROGRAM SYNTHESIS
In (symbolic) program synthesis (Solar Lezama 2008 Devlin al. 2017b; Guu et al. 2017), the synthesizer takes in a natural program, and reformulates it as code over a DSL, which can be directly executed interpreter. We have manually crafted DSL based loosely the concepts present in the LARC corpus and built its corresponding interpreter (see Appendix A.4).
Generate and Check Using I0 If the given natural program contains I0 examples. the standard symbolic program synthesis approach (Solar-Lezama et al.) 20066] Devlin et al. (017b) follows the generate and check strategy. Let nolprog be natural program, the synthesizer returns programs prog from DSL from the following distribution:
Paynth (prog) natprog) = (errooggnatproo (prog* + IO]
Peen is the generative distribution: given a natural program, it proposes program prog from the DSL. 11 (prog* + IO) is the checker: it validates prog by executing it on the interpreter, ensuring that prog(z) y for all input-output pairs (ar E 1O. The key strength of this approach lies in its generalizability: If a proposed program can be checked against all 10 examples, it is very likely to generalize to an new instance of the same task due the inductive bias of the DSL.
Generation Models Our Pgen (prog) natprog) generates programs in two parts: neural model outputs a tree bigram over the grammar of the DSL (Lari Young 1990). then a dedicated Ocaml enumerator deterministically enumerates programs from PCFG fitted to this bigram distribution in decreasing probability (Ellis et al.] 2020). For simplicity, we report results of unconditioned gen- erators P gee (prog) (i.e. fitted prior) when language absent, and language-conditioned models P Pee (prog) N L) when language is present. This way, we can use the same P (prog) /N L) model for both IO+NL and NL-only tasks in the set, as does not depend on 1Ō. Similar to (Dechter et al. 2013 Catherine et al. 2021), we first bootstrap our generative models with 10 "seed" pro- grams, discovered by enumerating an uniform unigram model. We find more complex neural models using a CNN encoder do not bring significant benefits, and a neural sequence decoder (as in Guu al. 2017)) performs poorly (for details see Appendix A.5
Leveraging Language We a pre-trained model (T5, Raffel et al. (019)) represent language by taking an average of its encoded tokens. To encourage the learning of compositional relation- ships between language and program, we pseudo-annotation. similar recent methods that have leveraged synchronous grammars (Marzoev et al.) 20200) Jia & Liang] 2016) (Shin et al.) [021] Catherine et al. 202I). First, we provide linguistic comments for each primitive function in the pro- gram DSL (c.g. flood_fill (color) with fill with the color). Then, during training, we obtain additional paired language and program examples by substituting primitives of artificial programs with their corresponding comments For more examples of pseudo- annoooa-inttiionn see Appendix A.4
for instance, (1 (1ambda (to_orig na gri d_overlay (remove_col 1 or (grid_to_block x) yell vollow) fal aase)) hecomes place block on imput grid remove color from block yellow
7

---

Under review as a conference paper at ICLR 2022
number of testing tasks solved 1188 total)
training tasks discovered
no-pseudo
pseudo
10 10 + NL
15 / 200
13 / 200
21 200
15-
NL (psoudo)
10
-0
10 NL (pseudo)
testing tasks solved
no-pseudo
pseudo
NL-only I0 10 + NL
1/183
183
18 183
16 183
22 / 183
200
300
time (6)
700
Table Executing different kinds of natural programs (IO Input- output examples from the original ARC corpus, IO+NL IO in con- junction with successful language in- structions in LARC, NL-only same as the MTurk builder task) using program synthesis. Training tasks discovered under distant supervision (top). Testing tasks solved (bottom). Models trained with NI can addi- tionally augment their training with pseudo-annotations consisting of arti- ficial language-progen program pairs.
Figure 8: Number of test tasks solved for the three kinds of natural programs, IO, NL, IO+NL. with and without pseudo annotations, as a func- tion of enumeration time. Of all models sider, IO+NL+pseudo achieves the best (22/183) outcome. There are error bars as the bigram enu- merator is deterministic. It is possible (but not likely) that re-training these models will have effect due to the randomness of sampling pseudo-annotater programs.
Distant Supervision LARC, similar to SCONE (Long et al. 2016), falls under the challenge of distant supervision: each training task only contains the correct output, but not the ground-truth program responsible for generating it. We adopt the iterative approach used in (Dechter et al. 2013 Ellis al., 2220 Catherine et al.) 2021 Guu et al. 2017) to discover suitable programs during the training phase. Specifically, we alternate between (1) searching for solutions by enumerating from bigrams proposed by our current neural model per task, (2) using the discovered programs to fit better bigram distributions that maximizes the marginal likelihood of the discovered programs per task, and (3) using these additional bigrams as targets to train our neural model.
5.2 RESULTS
We split the ARC tasks into 200 training tasks and 200 testing tasks, and additionally filter the testing tasks down to 183 tasks with successful NL communications. We then train the models for wall clock time of 10 hours each using iterative learning. We test on the 183 test tasks by first using the neural model propose bigram per task, then enumerating the bigram for 720 seconds. We keep the top-3 most likely programs that also satisfy the I0 examples if the natural program contains IO. We then check if any of the top 3 programs satisfies test input-output. See Table and Figure S
Quantitative Findings Our best model, IO+NL+psuedo, solves only 22/183 of the training tasks. We believe this model obtains better results than IO+NL (22 vs 16) likely due to the lack of training data in the LARC corpus (only hundreds of NI annotations) whereas with psuedo-annotation one can generate an infinite number of artificial NL-prog pairs, albeit limited to how well each primitive's comment resembles that of the language descriptions in LARC. We note that having the ability to check a proposed program is correct under IO is crucial for the success of current program synthesizers, with no than 1 task solved with NL-only Like the validation phrases in LARC, the ontut- examples in 10 serve as a form validation for the enumerative synthesizer. This corroborate with similar findings in Austin al. (201)
8

---

Under review as a conference paper at ICLR 2022
Qualitative Findings We investigate in what way does language affect synthesis. We compare the bigram model conditioned on language (1O+NL+psuedo) to the unconditional bigram model (IO). Specifically, for each primitive in our DSL, ask how many times more likely is it going to appear in correct programs generated with the language-conditioned bigram vs the unconditioned one? We plot this ratio log scale for all primitives that were used in ground-truth programs, see Figure conditiond generator is more likely generate the correct primitives than the unconditioned generator. We conclude that while language definitely helps current approaches, the overall results are still poor.
Ω We note that for most primitives that are frequently used, the
odddl (log stak))
2-
0-
Sonoon 20000 Jn 00 Too Tra vance bookean
Slack rel 22
02
con 01
cover
air de
(3
10
10 tonce
10 was
pur Teeero
fest maae bn put
19) 1 song Sooun
22
Wo3 10:00
20 m
10 Sewe te SO0
syts
Figure 9: Relative odds of using the correct primitive for a task, condttie-on vs uncondi- tioned generation. Number in parenthesis denotes the total number of times a primitive is used.
Challenges We highlight key challenges from our experience in executing natural programs. Scop- ing: We are never sure if our current DSL can explain all the tasks in DSL-open domain, leading to cycle of continuously adding more primitives and refactoring. Referencing: How might syn- thesizer reliably attend to the relevant concepts from a large number of irrelevant concepts (that are required to operationalize rest of ARC)? Not Paraphrasing: When natural programs are NL-only, our best model solves only / 183 tasks because it, like other NL-to-code approaches, assumes a close, 1-to-1 paraphrasing relationship between language and code, leading it to miss crucial framing and validation statements, which occurs in abundance in natural programs.
Suggestions It is likely that any intelligent system in a general domain will have to operate with large number of concepts. Thus, if we choose DSL as representation of concepts, we need to grapple with the challenge of extending and synthesizing a large DSLss Alternatively, program in- duction (Gaunt et al. 2016 Devlin et al. 2017a) might allow agent to represent concepts without an explicit DSL given the right data. Recent advances in large language models, such as codex, (Chen al. (021 have demonstrated conventional understandings of language and programs. We expect that specific domains, such as LARC, may benefit from adapting conventional understand- ings. Finally, approaches that leverage different communicative strategies in linguistic instructions (Sumers et al. 2020) will be crucial in handling NL-only instances.
CONCLUSION
We propose natural programs instructions that can be interpreted by humans to produce a ver- ifiable output as a pathway to building intelligent systems that can solve general tasks given in a natural way. To this end, we present the Language-complete Abstraction and Reasoning Corpus (LARC). By being simultaneously DSL-open and language-complete, LARC highlights the distinc- tive gap between communication to humans and machines: Where programmers struggle to build program synthesizer, end-users readily communicate the same tasks using words alone. We hope that by studying and curating the LARC dataset multiple communities - such as psychology, cogni- tive science, and machine learning can work together to close this gap.

---

Under review as a conference paper at ICLR 2022
POTENTIAL NEGATIVE IMPACT
The long-term goal of this work is to 'reverse-engineer" how humans think and communicate, in order jointly inform cognitive research how do people solve and learn from structured tasks and computational systems, that can learn and collaborate with humans. While this work takes con- strained steps in these directions, assumes both of these aims important end goals. Any system that seeks to accurately use and interpret human language raises concerns regarding safe deployment for downstream applications, for instance, non-experts operating safety-critical equipment using natural language. Further, Al could exploit ambiguity in human language to write legally-binding agreements that can be read in different ways.
REPRODUCIBILITY STATEMENT
The source code for the models and the datasets are available the following github repository, along with instructions on how to use them: eC-A3EE
4oppe. science/ r/
The bandit web code that collects human responses, and the LARC dataset itself, given in the suppliment ZIP file.
REFERENCES
Yoav Artzi and Luke Zettlemoyer. Weakly supervised learning of semantic parsers for mapping instructions to actions. Transactions of the Association for Computational Linguistics, 1:49-62, 2013.
Yoav Artzi, Dipanjan Das, and Slav Petrov. Learning compact lexicons for ceg semantic parsing. 2014.
Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry Quoc Le, al. Program synthesis with large language models. arXiv preprint arXi::2108.077 2021.
Frederic Charles Bartlett. Remembering: A study in experimental and social psychology. Cambridge University Press, 1932.
Bobby R Bruce, Tianyi Zhang, Jaspreet Arora, Guoqing Harry Xu, and Miryung Kim. Jshrink: in-depth investigation into debloating modern java applications. In Proceedings of the 28th ACM Joint Meeting European Software Engineering Conference and Symposium the Foundations of Software Engineering, pp. 135-146, 2020.
Wong Catherine, Levin Ellis, Jacob Andreas, and Joshua Tenenbaum. Leveraging natural language for program search and abstraction learning. Thirty-eighth International Conference on Machine Learning, 2021.
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde, Jared Kaplan, Harri Ed- wards, Yura Burda, Nicholas Joseph, Greg Brockman, et al. Evaluating large language models trained on code. arXiv preprint arXiv:2107.03374 2021.
Michelene TH Chi, Robert Glaser, and Marshall Farr. The nature of expertise. Psychology Press, 2014.
François Chollet. On the measure of intelligence. arXiv preprint arXiv:1911.01547, 2019.
Herbert H Clark and Deanna Wilkes-Gibbs. Referring collaborative process. Cognition, 22(1): 1-39, 1986.
Herbert H Clark, Robert Schreuder, and Samuel Buttrick. Common ground at the understanding of demonstrative reference. Journal of verbal learning and verbal behavior, 22(2):245-25) -588, 1983.
Eyal Dechter, Jon Malmaud, Ryan P Adams, and Joshua B Tenenbaum. Bootstrap learning via mod- ular concept discovery. In Twenty- Third International Joint Conference on Artificial Intelligence, 2013.
10

---

Under review as a conference paper at ICLR 2022
Jacob Devlin, Rudy R Bunel, Rishabh Singh, Matthew Hausknecht, and Pushmeet Kohli. Neural program meta-induction. In NIPS, 2017a.
Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli. Robustfill: Neural program learning under noisy i/o. ICML, 201
Kevin Ellis, Maxwell Nye, Yewen Pu, Felix Sosa, Josh Tenenbaum, and Armando Solar-Lezama. Write, execute, assess: Program synthesis with a repl. In Advances in Neural Information Pro- cessing Systems, pp. 9165-9174, 2019.
Kevin Ellis, Catherine Wong, Maxwell Nye, Mathias Sable-Meyer, Luc Cary, Lucas Morales, Luke Hewitt, Armando Solar-Lezama, and Joshua B Tenenbaum. Dreamcoder: Growing gen- eralizable, interpretable knowledge with wake-sleep bayesian program learning, arXiv preprint 0881:20006.08881, 2020.
Alexander I. Gaunt, Marc Brockschmidt, Rishabh Singh, Nate Kushman, Pushmeet Kohli, Jonathan Taylor, and Daniel Tarlow. Terpret: A probabilistic programming language for program induction. arXiv preprint arXiv:1608.044:
2016.
Sumit Gulwani, José HemándezzOrallle Emanuel Kitzelmann, Stephen Muggleton, Ute Schmid, and Benjamin Zorn. Inductive programming meets the real world. Communications of the ACM, 58(11):90-99) 2015.
Kelvin Guu, Panupong Pasupat, Evan Zheran Liu, and Percy Liang. From language pro- grams: Bridging reinforcement learning and maximum marginal likelihood. arXiv preprint 17X1v:1704.07926. 2017.
Harry F Harlow. The formation of learning sets. Psychological review, 56(1):51, 1949.
Yuan Huang, Nan Jia, Junhuai Shu, Xinyu Hu, Xiangping Chen, and Qiang Zhou. Does your code need comment? Software: Practice and Experience, 50(3):227-245 2020.
Robin Jia and Percy Liang. 160::06006.0662,, 2016.
Data recombination for neural semantic parsing. arXiv preprint
Aysja Johnson, Wai Keen Vong, Brenden Lake, and Todd M Gureckis. Fast and flexible: Human program induction in abstract reasoning tasks. arXiv preprinl arXiv:2103.05880 2021.
Sumith Kulal, Panupong Pasupat, Kartik Chandra, Mina Lee, Oded Padon, Alex Aiken, and Percy Liang. Spoc: Search-based pseudocode to code. arXiv preprint arXiv: 1906:/9906.4000 2019.
Brenden M Lake and Steven T Piantadosi. People infer recursive visual concepts from just a few examples. Computational Brain & Behavior, 3(1):54-65, 2020.
Brenden M Lake, Tomer D Ullman, Joshua Tenenbaum, and Samuel Gershman. Building machines that learn and think like people. Behavioral and brain sciences, 40, 2017.
Karim Lari and Steve J Young. The estimation of stochastic context-free grammars using the inside- outside algorithm. Computer speech & language, 4(1):35-56, 1990.
Adam Lerer, Hengyuan Hu, Jakob Foerster, and Noam Brown. Improving policies via search in cooperative partially observable games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 7187-7194, 2020.
Percy Liang. Learning executable semantic parsers for natural language understanding. Communi- cations of the ACM, 5969) 2016.
Tania Lombrozo. The structure and function explanations. Trends in cognitive sciences, 10(10): 464-470, 2006.
Reginald Long, Panupong Pasupat, and Percy Liang. Simpler context-dependent logical forms via model projections. arXiv preprint 1:Xiv:/606.05:.. 2016.

---

Under review as a conference paper at ICLR 2022
Alana Marzoev, Samuel Madden, M Frans Kaashoek, Michael Cafarella, and Jacob Andreas. Un- natural language processing: Bridging the gap between synthetic and natural language data. arXiv preprint arXiv:2004. 2020.
W. McCarthy, R.D. Hawkins, C. Holdaway, H. Wang, and J Fan. Learning communicate about shared procedural abstractions. In Proceedings of the 43rd Annual Conference of the Cognitive Science Society, 2021.
Emilio Parisotto, Abdel-rahman Mohamed, Rishabh Singh, Lihong Li, Dengyong Zhou, and Push- meet Kohli. Neuro-symbolic program synthesis. arXiv preprint arXiv: 1.000855, 2016.
Yewen Pu, Kevin Ellis, Marta Kryven, Josh Tenenbaum, and Armando Solar-Lezama Program synthesis with pragmatic communication. Advances in Neural Information Processing Systems, 33, 2020.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. arXiv preprint arXiv: 10683, 2019.
Richard Shin, Christopher H Lin, Sam Thomson, Charles Chen, Subhro Roy, Emmanouil Antonios Platanios, Adam Pauls, Dan Klein, Jason Fisner, and Benjamin Van Durme. Constrained language models yield few-shot semantic parsers. arXiv preprint arXiv:2104..m 04.08768, 2021.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. Mastering chess and shogi by self-play with a general reinforcement learning algorithm. arXiv preprint arXiv: arXiv:1712.018155 2017.
Armando Solar Lezama. Program Synthesis By Sketching. PhD thesis, 2008
Armando Solar-Lezama, Liviu Tancau, Rastislav Bodik, Sanjit Seshia, and Vijay Saraswat. Combi- natorial sketching for finite programs. In ACM Sigplan Notices, volume 41, pp. 404-415. ACM, 2006.
César Valero, Nicolas Harrand, Martin Monperrus, and Benoit Baudry, comprehensive study of bloated dependencies in the maven ecosystem. Empirical Software Engineering, 26(3):1-44, 2021.
Elizabeth S. Spelke and Katherine D. Kinzler. Core knowledge. 89-96, 2007.
Developmental Science, 10(1):
Elizabeth Spelke, Karen Breinlinger. Janet Macomber, and Kristen Jacobson. Origins of knowl- edge. Psychological review, (9(4):60, 1992.
Theodore R Sumers, Mark K Ho, Robert D Hawkins, Karthik Narasimhan, and Thomas L Griffiths. Learning rewards from linguistic feedback. arXiv preprint urXiv:2009. 14715, 2020.
Lucas Tian, Kevin Ellis, Marta Kryven, and Josh Tenenbaum. Learning abstract structure for draw- ing by efficient motor program induction. Advances in Neural Information Processing Systems, 33, 2020.
Sida Wang, Percy Liang, and Christopher D Manning. Learning language games through interac- tion. arXiv preprini arXiv:1606. 160o:0200024477 2016.
Yizao Wang, Jean- Yves Audibert, and Rémi Munos. Infinitely many-armed bandits. In Advances in Neural Information Processing Systems, 2008.
Yushi Wang, Jonathan Berant, and Percy Liang. Building semantic parser overnight. In Proceed- ings of the 53dd Annual Meeting of the Association for Computational Linguisties and the 7th International Joint Conference Natural Language Processing (Volume 1: Long Papers), pp- 1332-1342, 2015.
Xi Ye, Qiaochu Chen, Isil Dillig, and Greg Durrett. Optimal neural program synthesis from multi- modal specifications. arXiv preprint arXiv:2010.01668. 2020.
12

---

Under review as a conference paper at ICLR 2022
A APPENDIX
The appendix serves as complimentary document to the paper detailing the data collection process, analysis, and program synthesis. It should be used in conjunction with the following:
1. the LARC dataset and its annotation workflow, and bandit algorithm can be found in the supplementary zip file LARC.
2. program synthesis using language codes is at this URL:
htttp:://aonymmuss 4oper. scis nociencerr// r/ r/ce A3EE
A.1 THE LARC EXPLORER GUI
We encourage the reader to explore the dataset first-hand using the explorer GUI (Figure 10
1. point the LARC root directory
2. run 'python3 http - server
3. open 1localhost:8000eexplloo in chrome browser
TASK 156
DESCRIPTION
DESCRIBER ATTEMPTS
should enalier
The
gld gray chopee
DESCRIPTON2
BUILDS (2)
BUILDER
CC
ATTEMPT
ATTEMPT
ATTEMPT
EDIT
ACTION SEQUENCE GRAPH
z wdge oewoens adins modyy Regil Thicarr
bo @ipare ron Grmic subccged @
Figure 10: The explore interface for task 1.56 (top). action sequence graph of builder (bot)
13

---

Under review as a conference paper at ICLR 2022
A.2 CONSENT FORM AND ANNOTATION WORKELOW
Consent Form In this study, you will interpret descriptions of an abstract pattern that you observe in grids. By answering the following questions, you are participating in study performed by cognitive scientists in [author institution]. If you have questions about this research, please contact [authrr] [author email]. Your participation in this research is voluntary. You may decline to answer any or all of the following questions. You may decline further participation, at any time, without adverse consequences. Your anonymity is assured; the researchers who have requested your participation will not receive any personal identifying information about you. By clicking 'I AGREE' you indicate your consent to participate in this study.
Annotation Workflow Then, the user given tutorials about communicating ARC tasks, and dynamically assigned a sequence of describe and/or build tasks until they have completed 45 minutes of work. Figure 11 shows the build and describe interface. For full workflow MARCcoollectio
Objective:
Create conect sutput based on the descrition and Inpel grs.
Description
Input
Output
The surgur sow the sarea argert
To make te outout you have unround each the grey
boors will Biu boider
Ducc
Objective:
Usirg the pavitus deuciptio refertice, dasc the commer patami suu grds
Input-Output Pairs
Old Descriptions
Description
What should
grant dersiw
the trpit, you should Slick rurber grop feem
The outpen gold vice the suno koout
To carpet you havenss aummune
grey
surper
nut of people ou coceeda aolvees tock dess satin.
25 malo
Figure 11: A. The builder interface. B. The describer interface.
14

---

Under review as a conference paper at ICLR 2022
A.3 LARC LINGUISTIC ANALYSIS TAGGING SCHEME
The tagged phrases can be found at atLaac//attaaettaattatea....pppa
The phrases codified by expert coders using set of 17 binary tags. For each tag, phrase either be a positive instance (+) or a negative instance (-) The following table details the tags and coding scheme used:
Tag
Description
Examples
Directly commands the builder to delete
(+) Fill each enclosed hole with yellow
Procedure
do something; If you it, the program will fail to execute.
(-) look at the color that form the design in the input.
metaphor can be an analogy or reference to human common sense knowledge e.g. spiral.
(+) A random green pattern
Metaphor
(+) A pattern like a long A
(+) Then, copy and paste each colored square in the input grid 4 times once in each "quadrant"
A phrase made following previ- ous statement that attempts to clar- ify misinterpretations.
(+) (or 5 rows or whatever the number of before it repeats).
Clarification
(+) Where there's 's dark blue square, put
orange squares directly above and below (4 total).
(+) The opposite is also true (for example if it light blue, change to dark red).
Example
Gives concrete instance.
(+) Where there's dark blue square, put orange squares directly above and below (4 total).
Makes comment about collec- tion of objects sharing some com- property.
Array
(+) Leave the magenta and light blue
squares they are; do not add anything
them if they are present.
(+) You should end up with all blue boxes touching each other
After the builder executes proce- dure, check if they got the right an- swer (i.e. asserts, test-cases, verifi- cation, or error handling).
Validation
(+) Fill in all of the black boxes com-
plete the pattern until there are no more black boxes.
(+) Continue coloring green until you reach the center of the grid.
Includes a looping procedure, such as the use of while, for, until, for each, or repeat.
Loop
(+) Reduce the grid size that one square
available for each group.
(+) start the upper right
Talks about the process duration of some operations.
Start_Stop
(+) the red shape needs to move until it is
touching the blue cube
(+) If they do not match, make the output
Conditional
Of the form if X then Y.
square green.
(+) The same size the input (+) You will not use dark blue squares at all (-) A 4x4
Includes first-order logic, such as same, and, or, or not.
Logic
pattern
Sets up the problem by offering particular point of view, defining some objects to be referred to later.
(+) four colored area.
Framing
(+) or squares filled with the same color black background.
marked and respectively the
15

---

Under review as a conference paper at ICLR 2022
Tag
Description
Examples
Any reference to a relative position in space some other component. Positive examples include: un- der, reaches, touches, angle, outer, downward, parallel, near, after, in between, central, etc.
Spacial Re- lation
(+) The red shape next to the blue shape (+) Put yellow inside the green
Physical
Any reference to an imaginary force.
(+) The red object falls
Interaction
Blue slides the left towards red
Influence via contact, i.c. any spe- cialized version physical inter- action that involves at least two objects and some rype of contact causality.
(+) Move X until contact with Y
Contact
(+) Set touching Y and turn it the color
Transform
of Y
Red moves left one square
Any reference to a affine transfor- mation over an object, such as rota- tion, translation, etc.
Affine
(+) Rotate 90 degrees
Transform
(+) Extend the square into line
Any other visual or graphical modi- fication other than geometric one, such as coloring, flood-fill, or draw- ing shape.
Visual-
(+) Make it gray
Graphical
(+) Draw a line
Transform
(+) The red shape
Object De- tection
The localization of a cohesive, bounded object.
(+) Move the left
(+) The pattern
These tags can also be grouped hierarchically into the following categories:
Programmatic:
procedure, array, validation, loop, start stop, conditional, logic
Human/Mcchanisms for Domain General Communication: metaphor, clarification, example, framing
Objects and Object Manipulation: opacial_relation ometric transsform risual_graphicat .ransssormm object_detection
contact_transfone ge-
16

---

Under review as a conference paper at ICLR 2022
A.4 THE ATTEMPTED LARC DSL
As LARC is DSL-open, we must first consiruct a suitable DSL before applying (symbolic) program synthesis approaches. Here also list its corresponding pseudo-annotation comments. We hand-designed DSL a for the LARC domain consisting of 103 primitives (implemented as set polymorphically typed X-calculus expressions) intended to be broadly and basically applicable to all tasks on the domain - the DSL operates over grids of pixels, and contains simple functions designed repeatedly perform image transformations over pixel grids to produce an output grid. The complete DSL is available at the released code repository; below we provide representative example functions and the accompanying natural language glosses of their behavior used in the psendoannotations generative procedure; as well as sampled program expressions and their generated pseudoannotations.
attempt at constructing such a DSL. For each DSL primitives,
Example DSL Functions and Natural Language Gloss Function Annotations
DSL Function
Natural Language Gloss
blocks_to originall_grid blocks to min grid
place blocks onto input grid'
get the smallest grid containing the blocks'
first of sorted object list
get the block with the smallest or greatest value of
saggleton_blcce
mlock_blocks
blocks
'remove the blocks that have'
map_blocks
'orr every block'
filter template block
'find the main block'
reflect
"reflect'
move
"move'
center_block.cg www.bblooooooooecc tile
'move block to tile"
duplicate
'duplicate'
grow
'nlargee'
fill.color fill snakewise
color the block' "color the block in snake pattern with'
poplace_color replace color
'replace colors' 'remove the black background'
banokeeblacckb
remove_color
'remove color from block'
box_block
get smallest rectangle containing block'
wrap block
'surround block with'
blockr.bockk
block tiles
"only keep tiles that"
map_block_tiles
for each tile of block'
.miingrrid
"llace block input grid'
gettheight
get height of block'
get width
get width of block'
get original grid height
get the height of the input grid'
get_original grid griid width
get the width of the input grid"
get_num_tiik _iles
"coutt the number of tiles of the block"
nth prhimhrrrayaaaam ccllor
"ind the nth most common color'
is mymetricaaal is rectaane has min tiles touches any boundary
is the block symmetrical'
'is the block a rectangle"
'does the block have at least n tiles'
'does the block touch any edge of the grid'
touches_boundar
'does the block touch the edge'
has-color
'does the block have color'
is_tile
"is the block tile'
block to tile
get block center
'ett the central tile of the block
map_for directions
'in every direction'
find same color blocks
find blocks based on shared color'
17

---

Under review as a conference paper at ICLR 2022
blockboccs.b..oo black_
'find blocks based if they separated by the black background'
find blocks by color
'find blocks based if they separated by the given color background"
braecks_b__infereee b
'find blocks based if they separated by the background"
grid_to blockk
split-grid
'split the grid in half"
find find_tiles_by. baddtiiee.b..black.
'find the tiles based if they are separated by the
black background'
interior
iss the tile in the interior of block'
seexterior
'is the tile in the exterior of a block'
fil..touches.bloc
'does the tile touch the block'
tile overlaps block
'does the tile overlap the block'
tile.to block
extend_ towards .until
extend tile towards direction until the condition is met'
eowands _until
"extend tile towards direction until it touches the edge'
extend_untin towchittttcchhe_looo
"extend tile towards a direction until it touches the edge'
move towards until
"move tile towards direction until condition is met'
move_towards. wnntarrdsunnnl....m.. Leng
"move tile towards direction until it touches edge' 'move tile towards direction until it touches block' 'move tile towards direction until overlaps block'
move_until toaetiilttchhs____t block
move.umtil.overllas.
get tile color
get the color the tile'
tiles to blocks
filter_tiles
"only keep tiles that'
map_tiles
'or every tile' 'overlap the split blocks based on colors'
overlap blocks
splitblocks. tt...o..... blocks
color logical
'take logical operation on colors using them as true and false'
land
'logical operator and' 'logical operator or'
lor Ixor negate boolcan
'logical operator xor' 'not'
map.tbe tbs
'or every block in template block scene'
make_co colooppii
"make pair of colors'
north
'top"
south
'bottom"
'left'
east
'right'
north east
ttop right'
north west
top left'
south_east
'bottom right'
south_west
'bottom left'
'0"
1
1''
2
2
3
5
'5'
6
'6'
7
'7'
8
'8
''
18

---

Under review as a conference paper at ICLR 2022
true
false
invisible
'invisible'
black
"black'
blue
'blue'
red
'red'
green
green"
yellow
yellow
grey
grey'
pink
pink'
orange
orange'
teal
'teal'
maroon
'maroon'
Example Sampled Programs and Pseudoannotations
Sampled Program
Natural Language Pseudoannotaaiin
(lambda (to original grid overlay (remove color (grid to block $0) yellow) false)) (lambda
'place block on input grid remove color from block yellow'
toxtenn_towards.uniii
'extend tile towards a direction until it touches the edge bottom right'
bllock-to_tike (grid_to_block $0)) south_eas true))
(lambda (blocks to mon grid (tiles to blocks (find tiles by black S0)) true true))
'get the smallest grid containing the blocks find the tiles based on if they are separated by the black background'
Compared to SCONE Long et al. 2016 supervision.
LARC poses a significantly greater challenge for distant
domain
dsl size
language kind
number of instances
LARC SCONE: ALCHEMY
DSL-
103
freeform text
354
DSL-closed
24
step-by-step instruction
4560
SCONE: TANGRAMS
DSL-closed
step-by-step instruction
4989
SCONE: SCENE
DSL-closed
33
step-by-step instruction
4402
Table 3: Comparison of LARC to SCONE
19

---

Under review as a conference paper at ICLR 2022
A.5 SUPPLEMENT TO SEC. 5 EXECUTING NATURAL PROGRAMS
Enumeration details For task, we enumerate from the bi-gram distribution (proposed by the neural model) a high-powered computing cluster for 720s; and with 24 CPUs in parallel.
Neural Sequence Decoder We experiment with using neural sequential decoder which can theoretically capture longer range dependencies. Specifically, we use GRU decode program one token at time. In addition mask the generated tokens to ensure the generated partial programs are syntactically correct (using the type system). We train using the distant super- vision approach exactly (Guu al. 2017), with an epsilon raallon-rddd beam search balance exploiting the current policy and exploring low probability programs under the policy and take gra- dient steps discovered programs using the meritocratic parameter update rule. We train using distant supervision on 24 CPUs for 10 hours of wall-clock time on the train split of 200 tasks. As we
Other Models:
Neural Sequence Decoder
training tasks discovered testing tasks solved 2/ 183
10 10 + NL NL
6 200
200
0/ 183
0/ 183
can see, the sequence decoder cannot even recover the 10 seed programs during training, and per- forms poorly on the testing tasks compared to bigram model. Consequently, we did not attempt pseudo-annotation on the sequence model.
CNN encoding of IO We take our best model (IO+NL+pseuddo) and additionally condition the neural model with CNN encoder, rather than leaving it un-conditioned. We find that this model can discover 2 more programs during training and achieves identical outcome to the simpler model without CNN.
Other Models:
train
test
IO+NLtpscudo 1O+NL+pseudo+CNN
21/200
22/183
23/200
22/183
In general, we find that the standard solution to distant supervision, although effective in SCONE, only discovers few programs in LARC. This finding is unsurprising for the following reasons:
1. LARC is DSL-open whereas SCONE is not, thus, there is no guarantee that we will dis- cover LARC programs even if we enumerate an infinite number of programs.
2. In SCONE, every computer program is sequence of 5 actions that transform the state of the world. A natural language utterance is collected for each of these actions. The language annotation (natural program) is the sequences of these utterances. As a result there a tight alignment from utterance to actions (tokens in the DSL).
3. SCONE domains have an order of magnitude more tasks to learn from (through distant supervision).
We conclude that collecting simpler, more fine-grained tasks in SCONE would confer significant benefits to solving LARC, notwithstanding the DSL-open challenge.
20

---

Under review as a conference paper at ICLR 2022
A.6 SYNTHESIS WITH CODEX
We conduct a exploratory study where we took the tasks solved by the IO+NL specification in addition to the IO-only specification, and whether github's co-pilot auto-complete tool (built on codex) can correctly infer the right program using language as prompt. The prompt is constructed by giving a few hundred of pseudo-annotation program pairs as context (see A.4), along with the NL description from LARC, and asking co-pilot to give the top- 10 suggestions on how this description might be translated into program in our DSL.
of syntacticall varid out of 10 somples
tooks
NL
coreect program
example coplott program
correct
look both left and right
06201667 Json
right parts Sxc,, For each square that is cofored on both the left and right parts. color the curput grid with rod on the now 3x3.
inpul "Yow will notion that left and (bembada (overlap spll Mlodaa (woill gii 50 fatso) (ammidd (lambda (color_ Jog call 5o 51 red landf(0))
(grid Jo blockokk 60) (i, symmeriiiial (grid to Mook $0) trae)))
(aarloda (to original and overlay
2
da 04148544jo json
oopy the pattern that a diffeiont color
(remove black (grid block 501) (nth, primary colorr (grid Jo b..boook 90) 13)
(ammbda
(remove
(orid Mtdd___o__bbooo block 5oj (heas color (gric to block
(bamroda (lo original uni overlay
(ebaa))
siyy pirejo
Bamrbda
ari
outpul www.ooooooeoooooooo soreed_ let (find onlor biocka 50 heise filse)
lambda (eapy
18ba joon
only biggest into the
grd
(fivd, Jame, rolos blocks 50 tru felne)
(frst_of object, lett
(aariida appl_num_lle 50JI tatoo) false))
(lambda $0) truell)
(to miii
jaboc8ddjoon
change ge grid the
(find,
90
(tambda (to www.orggnnaa.oooo.o gord, ooveray color (grid block $0) book (rue))
color
(umbbda num, llee 501)
(negate_ boolcan talsel) taisa))
5880u5icajon
mujurily the then color
determine
outbut grid.
(merge,
nambda to hou_orggnallcoooo _otooooooooo oovoovy coolr
(grid tn hinok 50) Inaa))
color
(bambodd original oveday (fedd majority 90) (lambdd (Jambdda $0100)
cruata light bluw border around grid.
So, any squares are touthing light border
(lambda Bo. orighnal Lord, overley (ambda
(ammbd original anid overly (map, Imap_Noock__ ignd, bluck (grid, block lggt_bkolllll
the semsiin black
lgnd talsoil)
50)
the
72ca073djoon oopy one the figures flgure.
(Thbrr blocks Jame, color blicka
(aambid (to, min grid (sigletonn block
faleny (bambeta fu_eymeeticall faBie))
Bambba original overlay (copy grid
(lambda (lambda thas, color (grid block tiack)000)
Figure 12: synthesizing programs using copilot
As we can see, while co-pilot suggests programs that look similar correct one stylistically, most tend to be syntactically invalid. Copilot often invents primitives that do not even exist in our DSL, such as "copy srpp__shape___ _t_tt_oouu ootput-gridh
None of the syntactically correct programs can produce the intended output either. This is to be expected, as we use DSL that has not been seen before in any existing corpus of code, and we should not expect codex to perform well naively. We believe a promising line of work lies in taking general model (such as codex) and specializing it to specific context (LARC) will be exciting future research.
21

---

Under review as a conference paper at ICLR 2022
B APPENDIX: MULTI-BANDIE INFINITE-ARM, BEST-ARM IDENTIFICATION
Imagine there are N different mAgIcAI casinos, where each has an infinite number of slot machines (arms). While each individual arm has its own probability p (Bernoulli) of generating an outcome of either 0 or 1, the arms are related to each other depending on the casinos they belong to. Some casinos are easier than others, in a sense that for some, easier to find "good" arm whereas for others, most arms will have a small chance of success, Moreover, each casino has one (or multiple) best arm, whose probability generating 1 is p.. Your job is to identify the best arm within each casino. This is in essence the multi-bandit, infinite-arm, best-arm identification problem.
You can take observations in the casinos, where each observation involves selecting a casino, and trying one of its arms (either one of the arms you already tried, or trying new one out of its infinite possibilities), observing an outcome of either or 1. We seek an online algorithm that, given any observation budget, propose set of N arms. Let pl ..... PN denote the ground-truth Bernoulli parameters of the proposed arms. We seek to minimize the following regret:
L -(et - p.)
Where each term pr Pt the "gap" between the proposed arm and the best arm in a given casino.
B.1 APPLICATION TO LARC
Our goal is to collect working natural program for each of the 400 ARC tasks. Natural programs are difficult to collect, because it involves both: 1) obtaining a natural program from a describer and 2) validating this natural program by having builder build from it. Thus, rather than exhaustively studying each task to estimate its difficulty, we are content with just getting a "good enough" natural program for each task. In another words, given a certain annotation budget, we want find single good natural program for each of the 400 tasks.
If take the 400 tasks as 400 casinos, then each casino would have an intrinsic difficulty, which corresponds to how easy it is to communicate a particular task. Within each task, there are an infinitely many possible natural programs (i.e. all natural language strings), which correspond the infinite-arm aspect. For each task, we are interested in finding as good of a description as we can, which correspond the best-arm identification aspect.
Specifically, we are seeking an online algorithm that at any budget can propose a set of natural programs, and this set proposed programs should improve with added budget (budget here is synonymous with total participants' time). To use the bandit algorithm in conjunction with the annotation process, we divide the 45 minutes pation, where each unit can be assigned one of two jobs: 1) The participant description to an ARC task, then immediately build from (in the form of describer verification) or 2) The participant be given existing description of task, and build from it to assess if it is a good description. See Figure [3 We estimate how many minutes would this particular unit take, and dynamically allocate additional units until the full 45 minutes are exhausted.
participant' 's time into several "units" of partici-
either give new
participant
unit
tasks
T1
T2
T3
desc
Figure 13: How "unit" of participant's time can be utilized
22

---

Under review as a conference paper at ICLR 2022
B.2 REINFORCEMENT LEARNING FORMULATION
A great way to formalize a bandit problem is casting it as an instance of a Markov Decision Process:
A state consists of all the observations (the outcomes) on all the thus far. Let there be N bandits/casinos, then the observation a collection of all casinos' outcomes .....Cr CN where for each casino C₁ we have observation for its K arms that we already sampled: cf ..... Each arm's observation, ef is simply tuple (A, B) where denotes the number of Is observed from arm of and B denotes the number of Os. Thus, the space of observation is O(N x K x (A+ + B)). See Figure 14
There are two kinds of actions the arm-selection action, and the selection consists of a tuple (i.j) where selects a casino, and selects from which of the arms within that casino sample an additional observation. We will use 1.... K to denote sampling from the K arms within a particular bandit i, and use j = 0 to denote sampling a new arm from bandit i. When the interaction budget is exhausted, the agent must make best-arm-pree corm-roposal action, in which the agent picks one sampled arm from each casino to be calculated in the regret. For arm proposal,
action. Arm
simple heuristic that selects the arm with the highest estimated mean using beta distribution with (1,1) prior. For the remainder of this section, action will refer exclusively to arm-selection.
Transition modifies the state to include the new observation. See Figure 14
Reward the sum of the Bernoulli parameters for the set of proposed arms. pl + ... + pN-
original state:
[(2,0), (1,1), (0,1)] # casinol, has 3 arms, 3rd arm has success and 1 fail [(1,1), (1,0)] # casino2, has 2 arms, first arm has 1 success and fail casino3, has arms so-far taking the 2 following actions:
[]
action (3,0) observed a 0, and action (2,1) observed a 1
resulting state after those actions:
[(2,0), (1,1), (0,1)] # casinol, has 3 arms, 3rd arm has success and fail # casino2, has 2 arms, first arm has 2 success and 1 fail # casino3, has 1 arm, first arm has e success and 1 fail
[(2,1), (1,0)]
[(0,1)]
Figure 14: an example transition where there are 3 casinos
B.3 A HEURISTICALLY DEFINED AGENT
To the best of our knowledge, there no bandit algorithm that address the specific bandit problem are solving. However Wang et al. (2008) solves the infinitely many armed bandit problem for a single bandit, where they explicitly model the difficulty of the underlying bandit. We take their algorithm as inspiration. Note that Wang et (2008) prescribe solution to the regret-minimizatton problem, which is not exactly best-arm- mest-arm-identifee identificatin. However, in the limit, the two are equivalent as minimizing regret is equivalent to finding the optimal arm. We will first state the result of Wang et al. (2008), which applies to the case of single casino/bandit, then extend it to the case of multi- bandit.
arm selection Suppose know that want to generate action in casino i. Wang et al. (2008) proposed the following rule for selecting which arm to interact with. Let 3 be the difficulty parameter of the task, defined as: P(p" Ps < é) = ()) Which is say, if you were to sample
23

---

Under review as a conference paper at ICLR 2022
arm with ground truth parameter Pj. the probability that this arm lies within of the optimal arm, is approximately e². For instance, if B = 1, the task is very difficult as el is tiny number, meaning it is almost impossible for you to sample an arm Pj that is e close to optimum. Conversely, [ 0, the task very simple, as e 1, so any arm you sample will be optimal.
Wang et al. (2008) states that, if you let M be the total number of observations on a bandit, and K be the total number of arms currently sampled, if K S M then you should sample a new arm. Otherwise, you should perform the standard UCB algorithm on the set of existing arms. In our bandit RL environment, M and K are well defined, but how do we estimate 3? We use the following heuristic estimate difficulty: Let j be the best arm in the current casino w.r.t. its sampled mean Pj, then we define 3 = 1 1-p For instance, if the best arm has a sampled mean of 0.9, then we are in an "easy" casino, and the diffieulty will be 1 0.9 0.1, which is fairly close to O, implying we should NOT be sampling new arms, as the best arm we have currently is likely to be good. Conversely, if the best arm has a sampled mean of 0.1, then are in "difficult" casino, where stand better chance of finding a good arm by sampling more arms.
casino selection To adopt the infinitely- many arm algorithm to a multi-bandit setting, we use the following heuristic: selecting the casino where we have the least information about p" of casino. In practice, we rank all K arms based on their sampled mean, and take the top-half of the arms, and aggregate beta distribution of the total number of Is and Os of these arms, and use the variance of the beta distribution as a proxy for uncertainty. For instance, a casino whose top-half arms have in total many observations, and most of them are 1s, then we certain about its p". Conversely, if casino whose top-half arms have few observations, and is an even split of 1s and Os, we are unsure of its p"-
B.4 SIMULATED EVALUATION
With both arm selection and casino selection, we have a functioning agent. We can evaluate this agents' performance against several baseline agents in the bandit RI. environment to verify that indeed more efficient. We consider the following baseline agents, rand is the random agent that select an action at random, tile is the agent that tries to evenly spread out the observation budget, tile-inf is the agent that uses the infinitely many arm algorithm, and tries to spread the budget evenly across casinos, cas-inf(ours) the agent that selects the casino using uncertainty of p", and use infinitely many arm algorithm.
The algorithms performance over 100 casinos with a total of 600 interaction budgets is in Figure [3
0.50
0.58
0.58
0.54
rand
1e. Inf
025.
Figure 15: performance of various bandit policies, of 100 casinos and budget of 600, averaged across 100 repetitions. horizontal bar is average, whiskers indicate standard deviation
As one can see, for the simulated environment, which makes several simplifications, such not tak- ing in the generation aspect of description making, and modeling difficulty of casino as a truncated gaussian, our proposed bandit algorithm out-performs the other baselines. The implementation of the bandit environment and the bandit policies can be found LARC/bandis
24


Reviews:
[{"review_id": "OZWmc8IS9Io", "reviewer": "Reviewer_4uxi", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "*Strengths*\n- The paper addresses an important problem: creating a benchmark aimed towards creating machine learning models that can help understand and reason concepts. Adding language annotations ( which is the way humans communicate) to ARC is the right direction to progress especially keeping in view the surge of large langauge models for both natural language and code. \n- The paper is well written in most parts ( especially introduction and motivation). However, there are significant improvements that can be done in terms of improving the clarity ( see comments below).\n\n*Weaknesses*\n- Even though the motivations are well set, I think just adding langauge to an existing dataset might be considered less novel. The linguistic analysis is interesting but I would have liked to see the results of more program synthesis systems especially the large models like Codex [1], GPT-Neo [2], GPT-J [3]. I feel the addition of language naturally makes the set of tasks in LARC more suitable for such language models that makes it essential to have this comparison. Using a program synthesis system that is not catered towards accepted natural langauge instructions (the system used in the paper) will not lead to significant improvements.\n- I felt that the clarity of the paper needs to be improved ( see concrete suggestions below). On a high-level including more examples will really help in understanding the ideas put forth in the paper.\n\n\n*Suggestions/ Comments*\n\n1. An example in each category of the tag will be useful. Just describing the results with these tags used directly in the sentences seemed a bit abrupt to me.\n2. More details should be provided about the exact program synthesis model employed.\n3. I felt the bandit algorithm for data collection was interesting and if more details about it are placed in the main paper, it will definitely add much value.\n4. More description of how psedo-annotations are produced along with examples.\n5.  More description of how exactly the distant supervision algorithm works.\n6. I found the brief section on suggestions quite interesting. Personally, I would like if the authors could expand this section with more observations drawn from other program synthesis systems and evaluation settings.\n7. Some sample cases showing in which cases the program synthesis system succeeds and why will be extremely useful. In fact, I will say it is needed to understand the role and contributions brought in by adding language. It might be possible that the DSL itself is not defined properly or the language annotations or pseudo-annotations are not good enough to accomplish the set of reasoning required to solve the particular task. Basically, more analysis of why the systems fail so terribly through sample cases needs to be added.\n\n[1] https://openai.com/blog/openai-codex/\n[2] https://github.com/hendrycks/apps\n[3] https://arxiv.org/abs/2009.03393", "summary_of_the_paper": "The paper extends the ARC dataset by adding human-written instructions that they term as \"natural programs\".  The extended dataset is called LARC. They draw parallels and cite differences between computer programs and natural programs. They draw some linguistic insights based on the natural programs and finally study the performance of a program synthesis model on the LARC dataset.", "summary_of_the_review": "The paper studies an important problem and the motivation is well laid. However, I feel the paper needs some work in terms of improving clarity as well as more extensive evaluation of large language models. They also need failure case analysis elucidating some sample cases.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "MKLOeV2K_jW", "reviewer": "Reviewer_iQUC", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Strengths:\n- The authors are attempting to tackle an important program in artificial intelligence: how to tackle open-ended puzzle learning, communication, and resolution. Past approaches have selected fixed goal posts via DSLs, implying there exists a known solution to the problem, while here the authors build off of ARC which has no DSL, and thus could prove to be unreachable via any standard DSL. Fortunately the authors show that in 88% of the cases human descriptions of a solution can correctly communicate a solution to another human. This single observation is one of the key achievements of the paper, and is interesting enough in that it constructs a new artifact that machines could try to approximate instead of tackling ARC directly.\n- The author methodology for obtaining the samples is cost efficient, and provides good coverage over the dataset.\n- The proposed approach is original and could prove valuable to researches in AI communication, planning, knowledge representation, linguistics, and meta or multimodal learning.\n\n### Weaknesses:\n- While the contribution of a natural language caption over the ARC dataset is compelling, is it not yet clear whether this data can prove useful for others downstream. The inclusion of a seq2seq model accuracy at predicting these descriptions, or some other form of evaluation would help highlight whether these annotations are within reach of current approaches, or too diverse or unpredictable to be effectively captured by present conditional language models.\n- Existence proof of the usability of a description certainly proves that some humans can save a task, but does not demonstrate the robustness of a description to all human receivers — in this sense it might be useful to either describe this limitation more extensively, provide an example, or a counter-example of this shortcoming.\n", "summary_of_the_paper": "Authors construct a dataset of natural language programs for solving ARC tasks by using a population of Mechanical Turk workers to validate that a turker can correctly communicate how to solve an ARC task to another turk purely via the natural language used. The collected dataset is then analysed by the author and evidence is gathered for the richness of the programming primitives implied by natural language, the use of refining language, and the diversity of terms. The authors use this analysis to motivate the need for an improved DSL for solving ARC.", "summary_of_the_review": "Paper presents a useful dataset complementary to the ARC effort for understanding the limits of DSLs and capabilities of natural language for expressing programs. The dataset appears to be adequately constructed, however a lack of downstream applications and proof of utility make the effort harder to contextualise, and the dataset can be seen as incremental over the original ARC effort.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "HYBGWh_s4eu", "reviewer": "Reviewer_doKU", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n1. The paper is well-motivated with the goal of studying the gap between communicating natural programs to humans and machines. The existing reasoning benchmark shows there still exists a large gap in reasoning and problem solving between them. It's a critical problem to be addressed.\n\n2. The LARC dataset construction is by collecting verifiable instructions from a describer and builder, which ensures the task finish rate. The dataset is valuable for the community to study how natural program boosts the abstraction and reasoning process. The linguistic analysis shows how concepts differ in computer and natural programs.\n\n3. It uses existing program synthesis techniques to study how to execute the natural programs as humans. Showing solid qualitative and quantitative findings.\n\nWeaknesses:\n\n1. The technical contribution of this paper is weak since it mainly uses previous approaches to analyze the program synthesis results. I would like to see a new learning method to tackle this challenge.\n\n2. The improvement from 16/183 to 22/183 is not trivial but still very poor. One main reason is the DSL-based program synthesis is limited by the scale and range of the DSL. The analysis of how the scale and coverage range of DSL affects the performance is required for a better understanding of how to close the gap.", "summary_of_the_paper": "The paper presents the language-complete ARC to study how human language can affect abstraction and reasoning capability.  It collects the natural program described by human annotators and applies program synthesis techniques to analyze the gap between communicating to humans and machines. The motivation is sound and the contribution is solid with the effort of annotating LARC and benchmarking the program synthesis approaches.", "summary_of_the_review": "I like the idea and solid contribution of this paper. The main concern I have is the technical contributions. Please refer to the above for details. I would consider raising the score if the concern is properly addressed.\n\nWhile I am not totally familiar with all the literature, my assessment of the novelty and originality might not be accurate enough.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents the Language-complete Abstraction and Reasoning Corpus (LARC): a collection of natural language descriptions by a group of human participants who instruct each other on how to solve tasks in the Abstraction and Reasoning Corpus (ARC).

Overall, the reviewers found the LARC benchmarks to be well-motivated. However, there were concerns about whether the value of the dataset to downstream tasks. Results from additional program synthesis systems (like Codex and GPT-Neo) would also make the paper stronger. I agree with these objections and am recommending rejection this time around. However, I encourage the authors to continue pursuing this line of work and resubmit after incorporating the feedback from this round.
Decision: Reject