Learning to Reason via Program Generation, Emulation, and Search
Authors: Nathaniel Weir
Muhammad Khalifa
Linlu Qiu
Orion Weller
Peter Clark
Venue: NeurIPS 2024 poster (2024)
Keywords: language models
instruction tuning
code generation
reasoning
program search
program emulation
Primary area: natural_language_processing
TL;DR: We show that fine-tuning LMs to generate and then emulate the execution of programs creates models can learn new tasks via program search.

Abstract: Program synthesis with language models (LMs) has unlocked a large set of reasoning abilities; code-tuned LMs have proven adept at generating programs that solve a wide variety of algorithmic symbolic manipulation tasks (e.g. word concatenation). However, not all reasoning tasks are easily expressible as code, e.g. tasks involving commonsense reasoning, moral decision-making, and sarcasm understanding. Our goal is to extend a LM’s program synthesis skills to such tasks and evaluate the results via pseudo-programs, namely Python programs where some leaf function calls are left undefined. To that end, we propose, Code Generation and Emulated EXecution (COGEX). COGEX works by (1) training LMs to generate pseudo-programs and (2) teaching them to emulate their generated program’s execution, including those leaf functions, allowing the LM’s knowledge to fill in the execution gaps; and (3) using them to search over many programs to find an optimal one. To adapt the COGEX model to a new task, we introduce a method for performing program search to find a single program whose pseudo-execution yields optimal performance when applied to all the instances of a given dataset. We show that our approach yields large improvements compared to standard in-context learning approaches on a battery of tasks, both algorithmic and soft reasoning. This result thus demonstrates that code synthesis can be applied to a much broader class of problems than previously considered.

