Synthesizing Libraries of Programs with Auxiliary Functions
Authors: Habibur Rahman
Thirupathi Reddy Emireddy
Kenneth Tjhia
Elham Parhizkar
Levi Lelis
Venue: Accepted by TMLR ()

Abstract: A common approach to program synthesis is to use a learned function to guide the search for a program that satisfies the user's intent. In this paper, we propose a method that offers search guidance, through a domain-dependent auxiliary function, that can be orthogonal to the guidance previous functions provide. Our method, which we call Auxiliary-Based Library Learning (Aulile), searches for a solution in the program space using a base algorithm. If this search does not produce a solution, Aulile enhances the language with a library of programs discovered in the search that optimizes for the auxiliary function. Then, it repeats the search with this library-augmented language. This process is repeated until a solution is found or the system reaches a timeout. We evaluate Aulile in string manipulation tasks. Aulile improved, in some cases by a large margin, the performance of several base algorithms that use different search and learning strategies: Bus, Bustle, Crossbeam, and Bee Search. Our results suggest that Aulile offers an effective method of injecting domain knowledge into existing systems through a library learning scheme that optimizes for an auxiliary function.

Published in Transactions on Machine Learning Research (04/2024)
Synthesizing Libraries of Programs with Auxiliary Functions
Habibur Rahman
habibur@hulbertta.cc
Amii, Department of Computing Science, University of Alberta
Thirupathi Reddy Emireddy
emireddy@ruabertt..c
Amüi Deportment of Computing Science, University Alberta
Kenneth Tjhia
tjhia@halberto.cor
Amii, Deportment of Computing Science, University of Alberta
Elham Parhizkar
parhizka@Qualeetta.cc
Amii, Department of Computing Science, University of Alberta
Levi H. S. Lelis
levi, weabbs@aarerrr....mm
Amiū, Depertment of Computing Science, University of Alberta
Reviewed on OpenReview: https: openreview. net/ farum? id= tPIPBrMULX
Abstract
common approach to program synthesis to use a learned function to guide the search for a program that satisfies the user's intent. In this paper, we propose a method that offers search guidance, through a domain-dependent auxiliary function, that can be orthogonal to the guidance previous functions provide. Our method, which call Auxiliary-Based Library Learning (AULILE), searches for solution in the program space using base algorithm. If this search does not produce solution, AULILE enhances the language with library of programs discovered in the search that optimizes for the auxiliary function. Then, it repeats the search with this library-augmented language. This process is repeated until a solution found or the system reaches a timeout. We evaluate AULILE in string manipulation tasks. AULILE improved, in some cases by a large margin, the performance of several base algorithms that use different search and learning strategies: BUS, BUSTLE, CROSSBEAM, and BEF SEARCH. Our results suggest that AULILE offers effective method of injecting domain knowledge into existing systems through library learning scheme that optimizes for an auxiliary function.
1 Introduction
There increasing interest in the discovery of programmatic hypothescs, i.c., hypotheses encoded as pro- grais written in domain-specific language (Ellis et al., 2023 Singh & Gulwani 2015p. Depending on the language used, these hypotheses cation (Bastani et al. )018), and generalize to unseen scenarios (Inala et al. 2020). The key difficulty in synthesizing such hypotheses is the size of the space of the programs. In addition to being large, the program space often discontinuous, making it difficult. to use gradient descent-based optimization algorithms.
be interpretable (Medeiros al.] 2022). , more amenable to verifi-
A popular solution speed up the synthesis process of programmatic hypotheses to learn functions guide the search of algorithms such Bottom-Up Search (BUS) (Albarghouthi et al.) 2013 [ddpaa et al. 2013) and Tow-Down Search (Wang et al. 2017). BUSTLE (Odena et al.) 2021). PROBE (Brkee et. al. 2020

---

Published in Transactions on Machine Learning Research (04/2024)
and CROSSBEAM (Shi et al. 2022) enhance BUS with guiding function. In addition to learning guiding function, DREAMCODER (Ellis et al. 2023) also learns a library of programs while solving a set of training tasks. DREAMCODER uses a compression scheme to learn a set of programs that can be reused as part of other hypotheses. Despite all these advances, depending on the size of the programmatic solution, existing methods still struggle to synthesize effective programs.
BEE SEARCH (Ameen & Lelis 2023;
In this paper, we consider the scenario in which one is able to encode domain knowledge through an auxiliary function that can be helpful in guiding the search for programmatic hypotheses. We use the auxiliary function to learn spec-ii libraries of programs. That is, instead of learning libraries of programs for problem domain, like DREAMCODER does, we learn a library of programs by scarching for solution to a specific task. We use a base synthesizer to search for a solution to the task. If the search is not successful, we augment the language with the program encountered in the search that optimizes for the auxiliary function, i.e., the program becomes a function in the language. The search for a solution is then repeated with the augmented language. Since the program added to the language can be used through a simple function call, the second search might still not solve the problem, but it may find yet another program that uses the program inserted into the language in the previous iteration that better optimizes the auxiliary function. We hypothesize that the auxiliary function will guide the search through sequence of augmentation steps that transforms the synthesis of a complex solution into an easy task, where the last search of the base synthesizer combines the programs added to the language. We refer to this process as Auxiliary-Basee Library Learning (AULIIE).
We also hypothesize that, since the auxiliary function is likely different from previously learned guiding functions, AULILE can provide search guidance that is orthogonal to that provided by existing functions. That is, using an auxiliary function can increase the number of problems existing systems can solve. To test this hypothesis, we used AULILE to augmeett BUS, BUSTLE, BEE SEARCHI, and CROSSDEAM in string ma- nipulation tasks {Alur et al. 2013 Odena et al. 2021). AULILE improved the performance of all synthesizers in terms of the number of tasks solved, in some cases by a large margin, thus supporting our hypothesis.
The empirical results we present in this paper suggest that AULILE offers an effective way to inject domain knowledge into the synthesis of programmatic hypotheses. The results also suggest future directions for systems learning how to guide the search in programmatic spaces, as simple auxiliary function can already improve the performance of existing systems; would learned auxiliary functions provide even better guidance?
Our implementation is available online! T
2 Problem Formulation
In program synthesis, one searches the space of programs defined by a domain-specific language (DSL), which is provided in the form of a context-free grammar g. The DSL includes a set of non-terminals (V), terminals (E), and relations (R) that define the production rules and the initial symbol of the grammar (I). Figure D (left) illustrates a DSL where V = {1}: Σ {<, i..,..... ik, concat, replace), and R defines the production rules (c.g. I <) A production rule with at least one non-terminal symbol on the right-hand side is referred lo as non-terminal, while production rule with no non-terminal symbols on the right-hand side is referred to as terminal. The set of programs G accepts defines the program space. For instance, the program replace(concat(( >), <, >) is accepted by G: we start with I and replace it with replace II) then we replace the leftmost with concat(I, I), the middle non-terminal I with <, and the rightmost non-terminal with >, etc.
Programs are represented as abstract syntax trees (ASTs). Figure Figure[rright) (right) illustrates the AST of the program replace(concat(s, >), <, >). Every node in the AST represents production rule. For example, the root of the AST in Figure 1 represents I + replace(T, T). Nodes representing a non-terminal rule have a number of children corresponding to the number of non-terminal symbols in the rule. Nodes corresponding to terminal rules are leaves in the AST. Note that each subtree in the AST represents program. A subtree rooted at a child of node p is referred to as a subprogram of p. For instance, concat(<, >), <, and are subprograms of replace(concat(4 >), <, >).
https://github..cm/llliess
2

---

Published in Transactions on Machine Learning Research (04/2024)
replace
I < 1 12 1a....11 is | concat([T 1) replace(7,
concat
Figure 1: DSL and AST for replace(concat($5 <,>),
A program synthesis task consists of DSL G, set of imputs I { In): and set of outputs O = (Or....,On). Here, each input I; and output O, can each represent a set of values. The goal is to find a program E G that correctly maps each input set to its corresponding output set, p(4:) = O,, for i= .I...,n.. n. For example, concat(i, i2) solves I = {[<, >], >><,>>,,>,>)) and O = {[>). |>>>] [>>}] where i1, and i2 are the input values associated with each input 4,
3 Base Synthesizers Used in Our Study
In this section, describe the synthesizers used in our augmentation study: bottom-up search (BUS) (Al- barghouthi et al. 2013 Udupa et al., 2013), BUSTLE (Odena et al.) 2021), BEE SEARCH (Ameen & Lelis 2023), and CROSSBEAM (Shi et al.J 2022). All synthesizers used in our experiments are based on the BUS algorithm. We chose to use these methods because they represent the current state of the art and all repre- sent improvements over BUS through a Iearned guiding function. By using our augmentation method with all of them, we can measure how much our enhancement can improve existing methods from the literature, i.e., how much the guidance of our approach orthogonal to the guidance of existing approaches.
In the following sections, we describe the synthesizers used in our study in level of detail that allows the reader to understand how the augmentation approach is implemented in each of them. We refer the reader to the original papers of each method for more detailed description of the approaches.
3.1 Bottom-Up Up Search (BUS)
BUS incrementally builds programs of increasing size. The process begins by generating all programs defined by the terminal symbols of the DST, which have size 1 in terms of the number of nodes in the program' 's AST. Then, using the programs of size 1, BUS generates the programs of size 2 by applying the production rules. This process continues using the programs of sizes and to generate programs of size 3, and so on. The search stops when a program generated that can map the inputs to the outputs the task.
Consider a scenario in which we need to synthesize a program that produces the output ><> with the DSL of Figure D (left). The of inputs for this task is emply and a solution concat(concat(>, <), >). To find the solution, BUS begins by generating and evaluating all programs of size 1, which are and in this case. Since neither of these programs correctly generates the output, BUS proceeds to generate the set of programs of size 2, which is empty in this example, because the programs of size cannot be combined into programs of size 2 in this DST. Next, BUS generates all programs of size 3, including concat(<, <), ..., concat(>, >). This process continues until the correct program is generated. This example illustrates how BUS performs a systematic search to find a solution by increasing the size of the programs generates.
One of the key features of the synthesizers we in our study is their ability to perform observational- equivalence checks. If Pı and P2 produce the same outputs for all inputs in I, we can keep pl P2 and discard the other. Observationnlleqquiill can dramatically reduce the size of the effective search space.
3.2 Bustle
BUSTLE performs cost-guided bottom-up search. Instead of enumerating programs in terms of AST size, BUS does, BUSTLE enumerates them in terms of cost. Here, the cost of program is determined by
3

---

Similarly to BUSTLE'S w, Equation assumes that the cost of each production rule and that the wo-cost of program p is given by 1 plus the sum of the wy costs of the subprograms of p. The difference between BUSTLE'S w--fnction and Wo is that the latter penalizes programs p with P(p), the model's estimated Published in Transactions on Machine Learning Research (04/2024)
cost function, which in BUSTLE'S case is trained neural network. Cheaper programs deemed to be more likely to be part of a solution to the problem and are evaluated first in the search.
BUSTLE'S cost function employs a neural network to compute the likelihood that a program is subprogram of a solution program. The network receives the input-output pairs (Z, O) and the outputs p(I), I I, of a program and returns the probability that p is part of solution. This neural cost. function is determined through functions: and w'. Let p r(p..-.. . .Pk) be a program determined by the production rule whose k non-terminal symbols replaced by programs Pt:" " Pa: the w-value of p is computed as follows:
w(p)) 1
Σ w (p:).
The value 1 represents the cost of the rule and w/ wp:)) is the cost of the program pr given by the following:
w (p) w(p) + - 5(p))
(1)
where 8(p) ,0,...,5} is an integer that is based on the probability of p being part of solution. The value of 8(p) is computed by binning the probability value the model returns. BUSTLE uses the values in follows: if the probability returned by the model is within the first two values [0.0, 0.1), 5(p) 0, if it is within the second and third values [0.1, 8(p) = 1, etc. 8 penalizes p according to the probability the neural network assigns to p; lower probabilities result in higher costs.
{0.0, 0.1, 0.2, 0.3, 0.4, 0.6, 1.0}
3.3 Bee Search
BEE SEARCH also performs cost-based search in the space of programs. However, in contrast BUSTLE, it does not require the cost function to produce integer values. Ameen & Lelis 2023 introduced variant of the BUSTLE cost function, denoted We, which does not use the binning scheme to discretize the cost values:
wo(p) 1+ Σ wh (p.)
(2)
where,
o wu(ps) logz P(p:).
likelihood of p being part of a solution, and not with a scheme that bounds the penalty to at most. 5.
3.4 Crossbeam
Similarly to BUS, BUSTLE, and BEE SEARCH, CROSSBEAM keeps all generated programs in memory so it can perform obserratioonleequivaeeene checks. However, instead generating all combinations of existing programs with a production rule r BUS does, CROSSBEAM samples subprograms ps from the existing set of programs to determine which programs r(pi,... (pk) are generated and evaluated next in search.
CROSSBEAM trains model that receives all the programs generated in the search so far, the input-output pairs, and production rule the model produces a probability distribution over all the programs encoun- tered in the search Lo define what the programs should be that comprise the next program r.p to be evaluated. The sampling procedure for programs P, can be performed with Beam Search or Uni- qucRandomizer (Shi al., (2000). If the sampled program p observationalloquivallnn seen program, then p is discarded. Crossbeam iteratively goes through all production rules and samples programs r'p..... .Pk), until solution is found or the search times out.
previously
4

---

Published in Transactions on Machine Learning Research (04/2024)
Algorithm 1 AULILE
Require: Input-output pairs Z, O, DSL 9, auxiliary function a, base synthesizer Y, and a budget B
Ensure: Solution program p 1
1: while not timeouu. do
2: p. solved <- O,
3: if solved then
4: return P
g= UUp
6: return T
4 Auxiliary-Based Library Learning
Our language augmentation method based an auxiliary function, AULILE, is presented in Algorithm 1 We denote the augmented version of base synthesizer Y as A-Y. For example, the augmented version of BUS is denoted A-BUS. AULILE receives a problem specification through input-output pairs I and O, a DSL 9, an auxiliary function a, a base synthesizer Y, and a computational budget B. AULILE returns either a solution program or a failure signal 1 as output. AULILE repeatedly invokes the base synthesizer Y to explore the space of programs (line 2). Each search with Y is bounded by a computational budget B (e.g.- number of programs evaluated in the search). the base synthesizer finds a solution, then p represents this solution (line 4.. Otherwise, p represents the program encountered in the search that optimizes the auxiliary function in which case p is added to the language so that it can be used in the next iteration of the search.
The base synthesizer is configured to return program that was not added to the language in previous iterations of AULILE. Different base synthesizers handle the addition of to the language differently. We discuss how the synthesizers used in our experiments handle language augmentation in Sections 4.1 and 4.2 AULILE runs while there available time for synthesis.
4.1 A-BUS, A-Bustle, and A-Bee
The program p added to the language in A-BUS, A-BUSTLE, and A-BEE is treated non-terminal symbol of the type that returns. For example, if returns integer value, then it can be used operation that returns an integer. This means that all added programs have cost of 1 (size 1 in the context of BUS), so they are evaluated early in the search and can be more easily combined with other programs.
4.2 A-Crossbeam
In the context of CROSSBEAM, the program p used to augment the language is added to the initial set of programs explored by the search. When sampling the next program p' to be evaluated in the search, CROSSBEAM will be able to use p one of the subprograms of p' starting in the first itcration of the search.
The model CROSSREAM uses to create the probability distribution on existing programs is trained on-policy. This means that CROSSDEAM uses the distribution of programs seen during the search to solve training problems to train the model. Since the programs added to the language can be of arbitrary complexity, it is unlikely that the CROSSBEAM model has trained on search contexts similar to those A-CROSSBEAN induces (i.c. the set of existing programs might contain complex programs even in the first itcration of scarch). We empirically evaluate if CROSSBEAM's model able to generalize to the search contexts of A-CROSSBEAM.
Since CROSSBEAM uses sampling, it benefit from random restarts (Hoos & Stützle 2004]. That is, instcad of running the system with a computational budget of X program evaluations, if we use N random restarts, we would sequentially perform N independent runs of the system with budget of X evaluations each. Since A- CROSSBEAM implicitly performs random restarts, where in each restart it uses an augmented version of the language, it would not be clear from the results if performance improvements were
N program due to random restarts or augmentation. Therefore, we also use version of CROSSBEAM that uses random restarts without augmentation as baseline in our experiments, denoted by CROSSHEAM (N), where N > 1.
5

---

Published in Transactions on Machine Learning Research (04/2024)
P1 Pa(ag):
P2(arg):
arg. replace ("-", "")
P1(arg)
replace (".", "")
reppaaee(<",, "")
.replace
concat (">", "), "")
Input
P1's Output
Input
P2's Output
801-456-8765
8014568765
801-456-8765 <978> 654-0299 978.654.022
8014568765 9786540299 9786540299
<978> 654-0299
<9786540299
978.654.0299
97865402299
Figure2 2: Example of the augmentation process in a string manipulation task.
4.3 Example of A-BUS on the String Manipulation Domain
Consider the example shown in Figure 2 The table on the right-hand side represents both the input-output pairs of the lask and the oulput of a solution program, P2. Although the solution program is long and search algorithms such as BUS would not be able to find it due to computational limitations, A-BUS with a simple auxiliary function finds a solution, In the first itcration of A-BUS, adds to the language program P1, which does not solve the problem, but produces output strings that are closer to the output strings of the problem specification. Among all generated programs, P1 is the one that better optimizes the auxiliary function (defined in Section 5 In the next iteration, the solution P2 uses P1 subprogram.
4.4 Weaknesses of Aulile
The main weakness of AULILE is its requirement. of auxiliary function. In this paper, we evaluate search algorithms in string manipulation problems, for which there exists obvious auxiliary function the Levenshtein distance (see Section 5). However, there might be no obvious choices for other domains. Future work will investigale how one can learn auxiliary functions to augment the language. AULILE also inherits some of the weaknesses of its base synthesizer. For example, BUS algorithms are
and so will be AULILE if using a BUS algorithm as its base synthesizer. Stochastic local search algorithms (Husien) & Schewe 2016b Medeiros et al., 2022) can explore repeated programs because they do not keep a list of evaluated programs. AULILE will suffer from the same problem if using such algorithms as base synthesizer.
5 Empirical Evaluation
We evaluate AULIEE on string manipulation (Alur et al. 2013 Odena et al.] 2021] ) tasks, which one is given a set of input-output examples and needs to find a program that maps each input to its corresponding output. We use two datasets from Odena et al. (2021): one with 89 instances of the SyGuS competition and another with 38 handcrafted instances. We implemented the DST for string manipulation, as well as BUS and BUSTLE. We use the implementations of CROSSBEAM and BEE SEARCH provided by their authors.
We perform three sets of experiments. In the first set, we compare the base synthesizers with their augmented counterparts (Figures 3 and 4 We compare the algorithms terms of the number of problems solved by the number of programs evaluated. This because all algorithms use the same model as a cost function and thus have similar per-evaluation computational cost. In the second set, we compare the best performing systems of each experiment in the first set (Figure 5). Since the algorithms use different models, use running time instead of number of evaluations. This is to account for the complexity of the models employed. For example, CROSSBEAM uses a more complex and thus slower model than BUSTLE. We used 14 million programs evaluated as the budget B of AULILE for A-BUS, A-BUSTLE, and A-BRE.
In the third sot, we perform ablation studies. In AULILE, if the base synthesizer does not solve the problem, it adds to the language the program p with the best a-value that is different from the programs added in previous iterations of AULILE. We evaluate a version of A-BUS that adds to the language, in each iteration,
6

---

Published in Transactions on Machine Learning Research (04/2024)
the best k 2 programs that are different from the programs added in previous iterations, for & in (1,2.3) (Figure Gj. We also present results of A-BUS with auxiliary functions of varied strengths (Figure 7
The budget B is determined differently for A-CROSSUEAM due to the restarts we implemented with CROSS- BEAM. In the first set of experiments, given a computational budget X, which is denoted by the rightmost point on the x-axis of our plots, we present curves for runs of CROSSBEAM and A-CROSSREAM with differ- ent values of N. For given N, the algorithm restarts after N evaluations. For legibility, CROSSBEAM is abbreviated as CB and A-CROSSBEAM as A-CB in the plots; the values in brackets denote N. In the second set of experiments, we used 5 million evaluations B for A-CROSSBEAM. We use smaller budget with A-CROSSBEAM because, as we show below, the algorithm can benefit not only from the augmentation of the language, but also from search restarts due to its sampling process. This is in contrast to A-BUS, A-BUSTLE, and A- A-BEE, which are deterministic and thus tend to benefit from the largest possible B.
We plot the mcan and standard deviation over five independent runs for BUSTLE, A-BUSTLE, BEE SEARCH, A-BEE, CROSSBEAM, and A-CROSSBEAM because they depend on the random initialization of the weights of their neural models and also sampling in the case of CROSSBEAM and A A-CROSSBEAM. BUS and A-BUS are deterministie, therefore present the results of single run. We used 1 CPU at 2.4 GHz and 64 GB of RAM in all experiments; for BUSTLE, A-BUSTLE, BEE SEARCH, A- CROSSBEAM, and A-CROSSBEAM we also used 1 GPU, since they use a neural model.
Auxiliary Function We use the Levenshtein distance (Levenshtein] 1966. as the auxiliary function. The Levenshtein distance between two words is the minimum number of single-character edits (insertions, dele- tions, or substitutions) required to change one word into the other. The higher the distance, the greater the dissimilarity between the strings. The auxiliary function measures the sum of the distances between the output of a program p(4,) and its corresponding output O,, for all 4 E I. two or more programs have the same Levenshtein distance, we arbitrarily select one of them to be added to the language in Algorithm
5.1 Empirical Results: First Set
Figure shows the results for the SyGuS benchmark, while Figure shows the results for the 38 benchmark set. Each figure shows plot for base synthesizer: BUS, BUSTLE, BEE SEARCH, and CROSSBEAM. The y-axis shows the total number of solved problems, and the x-axis shows the number of programs evaluated. For example, A-BUS solves 87 problems after evaluating 5 x 10th programs. The line CB without brackets represents CROSSBEAM as presented in its original paper (Shi et al. 2022).
The auxiliary-based language enhancement. increased the number of problems solved by all base synthesizers evaluated on the SyGuS benchmark, often by large margin. For example, increased the number of problems BUS solved from 74 to 87. The results of CROSSBEAM show that not only the augmentation approach is effective, but also simply performing restarts already increases the number of problems the system can solve. Namely, CROSSBEAM M with no restarts solved average of 66.2 problems, while CROSSBEAM with 4 restarts solved an average of 69.0 problems. The best A- A-CROSSBEAM, A (B), solved an average of 75.6 problems. Improvements to the 38 benchmark problems are more modest than those observed on the SyGuS benchmark, but the augmented approach is never worse and sometimes superior (e.g., A-CROSSBEAM).
5.2 Empirical Results: Second Set
In Figure 5 wC compare the best performing algorithms from Figures and g in terms of running time, rather than the number of programs evaluated. We allowed the same computational budget in terms of running time (x-axis) for both SyGuS and the 38 benchmarks. Note that the results shown in Figure are not directly comparable to those shown in Figures 3 and 4 This is because the computational budget used in the first set of experiments can be different from the budget used in this set. This is particularly noticeable for A-CROSSBEAM, which uses a much smaller computational budget in Figure 4 than in Figure 5
The results show that A-BUSTLE and A-BEE are the best performing systems on the SyGuS benchmark, while A-CROSSBEAM is the best performing on the 38 benchmark. Interestingly, A-BUSTLE and A-BEE solved almost all instances of the SyGuS benchmark, and A-CROSSHEAM solved all instances of the 38
7

---

Published in Transactions on Machine Learning Research (04/2024)
SyGuS Benchmark
90
90
Problems Solved
82
82
%1.4
74
A-BUS
BUS
Bust
60
60
0
5x10
11x10
16x10
21x10*
0
5x10"
10x10"
15x10"
20x10²
Number of Programs Evaluated
Number of Programs Evalunted
90
77
A-CB(8)
CB(4)
A-CD(4)
CB(2)
Problems Solved
82
72-
A-CB(2)
CB
71.8
CB(()
60.0
75
68
07.8
16.6
16.2
67
64
A-Bee
Bee
60
60
0
6x10*
11x10*
17x10
23x10*
0
1x10
2x10
4x10
5x10
Number of Programs Evaluated
Number of Programs Evaluated
Figure Number of problems solved per number of evaluations on the SyGuS benchmark for four base synthesizers: BUS, BUSTLE, BEE SEARCH, and CROSSBEAM. This benchmark has 89 problems.
benchmark. These results suggest that the community may need more difficult string manipulation bench- marks. Although A-BUS is not the best performing system on the SyGuS benchmark, it is notable that it performs so well on this set of problems. While A-BUSTLE, A-BEE, and A-CROSSBEAM employ a neural model to guide the search, A-BUS simply relies on the uninformed search of BUS and the augmentation of the language with the auxiliary Levenstein function.
5.3 Empirical Results: Third Set
Figure f shows the results of A-BUS when it adds the best k programs to the language in each AULILE iteration, for k in {1, 3). The results on the SyGuS benchmark show that there is no variance in the number of problems solved for the small values small advantage for & 3, as A-BUS with that number solves problems, while solves 32 with k and k This experiment shows that AULILE is robust to small values of k in these benchmarks.
used in this experiment. The results on the 38 benchmark show
Figure 7 shows the number of problems A-BUS auxiliary functions of different strengths. We define different auxiliary functions that are based the Levenshtein distance. This is achieved with a parameter 0.0 < L 1.0. The value of 1 determines the percentage of the longest. of the two strings used to compute the distance. For example, for / = 0.50, we compute the Levenshtein distance considering only half of the characters of the longest the two strings. If 1.0, then this metric is exactly the Levenshtein distance. Values of 1.0 result weaker versions of the distance because it considers less information. As we weaken the auxiliary function by decreasing the value of I, A-BUS solves fewer problems, thus showing the importance of the auxiliary function used.
solve per number of programs evaluated when using
8

---

Published in Transactions on Machine Learning Research (04/2024)
38 Benchmark
36
Problems Solved
30
30.2
25
20
A-BUS BUS
Bust
15
0
1x10
2x10
3x10
5x10
0
4x10"
7x10
11x10"
15x10"
Number of Programs Evaluated
Number of Programs Evalunted
36
Problems Solved
30-
30.1
A-CB(S)
20
A-C((4)
CD(2)
A-Bee
A-C((2)
CB(8)
15
0
18x10
37x10*
55x10*
74x10*
0
1x10
2x10
4x10
5x10
Number of Programs Evaluated
Number of Programs Evaluated
Figure Number of problems solved per number of evaluations on the 38 benchmark set for four base synthesizers: BUS, BUSTLE, BEE SEARCH, and CROSSBEAM. This benchmark set has 38 problems.
SyGuS Benchmark
38 Benchmark
90
40
38.0
Problems Solved
82
$1.4
33
32.0
31.4
75
27
ABB
A-BUS
67
A Bustle
21
A Bustle
A-Boc
A-Boc
A-Creshhamm
A-Crossheam
60
15
2x10
4x10*
6x10*
9xc10
2x10
4x10
6x10*
9xc10
Running Time in Seconds
Running Time in Seconds
Figure 5: Number of problems solved per running time the SyGuS and the 38 benchmark sets for the best performing system for each base synthesizer, as shown in Figures 3 and 4
5.4 Discussion
The results of our experiments suggest that our auxiliary-based language augmentation approach offers search guidance that orthogonal to that provided by existing methods. This because it improved the results of BUSTLE, BEE SEARCH, and CROSSBEAM. While BUSTLE and BEE SEARCH use similar cost functions guide the search, CROSSBEAM uses an entirely different approach. The models of BUSTLE and BEE SEARCH are conditioned the problem to be solved, while CROSSBEAM's is conditioned not only on the problem,

---

Published in Transactions on Machine Learning Research (04/2024)
SyGuS Benchmark
38 Benchmark
89
35
87
Problems Solved
81
31
74-
27-
A-BUS (R 1)
A-BUS (A 1)
67-
A-BUS (e = 2]
A-BUS (A 2)
A-BUS (6 = 8)
23
A-BUS (A 8)
BUS
BUS
60
20
5x108
10x10*
15x10
19x10
1x108
2x10
4x10a
5x10
Number of Programs Evaluated
Number of Programs Evaluated
Figure 6: Number of problems solved per number of programs evaluated the SyGuS and the 38 benchmark sets for A-BUS with different number k of programs added to the language in each AULILE loop.
SyGuS Benchmark
38 Benchmark
89
35
83
Problems Solved
30-
30
77-
71
A-BUS (1= 1.00)
25
A-BUS (f= 1.00)
A-BUS [1= 0.75)
A-BUS (f= 0.78)
65
BUS (1= 0.50)
A- BUS (f= 0.50)
A BUS (1= 0.25)
A BUS (1= 0.25)
60
20
5xc10
10x10
15x10"
19x10*
Ix10
2x10
3x10
4x10
Number of Programs Evalunted
Number of Programs Evalunted
Figure 7: Number of problems solved per number of programs evaluated on the SyGuS and the 38 benchmark sets for A-BUS with an auxiliary function of different strengths, where / = 1.00 is the original Levenshtein distance; values < 1.00 represent weakened versions of the function.
but also on the search state (i.c., the set of programs evaluated in search). Despite these differences, our augmented approach improved the results of all three systems, in addition to the uninformed BUS.
6 More Related Works
The challenge of synthesizing computer programs that meet a given specification has been widely discussed in the field of Computing Science (Manna & Waldinger
1971
Summers) 1977), drawing significant attention
from rescarchers in Artificial Intelligence (Balog et al.
2016
Devlin et al. 2017a Kalyan et al. 2018 Ellis
et al. 2023 and Programming T Languages (Lee al.
2018
Barke et al. 2020 Ji al. 2020).
A variety of search methods have been investigated to solve synthesis tasks. One such method is to use constraint satisfaction algorithms, which convert the synthesis task into constraint satisfaction problem that can be solved with an SMT solver (Solar-Lezama) 2009). Additionally, synthesis tasks can be addressed using stochastic scarch algorithms, such as Simulated Annealing (Husien & Schewe 2016a. Medeiros et al. 2022), stochastic hill climbing (Aleixo & Lelis 2023), and genetic algorithms (Koza, 1992). In this paper, we evaluate the augmented approach with algorithms based on BUS, which are enumerative since they systematically evaluate a set of programs in the space defined by the DSL. Top-down search algorithms are also enumerative, but search in tree where the root is given by the initial symbol of the grammar defining the language; the children of node in the tree are given by the different ways of how non-terminal symbol
10

---

Published in Transactions on Machine Learning Research (04/2024)
can be replaced by other symbols of the grammar. The key disadvantage of top-down algorithms is that all internal nodes of the search tree are partial programs that cannot. be executed, thus only allowing weaker forms of equivalence checks (Lee et al.) 2018 Wang et al. 2017). The ability of removing observational- equivalent programs justifics our choice for BUS-like algorithms. However, our approach can be used with stochastic, top-down Chen et al. (2019); ; Zohar Woll (2018); Bunel el. al. (2018); Devlin et al. (201bb); Wang et al. (2017), and other bottom-up base synthesizers (Barke et al., 2020 Fijalkow et al. 2022]:
DREAMCODER also learns a library of programs, which involves compressing the programs used to solve set of training problems (Ellis al. 2023 Our method differs from DREAMCODER in important ways, First, DREAMCODER learns a library of programs for a problem domain given a set of training tasks. AULILE learns a library of programs for & specific task, without training tasks and no reuse of the library across tasks. Second, DREAMCODER learns a model to guide the search given a library of programs, while our approach either does not use a model to guide the search (e.g., A-BUS) or simply uses existing models without retraining for the learned library (e.g., A-BUSTLE, A-BEE, and A-CROSSBEAM).. DREAMCODER was exlended in two different ways. STTTCH is a search-based system aimed at improving the performance of DREAMCODER'S s compression system in terms of memory and rumning time (Bowers al. 2023). BABBLE improves the set of learned programs by considering the functionality of the programs despite their potential syntactical differences (Cao et al. 2023). AULILE differs from STITCH and BABBLE because it does not use compression to learn a library of programs, but uses an auxiliary function to learn a task-specific library.
7 Conclusions
In this paper, we introduced Auxiliary-Based Library Learning (AULILE), system that leverages a domain- specific auxiliary function to learn task-specific libraries of programs. AULILE uses base synthesizer to search for programmatic solution to a task; in the case of failure, AULILE adds to the language the program encountered in the search that best optimizes the auxiliary function. The search is then repeated with the augmented language. The augmentation and search steps are repeated until one of the following conditions met: the task solved, or the system reaches a time out. We evaluated AULILE on string manipulation tasks. Our results suggest that a simple auxiliary function offers guidance that is orthogonal to that provided by existing functions. This is because AULILE was able to improve the performance of all base synthesizers evaluated, in some cases by large margin. In general, our empirical results suggost that AULILE can offer an effective way to inject domain knowledge into the synthesis process.
A promising direction for future research is to investigate learning schema for the auxiliary function. We cnvision two dircctions for learning auxiliary functions. The first is to investigate the use of existing cost functions as auxiliary functions (Odena et al. 2021: Barke et al.) 2020). Can the cost function be used effectively to select the program that is added to the language AULILE? The second direction is to try to learn auxiliary functions that provide orthogonal information what existing cost functions provide.
Acknowledgments
This research was supported by Canada's NSERC and the CIFAR Al Chairs program, and was enabled in part by support provided by the Digital Research Alliance of Canada. The authors thank the reviewers for their helpful suggestions.
References
Aws Albarghouthi, Sumit Gulwani, and Zachary Kincaid. Recursive program synthesis. In International Conference Computer Aided Verification, CAV, pp. 934-950, 2013.
David S. Aleixo and Levi H.S. Lelis. Show me the way! Bilevel scarch for synthesizing programmatic strategies. Proceedings of the AAAI Conference on Artificial Intelligence, 37(4):4991 Jun. 2023. doi: 10. 10.1609/anai. v37/444.....34..2222 25626.. URL
aaai https///waw...a...a......aaaaaa/
11

---

Published in Transactions on Machine Learning Research (04/2024)
Rajeev Alur, Rastislav Bodik, Garvit Juniwal, Milo Martin, Mukund Raghothaman, Sanjit Seshia, Rishabh Singh, Armando Solar-Lezama, Emina Torlak, and Abhishek Udupa. Syntax-guided synthesis. pp. 1-17, 10 2013. doi:
Saqib Ameen and Levi H.S. Lelis. Program synthesis with best-first bottom-up search. Journal of Artificial Intelligence Research, 2023.
Matej Balog, Alexander I, Gaunt, Marc Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. Deepeoder: Learning to write programs. arXiv preprint wrXi::1611.01988 2016.
Shraddha Barke, Hila Peleg, and Nadia Polikarpova. Just-in-time learning for bottom-up enumerative
synthesis. Proceedings of the ACM on Programming Languages, 4(0OPSLA): 29, 2020.
Osbert Bastani, Yewen Pu, and Armando Solar-Lezama, Verifiable reinforcement learning via policy ex- traction. In Proceedings of the International Conference on Neural Information Processing Systems, pp. 2499 2509. Curran Associates Inc., 2018.
Matthew Bowers, Theo X. Olausson, Lionel Wong, Gabriel Grand, Joshua B. Tenenbaum, Kevin Ellis, and Armando Solar-Lezama. Top-down synthesis for library learning. Procedings of the ACM on Programming Languages, 7(POPL) 2023. doi: 10.1145/3571234 URL https://doi: w0g/10..///. 1145/3571234
Rudy Bunel, Matthew Hausknecht, Jacob Devlin, Rishabh Singh, and Pushmeet Kohli. Leveraging gram- mar and reinforcement learning for neural program synthesis. In International Conference on Learning Representations, 2018. URL https::/
David Cao, Rose Kunkel, Chandrakana Nandi, Max Willsey, Zachary Tatlock, and Nadia Polikarpova. Babble: Learning better abstractions with e-graphs and anti-unification. Procedings of the ACM on Pro- gramming Languages, 7(POPL) 2023, doi: 10.1145/3571207. URL https://doi. org/10001110000 1145/3571277
Xinyun Chen, Chang Liu, and Dawn Song. Exccution-guided noural program synthesis. In International Conference on Leurning Represenlations, 2019. URL http///pp///ggaereeeeeeee//////r
Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli. Robustfill: Neural program learning under noisy i/o. In International conference on machine learning, pp. 990 998. PMLR, 2017a.
Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel rahman Mohamed, and Pushmeet Kohli. Robustfill: Neural program learning under noisy i/o. In JCML, 2017b.
Kevin Ellis, Lionel Wong, Maxwell Nye, Mathias Sabl-Meyer, Lue Cary, Lore Pozo, Luke Hewitt, Armando Solar-Lezama, and Joshua Tenenbaum. Dreamcoder: growing generalizable, interpretable knowledge with wake-sleey sleep bayesian program learning. Philosophical Transactions of the Royal Sociely A: Malhemalical, Physical and Engineering Sciences, 381, 06 2023. doi: 10.1098/ N0.1098/rsta.2022. 202............... 0050..
Nathanaël Fijalkow, Guillaume Lagarde, Théo Matricon, Kevin Ellis, Pierre Ohlmann, and Akarsh Potta. Scaling neural program synthesis with distribution-based search. In AAAI, 2022.
H. H. Hoos and T. Stützle. Stochastic Local Search: Foundations & Applications. Elsevier / MMrgan Kaufmann, 2004. ISBN 1-55860-872-9.
Idress Husicn and Sven Schowe. Program generation using simulated anncaling and model chocking. Rocco De Nicola and Eva Kühn (eds.), Software Engineering and Formal Methods, pp. 155-171. Springer International Publishing, 2016a. ISBN 978-3-319-41591-..
Idress Husien and Sven Schowe. Program gencration using simulated annealing and model checking. In Rocco De Nicola and Eva Kühn (eds.), Software Engineering and Formal Methods, pp. 155-171. Springer International Publishing, 2016b. ISBN 978-3-319-41591-8.
12

---

Published in Transactions on Machine Learning Research (04/2024)
Jeevana Priya Inala, Osbert Bastani, Zenna Tavares, and Armando Solar-Lezama. Synthesizing program- matic policies that inductively generalize. In International Conference on Learning Representations, 2020. URL
Ruyi Ji, Yican Sun, Yingfei Xiong, and Zhenjiang Hu. Guiding dynamic programing via structural proba- bility for accelerating programming by example. Proceedings of the ACM on Progrumoing Languages, (OOPSTA):: -29 2020.
Ashwin Kalyan, Abhishek Mohta, Oleksandr Polozov, Dhruv Batra, Prateek Jain, and Sumit Gulwani. Neural-guide doductive search for real-time program synthesis from examples. In International Conference on Learning Represenlations, 2018.
J. R. Koza. Genelic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge, MA, 1992.
Woosuk Loe, Kihong Hco, Rajecv Alur, and Mayur Naik. Accelerating search-based program synthesis using learned probabilistic models. ACM SIGPLAN Notices, 53(4):436 449, 2018.
Vladimir Levenshtein. Binary codes capable of correcting deletions, insertions, and reversals. In Soviet physics doklady, pp. 707-710. Soviet Union, 1966.
Zohar Manna and Richard J Waldinger. Toward automatic program synthesis. Communications of the ACM, 14(3):151 165, 1971.
Leandro C. Medeiros, David S. Aleixo, and Levi H. S. Lelis. What can we learn even from the weakest? Learning sketches for programmatic strategies. In Proceedings of the AAAI Conference on Artificial Intelligence. AAAT Press, 2022.
Augustus Odena, Kensen Shi, David Bieber, Rishabh Singh, Charles Sutton, and Hanjun Dai. BUSTLE: Bottom-up program synthesis through learning corning-guidedd guided exploration. In International Conference on Learn- ing Represenlations, 2021. URL httpps://operreviex. httpp/reww....eeeeoooor/r//raaaa
Kensen Shi, David Bieber, and Charles Sutton. Incremental sampling without replacement, for sequence models. In International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 8785-8795, PMLR, 2020.
Kensen Shi, Hanjun Dai, Kevin Ellis, and Charles Sutton. Crossbeam: Learning to search in boltom- up program synthesis. In International Conference on Learning Representations, 2022. URL https: //openreview wwt.:/ooummidddggeeeeee...
Rishabh Singh and Sumit Gulwani. Predicting a correct program in programming by example. In Interna- lional Conference on Compuler Aided Verification, pp. 398 41444 Springer, 2015.
Armando Solar-Tezama. The sketching approach to program synthesis. In APLAS, 2009.
Phillip D Summers. A methodology for lisp program construction from examples. Journal of the ACM (JACM), 24(1):161-175, 1977.
Abhishek Udupa, Arun Raghavan, Jyotirmoy V Deshmukh, Sela Mador-Haim, Milo MK Martin, and Rajeev Alur. Transit: specifying protocols with concolic snippets. ACM SIGPLAN Notices, 48()) 296, 2013.
Xinyu Wang, Isil Dillig, and Rishabh Singh. Program synthesis using abstraction refinement. Proceedings of the ACM on Programming Languages, 2(POPL., 2017. doi: 10.1145/3158151. URL htttp:://oo..rrg 10. 1e111/155581511
Amit Zohar and Lior Wolf. Automatic program synthesis of long programs with learned garbage collector. CoRR, http/8809.0465 2018. URL http://rrr...rrr//b////000.000 04682
13

---

Published in Transactions on Machine Learning Research (04/2024)
SyGuS Benchmark
38 Benchmark
Prohlem Solved
31
52
80
A- BUS
BUS
29
A-BUS
BUS
10
12
Number of Iterations
Number of Iterations
Figure 9: Number of problems solved per number of iterations of A-BUS. BUS is shown with flat horizontal line because it does not perform language augmentation.
A Appendix
A.1 DSL for String Processing Domain
Expression,
I
String expression, S
Concat(S1, Left(S, I)
(Sght((S,)) Substr 11,
Replace (S, /1, I2, 52) Trim(S) Repeat(S, Substitute(S1, $2,
Substitute S2, S3, I) [oText([] LowerCase(5) UpperCase(S)
ProperCase(S) T
I, $1,
Integer expression, I
11 + 12 /1 12
(S1, Find I) Len(S)
Boolean expression, B
Equals(S1, S2)
Greater GreaterThan[II
Greater SaatteeraanOEEuaaTo///oo
String constants, T
am
4?"
"("
"<"
6m
66
4
" "#"
4.8
6.
" "
"%" "
"0"
string constants extracted from I/O examples
Integer constants, J
0 3
99
Input, X
21 2%
Figure 8: DSL considered for the string manipulation domain.
A.2 Problems Solved Iteration of Language Augmentation
Figure shows the cumulative number of problems A-BUS can solve in each iteration of the search for both the SyGuS and the 38 benchmarks. Although most of the problems are solved in the first iteration of the search (72 for SyGuS and 28 for the 38 benchmark), many problems are solved with more iterations. particular, one the problems the SyGuS benchmark is solved after 10 iterations of the AULILE's language augmentation loop. We note that the number of problems solved in the first. iteration of A-BUS does not match the number of problems BUS solves due to the limitation of A-BUS's budget each iteration of A-BUS is limited to evaluating 14 million programs, while the only iteration of BUS evaluates 2.1 billion programs. The gap we observe between A-BUS and BUS (87 versus 74 problems solved) highlights the advantage of augmenting the language with programs that optimize the score of the auxiliary function.
A.3 Aulile's Average Program Size
Figure 10 shows the average program size of the solution program that A-BUS finds different language augmentation iterations. The average program size, terms of the number of nodes in the AST of the program, is calculated for all solution programs encountered in given iteration of A-BUS. The plot also
14

---

Published in Transactions on Machine Learning Research (04/2024)
SyGuS Benchmark
38 Benchmark
100
A-BU8
BUS
26
Averige Program
57
12
28
14
4-
A-BUS
BUS
0
1
Number Tterations
Number Iterations
Figure 10: Average program size for the problems solved across different iterations of A-BUS.
presents the average solution program size BUS finds. The size of the solution programs grows rapidly the early iterations (1-4 for the SyGuS benchmark and 1 and for the benchmark), but the average size becomes somewhat constant in both domains in later iterations. The sizes of the ASTs of the solution programs A-BUS finds are much larger than those of the solution programs BUS finds. Although BUS is optimal with respect to the AST size, it is unable to solve many of the problems in the two benchmarks evaluated. AULILE offers the option of trading the simplicity of the solution for more problems solved.
15


Reviews:
[{"review_id": "WnQGctO9jx", "reviewer": "Reviewer_UZNi", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- **Clarity of writing and comprehensive related work**: The paper is written clearly and the baseline methods are discussed in adequate detail given that they are based on related work. The discussion of related work is also comprehensive.\n- **Presentation of results**: The results presented on the two benchmarks for the string manipulation task were clear and addressed the hypothesis adequately.\n\nWeaknesses:\n- **Domain dependency of the auxiliary function**: I see the benefit of having a domain-dependent function to further guide the search of the solution program. However, finding the optimal auxiliary function for different domains can be challenging. For the string manipulation task, used in the experiments, the Levenstein distance function was appropriate, but for more complex domains finding such a function may not be trivial.\n- **In-depth analysis of auxiliary function**: Given the critical role of the auxiliary function in enhancing the search for solution codes, it would be valuable to explore the impact of different auxiliary functions when combined with various base synthesizers.\n- **Additional experiments with Top-down search algorithms**: The paper briefly mentions AULILE's use with stochastic top-down base synthesizers. Expanding on this aspect by including the results from this synthesizer alongside others would improve the diversity of the reported outcomes.\n- **Comparison with DREAM-CODER**: The paper discusses the differences between the presented approach with Dream Coder; specifically, that Dream Coder requires training tasks to learn a library of programs for a problem domain while AULILE doesn't require training tasks and learns programs in a task-specific manner. However, this still doesn't explain why one should prefer AULILE over Dream Coder, and in which instances would the former be the better choice. Further clarification on this point might be insightful.\n- **Lack of discussion on future work**:  For a more organized structure, it might be beneficial to reserve a dedicated section to discuss potential directions for future research.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper tackles the problem of synthesizing solution programs for a given set of input-output examples. It presents a new method for program synthesis using search-based guidance through a pre-defined domain-dependent auxiliary function, called AULILE. The method operates by building on top of existing search-based program synthesis methods such as Bottom-Up Search (BUS), BUSTLE, BEE search, and CROSS BEAM (referred to as the base synthesizer) by optimizing for the pre-defined auxiliary function in addition to the search-based (optimization) methods of the base synthesizer. To empirically verify the benefit of the AULILE, the authors use a string manipulation task and augment AULILE on base synthesizers using BUS, BUSTLE, BEE, and CROSSBEAM. The results show that methods augmented with AULILE outperform the base synthesizers on both string manipulation benchmarks SyGuS (significant gains) and a hand-crafted benchmark consisting of 38 instances.  The methods also perform reasonably well in terms of their runtime. The auxiliary function used for these tasks was the Levenstein distance between the output of the found program and the expected output for the specific string-based test case.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The paper is largely clearly written. However, there are still some additional clarifications required:\n- As discussed in the Weaknesses, further clarification on the differences between Dream-Coder and AULILE might be beneficial. Are there specific instances where AULILE performs better, for instance in terms of faster runtimes? It still seems like, Dream-Coder is the more general version of AULILE. Can the string manipulation task be slightly modified to use Dream-Coder as a baseline for AULILE?\n- Adding a stochastic top-down program synthesizer to the set of baseline methods would enhance the baselines used in the experiments and showcase the diversity of AULILE further. \nThe addition of an explicit future work section would be insightful.\n- Expanding the scope of AULILE: Currently, the benefits of AULILE are illustrated in the string manipulation domain. Illustration of the method on a slightly more intricate/complex program synthesis domain/DSL or an additional DSL (such as Bit Vector DSL) might strengthen the paper.\nThe addition of an explicit section on the limitations of the presented approach would make the findings of the paper more comprehensive.", "broader_impact_concerns": "In its current state, the paper does not present any ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "NbMGAiXJEf", "reviewer": "Reviewer_ATes", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe proposed approach is simple, and show consistent improvement when combined with multiple base program synthesis algorithms on SyGuS.\n\nWeaknesses:\nIn general, this work lacks ablation studies and error analysis to understand where the performance improvement comes from.\n\n1. In Algorithm 1, in general how many iterations are conducted for the algorithm to finish, and what is the number of solved problems after each iteration?\n\n2. Is there any analysis on the complexity of programs solved in each iteration? For example, the improvement of Aulile might be because using the subprograms enables the algorithm to find more complex programs after each iteration, but it is unclear from the current results.\n\n3. What are the differences between the setting of Figure 5 and Figures 3-4? I wonder why the results are different in the 2 sets of plots.\n\n4. In the design of Algorithm 1, have the authors tried adding multiple subprograms in each iteration? Does it improve or decrease the sample efficiency?\n\n5. After adding new subprograms in the search space, is it required to do a retraining for those algorithms that involve neural networks? What is the additional training cost?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents Auxiliary-Based Library Learning (Aulile) for program synthesis from input-output examples, which can be combined with various base program synthesis algorithms. Basically, after each synthesis iteration, if the task is not solved yet, Aulile picks one synthesized program that is the closest to the target outputs, then adds that program into the library, so that in the next iteration, the synthesizer can directly call that program as a subprogram. They evaluate Aulile in the string manipulation domain, including SyGuS benchmark and a collection of 38 tasks from prior work. They demonstrate that Aulile can improve base program synthesizers by a notable margin on SyGuS.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Add information on how many iterations are conducted for the algorithm to finish in general, and what is the number of solved problems after each iteration.\n\n2. Add an analysis on the complexity of programs solved in each iteration.\n\n3. Explain the differences between the setting of Figure 5 and Figures 3-4, and why the results are different in the 2 sets of plots.\n\n4. In the design of Algorithm 1, add discussion on whether adding multiple subprograms improve or decrease the sample efficiency.\n\n5. Explain whether it is required to do a retraining for those algorithms that involve neural networks after each iteration, and the additional training cost.", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "2cphgver3C", "reviewer": "Reviewer_e3NF", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The proposed method is quite simple and easy to understand.\n- The proposed method shows empirical improvement on benchmarks compared to prior work.\n\nWeaknesses:\n- The generality of the method is unclear as the paper only considers one program domain (string manipulation). It may be not so straightforward to pick a good auxiliary function for other domains.\n- By adding large programs as primitives to the bottom-up search, equal to all the other regular primitives, the method may end up generating more complex programs than otherwise.\n- The paper proposes to use the auxiliary function provided in the outer loop of the process, but does not investigate other ways to use the same information. Bustle, Bee Search, and Crossbeam all contain a component to learn whether some program fragment is likely to be useful as part of the ultimate solution. Using an auxiliary function which explicitly computes Levenshtein distance could be a way to shortcut this learning, and might work better inside the inner loop as well.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes to augment methods for program synthesis from input-output specifications based on bottom-up search, by additionally using an auxiliary function to help select among incomplete programs to reuse in later iterations of the search. The proposed method, Aulile, invokes an inner search method in a loop. In each iteration, the inner method returns either a solution, or the program found with the best score according to the auxiliary function. This program is added to the set of base programs for the next iteration of the outer loop.\n\nThe authors evaluate their approach added to 4 different bottom-up search methods, using two sets string manipulation tasks used in prior work. They show that it can improve the success rate compared to the baseline method.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I would like to see the authors try at least one more auxiliary function and analyze how that impacts the performance of the method, in order to answer the following questions:\n- How does the choice of auxiliary function affect the performance of the method?\n- Can we see whether the use of a better auxiliary function is correlated with increased performance on the method?\n\nSome examples could include the difference in length between the program's output and the true output, and the length of the prefix which matches between the program's output and the true output.", "broader_impact_concerns": "I have no concerns about broader impact.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The advances made in this paper and fairly narrow in technique (using a domain-specific auxiliary function to identify promising program subroutines) and domain, but the claims seem appropriately scoped. Most of the requests by reviewers for additional experiments were addressed. In total, the matching of evidence and claims is appropriate for TMLR.
Decision: Accept (poster)