Learning to Reason via Program Generation, Emulation, and Search
Nathaniel Weir*t Johns Hopkins University nweir@jhu. edu
Muhammad Khalifa University of Michigan khal mallfammumicc ch. edu
Linlu Qiu' MIT LinlugiuOmit.edi
Orion Weller* Johns Hopkins University oweller8cs, jhu, edu
Peter Clark Allen Institute for Al peterc@allenai.c org
Abstract
Program synthesis with language models (LMs) has unlocked a large set of reason- ing abilities; code-tuned LMs have proven adept generating programs that solve a wide variety of algorithmic symbolic manipulation tasks (c.g. word concatena- tion). However, not all reasoning tasks are easily expressible as code, c.g. tasks involving commonsense reasoning, moral deeision-making. and sarcasm under- standing. Our goal to extend LM's 's program synthesis skills such tasks and evaluate the results via pseudo- leaf function calls are left undefined. To that end, we propose, Code Generation and Emulated EXecution (CoGEX). CoGEX works by (1) training LMs to gen- erate pseudo-programs, (2) teaching them to emulate their generated program's 's execution, including those leaf functions, allowing the LM's knowledge to fill in the exccution gaps; and (3) using them to search over many programs to find an optimal one. To adapt the CoGEX model to new task, introduce method for performing program search to find a single program whose pseudo-execution yields optimal performance when applied to all the instances of a given dataset. We show that our approach yields large improvements compared to standard in-context learning approaches
psendo-programs, programs, namely Python programs where some
battery of tasks, both algorithmic and soft reasoning. This result thus demonstrates that code synthesis can be applied to a much broader class of problems than previously considered
Introduction
Recently there have been rapid advances in training language models (LMs) to generate code rather than natural language (NL), following the intuition that code may be more effective than NL for certain tasks. such as those requiring complex calculations, iteration, data structure manipulation et al. 2022, Gao et al.) (023). Although successful, these works have mostly studied tasks conducive to programmatic paradigm, such as symbolic manipulation or algorithmic reasoning, i.e., tasks for which clear compilable program can be devised. However, it is unclear how apply this approach to "softer" reasoning tasks such as commonsense and social reasoning, where algorithmic solutions are less obvious ZZhang et al. 2023a).
Work done in part during internships at Allen Institute for AL. !Our released dataset, fine-tuned models, and implementation can be found at https://github.com
nweir127/Coch
"Co-first authors.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Alpaca Instance
CoGEX Instance
Kir Instruction: Pluralize the given word
HI Instreetion
**# inpu:: Corpus
Instruction from Alpaca
<xe Output Corpara
II tapat
def plerelsre vord (word):
cimitiy
ending eentity (vord)
Oulpui Reformetting
Edentidy ploretsration role for
5 apply the ploraltration cule to the vord
Generation
planel fom apply__ttrrileette wtrttatttrrrrrrteereeet endlago
return
(origias] woed!: word.
endinny
Code Instantistion
tealel: Atrraliaaion_nii
'ossuer" planol frrm
205 plecalise yeod Cospea')
Function Call
I1
Output Dictionary
"endlag 'e"
L'enet
"cleas": decterstor nester')
Figure 1: Example from the CoGEX dataset automatically converted from an Alpaca (Taori et al. 2023) instance via LLM prompting. We train the model to receive the instruction and input and generate the Python program and function call an intermediate), before outputting the final dictionary that contains the answer and any intermediate reasoning steps.
Our goal expand an LM's program synthesis skills to such softer reasoning tasks. Our approach builds on the insight that, beyond generating code, LMs can also emulate the execution of code. This includes handling function calls that are defined only by name and documentation, even if they lack a full implementation. We refer to these types of programs- where only the function skeletons are provided without actual code implementations- as pseudo-programs. Such gseudo-programn can encompass both well-defined reasoning steps, such as mathematical or algorithmic operations, as well as function calls representing less precise reasoning, such as commonsense logic. This work investigates whether generating and pseudo-executing such programs can effectively address soft reasoning tasks in addition to traditional algorithmic problems.
To achieve this, we propose novel approach: training models to follow NL instructions by generating a program and then emulating that program's 's code execution. Our paradigm, called CoGEX, changes the inference process to (1) generate a Python function given an arbitrary instruction and optional input, (2) generate a call that function, and (3) produce the result of simulating its execution. Unlike other work (Zhang et al.] 20236) Li et al.) 2023), we do not use a Python interpreter to execute any code; rather, the model is trained to emulate execution. This allows the generated code to deliberately include calls to underspecified functions (i.e., where only the function name and documentation are included), by allowing the LM emulator to fill in the functions implementations using its latent knowledge. We train the model to not only output the result of pseudo-executin the code but also the results of intermediate function calls in the code. CoGEX thus suggests a way to leverage the flexible ad-hoc reasoning abilities of LMs while encouraging programmatic reasoning via the program structure. We train COGEX models by adapting the recent A Alpaca instruction tuning dataset TTooi al. 2023 into set of analogous Pythonic examples by prompting GPT-4 to perform the conversion, and then use the resulting COGEX dataset to mne-tune smaller (7B and 13B) LMs to answer instructions via code.
The CoGEX paradigm allows us to explore new way to learn new tasks: identifying a general program that applies across task, such that new task instances can be solved by emulating calls to that one program. Inspired by work on hard prompt tuning (Wen et al., (024) and example selection for in-context learning (Gupta et al. 2023a), introduce search procedure that uses the frozen COGEX model to try out many programs on a set of training examples and identify which single program is optimal for the dataset. The procedure, termed COTACS: COGEX Task Adaptation via Code Search, performs no parameter updates and requires saving nothing more than a program string.
We evaluate over a diverse suite of reasoning tasks, including commonsense QA, text classification, and math datasets. These datasets cover symbolic tasks that could conceptually benefit from program- matic operations and standard natural language tasks whose solutions might not be easily described in code. We find that applying COTACS leads the COGEX models to substantially outperform the comparable NL- based LM using the same original checkpoint and the same set of training examples

---

available for in-context learning, even in the few-shot regime. COTACS thus gives us one way to fit a model new dataset without having to perform any gradient descent or parameter updates, both for algorithmic and softer reasoning datasets. Our contributions are thus:
1. A novel reasoning paradigm, CoGEX, that trains language models to generate and emulate the execution of pseudo-programs CoGEX is a general paradigm that allows LMs to leverage code for different types of reasoning.
2. A program search method, COTACS, enabling a task task-general program suitable for a dataset (rather than single instance) to be found using a CoGEX model.
3. A dataset, derived from the Alpaca instruction tuning dataset, for training CoGEX models.
Overall, this work provides a significant step in showing how code generation can be applied to much broader class problems than previously considered.
2
Approach
In this section, we start by formalizing our approach and describing our data construction process We then deseribe program search approach to tune a COGEX model on given task through program search ($2.2)
2.1 Method: COGEX
Formulation. Our goal is for the model to execute given task by simulating code execution. That means our model will take as input the task description, generate a Python program, and simulate the expected output of executing that program. Formally, given a natural language (NL) task description I, optional input argument A, Python function F, function call C, and output dictionary O designating the output from the program pseudo-execution the LM will take (T, A) as input and generates (F, C, O) as output, Since the process is sequential, CoGEX models can work as either a reasoner freasoner (I, + (P.C) + O or as a call-instantiating and exccution-emulatinn model femulator (L, A. P) + C + O that takes pre-specified program /' and applies it to the variable arguments A. This latter formulation enables searching over the space of task-specific programs: searching for one Pusk to solve class of problem (e.g., emotion classification) and then applying femulstor I, A,, Prask) to emulate its execution on each instance A; of that problem. We expand on program search in 2.2
As we want a general-purpose dataset that spans tasks with diverse reasoning requirements, we choose the Alpaca instruction tuning dataset Taori et al. (023). Following Peng et al. (003)), we rely on 4PT-4 to convert the Alpaca dataset into their COGEX versions. Specifically, every NL instance in the Alpaca dataset is mapped into a corresponding COGEX version. We split the conversion process into three steps, each of which involves prompting GPT-4 with the output from the previous. This stepwise approach proved more effective than directly prompting GPT to convert each instance to code in one shot.
Training Data Construction.
As depicted in Figure I the three steps are: (1) converting the outputs and (optional) inputs into Pythonic data structures like strings, lists, and integers whenever relevant determined by GPT-4; (2) generating an instraction-specific plan, or a series of NI steps that should perform the task for any potential input; (3) instantiating the plan as a Python program whose inline comments are the plan steps and whose output is a dictionary containing all intermediate and final outputs that the LM believes would result from exccuting each step. Prompts for all steps can be found in Appendix [A]
Importantly, we allow for GPT to include undefined functions, e.g., identify Seentiff_enddigg () and f annd_plurlizzatinn..mmmm wwwoooerreeloleeeee () in Figure I] The goal is to leverage the LM knowledge to fill in the semantics of these undefined functions when emulating the execution of a given program. In addition, we include the program's 's intermediate results in the output dictionary before the fi- nal answer to encourage the model to stick to the NL reasoning plan delineated in the program comments. After defining the program, we cue GPT-4 to call the function on an argument, e.g. pluralize. sereewdod(( corpus') which can reflect the optional Alpaca example input, or can reflect specific details from the instruction itself. Our prompts encourage GPT-4 to write a program that
"The dataset was constructed between August ith-26th, 2023 using the gpt-4 model in the OpenAl API.
3

---

is as general purpose as possible and not tied to specific input: e.g. pluralizo_worddxord) is preferable pluralize_corput ()
Fine-tuning any LM on the resulting COGEX dataset creates our desired model, which accepts any task description/input combination and responds by dynamically generating Python program and then emulating its execution.
2.2 Program Search: COTACS
CoGEX model can generate new program for any new task instruction and instance; however, some programs might be more or less effective at performing the task. How can we find the optimal program for specific task, especially when some training data available? As CoGEX relies on argument-accepiing pseudo-programs, it naturally enables program optimization. Given multiple examples of new task, we can search for one program that performs well, and then apply the same program to new test examples by invoking the program with different input arguments.
Our search process, COTACS: COGEX Task Adaptation via Code Search, finds single program that optimizes COGEX model for a particular task dataset, enabling adapting a CoGEX model given task without learning any weight parameters. We learn finetuned CoGEX model to generate and then evaluate many program candidates to find the one that best fits the given dataset. As described in algorithm I] we split dataset D of argument and output pairs (a;, o:) into a small training set (n 300 in experiments) and a larger development set; we then generate separate code candidate for every training item and retain the programs with decent performance on the training set [ We then rank these programs according by their performance on the development set. For certain tasks, we find it beneficial find multiple programs for a task and then at test time take majority vote across the CoGEX model's 's responses using each code. To accomplish this, we retain some top-k performing codes over the development set.
dataset simply by using
Algorithm COTACS search that identifies a set of & programs Pp that best adapts a CoGEX model to new dataset D
Input: CoGEX model f. Dataset D = [(a1, 01), (22,02),... o2)...... Instruction I, number of code candidates minimum training performance a, task metric 8 Result: Optimal programs Pn that maximize model performance on L)
Programs <- 0:
TrainSet <- RandomSample(D. D, r));
// Sample from D // Remaining [D] examples serve as dev set
DevSet + D TrainSet;
for (a,, o.) in TrainSet do
+ =f(1 a.):
// Sample a program for the instance
TrainPert Evaluate(p;, TrainSet);
while TrainPerf a do
P: < f(T TrainPerf +- Evaluate(p,, TrainSet);
// Resample code low performance
end
11
Add p. Programs;
12
end
13 f argmax (pi PE) ) Prrggrams Et. Evaluate(p,, DevSet);
return PD;
15 Function Evaluate (p. D): for (ai, in do
(:. +- [[I, a.. p): end 18
17
// Run the model with program p
19
return 1 ID2 8(6 o;); [
// Average taak metric (e.g., exact match)
"To ensure quality of the retained programs, a user defined threshold a is used to keep only the programs whose training performance is at least a. If no program achieves after tixed number of trials, we use the best performing sampled so far.

---

Table 1:
Benchmark results by CoGEX models optimized for each dataset using the COTACS method, compared to the corresponding off-the- 2 checkpoint performing 2-shot reasoning using a BM25 retrieval index of 1000 exemplars. Results are also compared to zero-shot Alpaca model fine-tuned from the same checkpoint. The top score per size is bolded. Colored cells indicate changes ( ggains, losses the same) ) relative the best-performing non-CoGEX baseline (Alpaca or 2-shot). Results show that CoGEX with CoTACS outperforms the baselines on nearly
every task and often does so even with only 10 examples.
Classification
Symbolic
Math
Commonsense
Nuain
CoLA
Emotn
SST
Coin
WSort
Sum
SVAMP
CSQA
SIQA
Avg
Alpaca 7B
O-shot 2-S BM25
0
70.6
53.4
87.3
49.5
40.0
21.6
25.7
46,8
54.1
49,9
Llama-2 7B
1000
57.5
55.2
82.1
32.4
45.5
35.2
34.7
45.7
46.0
48.3
COTACS &
10
75.0
52.2
86.9
50.8
40.6
61.3
33.3
42.3
50.1
56.7
COGEX
COTACS &
1000
78.5
56,2
91.2
60.0
39.5
62.8
41.3
52.7
57.7
60.0
Llama-2 7B
COTACS &
1000
79.2
56.0
90.9
61.9
40.8
63.6
42.7
52.4
59.3
60.8
Alpaca 13B
0-shot
74.6
53.0
86.0
63.8
50.3
44.5
37.3
62.2
63.4
59.5
Llama-2 13B
2-S BM25
1000
78.9
54.0
92.4
48.6
50.0
38.7
46.0
63.4
62.8
59.4
COGEX
CoTACS k =1
10
80.9
55.1
88.9
58.0
51.3
61.3
42.8
59.2
57.6
61.7
COTACS
1000
81.0
56.4
92.1
65.7
50.8
64.0
48.3
63.4
64.6
65.1
Llama-2 13B
COTACS 1000
81.0
56.6
92.1
69.5
51.6
63.9
50.3
64.0
65.5
66.1
3 Experiments and Results
Below we describe the training and evaluation of CoGEX models. We first show overall performance across a wide array of tasks compared to off-the-shelff baselines ($3.2) then ask a series of follow-up research questions investigating ablated scenarios ($3.3).
3.1 Experimental Setup
Model Training. We fine-tune the 7B and 13B variants of Llama-2 Touvron et al. 2023). We use parameter-effiiient training via Low-rank adaptation (LoRA) (Hu et al., (002)) with rank of 16, dropout rate of 0.05, and LoRA weights added to the query, key, value, and output matrices in all layers. We train all models for five epochs using a batch size of 32 and learning rate of 0.0003. As a validation set, we randomly sample 2K examples from the training set and keep the checkpoint with the lowest perplexity on the validation set for testing. Model training was done on server with 128GB of RAM and Nvidia A6000 48GB GPUs On our dataset, training a single 7B model and 13B models took around 12 and 20 hours, respectively. To ensure a fair comparison, all the baselines are trained with the exact same hyperparameters.
Datasets. We measure COGEX model performance on a variety of benchmarks ranging from sym- bolic manipulation to commonsense and social reasoning. We choose these datasets as representatives of tasks that involve complex reasoning and tasks whose solutions cannot be easily described in code. As for symbolic and math reasoning, we use the Word Sorting task from BIG-bench hard (Srivastaval eet al. 2022; Suzgun et al., (022), the math word problem dataset SVAMP (Patel et al.) 2021), )) the coin flip tracking dataset from Wei et al. (2022). and the large number arithmetic task (referred to as Sum) from Zelikman et al. (222). For the last, we use the 5-digit examples for training and 6-digit for testing. We measure string-normalized exact match accuracy for all tasks. Following Zhang
ct al. 2023b), we evaluate a series of Text Classification datasets: CoLA (2 labels) (Warstadt
ctt al. 2019), Emotion (6 labels) (Saravia et al., 2018), and SST2 (2 labels) (Socher et al. 2013)). We
also evaluate on the Commonsense Reasoning datasets CommonsenseQA (Talmor et al. 2019) and
Social IQa (Sap et al.) 2019), which are 4- and 5-way multiple-choie datasets. We hand-write the instruction Lunk for these datasets they do not provide any.
Code Search. For all datasets, we use a maximum of 1000 training examples. We use n 300 training items to generate candidate codes and evaluate them on the remaining 700 items to identify the most generalizable ones. We experiment with retaining the top-k E (1,3) performing programs for use at test time. For k 3, we take majority vote of answers, breaking ties randomly, We use
5

---

Table 2: Difference in performance by COTACS k = 3 comparing Llama-2 vs Code Llama CoGEX models (++' implies Llama-2 better). We see that Code Llama is more effective for some tasks but worse on others, while the 13B version performs worse than the 13B Llama-2 on all but 2 tasks.
Model Size CoLAA
Emotn
SST
Coin
WSort
Sum
SVAMP
CSQA
SIQA
+1.3
-0.8
+1.2
-10.5
-4.5
+6.2
+2.7
-3.6
+4.2
13B
+0.5
+0.2
+0.9
-12.4
+2,4
-9.3
+3.0
+6.8
+4.7
sampling temperature t = 0.7 when generating candidate codes and f = 0.05 to generate answers given a program and argument. We report results on the released dev sets of all considered tasks.
Baselines, We consider two baselines that represent standard practices for adapting an LM to a new task: (1) few-shot prompting using the off- the-shelf Llama-2 and CodeLlama models and (2) zero-shot prompting using the Llama-2 models instruction-tune from the original Alpaca dataset For the in-context learning baseline for (1) we use the same 1000 training data-points COTACS and optimize the examples by retrieving the most similar few-shot examples using BM25. For zero-shot alpaca models, we use the standard Al Alpaca-7B and -13B models. As COTACS might not require many training examples to achieve strong performance, we compare the 1000-example CoTACS run with one that only uses 10 total examples generate and evaluate candidates.
3.2 Results
Our main results depicting the difference in performance between CoGEX models tuned via Co- TACS versus aff-the-shelf sho-shot baselines and Alpaca models are shown in Table 1 The CoTACS method with 1000 training examples outperforms the baselines for a large majority of tasks and models (8/9 tasks for both Llama-2 7B and 13B). CoGEX shows particularly strong gains the baselines in the Sum and coin flip tracking tasks (+10-209) as expected due to its code-related nature. We observe that the COTACS method with Nizain 1000 training examples performs best average across the 9 tasks, and still performs better than the baselines with only Numin = 10 examples. Retaining the top a: 3 programs instead of I improves performance in most cases (+ % average).
Instruction Following. As our models are trained on instruction following in code, can they still perform instruction--reated tasks as well models trained text-only Alpaca? We verify this by using alpaca-eval to compare Alpaca-7B against our COGEX-7B model trained from the same base Llama model. We find a similar win rate (50% within the 2 SD range) indicating similar instruction following ability. Thus we can see that training on code-basee based instructions does not hurt standard fooluction-followiin abilities, while opening up many possibilities for program search.
Effect of Code Pre-training. As we are fine-tuning LMs on code data and then evaluating them on tasks that are more less code-related, a natural question to ask is whether LMs pre-trained on code datasets yield stronger CoGEX models. We investigate this by fine-tuning Code Llama (Roziere et al.. 2023) on the CoGEX dataset instead of Llama. Table 2 shows the resulting change in performance using CoTACS (k=3) program search. The Llama-2 models show improved performance on Social IQa (+4%) but much worse coin flip tracking 1-11-12)) These results do not provide conclusive evidence that Llama-2 models are better or worse than Code Llama on particular task categories.
3.3 Ablation Studies
Here we present a series of ablation studies to ask the following questions:
How many training examples needed for search? In the above experiments, we chose 1000 training examples and 300 program candidates for the COTACS algorithm. This raises the question: how many examples are required yield the strong performance provided by the search? We investigate this by simulating the algorithm and sampling 1000 trials with varying numbers of training examples and program candidates. Results are shown in Figure In nearly all cases, performance with 50 or 200 training examples is within a couple of points of the full performance with the 300/1000 configuration. The performance when sampling 10 code candidates (green) lands within points of sampling 300 candidates on 5 of the 7 datasets. Benefits do not appear on Word Sorting, as
WWe also experimented with few-shot prompting the Alpaca models, but found them to perform significantly worse than zero-shot, which is likely side effect of instruction tuning.

---

SST2
Word Sorting
SVAMP
Social IQa
0.05
0.92
Bosilin
0.63
0.2
0..00
8.96
0.50
0.575
0.400
0.30
CoinFlip
Nurber Summing
0.64
Commmomsnnse QA
Code Cundidaics
08550
0,506
20
010
0,575
0,558
0.60
0.58
23 33 I0 20) 309 193)
10 20
30 ise 2M 59/340
5.3 18 3) 30 100 29 3911199
Number Trining Btres
Number Training Items
Number of Training Iemms
increase the number of training Figure 2: Change in COTACS performance using Llama-2 13B items from 5 to 1000 and program candidates from 3 to 300. Results are averaged across 1000 trials.
performance lands between 0.51 and 0.515 regardless of configuration. This suggests that the range of quality in generated programs for the Word Sorting dataset is much smaller than the others, so picking between just few candidates is sufficient. Overall, we see that we can significantly reduce the search space and still see large gains most tasks.
Is it better execute an NL plan instead of Python code? We have proposed mechanism to generate Python programs whose steps are meant to reflect the reasoning process, stated in NL, that answers given instruction. plan and achieve the same performance? We fine-tune Ilaaaa model on version of the COGEX 52k-item training set where each Python program has been replaced with just the NI. steps (removing step 3 Figure 1}. This NI. Plan model still returns the same output dictionary with intermediate results. To fit the plan-only model to dataset, we run the COTACS algorithm but sample and retain the NL plans instead of programs. We see in Figure 4 (orange vs gold) that NL Plan COTACS can match the performance
the code necessary, or can model be trained generate only the
regular program COTACS on some tasks (CoLA, SST, Word Sorting, Emotion), but performs much worse others, particularly Coin Flip, SVAMP, and Sum. This follows the intuition that these tasks benefit from programmatic reasoning paradigm.
Is it better to find one program or generate new one for each instance? CoTACS finds one or multiple programs that can be reapplied to task instances in a dataset to achieve high performance. Is this better than letting the CoGEX model generate a separate program for every instance? It might be the case that the latter allows for catering the program to the specifics of particular task instance- e.g. in Figure 3. where the left (red) COGEX-generann crafted to identify actions to be taken by a particular person. Finding single program disallows this flexibility. We investigate this question by running the model end-to-end on each instance. The COTACS model performs the mapping [(uusk A,, PCOTACS) - C; + ; for each task instance A,, while the end-to-end model performs f[ausk A.) - (P., C,) O, We sample from the latter using temperature = 0.05 5 Results are shown in FFiuue (maroon vs gold); end-to-end performance is comparable to CoTACS only on Word Sorting and Sum. In all other cases, it is substantially worse.
program has steps specifically
Increasing & and/or using self- celf-connistency
WWan al. 2023) did not meaningfully affect performance.

---

def anaver qurnttiiggiiioooooo
(quastion, Iqaatiioiggaation options):
Anaver Social Interaction QA question.
Arge:
question (ste): the Social Interaction @A question.
options (Liat): lsst of potential anaveze.
Baturna:
A 'dlct" containing the field 'anssez', whose value is of type "ste" and contains the letter of the correct anssez, plus finlds for interredaate steps of the reasoning process.
Item-Speelfic Program:
General Program:
Iduntidy key clesents
Lion.
key, Identity key
problan.
bey ellemenee identsfy_kepp key.etyy______yeeee ely_eeteenta (queation)
identify, key, elenents (question)
Stup 2: Analyse the context of the question
Step 2:
Analyse the context to unders tand the pelationship
underatand what action Saaha neads take.
between the key elements.
key
analyse_
elements)
Step Retten the letter the correct option.
Stop
context,
likely
anover solect, (option,,,,on.. action]
anRvec determine likely snawer (context, bay elaments, options)
rutura "ayy Glementa" key elemente,, "action".
return l'kay elazente': key elerects, 'conbaxt". contaxt, "answez": answez]
action,
>>> anaver Queation "Cassyy gave sone money to Jease so ahe could go to the novie. How would you describe Caxey?", ("(A) thankful",
[[]] gready", (()) giving"])
Figure 3: Example CoGEX model-generated programs for Social IQa (Sap et al. 2019) questions. The left item fits well specific SociallQa question pertaining to question-speet spciion--peciicc entities but does not generalize well to the dataset, while the right item applies more generally to cases such as the instance shown the bottom, which does not pertain character actions. Applying COTACS to identify a single program such as the right one shows to improve overall task accuracy.
Serting
IQ
1318
Liara-2718
Limad
Liara-2'18
Lanza22
Limre-2
Liarad
CrinPlip
Summing
Commonenne
CoGEX End Eld
Alpaca Thought
NL Plan CoTACS
Liare-200
Llaxm-2
Figure 4: Performance comparison between COTACS (k=1) and various ablations: (1) CoGEX End-to-End that generates separate programs for each instance, (2) chain-of-thought prompting, and (3) searching for an optimal NL plan instead of code program. COTACS consistently equals or outperforms ablations on tasks, while each ablation drops performance on least 2-3 tasks.
Is COTACS better than chain-of-thought? A common practice to elicit systematic reasoning from LMs is to prompt it for the reasoning some version of "explain your answer step-by-step" (Kojima al. 2022). How does this compare to CoGEX models on given dataset? We compare COGEX to zero-shot CoT by prompting our Alpaca models with task-specific instruction, while additionally appending the instruction to "think step-by-step" before producing the answer. Figure 4 (blue vs gold) shows that CoT prompting performs similarly to the NL plan search method; can approach COTACS performance some NLP classification tasks but performs worse over SVAMP, Number Summing, and CoinFlip.
When is COTACS better than fine-tuning? Fine-tuning is a standard practice to adapt an LM to new task. However, fine-tuning often requires large amount of training data and storing new model for each task. Here, we study the impacts of the number of examples on fine-tuning and COTACS. find that when there are many examples available, fine-tuning achieves stronger performance. However, COTACS is generally better until there are a large number of examples available: it outperforms fine-tuning on 4/9 tasks with 500 examples. This suggests that CoTACS can be lightweight alternative in the low-to- to-meduum shot setup.

---

CoLA
SST2
Word Sorting
SVAMP
Social IQu
6.7
0-9
0.91
9.23
0.5
0.30
100
300
1000
100
300
1000
100
500
1000
100
500
1000
100
500
1000
Emotion
CoinFlip
Namber Summing
Commonsense QA
0.63
0.7
Method
CoTACS
Fine-tuning
0.00
100
300
1000
100
245
100
500
1000
100
500 1000
Figure 5: Performance tradeoff between COTACS, which requires saving just program string, and fine-tuning, which requires saving an entire checkpoint, as we increase the number of training examples. Although fine-tuning typically performs better with more data, COTACS provides an alternative that is lighter-weije and stronger at low-to-medium numbers of instances.
def Frack__oon_flip(teeee mun_t
Track the current state coin after certain number of flipe. Arge:
(atr): string containing information about the of coin different stages.
nun_flip (int): the number of flips to consider.
Returns:
dictionary containing (at. least) the field 'ansuer', whose value in of type 'str' and contains the state the coin after the specified number flips.
The dicticnary also contains the result of the intermediate stepe of the reasoning process.
nentions flipping coin.flip.me flin..entoonn - extract_colna Cbbract_coin_flip.eeee conp.n..iip...niiiaaaaaeo (text)
Identify
the input text.
Step 2: For each identifiid instance of flipping, determine obether it 1s heads tails outcome. clip_outeones (mention: deternine_ httpe/lllpppoooteeeeeeeeeo (mention) for nention in fipp_ttip_mmttions?
Step 3: Track and record the state of the coin after each flip.
coin_atate track_coin_stan stt.nnnsaterrllp.ooooo
nun_rlip)
return bocin_flip_manttinn
ii..flliomtnnonns #rippoaatcomes': autpooutcomes, 'ansuer": coin_atate)
Exemple Input: 'A coin is heade up. Gee does not flip the coin. Joseluis flips the coin. Cory does not flip the coin. Stefanie flips the coin. Is the still heads up?'
Example Output:
'coin, fwwpppppppee... mentiont:: ['A coin is heads up', 'Joseluis flips the coin', 'Stefanie flips the coin?), 'rlip_outconest
'A coin is heeds up": 'heads', 'Joseluis flips the coin': 'heade', 'Stefanic flips the coin': 'heads'
},
'beads"
Figure 6: Qualitative examples of LLama-2 13B the coin flip tracking task where the model fails correctly simulate the program and correct for the wrong reasons.
3.4 Qualitative Analysis
Since we rely on the LM code emulator, there is no guarantee of correct execution. The generated intermediate outputs allow us examine if the model can faithfully emulate the program. We observe failure cases where the LM incorrectly simulates the program execution even the generated program is correct shown in Figure 6 We also include positive qualitative examples in Appendix B
4 Related Work
Reasoning via Code. Using code for reasoning is a burgeoning area that has shown improved results on many algorithmic tasks (Chen et al. 2022 Gao et al., 2023). Many approaches ask LLMs to express their reasoning as code and leverage code interpreters to execute them. Recently, and concurrent with our work, some studies investigate training L.LMs as code compilers, where the LM
prompted to emulate code exccution (Li et al. 2023
Chac et al. 2024 Mishra et al. 2023). These

---

LM-as-compp -o-aplcompiler approaches fall into broader category of work that invokes LLMs as subroutines in programs (Kalyanpur et al. 2022] Weir et al., 2024p. Different from ours, these works mainly rely on manually prompting very large models, while we focus on training open-source LMs to both generate and emulate programs. In addition, we aim to achieve task generalization by searching for an optimal program for a given likk-diffeent from Chae et al. (2024) who rely on prompting LMs with specific code instructions. Ours is the first work on cose-based reasoning that employs search over the program space with the goal of generalizing optimal program task.
Prompt Optimization. Our search procedure, COTACS, has a similar spirit to in-context learning optimization approaches where the goal is to find an optimal set of exemplars (an optimal pseudo- program, in our case) for a given task. Existing studies (Zhang et al., [022] Rubin et al.) 2022] Ye
et al. 2023a Gupta et al., [2023b] Khalifa et al. (2023a) explored various methods to select optimal
in-context examples, leveraging similarity- or diversity- -basid heuristics to name a few. Searching
for useful task instructions has also been explored (Honovich et al. 2022 Khalifa et al.
2023b Chen
et al.
2023).
Another related area of research is automated prompt engineering (Shin et al.
2020 Deng et al.
2022
Prasad al.) 2023) that bootstraps an effective prompt using some reward function. While
Yang et al. 2023 Ye et 2023b), our work shows that LMS can also reason by generating and executing their own generated programs. Our method differs from these studies as it uses the same input instruction and optimizes the intermediate representation. rather than modifying via prompt optimization. Finding single program string to solve a class of problems is also related to finding a high-level NI. description of a task using one or multiple demonstrations (Weir et al. 2023).
LMs
have been shown to be effective at producing their own prompts (Zhou et al. 2022
2024
Pryzant et
Conclusion
We present CoGEX. methodology that trains language models to generate and execute their own Pythonic reasoning programs in response to task instructions. We convert the Alpaca instruction tuning data into COGEX instances that can be used to CoGEX-tune any models. We design an optimization algorithm, COTACS, that applies COGEX models to a new dataset by generating and searching through possible programs that can be reapplied to new task items. Applying the COTACS search algorithm yields task performance that exceeds that of few-shot in-context-leate learnin and typical NL instruction following. Our work demonstrates a way to apply LM-based programmatic reasoning to NLP benchmarks that require softer reasoning skills not easily stated in code syntax.
6 Limitations
While our work represents step towards utilizing code language models for non-algorithmic reasoning tasks, CoGEX still suffers from the following limitations:
CoGEX is suitable for soft reasoning tasks for which step-by-step programs are difficult to describe. However, when solving algorithmic tasks where a precise step-by-step program is possible, passing the generated code directly to an interpreter may be preferable emulating code execution via the LM.
We have found that the LM can occasionally produce result that is inconsistent with the code emulated, as noted in subsection 3.4 which case, the code does not faithfully reflect the reasoning process followed by the model.
There is extra computational overhead when emulating code execution via an LM compared to using an interpreter as the LM needs to generate intermediate variables along with the final answer.
7 Acknowledgements
We thank Li Zhang, Valentina Pyatkin, and Khyathi Chandu for feedback on ideas and earlier drafts. We also thank the organizers of the AI2 Summer 2023 Hackathon during which this project was initially conceived.
10

---

References
Hyungjoo Chae, Yeonghyeon Kim, Seungone Kim, Kai Tzu-iunn Ong. Beong-woo Kwak, Moohyeon Kim, Seonghwan Kim, Taeyoon Kwon, Jiwan Chung, Youngjae Yu, et al. Language models as compilers: Simulating pseudocode execution improves algorithmic reasoning in language models. arXiv preprini arXiv:2004.00 02575, 2024.
Lichang Chen, Jiuhai Chen, Tom Goldstein, Heng Huang, and Tianyi Zhou. Instructzero: Efficient instruction optimization for black-box large language models. arXiv preprint arXiv:2306.03082, 2023.
Wenhu Chen, Xueguang Ma, Xinyi Wang, and William W Cohen. Program of thoughts prompt- ing: Disentangling computation from reasoning for numerical reasoning tasks. arXiv preprint arXiv:2211.12588 2022.
Mingkai Deng, Jianyu Wang, Cheng-Ping Hsieh, Yihan Wang, Han Guo, Tianmin Shu, Meng Song, Eric Xing, and Zhiting Hu. Riprompt: Optimizing discrete text prompts with reinforcement learning. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pp. 3369-3391, 2022.
Luyu Gao, Aman Madaan, Shuyan Zhou, Uri Alon, Pengfei Liu, Yiming Yang. Jamie Callan, and Graham Neubig. Pal: program-aide aided language models. Proceedings of the 40th International Conference on Machine Learming, ICML' 23. JMLR.org. 2023.
Shivanshu Gupta, Matt Gardner, and Sameer Singh. Coverage- based example selection for in-context learning. In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), Findings of the Association for Computational Linguistics: EMNLP 2023, pp. 39924-13950, Singapore, December 2023a. Association for Computational Linguistics. doi: 10. 1/2282 2t055///11222...dnng-emmmll/p findings-emmlp.900 URL htttss://cclatthol.gg .rr.igoyo.rrrroooooooooooo wrg//023. httg:/222.....ngs....o. eeaddingssemn1pp 930
Shivanshu Gupta, Matt Gardner, and Sameer Singh. Coverage-based example selection for in- context learning. Findings of the Association for Computational Linguisties: EMNLP 2023, pp- 13924-13950, 2023b.
Or Honovich, Uri Shaham, Samuel Bowman, and Omer Levy. Instruction induction: From few examples to natural language task descriptions. arXiv preprint arXiv:2205. 10782 2022.
Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen Yuanzhi Li, Shean Wang. Lu Wang, and Weizhu Chen. Lora: Low-rank adaptation of large language models. arXiv preprint arXiv:2/06.099 09685, 2021.
Aditya Kalyanpur, Tom Breloff, and David A Ferrucci. Braid: Weaving symbolic and neural knowledge into coherent logical explanations. Proceedings of the AAAI conference on artificial intelligence, volume 36, pp. 10867-10874, 2022.
Muhammad Khalifa, Lajanugen Logeswaran, Moontae Lee, Honglak Lee, and Lu Wang. Exploring demonstration ensembling for in-context learning. arXiv preprint 2rX.v:2308.08780, 2023a.
Muhammad Khalifa, Lajanugen Logeswaran, Moontae Lee, Honglak Lee, and Lu Wang. Few-shot reranking for multi-hop QA via language model prompting. In Anna Rogers, Jordan L. Boyd- Graber, and Naoaki Okazaki (eds.), Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Pupers), ACL 2023, Toronto, Canada, July 9- 9-14, 2023, pp. 15882-1 5897. Association for Computational Linguistics, 2023b. doi: 10. 10.18/53/V1/ 2023.ACI-L.ONG.B58 URL. https::/ttss...../ org 10. 100...1663/v110000 acl-long. 885
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. Advances in neural information processing systems, 35: 2022.
Chengshu Li, Jacky Liang, Andy Zeng, Xinyun Chen, Karol Hausman, Dorsa Sadigh, Sergey Levine, Li Fei-Fei, Fei Xia, and Brian Ichter. Chain of code: Reasoning with a language model-augmented code emulator. arXiv preprint ar Xiv::3112.044777 2023.

---

Mayank Mishra, Prince Kumar, Riyaz Ahmad Bhat, Rudra Murthy, Danish Contractor, and Srikanth G Tanilselvam. Prompting with pseudo-code instructions. In The 2023 Conference on Empirical Methods in Natural Language Processing, 2023.
Arkil Patel. Satwik Bhattamishra, and Navin Goyal. Are NLP models really able to solve sim- ple math word problems? In Kristina Toutanova, Anna Rumshisky, Luke Zettlemoyer, Dilck Hakkani-Tur, Iz Beltagy, Steven Bethard, Ryan Cotterell, Tanmoy Chakraborty, and Yichao Zhou (eds.), Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 2080-2094 Online, June 2021. Association for Computational Linguistics. doi: 10. 18653/2222222 nnacll main. 168. URL 2001 maacl- 168
https://ac..antholoog
Baolin Peng, Chunyuan Li. Pengcheng He, Michel Galley, and Jianfeng Gao. Instruction tuning with gpt-4. arXiv preprint S3t::22304003227,, 2023.
Archiki Prasad, Peter Hase, Xiang Zhou, and Mohit Bansal. Grips: Gradient-free, edit-based instruction search for prompting large language models. In Proceedings of the 17th Conference of the European Chapter of the Association for Computational Linguistics, pp. 3845-3864, 2023.
Reid Pryzant, Dan Iter, Jerry Li, Yin Tat Lee, Chenguang Zhu, and Michael Zeng. Automatic prompt optimization with" gradient descent" and beam search. In The 2023 Conference on Empirical Methods in Natural Language Processing, 2023.
Baptiste Roziere, Jonas Gehring, Fabian Gloeckle, Sten Sootla, Itai Gat, Xiaoqing Ellen Tan, Yossi Adi, Jingyu Liu, Tal Remez, Jérémy Rapin, et al. Code Ilama: Open foundation models for code. arXiv preprint ar3iv:2308.0 /2900, 2023.
Ohad Rubin, Jonathan Herzig, and Jonathan Berant. Learning retrieve prompts for in-context learning. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 2655-26771 2022.
Maarten Sap, Hannah Rashkin, Derek Chen, Ronan Le Bras, and Yejin Choi. Social IQa: Common- sense reasoning about social interactions. Kentaro Inui, Jing Jiang, Vincent Ng. and Xiaojun Wan (eds.), Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNPP), pp. 4463 4473, Hong Kong, China, November 2019. Association for Computational Linguistics. doi: 10.18653/v 1/D1////1199-9-1111 URL pestps://aclanttho...o .ocggy..rrggge org/D19- 1454
Elvis Saravia, Hsien-Chi Toby Liu, Yen-Hao Huang, Junlin Wu, and Yi-Shin Chen. CARER: Contextualized affect representations for emotion recognition. In Ellen Riloff, David Chiang, Julia Hockenmaier, and Jun ichi Tsujii (eds.), Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 3687-3697, Brussels, Belgium, October-November 2018. Association for Computational Linguistics. doi: 10.18653/v1/D18.. 1404411444 //aclanthology .raeoogy.orrg// D18 1404
URL https
Taylor Shin, Yasaman Razeghi, Robert L Logan IV, Eric Wallace, and Sameer Singh. Autoprompt: Eliciting knowledge from language models with automatically generated prompts. urXiv preprint arXiv:2010. 159800 2020.
Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D. Manning, Andrew Ng, and Christopher Potts. Recursive deep models for semantic compositionality over a sentiment treebank. In David Yarowsky. Timothy Baldwin, Anna Korhonen, Karen Livescu, and Steven Bethard (eds.), Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pp. 1631 Seattle, Washington, USA, October 2013. Association for Computational Linguistics. URL httpp::/aclantholleee wtwpooooog..rg/1111110000
Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R Brown, Adam Santoro, Aditya Gupta, Adrià Garriga-Alonse et al. Beyond the imitation game: Quantifying and extrapolating the capabilities of language models. arXiv preprint arXiv:2206.0 20X.0:2206.04665. 04615, 2022.
12

---

Mirac Suzgun, Nathan Scales, Nathanael Schärli, Sebastian Gehrmann, Yi Tay, Hyung Won Chung. Aakanksha Chowdhery, Quoe V Le, Ed H Chi, Denny Zhou, and Jason Wei. Challenging big-hench tasks and whether chain-of-thougle can solve them. arXiv preprint arXiv:2210.09261, 2022.
Alon Talmor, Jonathan Herzig, Nicholas Lourie, and Jonathan Berant. CommonsenseQQ: A question answering challenge targeting commonsense knowledge. In Jill Burstein, Christy Doran, and Thamar Solorio (eds.), Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume (Long and Short Papers), pp. 4149-4155 Minneapolis, Minnesota, June 2019. Association for Computational Linguistics. doi: 10. 10.18653/1/N11-142211 /ttL/ttts///cccaattttt .rg.g//.ooooooooooooo....o...... org/N19 NN1- STg/N19-1421
Rohan Taori, Ishaan Gulrajani, Tianyi Zhang, Yann Dubois, Xuechen Li, Carlos Guestrin, Percy Liang, and Tatsunori B Hashimoto. Alpaca: A strong, replicable instruction-follooing model. Stanford Center for Research on Foundation Models. https://erfm. stanford, eduu2023/03311/aapaeeee html, 3(6):7, 2023.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.09288 2023.
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc V Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. In The Eleventh International Conference on Learning Representations, 2023. URL htttps://openreviet wwtp://oooooddddd..IiiI.........
Alex Warstadt, Amanpreet Singh, and Samuel R. Bowman. Neural network acceptability judgments. Transactions of the Association for Computational Linguistics, 7:625-641, 2019. doi: 10.1162/
tacl 20lla_00200 00290. httpsts:::/ acl aww.acoolontotoooaoooooo wrg/ Qt/0/11911110 1040
Jason Wei, Xuezhi Wang. Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. ofain-of-thouglle prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824-24837 2022.
Nathaniel Weir, Xingdi Yuan, Marc-Alexande Côté, Matthew Hausknecht, Romain Laroche, Ida Momennejad, Harm Van Seijen, and Benjamin Van Durme. One-shot learning from a demonstra- tion with hicrarchical latent language. In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, pp. 2388-2390, 2023.
Nathaniel Weir, Peter Clark, and Benjamin Van Durme. NELLIE: A neuro-symbolic inference engine for grounded, compositional, and explainable reasoning. IJCAI, 2024.
Yuxin Wen, Neel Jain, John Kirchenbauer, Micah Goldblum, Jonas Geiping, and Tom Goldstein. Hard prompts made easy: Gradient-based discrete optimization for prompt tuning and discovery. Advances in Neural Information Processing Systems, 36, 2024.
Chengrun Yang, Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoc Le, Denny Zhou, and Xinyun Chen. Large language models as optimizers. In The Twelfth International Conference on Learning Representations, 2024. lttps wtt.eere.....eooro///dd/ooooaaaa
Jiacheng Ye, Zhiyong Wu, Jiangtao Feng. Tao Yu, and Lingpeng Kong. Compositional exemplars for in-context learning. In International Conference on Machine Learning, pp. 39818-398333 PMLR, 2023a.
Qinyuan Ye, Maxamed Axmed, Reid Pryzant, and Fereshte Khani. Prompt engineering a prompt engineer. arXiv preprint 1.Xiv:2311.05660 2023b.
Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah Goodman. Star: Bootstrapping reasoning with reasoning, Advances in Neural Information Processing Systems, 35:15476-15488, 2022.
Li Zhang, Liam Dugan, Hainiu Xu, and Chris Callison-burch. Exploring the curious case of code prompts. In Proceedings of the 1st Workshop on Natural Language Reasoning and Structured Explanations (NLRSE), 2023a.
13

---

Tianhua Zhang, Jiaxin Ge, Hongyin Luo, Yung-Sung Chuang, Mingye Gao, Yuan Gong, Xixin Wu, Yoon Kim, Helen Meng, and James Glass. Natural language embedded programs for hybrid language symbolic reasoning. arXiv preprint arXiv:2309. 10814, 2023b.
Yiming Zhang, Shi Feng, and Chenhao Tan. Active example selection for in-context learning. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pp- 9134-9148, 2022.
Yongchao Zhou, Andrei loan Muresanu, Ziwen Han, Keiran Paster, Silviu Pitis, Harris Chan, and Jimmy Ba. Large language models are human-level prompt engineers. arXiv preprint arXiv:2211.01910, 2022.
14

---

Clean up the follozing Jaon itema. Map the inpat and output fields in each item to proper pythonic iten
(e.g- List, dictionary, clean string). abouldn't have newlines string. DO NOT INCLUDE "..." in your outpute.
INPUT 1:
inntrructonn 'classify the following objecta by color.", 'input?; RRibbon, Tie, Pen?, "output"; <RRed: Bn-luer Tie'n-Black: Pen')
OUTPUT
{ ('instruction': 'Claseify the following objects by color.', 'input' ('Ribbon', 'Tie', 'Pen'] '] 'output': ( 'Red', 'Tie": 'Blue', 'Pen': 'Black")
INPUT
{ l'instrucionn: "Convert the following text into list.', 'input': 'The four elements of design line, color, shape, and texture.', "output"; +- Line An- Color Vn- Shape'n- Texture")
OUTPUT 2: i'instruction':
list.', 'input'; color, shape, and texture.", "output'; ['1ine', 'color', 'abape', 'texture"]]
follocing
alenenta design line,
INPUT
{ L'intruction'' 'Generate 1ist of five iteme peraon night need for a camping trip', 'input'; ", output"; Tent Sleeping bagela3. Flechlightlad. Matches/Lighterlas Insect repellent)
OUTPUT
{' "Inatruction': "Generate list of five itens person night need for camping trip', 'input'; f, output'; ('tent', 'eleeping bags', 'flachlight', 'ratches/Lighser', 'ineect repellent"))
INPUT 4: (input)
OUTPUT 4:
Figure 7: Prompt used for converting inputs and outputs of Alpaca items into Pythonic data types.
high-level plan with complete the folloving problem. If the problem takes in inputs, your plan should be a high-level abatraction ganerally applicable imputs, juat shown
steps problen-solving artificial agent could
Instruction: (inetruction) Input: (possible_inputs)
output should series serialized jacas, per line, step plan. They should have the format {"nunhor": <atop number>", "description": <atep description>)
Figure 8: Prompt used for generating stepwise NL plans for Alpaca items.
A Prompts for Converting Alpaca to CoGEX
Figure 8 and Figure display the prompts used to GPT-4 in sequence convert Alpaca into the COGEX dataset. The prompts (1) convert all inputs and outputs into Pythonic types like strings, lists and dicts, (2) generate plans to answer given instruction, and (3) instantiate each plan as a Python program with underspecified function calls.
Figure 7
Further Qualitative Analysis
Figure an Figure 11 show good qualitative examples generated by COTACS, along with outputs from the 2-shot prompting baseline for the text classification and math reasoning tasks, respectively. We find that COTACS encourages general-purpose code that is generalizable across multiple examples within the same task. It also enables better interpretability by generating outputs of the intermediate reasoning steps.
15

---

For the following questions with example imputs and outpute, generate function that performs the provided high-leval stepa. function well as the values for internediate decisiona. Don't bard code input-specitic itens whenever possible. You can nake externel calls to undefined functions as long as the fuaction name describes its purpose.
dictionary
"ansver":
Instruction: Generate three antonyne the word "wonderful".
Input:
Answar:
('horribla', 'abyamal', 'appalling']
Steps:
aynonyns Identify antonyus of the aynonyna found in step Package the antonyne as the output in the required fornat.
target using thesauros.
Code:
def generate_antonyns (nan_ sards word):
n..
Gonerato antonyns for given word.
Arge:
nun_worde (int): the number of antonyme to generate for the word word (str): representing the word for which need find the antonyna.
Re
A dictionary containing the antonyus of the given vord, plus the result of the intermediste steps the reasoning process
Search for synonyna of the target vord using thesaurus. aynonyns thesaurus 1ookup
Step 2: Identify antonyns of the вyлопyиs found in step 1. antonyus_ of synonyye bookup__ntonypee (synonyn) for synonyn ln synonyus]
Step 3: Package the antonyus as the output in the required format. all_antonyma for aitt in antonyns_of http:/m__o___oooooo aynonyym:: antonyns. extendlantoony list)
a_ A_antouyne all, antoryus (:nun_Norde) words]
return
"aynonyas": aynonyna,
of antonyus_of stlonyyssoffeyyoayaaa 'all, antonyns' all_ antonyee,
'ansver': a_antonyns
>>> generate, antrryas,, 'sanderful))
Exemple Output:
output
ayyonynss: ('amazing', 'fantastic', 'tarrific'),
["horrible', 'abysmal', 'appalling'), ['dull', 'disappointing', 'unaxceptional",, ['auful', 'terrible', 'dreadful']
"all_antonyns":
'horrible', 'abyanal', 'appalling', 'dull', 'disappointing', "unexceptional', 'axful', 'terrible', 'dreadful'
'ansser"; ['horrible', 'abyanal', 'sppalling"]
Inetruction: Generate idese for travel blog for young touriste vieiting India
<...>
###
Instruction: (instruction)
Isput: (input)
Answer: (output)
Stepe:
(steps)
Code:
Figure 9: Prompt used for instantiating Python programs from NL plans, See repository for full-length prompt.
16

---

def datermine, anotion (santence):
Deternine the enotion expreezed in given senteace.
Args:
(stx):
'anszer', determined.
Returns:
dictionary containing least)
type
the amotion expressed in the sentance. The dictionary also containa the result of the internediate steps the reasoning process.
Step 1: Extract all the vords from the input sentence and analyze then to understand their context and meaning.
words extract_ extract_vordes corrt__oorrrreeeeeet (sentenne)
word_context
saallyzaxxord_comm (xords)
Step 2: Identify the enotion-related vords or phrases in the sentence. emotion_related_ words
wtw.il._enotiiorereteeeded (vordd))))) (words)
Step
enotion-related identified in
sentence. datermina_beet
contaxx, poetianrellated_ooom
return ('sentence': sentence, 'words'; vords, word_contezt?> contezt,
moation_relatod_vvraaa emstion_rolatod__enn sorddd 'ansver'; emotion)
Example Input: feeling yesterday
Example Output:
'senteace'; '1 feeling festive yesterday',
'sords': [1i,, 'vas', 'feeling', 'festive', 'yesterday'),
cond___ottttt
'P': 'first person singular", feas': 'past tense', 'fellingg: 'verb', "fsstive:; 'adjectiva'
"emotion, aanttion.relaadd_eee vard'' ['fastiva'], "aawwer;; "joy"
2-shot
Baseline Dutput: joy
Figure 10: Qualitative example of LLama-2 13B CoGEX-generated program for the text classifica- tion task on the Emotion benchmark.
17

---

def aatoe..ath..err..pohlmmmmmoooo :roblen):
Solve math word problen.
Arge:
word_problen (str): string representing the nath word problen.
Raturna:
dictionary containing least) the field 'anaver', whose value of type "Int" containe the solution the nath vord problem.
The dictionary also contains the result of the intermadiate stepa of the reasoning process.
nE*
Step Identify koy nnyberb couttiryy.yy..mbeelee www.berraeerd..pooble....o
problen
2: Understand the problen context.
problan_centext understand_prooat brraaanddppoeeeeeeeeee contexttooootttooaeeeaaeeoetttee (sord_problem)
Step 3: Perforn the appropriate mathenatical. operations to solve the problen.
perforn math, wwatmmatthhrrrrt (aaraattioaa(ay_nniann numbers,, problen_context)
return {
'key nunnebrbb' key_nunbers, 'problan_comtxtt'. problan_ conttox,, 'ansver'; solution
Exemple Input: Paco had cookies. He cookies his friend and 10 cookies. How many cookies did Paco have left?
Example Output:
kuyyeambers'' Sinistialqquatitty : "quantity sereiityyggvveaaeeeee givan_avay's 'guantity_aaten eaten":
crroblen_contece 'Paco had 36 cookies. Be gave 14 cookies to big fri and ate 10 cookies.?, "naser";
2-shot Baseling Dutput:
Figure Qualitative example of LLama-2 13B CoGEX CoGEX-generated program for the math reasoning task on the SVAMP benchmark.
18

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The claim of the paper is novel reasoning paradigm, dataset for finetuning models on the paradigm, and a task-specific optimization algorithm. We show the empirical benefits of the paradigm and algorithm through our experiments.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
In Insscctoon
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model cell-speciiiaatinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
19

---

Answer: [NA]
Justification:
No theoretical proofs given.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
Hyperparameters and other details are included in section 2
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
20

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
Public access to these will be released when not anonymized.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "pippscc/puullc//uuu /ttee//gguddeeeeedSuuuummbbbba ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: In sectiono
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: We only report single runs, following previous work.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
21

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative emrr rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
In susseeccti 3.1
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httpps:/neuurpps.co
Answer: [Yes]
Justification: It follows the code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer:
[Yes]
Justification:
In Iectccnoon
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
22

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not provide any new risks and discusss risks in section 6
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: They are properly credited via citation and licenses are in their respective Github pages. As they are open-source do explicitly discuss the license here and point interested readers to the original authors license.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URI
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
23

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: Yes, described in Section 2.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mooel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
No crowdsourcing was done.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No crowdsourcing done.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.


Reviews:
[{"review_id": "fFdk0G6GBc", "reviewer": "Reviewer_a6dH", "summary": "This paper proposes a means of training language models to perform semi-programmatic reasoning, along with an adaptation method based on program search to specialize the resulting models for particular downstream tasks without updating their parameters.\n\nThe authors use GPT-4 to generate programmatic reasoning strategies from Alpaca instruction-tuning examples, allowing GPT-4 to include undefined function calls as the resulting code does not actually need to be executable, only used to guide the downstream language model's inference process.\n\nThe authors evaluate their method by fine-tuning Llama 2 models on their version of the Alpaca dataset, then comparing benchmark performance against few-shot, instruction-tuned zero-shot, and chain-of-thought baselines on several tasks picked to represent both algorithmic and non-algorithmic reasoning.\n\nExperimental results indicate that the proposed method outperforms the considered baselines across most tasks by a good margin.", "questions": "1. Did you try few-shot with the Alpaca (instruction-tuned) models that you used zero-shot in the paper?", "limitations": "The authors include a short statement to the effect that their models may make reasoning mistakes and the model artifacts are provided without any guarantees of safety. It might be worth including the fact that models may fail to execute generated code consistently, and thus generated code may be seen as an unfaithful explanation of model reasoning.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The proposed method appears to strike a nice balance between the rigidity of code-structured reasoning and freeform CoT, as it performs well across domains where CoT excels and ones where it struggles.\n- Being able to specialize reasoning for a particular task by selecting a pseudo-program is neat. It also appears to work well with a much smaller number of examples than are required to effectively fine-tune a model.\n- The authors do a very good job of proactively answering natural questions with their ablations in section 3.3.\n- As for clarity of exposition, all the writing is easy to follow and the paper is laid out intuitively.", "weaknesses": "1. The authors don't report statistical significance (e.g. through bootstrapping) or variance across runs with different subsamplings of training data.\n2. As far as I can tell, the reported experiments don't really include domains where the correct solution can be reached by actually executing a fully specified program, besides Number Summing (accordingly, a program-of-thought baseline is also missing). In CoGEX the model is responsible for simulating program execution, so it seems likely that it would underperform in these settings. While actually integrating an interpreter into a system that can still handle underspecified functions would be out of scope, it would be good to address this issue at the conceptual level somewhere in the text.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for the constructive feedback on our submission. We are glad that you found our approach neat, our ablations useful, and our writing clear. We aim to address your concerns below. \n\n> W1: The authors don't report statistical significance (e.g. through bootstrapping) or variance across runs with different subsamplings of training data.\n\nThank you for pointing this out, due to the limited time of the rebuttal, we will compute statistical significance of CoGEX against the baselines and add variance information to Figure 2 in the revision. \n\n> W2: As far as I can tell, the reported experiments don't really include domains where the correct solution can be reached by actually executing a fully specified program, besides Number Summing (accordingly, a program-of-thought baseline is also missing). \n\nThank you for this insight. As there is already much literature about generating correct programs (e.g., program-of-thought, PAL, etc.), we want to focus on tasks where this is less feasible. We therefore focus on tasks where it is hard to describe the reasoning in code (see line number L29-L32) and which will not benefit much from an interpreter. We will highlight the pros and cons of CoGEX compared to using an actual interpreter in the revision, as you suggested.\n\n> Q1: Did you try few-shot with the Alpaca (instruction-tuned) models that you used zero-shot in the paper?\n\nWe did, but found it to perform significantly worse than zero-shot. This is mainly due to that instruction tuning is zero-shot, i.e., the model is trained to generate output given the instruction and input without in-context examples. We will include a note describing this in the next version of the paper.\n\n> It might be worth including the fact that models may fail to execute generated code consistently, and thus generated code may be seen as an unfaithful explanation of model reasoning.\n\nThank you for noting this. We will include this in our limitations in the paper revision.", "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": "", "extra_scores": {}}, {"review_id": "ru4zfozGZq", "reviewer": "Reviewer_Hd75", "summary": "The proposed approach, Code Generation and Emulated Execution (COGEX), involves training LMs to generate pseudo-programs with some undefined functions and then emulate the execution of these programs. This allows the LM's knowledge to fill in the gaps while maintaining a program like reasoning framework. The COGEX model is adapted to new tasks through program search, optimizing performance across dataset instances. The approach shows improvements over standard in-context learning methods, demonstrating that code synthesis can be applied to a wider range of problems.", "questions": "(I asked majority of questions along with the listed weaknesses)\n- Typo in Figure 3 caption: “SocialIQa” -> “Social IQa”", "limitations": "- The author listed the limitations in the Appendix, which I would prefer doing in the main text. This also relates to the first listed weakness that I wrote: giving a proper overview would help people identify where and when your methodology could be applied.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The concept of pseudo-program and LLM emulation of program is interesting.\n- The authors evaluated the methodology on many different dataset and tasks.", "weaknesses": "I would consider raising my score if a fair number of the following weaknesses can be fixed by the authors. Many of them should be doable without extra experiments.\n\n- Motivation: While in general I like the idea of pseudo-programs, but I don’t think it is very well motivated or explained in the paper. For this relatively new concept to be introduced, I would like to see a more precise definition that describes each type of reasoning, whether its intuition based with no reasoning, “soft reasoning”, and exact reasoning. State clearly what task falls into the camp of “soft reasoning”.\n- Examples: I think the motivation is insufficient partly because of that the motivating examples (Fig. 1, 3, 10) do not seem to be requiring any “complex reasoning”. By “complex reasoning” I specifically mean things like composition of multiple sources of information, long range dependency of information, the use of logical operations like “and”, “or”, “not”, and “implies”, and etc.\n- Task/Dataset selection: (also related to previous points) I would want some more clarification on why the authors pick the presented tasks and datasets. What makes these dataset special so that COGEX can be applied to them? What additional conceptual benefits do COGEX bring to them? This will also help motivate the methodology you proposed.\n- Formalization: the symbol $f$ for COGEX model is unnecessarily abused. It can be invoked with either 2 or 3 arguments, which does not type check as a well-defined formalization. You should at least create two separate symbols, such as $f_{\\text{reasoner}}$ and $f_{\\text{enumlator}}$.\n- Algorithm: The while loop in line 7-10 of Algorithm 1 does not seem to have termination guarantee. This is a potential flaw in the algorithm. What if the task and dataset is malformed and there exists no proper pseudo-program? Your algorithm should account for this.\n- Comparison to GPT-4: I don’t want to suggest to do new experiments with GPT-4 as baselines, but I do want clarification on why GPT-4 is not used as a zero-shot baseline. I see that authors use GPT-4 to generate datasets used for training. So it’s definitely not the case that authors do not have access or hardware/financial limitations for doing so. Then why isn’t GPT-4 used as a baseline? I would assume that GPT-4 without training can still be used to synthesizing pseudo-programs, right?\n- Claim in the experimental results: authors describes Fig.4 as “Figure 4 (blue vs gold) shows that CoT… can approach COTACS performance on some NLP classification tasks but generally performs substantially worse.” But to me when looking at Fig.4, I don’t see this claim accurate. I can only see significant difference on CoinFlip and Number Summing.\n- Experimental setting: (related to the previous point) the direct comparison with zero-shot CoT might not be fair because your model has undergone fine-tuning, right?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your elaborate review and feedback on our submission. We aim to address your concerns below: \n\n> Motivation: While in general I like the idea of pseudo-programs, but I don’t think it is very well motivated or explained in the paper. For this relatively new concept to be introduced, I would like to see a more precise definition that describes each type of reasoning, whether its intuition based with no reasoning, “soft reasoning”, and exact reasoning. State clearly what task falls into the camp of “soft reasoning”.\n\nWe define pseudo-programs in L7-8 and L29-34, mainly as programs with one or more leaf functions left undefined. While ours is not a formal definition, we believe it should be sufficient for the scope of our paper. As for “soft reasoning”, it refers to tasks whose solution is difficult to fully describe in code. We agree with your feedback here, and we intend to give a more concrete definition of it in future revisions. \n\n> Examples: I think the motivation is insufficient partly because of that the motivating examples (Fig. 1, 3, 10) do not seem to be requiring any “complex reasoning”. By “complex reasoning” I specifically mean things like composition of multiple sources of information, long range dependency of information, the use of logical operations like “and”, “or”, “not”, and “implies”, and etc.\n\nMany of the tasks we work with require a level of multi-hop reasoning. For example, solving SVAMP requires multistep aggregation of math operations, as in the following example:\n\n```\nRobin has 28 packages of gum and 14 packages of candy. There are 6 pieces in each package. How many pieces does Robin have?\n\nSolution: ( ( 28.0 + 14.0 ) / 6.0 )\n```\n\nAlso, CSQA requires understanding multiple commonsense relations between entities as in the following entities:\n```\nThe teacher told all the students that listening was key, it was the main way they would gain what? [ \"empathy\", \"anxiety\", \"knowledge\", \"falling down\", \"hear things\"]\n ```\nYou are right that we didn’t consider tasks targeting e.g., discrete logical operations. However, the **key contribution of our work is not to push the boundary of complex reasoning that LLMs can do, but to show that code generation can be utilized to solve NLP tasks whose solution cannot easily be described in code**, and we show on a variety of standard reasoning benchmarks that are commonly used in the literature.\n\n\n> Why the authors pick the presented tasks and datasets. What makes these dataset special so that COGEX can be applied to them? What additional conceptual benefits do COGEX bring to them?\n\nWe chose these particular datasets to get a representative sample of different categories of NLP tasks currently of interest to the community (e.g. typical classification like SST/emotion, commonsense QA tasks (CSQA, SIQA), math (SVAMP) etc. There is nothing particularly “special” about these datasets except for the fact that a shared \"plan,\" expressible as a discrete pseudo program, can be readily applied to all the different data points for the given task.  We drew a number of them from recent work on code generation, e.g. the text classification tasks from [[1](https://aclanthology.org/2024.findings-naacl.259.pdf)]. \n\n> Formalization: the symbol 𝑓 for COGEX model is unnecessarily abused. [...] You should at least create two separate symbols, such as 𝑓reasoner and 𝑓emumlator\n\nThanks for pointing this out; we agree that it would be clearer to create two separate symbols and will modify the paper accordingly\n\n> Algorithm: The while loop in line 7-10 of Algorithm 1 does not seem to have termination guarantee. This is a potential flaw in the algorithm. What if the task and dataset is malformed and there exists no proper pseudo-program? Your algorithm should account for this.\n\nThank you for this insightful observation. We apologize for overlooking this case and will modify the algorithm accordingly in the revision. \n\n\n> why isn’t GPT-4 used as a baseline? I would assume that GPT-4 without training can still be used to synthesizing pseudo-programs, right?.\n\nOur concept of pseudo-programs is agnostic to the synthesizer model used. Indeed, GPT-4 can be used to synthesize pseudo-programs at test time, but also can smaller, less expensive LLMs as we show. Whether GPT-4 can produce more expressive pseudo-programs at test time compared to our fine-tuned models is unclear and would need additional experiments to verify. In addition, the relatively cheap inference of smaller models enables us to perform our program search during training to find an optimal pseudo-program for a given dataset/task.\n\n> When looking at Fig.4, I don’t see this claim accurate. I can only see significant difference on CoinFlip and Number Summing.\n\nThank you for the observation. We apologize for this mistake, and we will revise to make it clear that CoTACS substantially outperforms CoT on Summing, SVAMP, and CoinFlip.\n\n> Experimental setting: (related to the previous point) the direct comparison with zero-shot CoT might not be fair because your model has undergone fine-tuning, right?\n\nZero-shot CoT refers to the way the model is prompted i.e., without in-context examples and using “Let’s think step-by-step” in the instruction. But just like our models are fine-tuned on the CoGEX data, the baseline is finetuned on the original Alpaca dataset before prompting. So the comparison is fair. \n\n> The author listed the limitations in the Appendix, which I would prefer doing in the main text. This also relates to the first listed weakness that I wrote: giving a proper overview would help people identify where and when your methodology could be applied.\n\nThank you for this observation. This was due to the page limit, but we will make sure to move the limitations section to the main text as you suggested. \n\n\nWe hope we have addressed all your concerns. Please let us know if you have any more concerns or questions.", "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": "", "extra_scores": {}}, {"review_id": "SajQXPcokU", "reviewer": "Reviewer_KtaJ", "summary": "In this paper, the authors present a fine-tuned LLM that reasons by generating pythonic code and executes it through the model rather than passing it to an external interpreter (CoGEX). They also use the model to generate a set of candidate programs from a training set, among which the top-k performing programs are selected and subsequently used to evaluate the test set (CoTACS). The model shows improved performance on several datasets against benchmark models without the pretraining, including with in-context learning and chain-of-thought reasoning. Several additional analyses are provided for model efficacy, including the number of training items and sampled programs.", "questions": "1. (Table 1): Could you define what BM25 means? It wasn’t clear to me from the paper exactly how you performed the benchmarks and how you chose the benchmark settings to ensure fair comparison.\n2. (Line 91): What does silver-quality mean?\n3. (Table 3 and Figure 2): It wasn’t clear from the paper whether the model generated meaningfully different programs. Footnote 3 (from Line 231) suggests that the model likely generated very similar outputs (assuming lower temperature means more deterministic outputs).\n4. (Line 103): Few questions about ‘fuzzy’ premitives. \n    A. Does the model come up with its own fuzzy primitive operations, or do they all need to be predefined by the engineer or GPT4? \n    B. How did you determine what level of granularity was appropriate for the dataset? \n    C. Does the model ever produce fuzzy primitives that were not included in the dataset by GPT4 and if so, how does the model deal with it? \n5. (Line 187) Could you provide the actual SD or the 95% interval?\n6. (Figure 2) Could you include baselines for these tasks, e.g. results from the off-the-shelf Llama-2 13B on these problems. (It’s hard to tell if the linear trends are misguiding for me or not because the x-axis is in log-scale while the y-axis is in raw percentages. Logit-scale for y-axis could potentially be more informative.)\n7. (S3.4) Do you observe instances where the generated program is incorrect but the model still gets the problems correct? In other words, does the model actually follow the incorrect program or does the model ignore it?", "limitations": "The authors provide no guarantee of safety (this is acknowledged in the supplements), but not addressed.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "1. Paper is well-written and easy to follow. All the analyses and results are clearly presented.\n2. The CoGEX model provides a useful datapoint on understanding how well LLMs can benefit from program-like planning without relying on an external program interpreter.\n3. Allowing the model to use ‘primitive’ functions that are difficult to define programmatically offers greater flexibility than relying on interpreters and the ability to query for factual information.", "weaknesses": "1. The ideas do not strike me as particularly novel. As noted in the paper, using LLMs to generate code is not new, and neither is using language models to simulate program executors. CoTACS is simply a top-k search.\n2. It isn’t clear to me what advantage this method has over just passing the code to Python Interpreter. Moreover, what advantage is there to using CoGEX to just using GPT4 given that the dataset was created using GPT4 in the first place?\n3. While I appreciate the completeness of the presented results (for the sake of good science), even for experiments where the improvements are marginal, the results are often marginal at best, and it is unclear in what circumstances this approach is favorable and when it is not. Likewise, the authors use 0-shot CoT as their comparison model (Line 236), which is the weakest CoT baseline possible. Given that using an actual program interpreter is a viable alternative, I would be hesitant to adopt CoGEX without having a clearer understanding of when it outperforms simpler alternatives. In my opinion, the paper would strongly benefit from the following:\n    A. A fair comparison with CoT, either controlling for the number of examples or showing at how many examples the models achieve parity. Since this is the simplest thing to try for most ML practitioners, even parity would have me favor CoT over most alternatives.\n    B. A comparison, if applicable, to actual interpreters (e.g. Python). If this is not possible (e.g. due to calls to undefined functions), how often is that the case? Alternatively, if the model was forced to use predefined functions, how much better is it to use undefined functions?\n    C. I really was hoping for a more extensive Qualitative Analysis section (S 3.4) to get a better understanding of when CoGEX strongly outperforms the baselines. The results in Table 1 demand too much prior knowledge about the individual tasks/datasets from the readers without some guidance on how to think about them.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate your feedback on our draft. We are excited that you have found our approach useful and flexible. We aim to address your concerns below: \n\n> W1: The ideas do not strike me as particularly novel. As noted in the paper, using LLMs to generate code is not new, and neither is using language models to simulate program executors. CoTACS is simply a top-k search.\n\nThis work shows how a code execution approach can be applied to a significantly broader class of tasks than previously considered. Generating code with LMs is indeed not novel, but to date has been limited to algorithmic tasks that can be easily expressed programmatically. **Our key contribution is to extend this approach to more complex tasks where a full, programmatic implementation is difficult or infeasible** (e.g., requires commonsense). Our novel solution is to generate partial (pseudo-)programs: while these cannot be directly executed, we find that LLMs can simulate their execution, including filling in gaps for calls to complex functions that would have been difficult to implement in code.\n\n> W2: It isn’t clear to me what advantage this method has over just passing the code to Python Interpreter.\n\nSince the generated code represents pseudo-programs that include undefined functions, **passing the code to an interpreter will not work**. Therefore, we rely on the LLM to emulate code execution. As for using GPT-4, it can indeed be used to synthesize pseudo-programs at test time, but also can smaller, less expensive LLMs as we show. Whether GPT-4 can produce more expressive pseudo-programs at test time compared to our fine-tuned models is unclear and would need additional experiments to verify. The relatively cheap inference of smaller models enables us to perform our program search to find an optimal pseudo-program for a given dataset/task. \n\n> W3.1: the results are often marginal at best.\n\nCoGEX shows substantial improvements compared to the baselines over most of the tasks we consider e.g., CoLA (+8.6), CoinFlip (+12.4), WSorting (+6.1), CSQA (+18.2), etc. Our results highlight how CoGEX can provide an effective alternative to the baselines for reasoning such as vanilla CoT. \n\n> W3.2  the paper would strongly benefit from a fair comparison with CoT..\n\nThe main obstacle here is that all the datasets we experiment with do not provide ground-truth CoT in their training data. However, our 2-shot BM25 baseline is a fair comparison since it has access to the same number of examples as CoGEX.\n\n> W3.3 . B. A comparison, if applicable, to actual interpreters.\n\nIt would not be possible to use actual interpreters, since almost all the generated pseudo-programs include at least one call to an undefined function. In addition, many of the tasks we evaluate on such as Social QA and Commonsense QA involve soft reasoning that can not be described in code.  \n\n> W3.4 if the model was forced to use predefined functions, how much better is it to use undefined functions?\n\nPredefined functions require precise reasoning, while our work tackles soft reasoning that cannot be easily described in code.\n\n> W3.5 C. A more extensive Qualitative Analysis section (S 3.4) to get a better understanding of when CoGEX strongly outperforms the baselines.\n\nWe include a high-level overview of the tasks/datasets we cared about in L147-160. We will add extra info and examples from each dataset in the Appendix to help with this in the revision. Also, based on your suggestion, we will include a more detailed qualitative analysis of CoGEX vs. the baselines.\n\n> Q1: (Table 1): Could you define what BM25 means?\n\nBM25 is a ranking algorithm which we use to retrieve similar examples from the training data to use as in-context examples. Retrieval is common to boost in-context learning by using examples that are similar to the input as demonstrations [[1](https://arxiv.org/abs/2101.06804)]\n\n> Q2: Line 91): silver-quality\n\n\"Silver quality\" typically refers to data that is of good but not perfect quality. It is a step below \"gold quality\" data, which is considered to be the highest quality and typically manually annotated by human experts.\n\n> Q3: Footnote 3 (from Line 231) suggests that the model likely generated very similar outputs (assuming lower temperature means more deterministic outputs).\n\n​​In L231, we say that we sample with temperature=0.05 only with the end-to-end model. With search, we use T=0.7 as indicated in L165.\n\n> Q4.1: Does the model come up with its own fuzzy primitive operations?\n\nIndeed, after training, the model learns to generate its own primitives based on the input. \n\n> Q4.2: How did you determine what level of granularity was appropriate for the dataset? \n\nWhen constructing our training data, GPT-4 handles determining the appropriate granularity for the Alpaca data. Our trained models then learn to generate programs of appropriate granularity based on the input instance. We further apply search to find an optimal program (and granularity) for a given task. \n\n> Q4.3: C. Does the model ever produce fuzzy primitives that were not included in the dataset by GPT4?\n\nCertainly, the model learns to generate appropriate primitives based on the provided task instance. Based on our observations and analysis, the LM can generate and emulate novel primitives not seen in the training data.\n\n> Q5: (Line 187) Could you provide the actual SD or the 95% interval?\n\nWe will add this information in the revision. \n\n> Q6: (Figure 2) Could you include baselines for these tasks, e.g. results from the off-the-shelf Llama-2 13B?\n\nWe will add a line to the plots to show the baseline performance for each task. \n\n> Q7: (S3.4) Do you observe instances where the generated program is incorrect but the model still gets the problems correct?\n\nYes, this sometimes happens, especially for tasks with binary output such as Coin Flip. However, we observe that the model mostly follows the program logic, which we verified by looking at the generated intermediate outputs.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: Thanks to the authors for submitting this work and engaging in the rebuttal period. I found that the paper introduced an innovative approach that balances code-based reasoning and thought-style reasoning by adopting more pseudo-program structures. This is a more relaxed approach to facilitate better reasoning with LLM while not requiring fully specified programs and corresponding program interpreters. The authors conducted comprehensive experiments and reported strong results with insightful ablation analysis. 

As noted by the reviewers, there are some minor issues found: (1) the approach might not perform as well in domains where exact/hard reasoning steps are more effective i.e. where the actual execution of a full program will lead to the correct output; (2) second, some experimental results demonstrate only marginal performance gains of the proposed method. 

Overall, I recommend accepting this paper and hope the authors will continue to improve the paper according to the above-mentioned points and other feedback from reviewers.
Decision: Accept (poster)