Differentiable Synthesis of Program Architectures
Year: 2021

Abstract:
Differentiable programs have recently attracted much interest due to their interpretability, compositionality, and their efficiency to leverage differentiable training. However, synthesizing differentiable programs requires optimizing over a combinatorial, rapidly exploded space of program architectures. Despite the development of effective pruning heuristics, previous works essentially enumerate the discrete search space of program architectures, which is inefficient. We propose to encode program architecture search as learning the probability distribution over all possible program derivations induced by a context-free grammar. This allows the search algorithm to efficiently prune away unlikely program derivations to synthesize optimal program architectures. To this end, an efficient gradient-descent based method is developed to conduct program architecture search in a continuous relaxation of the discrete space of grammar rules. Experiment results on four sequence classification tasks demonstrate that our program synthesizer excels in discovering program architectures that lead to differentiable programs with higher F1 scores, while being more efficient than state-of-the-art program synthesis methods.

heading: 1 Introduction
text: Program synthesis has recently emerged as an effective approach to address tasks in several fields where deep learning is applied traditionally. A synthesized program in a domain-specific language (DSL) provides a powerful abstraction for summarizing discovered knowledge from data and offers greater interpretability and transferability across tasks than a deep neural network model, while achieving competitive task performance [1–4].
A differentiable program encourages interpretability by using structured symbolic primitives to compose a set of differentiable modules with trainable parameters in its architecture. These parameters can be efficiently learned with respect to a differentiable loss function over the program’s outputs. However, synthesizing a reasonable program architecture remains challenging because the architecture search space is discrete and combinatorial. Various enumeration strategies have been developed to explore the program architecture space, including greedy enumeration [1, 2], evolutionary search [5], and Monte Carlo sampling [6]. To prioritize highly likely top-down search directions in the combinatorial architecture space, NEAR [7] uses neural networks to approximate missing expressions in a partial program whose F1 score serves as an admissible heuristic to effective graph search algorithms such as A∗ [8]. However, since the discrete program architecture search space is intractably large, enumeration-based search strategies are inefficient in general.
We propose to encode program architecture search as learning the probability distribution over all possible program architecture derivations induced by a context-free DSL grammar. This problem bears similarities with searching the structure of graphical models [9] and neural architecture search. Specifically, to support differentiable search, DARTS [10] uses a composition of softmaxes over all possible candidate operations between a fixed set of neural network nodes to relax the discrete search space of neural architectures. However, applying this method to program synthesis is challenging
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
because the program architecture search space is much richer [7]. Firstly, different sets of operations take different input and output types and may only be available at different points of a program. Secondly, there is no fixed bound on the number of expressions in a program architecture.
To address the aforementioned challenges, we learn the probability distribution of program architectures in a continuous relaxation of the search space of DSL grammar rules. We conduct program architecture search in a program derivation graph, in which nodes encode architectures with missing expressions, and paths encode top-down program derivations. For each partial architecture f on a graph node, we relax the categorical choice of production rules for expanding a missing expression in f to a softmax over all possible production rules with trainable weights. A program derivation graph essentially expresses all possible program derivations under a context-free grammar up to a certain depth bound (on the height of program abstract syntax trees), which can be iteratively increased during search to balance accuracy and architecture complexity. We encode a program derivation graph itself as a differentiable program whose output is weighted by the outputs of all the programs involved. We seek to optimize program architecture weights with respect to an accuracy loss function defined over the encoded program’s output. The learned weights allow our synthesis algorithm to efficiently prune away search directions to unlikely program derivations to discover optimal programs. Compared with enumeration-based synthesis strategies, differentiable program synthesis in the relaxed architecture space is easier and more efficient with gradient-based optimization.
One major challenge of differentiable program architecture synthesis is that a program derivation graph involves an exponential number of programs and a huge set of trainable variables including architecture weights and program parameters. To curb the large program derivation search space, we introduce node sharing in program derivation graphs and iterative graph unfolding. Node sharing allows two partial architectures to share the same child nodes if the missing expressions in the two architectures can be expanded using the same grammar rules. Iterative graph unfolding allows the synthesis algorithm to construct a program derivation graph on the fly focusing on higher-quality program derivations than all the rest. These optimization strategies significantly reduce the program architecture search space, scaling differentiable program synthesis to real-world classification tasks. We evaluate our synthesis algorithm in the context of learning classifiers in sequence classification applications. We demonstrate that our algorithm substantially outperforms state-of-the-art methods for differentiable program synthesis, and can learn programmatic classifiers that are highly interpretable and are comparable to neural network models in terms of accuracy and F1-scores.
As a summary, this paper makes three contributions. Firstly, we encode program synthesis as learning the probability distribution of program architectures in a continuous relaxation of the discrete space defined by programming language grammar rules, enabling differentiable program architecture search. Secondly, we instantiate differentiable program architecture synthesis with effective optimization strategies including node sharing and iterative graph unfolding, scaling it to real-world classification tasks. Lastly, we present state-of-the-art results in learning programmatic classifiers for four sequence classification applications.

heading: 2 Problem Formulation
text: A program in a domain-specific language (DSL) is a pair (α, θ), where α is a discrete program architecture and θ is a vector of real-valued parameters of the program. Given a specification over the intended input-output behavior of an unknown program, program synthesis aims to discover the program’s architecture α and optimize the program parameters θ.
In this paper, we focus on learning programmatic classifiers for sequence classification tasks [11]. We note that the proposed synthesis technique is applicable to learning any differentiable programs.
Program Architecture Synthesis. A program architecture α is typically synthesized based on a context-free grammar [12]. Such a grammar consists of a set of production rules αk → {σj}Jj=0 over terminal symbols Σ and nonterminal symbols Y where αk ∈ Y and σj ∈ Σ ∪ Y . As an example, consider the context-free grammar of a DSL for sequence classification depicted in the standard Backus-Naur form [13] in Fig. 1, adapted from [7]. A terminal in this grammar is a symbol that can appear in a program’s code, e.g. x and the map function symbol, while a nonterminal stands for a missing expression (or subexpression), e.g. α2 and α3. Any program in the DSL operates over a real vector or a sequence of real vector x. It may use constants c, arithmetic operations Add and Multiply, and an If-Then-Else branching construct ITE. To avoid discontinuities for
α ::= x | c | Add α1 α2 |Multiply α1 α2 | ITE α1 ≥ 0 α2 α3 | FS,θ(x) | map (fun x1.α1) x | mapprefix (fun x1.α1) x | fold (fun x1.α1) c x | SlideWindowAvg (fun x1.α1) x
Figure 1: Context-free DSL Grammar for Sequence Classification (adapted from [7]).
…
…
0.2 0.34 0.46 0.5 0.17 0.33 0 0 0 𝐴𝑑𝑑: 𝛼! ",$ 𝐼𝑇𝐸: 𝛼! "," 𝑀𝑎𝑝: ∅ 𝐹𝑜𝑙𝑑 𝐴𝑣𝑔 𝑥 𝑾
𝑾
Depth 0 Depth 1
Depth 2
Depth 3
Depth 0
Depth 1
… … … … Depth 2 𝑾
0.45 0.2 0.35𝐴𝑑𝑑: 𝛼" ",$
𝐴𝑑𝑑 𝑀𝑢𝑙 𝑥
𝑾
0
0 1
2 3
4 5
𝐴𝑑𝑑 𝛼" ",$ 𝛼! ",$ 𝐼𝑇𝐸 𝛼" "," 𝛼! ","𝛼% "," 𝑀𝑎𝑝 𝛼" ",!
𝐴𝑑𝑑 𝛼" !,$ 𝛼! !,$ 𝑀𝑢𝑙 𝛼" !," 𝛼! !," 𝑥 ∅
𝐹𝑜𝑙𝑑 𝛼" %,$ 𝛼" %," 𝐴𝑣𝑔 𝑥 ∅
𝐼𝑇𝐸 𝛼" &,"𝛼! &,"𝛼% &," 𝑀𝑢𝑙 𝛼" &,! 𝛼! &,! 𝐴𝑑𝑑 𝛼" &,% 𝛼! &,% 𝐼𝑇𝐸 𝛼" ',"𝛼! ',"𝛼% '," 𝑀𝑢𝑙 𝛼" ',! 𝛼! ',! 𝑥 ∅
𝑆𝑡𝑎𝑟𝑡 𝛼" $,$
𝑆𝑡𝑎𝑟𝑡 𝛼" $,$
1 𝐴𝑑𝑑
𝛼" ",$ 𝛼!
",$ 𝐼𝑇𝐸
𝛼" "," 𝛼! ","𝛼% "," 𝑀𝑎𝑝 𝛼" ",!
2 𝐴𝑑𝑑
𝛼" !,$ 𝛼!
!,$ 𝑀𝑢𝑙
𝛼" !," 𝛼!
!," 𝑥 ∅ 3 𝐹𝑜𝑙𝑑 𝛼" %,$ 𝛼" %," 𝐴𝑣𝑔 𝑥 ∅
Figure 2: Program Derivation Graph of the grammar in Fig. 1.
differentiability, we interpret it in terms of a smooth approximation: JITE(α1 ≥ 0, α2, α3)K(x) = σ(Jα1K(x)) · Jα2K(x) + (1 − σ(Jα1K(x)) · Jα3K(x) where σ is the sigmoid function. A program may invoke a customized library of differentiable, parameterized functions. In our context, these functions are in the shape FS,θ(x) that extract a vector consisting of a predefined subset S of the dimensions of an input x and pass the extracted vector through a linear function with trainable parameters θ. A program may also use a set of higher-order combinators to recurse over sequences including the standard map and fold combinators. The higher-order combinators takes as input an anonymous function fun x.e(x) that evaluates an expression e(x) over the input x. For a sequence x, the mapprefix higher-order combinator returns a sequence f(x[1 : 1]), f(x[1 : 2]), . . . , f(x[1 : n]), where x[1 : i] is the i-th prefix of x. The SlideWindowAvg function computes the average of a sequence over a moving window of frames.
We define the complexity of a program architecture α. Let each grammar rule r have a non-negative real-valued cost c(r). The structural cost c(α) is the sum of the costs of the multi-set of rules used to create α. Intuitively, program architectures with lower structural cost are more interpretable. In the context of this paper, program synthesis aims to learn a simple program (in terms of structure cost) that satisfies some specifications over program input-output behaviors. In this paper, we set c(r) = 1 for any production rule r.
Program Synthesis Specifications. In a sequence classification task, a set of feature sequences {ik}Kk=1 are taken as input and we expect to classify ik into a certain category ok. Each ik is a sequence of observations. Each observation captures features extracted at a frame as a 1-dimensional real-valued vector. We aim to synthesize a program P (·; α, θ) as a classifier with high accuracy and low architecture cost. Our program synthesis goal is formalized as follows:
arg min θ,α
Eik,ok∼D[` ( P (ik; α, θ), ok ) ] + c(α) (1)
where D(ik, ok) is an unknown distribution over input sequences ik and labels ok. The first term of Equation (1) defines some prediction error loss ` of a program P (·) for a classification task over P ’s predicted labels and the ground truth labels. The second term enforces program synthesis to learn an architecturally simple programmatic classifier.

heading: 3 Differentiable Program Architecture Synthesis
text: We formulate program architecture derivation as a form of top-down graph traversal. Given the context-free grammar G of a DSL, an architecture derivation starts with the initial nonterminal (i.e. the empty architecture), then applies the production rules in G to produce a series of partial architectures which consist in expressions made from one or more nonterminals and zero or more terminals, and terminates when a complete architecture that does not include any nonterminals is derived.
Formally, program architecture synthesis with respect to a context-free grammar G is performed over a directed acyclic program derivation graph G = {V,E} where V and E indicate graph nodes and edges. Fig. 2 depicts a program derivation graph for the sequence classification grammar in Fig. 1. A node u ∈ V is a set of partial or complete program architectures permissible by G. An edge (u, u′) ∈ E exists if one can obtain the architectures in u′ by expanding a nonterminal of an architecture in u following some production rules of G. For simplicity, Fig. 2 only shows three partial or complete architectures in any node of the program derivation graph. In the graph node at depth 1, we expand the initial nonterminal α0,01 to the Add, ITE and Map functions (each with missing expressions) using the grammar rules in Fig. 1. Notice that the edge direction in a program derivation graph indicates search order. However, program dataflow through each edge (u, u′) is in the opposite direction. The output of u′ is calculated first and then passed as input to u.
The main challenge of program architecture synthesis is that the search space embedded in a program derivation graph is discrete and combinatorial. Enumeration-based synthesis strategies are inefficient in general because of the intractable search space. Instead, we aim to learn the probability distribution of program architectures within a program derivation graph in a continuous relaxation of the search space. Specifically, to expand a nonterminal of a partial program architecture, we relax the categorical choice of production rules in a context-free grammar into a softmax over all possible production rules with trainable weights. For example, in Fig. 2, if we expand the initial nonterminal α0,01 to a partial architecture Add α1,01 α 1,0 2 on node 1, we have several choices to further expand the architecture’s first nonterminal α1,01 , weighted by the probability matrix w (obtained after softmax) drawn in Fig. 2. Based on w, the synthesizer will choose to expand α1,01 to Add α 2,0 1 α 2,0 2 on node 2. Our main idea to learn architecture weights is to encode a program derivation graph itself as a differentiable program Tw,θ whose output is weighted by the outputs of all programs included in Tw,θ, where w represents architecture weights and θ includes program parameters of all the mixed programs in the graph. The parameters w and θ can be jointly optimized with respect to a differentiable loss function ` over program outputs via bi-level optimization. Similar to DARTS [10], we train θ and w on a parameter training dataset Dθ and an architecture validation dataset Dw respectively until convergence:
θ′ = θ −∇θEik,ok∼Dθ` ( Tw,θ(ik), ok ) w′ = w −∇wEik,ok∼Dw` ( Tw,θ′(ik), ok
) (2) However, a program derivation graph includes an exponential number of programs. Therefore, it involves a huge set of trainable variables including program architecture weights w and unknown program parameters θ. To curb the large program derivation search space, we introduce node sharing (Sec. 3.1) and iterative graph unfolding (Sec. 3.2).

heading: 3.1 Node Sharing
text: Intuitively, node sharing in a program derivation graph allows two partial architectures to share the same child nodes if the nonterminals in the two architectures can be expanded using the same grammar production rules. Fig. 3 depicts the compressed program derivation graph for the sequence classification grammar in Fig. 1. At depth 1, three partial architectures Add α1,01 α 1,0 2 , ITE α 1,1 1 ≥ 0 α1,12 α 1,1 3 , and Map (fun x1.α 1,2 1 ) are expanded from the initial nonterminal α 0,0 1 . Because only one of the three partial architectures would be used to derive the final synthesized program, we allow the nonterminals α1,02 , the second parameter of Add, and α 1,1 2 , the second parameters of ITE, to share the same child node 3, weighted by the probability matrix w drawn in Fig. 3. Importantly, node sharing takes function arities and types into account. The matrix w has 0 probability for the Map partial architecture because unlike Add and ITE it does not contain a second parameter.
Formally, in a program derivation graph, let Ku be the number of program architectures on node u. Denote fuk ( αu,k1 , . . . , α
u,k η(fuk )
) as the k-th (partial) architecture on u where η(fuk ) is the number
of nonterminals contained in fuk and α u,k i is the i-th nonterminal of f u k . For the grammar of Fig. 1, essentially each fuk is a function application with missing argument expressions α u,k i , 1 ≤ i ≤ η(fuk ), and η(fuk ) is the arity of the function. Assume that u ′ is the i-th child of u from left to right in the program derivation graph. The weight we of the edge e = (u, u′) is of the shape RKu×Ku′ where the matrix rows refer to the partial architectures on u and the matrix columns refer to architectures on u′. We have we[(k, k′)] proportional to the probability of expanding the i-th nonterminal of fuk to f u′ k′
Depth 0
Depth 1
… … … … Depth 2 𝑾
0.45 0.2 0.35𝐴𝑑𝑑: 𝛼" ",$
𝐴𝑑𝑑 𝑀𝑢𝑙 𝑥
𝑾
0
𝑆𝑡𝑎𝑟𝑡 𝛼" $,$
1 𝐴𝑑𝑑
𝛼" ",$ 𝛼!
",$ 𝐼𝑇𝐸
𝛼" "," 𝛼! ","𝛼% "," 𝑀𝑎𝑝 𝛼" ",!
2 𝐴𝑑𝑑
𝛼" !,$ 𝛼!
!,$ 𝑀𝑢𝑙
𝛼" !," 𝛼!
!," 𝑥 ∅ 3 𝐹𝑜𝑙𝑑 𝛼" %,$ 𝛼" %," 𝐴𝑣𝑔 𝑥 ∅
(obtained after softmax), e.g. the w matrix drawn in Fig. 3. To make the architecture search space continuous, we relax the categorical choice of expanding a particular nonterminal αu,ki to a softmax over all possible grammar production rules for αu,ki in the program derivation graph:
Jαu,ki K(x) = Ku′∑ k′=0 exp(we[(k, k ′)])∑Ku′ j=0 exp(we[(k, j)]) · Jfu′k′ ( αu ′,k′ 1 , . . . , α u′,k′ η(fu ′ k′ ) ) K(x)
where u′ is the i-th child of u and e = (u, u′)
(3)
Complexity. Let D be the depth of a program derivation graph, Kmax be the number of productions rules, and ηmax be the maximum number of nonterminals in any rules of a context-free grammar. With node sharing, we reduce the space complexity of the program derivation graph from O([Kmax · ηmax]
D+1) to O([ηmax]D+1). In a program synthesis task, Kmax is typically much larger than ηmax. Without compression, the program derivation graph of a grammar with a large Kmax even hardly fits GPU memory.

heading: 3.2 Iterative Graph Unfolding
text: Node sharing significantly restricts the width of a program derivation graph. However, a derivation graph still grows exponentially with its depth, which limits the scalability of differentiable architecture search. To address this problem, we propose an on-the-fly approach that unfolds program derivation graphs iteratively and prunes away unlikely candidate architectures at the end of each iteration based on their weights. Fig. 4 depicts the iterative procedure of derivation graph unfolding.
At the initial iteration, the program derivation graph is shallow as it only contains architectures up to depth ds. We set ds = 2 in Fig. 4. For any partial program architecture fuk ( αu,k1 , . . . , α
u,k η(fuk )
) on any
node u of the depth-bounded graph, our algorithm substitutes neural networks for the nonterminals αu,ki to approximate the missing expressions. These networks are type-consistent. For example, a recurrent neural network is used to replace a missing expression whose inputs are supposed to be sequences. For a program derivation graph as such, the unknown program parameters θ come from both parameterized functions like fuk and the neural modules. The goal is to optimize the architecture weights and the unknown program parameters using Equation 2. The qualities of candidate partial architectures on each graph node are ranked based on the learned architecture weights.
In the next iteration, on each graph node, our synthesis algorithm retains top-N program architectures as children for each partial architecture on the node’s parent, which are defined to be those assigned with higher weights on the node’s incoming edge in the previous iteration. We set N = 2 in the example of Fig. 4. After top-N preservation on each node, our synthesis algorithm increases the depth of the program derivation graph by expanding the nonterminals (that were replaced with neural modules in the previous iteration) ds depths deeper. Suitable neural networks are leveraged to substitute any new nonterminals at depth 2ds + 1. Our algorithm again jointly optimizes architecture weights and unknown program parameters and performs top-N preservation on each node based on
Top-2 Sel. 0
∅
Extend
Train𝑤/𝜃
Top-2 Sel.Extend
Train𝑤/𝜃
…
𝑾′
0.5 0.41 ⋯ 0.02 0.6 0.02 ⋯ 0.29
𝑾′
0.55 0.45 0 0.67 0 0.33
Search w. train
0
1
3
5
6 7
… 𝑾 0.3 0.36 ⋯ 0.02 0
1
NN
2 … … 𝑾
0
1
NN
2
0
1
3
5 … 6 7… …
𝑾′
0
1
3
5
6 7
𝑾′
learned architecture weights, as depicted in Fig. 4. Such a process iterates until the unfolded program derivation graph contains no nonterminals or the maximum search depth is reached. Our differentiable program architecture synthesis method is outlined in (the first while loop of) Algorithm 1.
3.3 Searching Optimal Programs
Algorithm 1: Program Archit. Synthesis Input :Grammar G, Graph expansion depth ds, Top-N parameter Output :Synthesized Program P G contains only the initial nonterminal; while G contains nonterminals do
Extend G depth ds deeper w.r.t. G; Optimize w and θ in G w.rt. Eq. 2; Top-N preservation in G’s nodes;
Q := [G]; while Q 6= ∅ do
q := arg minq∈Q f(q); Q := Q \ {q}; if q is a well-typed program then
return q; u is the top-left most node in q with more than one architecture choice; for each partial archit. fuk on u do q′ := q[u/fuk ]; Compute g(q′), h(q′), s(q′); Q := Q ∪ {q′};
Once we have an optimized program derivation graph G, due to the top-N preservation strategy, each node retains a small number of partial architectures. From G, we could greedily obtain a discrete program architecture top-down by replacing each graph node containing mixed partial architectures with the most likely partial architecture based on learned architecture weights. However, the performance estimation ranked by architecture weights in a program derivation graph can be inaccurate due to the co-adaption among architectures via node sharing. Recent work also discovers that relaxed architecture search methods tend to overfit to certain functions that lead to more rapid gradient descent than others [14–17] and thus produce unsatisfying performance.
To overcome this potential disadvantage of differentiable architecture search, our algorithm introduces a search procedure as depicted in Fig. 4. The core idea is that while one super program derivation graph may not be able to model the entire search space accurately, multiple sub program derivation graphs can be used to effectively address the limitation by having each sub graph modeling one part of the search space.
In the search, Algorithm 1 maintains a queue Q of program derivation graphs sorted by their quality that is initialized to [G]. Our algorithm measures the quality of a program by both its task performance and structure cost. The algorithm dequeues one graph q from Q and extracts the top-most and left-most node u of q that still contains more than one partial architecture for search. As u co-adapts multiple architectures, we separate the entire search space into disjoint partitions by picking each available architecture fuk ( αu,k1 , . . . , α
u,k η(fuk )
) from the
compound node u and assign a sub program derivation graph to model each partition. The algorithm computes a quality score s for each option of retaining only fuk on u, denoted as q[u/f u k ]:
s(q[u/fuk ]) = g(q[u/f u k ]) + h(q[u/f u k ])
The g(q[u/fuk ]) function measures the structure cost of expanding the initial nonterminal up to u (Sec. 2) and h(q[u/fuk ]) is an -Admissible heuristic estimate of the cost-to-go from node u [18]:
h(q[u/fuk ]) = 1− F1(Tw∗,θ∗ [u/fuk ], Dval) where w∗, θ∗ = arg min w,θ
Eik,ok∼D[` ( Tw,θ[u/fuk ]), ok ) ]
where T encodes the program derivation graph q itself via Equation (3) as a differentiable program whose output is weighted by the output of all complete programs included in q, w and θ are the sets of architecture weights and unknown program parameters in the subgraph rooted at u in q[u/fuk ]. The h
function fine-tunes these trainable variables using the training datasetD to provide informed feedback on the contribution to program quality of the choice of only retaining fuk on node u, measured by the program’s F1 score. In practice, to avoid overfitting, we use a separate validation dataset Dval to obtain the F1 score. After computing the quality score s, we add q[u/fuk ] back to the queue Q sorted based on s-scores. The search algorithm completes when the derivation graph with the least s-score from Q is a well-typed program, i.e. each graph node contains only one valid architecture choice. Our architecture selection algorithm is optimal given the admissible heuristic function h — the returned program optimally balances program accuracy and structure complexity among all the programs contained in G. The proof is given in Appendix A.

heading: 4 Experiments
text: We have implemented Algorithm 1 in a tool named dPads (domain-specific Program architecture differentiable synthesis) [19], and evaluated it on four sequence classification datasets.

heading: 4.1 Datasets for Evaluation
text: We partition a dataset to training, validation, and test datasets. dPads uses the training dataset to optimize the architecture weights and program parameters in a program derivation graph. When searching a final program from a converged program derivation graph, we use the validation dataset to obtain the program’s F1 score to guide the search. We use the test dataset to obtain the final accuracy and F1 score of a program. Additionally, in training we construct two separate datasets by randomly selecting 60% of a training dataset as Dθ to optimize program parameters θ and using the remaining 40% as Dw to train architecture weights w via Equation 2.
Crim13 Dataset. The dataset collects social behaviors of a pair of mice. We cut every 100 frames as a trajectory. Each trajectory frame is annotated with an action by behavior experts [20]. For each frame, a 19-dimensional feature vector is extracted including the positions and velocities of the two mice. The goal is to synthesize a program to classify each trajectory to action sniff or no sniff. In total we have 12404, 3077, and 2953 trajectories in the training set, validation set, and test set respectively.
Fly-vs-fly Dataset. We use the Boy-meets-boy, Aggression and Courtship datasets collected in the fly-vs-fly environment for monitoring two fruit flies interacting with each other [21]. Each trajectory frame is a 53-dimensional feature vector including fly position, velocity, wing movement, etc. We subsample the dataset similar to [7], which results in 5341 train trajectories, 629 validation trajectories, and 1050 test trajectories. We aim to synthesize a program to classify each trajectory as one of 7 actions displaying aggressive, threatening, and nonthreatening behaviors.
Basketball Dataset. The dataset tracks the movement of a basketball, 5 defensive players and 5 offensive players [22]. Each trajectory has 25 frames with each frame as a 22-dimensional feature vector of ball and player position information. We aim to learn a program that can predict which offensive player handles the ball or whether the ball is being passed. In total we have 18000, 2801, and 2693 trajectories in the training set, validation set, and test set respectively.
Skeletics 152 Dataset. The dataset [23] contains 152 human pose actions as well as related YouTube Videos subsampled from Kinetics-700 [24]. For each video frame, 25 3-D skeleton points are collected, resulting in a 75-dimensional feature vector per frame. We extract 100 frames from each trajectory to reduce noise. Finally, the training set contains 8721 trajectories, the validation set contains 2184 trajectories, and the test set contains 892 trajectories. We aim to learn a program to classify a pose trajectory as one of 10 actions.
As discussed in Sec. 2, the DSL for each dataset is equipped with a customized library of differentiable and parameterized functions FS,θ(x). We define these functions in Appendix B. In this paper, we focus on sequence classification benchmarks. However, dPads is a general program synthesis algorithm and is not limited to sequence classification. In Appendix C.6, we evaluate dPads on cryptographic circuit synthesis to demonstrate the generalizability of dPads.

heading: 4.2 Experiment Setup
text: To train architecture weights w and unknown program parameters θ in a differentiable program architecture derivation graph, we use the Adam optimizer [25]. In Algorithm 1, we set N = 2
Table 1: Experiment results on the performance of dPads compared with NEAR [7]. All results are reported as the average of runs on five random seeds. Costs of time are set in minutes.
Crim13-sniff Fly-vs-fly Bball-ballhandler SK152-10 actions F1 Acc. Time F1 Acc. Time F1 Acc. Time F1 Acc. Time
RNN .481 .851 - .964 .964 - .980 .980 - .414 .428 - A∗-NEAR .286 .820 164.92 .828 .764 243.82 .940 .934 553.01 .312 .315 210.23 IDS-BB-NEAR .323 .834 463.36 .822 .750 465.57 .793 .768 513.33 .314 .317 848.44 dPads .458 .812 147.87 .887 .853 348.25 .945 .939 174.68 .337 .337 162.70
𝑌! ∷= 𝑥 | 𝑌"
𝑌" ∷= 𝑀𝑎𝑝 𝑌" 𝑥 𝑀𝑎𝑝𝑝𝑟𝑒𝑓𝑖𝑥 𝑌" 𝑥 𝐹𝑜𝑙𝑑 𝑌" 𝑥 | 𝐼𝑇𝐸 𝑌!, 𝑌!, 𝑌! |
𝑠𝑙𝑖𝑑𝑒𝑊𝑖𝑛𝑑𝑜𝑤 𝑌! 𝐴𝑑𝑑 𝑌!, 𝑌! 𝑀𝑢𝑙𝑡𝑖𝑝𝑙𝑦 𝑌!, 𝑌! | 𝐹𝑒𝑎𝑡𝑢𝑟𝑒#(𝑥)
Map( Multiply( PositionSelectθ1(xt),DistanceSelectθ2(xt))) x SlideWindowAvg(Add( Multiply(LegsAffineθ1(xt), LegsAffineθ2(xt)), Multiply(ArmsAffineθ3(xt), ArmsAffineθ4(xt)))) x
Time (min)
F1 Sc or e
Time (min)
F1 Sc or e
(a) Crim13-sniff (d) SK152-10 actions Time (min) (c) Bball-ballhandler
F1 Sc or e
Time (min)
F1 Sc or e
(b) Fly-vs-fly(a) Crim13 (b) SK152
MapPrefixes( Fold( if DistanceSelectθ1(xt) then PositionSelectθ2(xt) else PositionSelectθ3(xt)))) x
Map( if AccelerationSelectθ1(xt) then if PositionSelectθ2(xt)
then PositionSelectθ3(xt) else VelocitySelectθ4(xt) else Multiply(DistanceSelectθ5(xt), DistanceSelectθ6(xt))) x
Fold( Add( Add(PositionalSelectθ1(xt), WingSelectθ2(xt)), RatioSelectθ3(xt))) x
Fold( Add( Add(AngularSelectθ1(xt), WingSelectθ2(xt)), Add(RatioSelectθ3(xt), RatioSelectθ4(xt)))) x
(a) Crim13 (b) Fly-vs-fly
SlideWindowAvg( Add( if ArmsXYZAffineθ1(xt) then ArmsXYZAffineθ2(xt) else ArmsXYZAffineθ3(xt),
if LegsXYZAffineθ4(xt) then FaceXYZAffineθ5(xt) else LegsXYZAffineθ6(xt))) x
Map( Multiply( Add(BallXYAffineθ1(xt), OffenseXYAffineθ2(xt)), Add(OffenseXYAffineθ3(xt), BallXYAffineθ4(xt)))) x
(c) SK152 (d) Basketball
Figure 5: Experiment results on the Crim13, Fly-vs-fly, Basketball and SK152 datasets over five random seeds. x axis refers to costs of time recorded in minutes and y axis refers to F1 scores.
for top-N preservation and set graph expansion depth ds to 2. For evaluation, we compare dPads with the state-of-the-art program learning algorithms A∗-NEAR and IDS-BB-NEAR [7]. We only report a comparison with NEAR because NEAR significantly outperforms other program learning methods based on top-down enumeration, Monte-Carlo sampling, Monte-Carlo tree search, and genetic algorithms [7]. All experiments were performed on Intel 2.3-GHz Xeon CPU with 16 cores, equipped with an NVIDIA Quadro RTX 6000 GPU. More experiment settings including learning rates and training epochs are given in Appendix C.1 and C.2.

heading: 4.3 Experiment Results
text: For a fair comparison with NEAR [7], for any of the four datasets, all tools search over the same DSL. We use random seeds 0, 1000, 2000, 3000, 4000 and report average F1 scores, accuracy rates and execution times for both methods. We also report the results achieved using a highly expressive RNN baseline which provides a task performance upper bound on F1-scores and accuracy.
Table 1 shows the experiment results. On both the Crim13 and SK152 datasets, dPads outperforms A∗-NEAR and IDS-BB-NEAR achieving higher F1 scores and using much less time consumption. dPads also achieves competitive accuracy with NEAR on Crim13. On the Basketball dataset, although dPads achieves a bit higher F1 score, the architectures synthesized by dPads and A*-NEAR are exactly the same. However, dPads takes 70% less time to get the result. While A∗-NEAR completes the search faster than dPads on Fly-vs-fly, the program architecture synthesized by dPads leads to a program with a much better F1 score and higher accuracy. More quantitative analyses of the experiment results are given in Appendix C.3.
We visualize the results of dPads and NEAR in terms of F1 scores (y axis) and running times (x axis) on the 5 random seeds in Fig. 5 where red triangles refer to the results of dPads, and black plus marks and rectangles refer to the results of A∗-NEAR and IDS-BB-NEAR. dPads consistently outperforms NEAR in achieving higher F1 scores with less computation and is closer to the RNN baseline.
Although the RNN baseline provides better performance, dPads learns programs that are more interpretable. Fig. 6 depicts the best programs synthesized by dPads on Crim13 and SK152 (among all the 5 random seeds). The program for Crim13 has a simple architecture and achieves a high F1 score 0.475 (only 0.006 less than the RNN result). It invokes two FS,θ library functions: PositionAffine and DistanceAffine. This program is highly human-readable: it evaluates the likelihood of "sniff" by applying a position bias and if the distance between two mice is small they are doing a "sniff". The programmatic classifier for SK152 achieves an F1 score 0.35 which is close to the RNN baseline. It uses the arm and leg positions of a 3-D skeleton to complete a human-action classification. We show more examples about the interpretability of programs learned by dPads in Appendix C.5.
Map( Multiply(
SlideWindowAvg(Add( Multiply(LegsAffineθ1 (xt),
LegsAffineθ2 (xt)),

heading: 4.4 Ablation Studies
text: We introduce two more baselines to study the importance of node sharing and iterative graph unfolding. The first baseline does not use node sharing to reduce the size of a program derivation graph but still performs iterative graph unfolding. The second baseline directly expands a program derivation graph to the maximum depth but still applies node sharing. We report the comparison results over 5 random runs in Table 2. Without the two optimizations, limited by the size of GPU memory, dPads may either time-out or encounter out-of-memory error when searching programs that need deep structures to ensure high accuracy. This is because the size of a program derivation graph grows exponentially large with the height of program abstract syntax trees and the number of DSL production rules. Moreover, while being more complete, training without these two optimizations does not necessarily produce better results even when there is not OOM or timeout. For example, on Basketball, dPads achieves .945 F1 score. dPads without iterative graph unfolding only obtains .848 F1 score. We suspect this is because the program derivation graph without top-N preservation and iterative unfolding is more difficult to train as it contains significantly more parameters.
We further investigate the effect of the top-N preservation strategy in program architecture synthesis (Sec. 3.2) and its impact on searching optimal programs (Sec. 3.3). We set N to 1, 2, 3 respectively and study how dPads responds to these changes. Table 3 summarizes the average results of F1 scores, accuracy rates, time costs, and the standard deviations of these results. When N = 1, dPads extracts final programs greedily from optimized program derivation graphs without conducting further search. There is a significant decrease in time consumption compared with N = 2. However, dPads in this condition achieves less F1 scores and the results have higher variances, which suggests that architecture weights learned using only differentiable synthesis overfit to sub-optimal programs. dPads gets similar F1 scores when setting N = 3 compared to N = 2 but consumes more time. It even times-out on the Basketball dataset while searching an optimal program from the converged program derivation graph, since N = 3 incurs a much larger search space. This result confirms that scaling discrete program search to large architecture search spaces is challenging. dPads addresses this fundamental limitation by leveraging differentiable search of program architectures to significantly prune away unlikely search directions. Therefore, it suffices to set N = 2 in our experiments to balance search optimality and efficiency. Additional ablation study results are given in Appendix C.4. The limitations of dPads are discussed in Appendix D.1.

heading: 5 Related Work
text: Program Synthesis. Tasks in program synthesis aim to search for programs in a DSL to satisfy a specification over program inputs and outputs. There is also a growing literature on applying deep learning methods to guide the search over program architectures [6, 26–34]. There exist efforts that extend this line of research to program synthesis from noisy data [1, 2, 35–37, 3, 4]. These approaches either require a detailed hand-written program template or simply enumerate the discrete
space of program architectures permitted by a DSL. Additionally, most of these literature methods build models that are trained using corpora of synthesis problems and solutions, which are not available in our setting. The most closest work to our technique includes [38, 7] that enumerate the space of program architectures prioritizing search directions with feedback from machine learning models. Specifically, Lee et al. [38] uses a probabilistic model (trained from a synthesis problem corpus) to guide an A∗ search over discrete program syntax trees and NEAR [7] uses neural networks to approximate missing expressions in a partial program whose F1 score serves as an admissible heuristic to guide an A∗ search again over discrete program syntax trees. As opposed to these efforts, our method more efficiently conducts program synthesis in a continuous relaxation of the discrete space of language grammar rules and only searches the optimal program in a much reduced search space after differentiable architecture synthesis for addressing its gradient bias problem [14].
Differentiable Architecture Search. Neural architecture search has attracted much interest as a promising approach to automate deep learning tasks [39–42]. Particularly, our program architecture synthesis algorithm is inspired by DARTS [10]. This method uses a composition of softmaxes over all possible candidate operations between a fixed set of neural network nodes to relax the neural architecture search space. Various methods further improve neural architecture search efficiency and accuracy [14–17, 43, 44]. Applying this line of algorithms to program synthesis is challenging because the space of program architectures is much richer. Different operations take different number and types of inputs/outputs and may only be available at different points of a program. There is also no fixed bound on the number of program expressions. By relaxing the discrete search space of language grammar rules with node sharing and iterative unfolding of program derivation graphs, our method addresses the aforementioned challenges. To the best of our knowledge, this is the first approach that applies differentiable architecture search to program synthesis.

heading: 6 Conclusions
text: This paper presents a novel differentiable approach to program synthesis. With gradient descent, our method learns the probability distribution of program architectures induced by the context-free grammar of a DSL in a continuous relaxation of the discrete space of language grammar rules. This allows the synthesis algorithm to efficiently prune away unlikely program derivations to discover optimal program architectures. We have instantiated differentiable program architecture synthesis with effective optimization strategies including node sharing and iterative graph unfolding, scaling it to real-world sequence classification tasks. Experiment results demonstrate that our algorithm substantially outperforms state-of-the-art program learning approaches.
Programmatic models in high-level DSLs are a powerful abstraction for summarizing discovered knowledge from data in a human-interpretable way. Programmatic models incorporate inductive bias through structured symbolic primitives in a DSL and open opportunities for programmers to influence the semantic meaning of learned programs. However, the programming biases in a DSL may also leave opportunities to attack on the security and fairness of a learned model. One direction for future work is to apply formal program reasoning to enhance the trustworthiness of programmatic models.
Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers for their comments and suggestions. This work was supported by NSF Award #CCF-2124155 and the DARPA Symbiotic Design for Cyber Physical Systems program.

Review summaries:
A method for synthesising programs using gradient descent is presented, alternating between optimisation of operator parameters (constants) and of the program structure (nested expressions). The submission focuses on reducing the complexity of the search for correct structures, using the idea of sharing different nodes in the search tree (i.e., allow them to appear in different contexts) as well as initially approximating subexpressions by neural networks and only starting to learn to represent them by programs when the subtree appears to be a promising candidate. Experiments on four small datasets show that the method compares favourably to a baseline in synthesizing programs that explain observed behaviour.

This work proposes a method for differentiable synthesis of program architectures. A program derivation graph is encoded as a differentiable program whose output is a weighted output of all the programs in the graph. The method learns a probability distribution over all possible program derivations induced by a context-free grammar. The grammar rule selection weights and the program parameters are co-optimized iteratively with respect to a loss function over program outputs. The approach is evaluated on four sequence classification tasks. The discovered architectures have better F1 scores as compared to the state-of-the-art program synthesis methods (A*-NEAR and IDS-BB-NEAR). 

This paper considers the task of synthesizing differentiable programs for sequence classification tasks. It introduces a novel method, dPads, that first constructs a program derivation graph representing a subset of the highest probability possible architectures under a CFG, and subsequently uses an A*-like search to find a program in the graph that balances minimizing complexity with maximizing accuracy. Central to the derivation graph construction method are the ideas of (1) iterative training of architecture weights and neural approximations of subexpressions, (2) node sharing, and (3) iterative graph unfolding. The method is evaluated on four sequence classification tasks, where it is found to have better performance than the program synthesis baselines considered, and worse performance than an RNN baseline, with the key advantage over the RNN being the interpretability of the resultant programs from dPads.

This paper introduces dPads, an approach to learning interpretable programs to perform sequence classification tasks, as an alternative to using RNNs which are less interpretable and possibly less robust. The programs are generated using a context-free grammar (adapted from prior work) of differentiable operations applied to sequences. The ultimate objective is to find a program that obtains high classification accuracy on a dataset, while having low architectural cost. This is done by using a continuous relaxation of the discrete choices in the grammar, using a softmax over all possible grammar production rules instead of a categorical choice, with learnable weights. Further optimizations include “node sharing” (where two nodes in the program derivation graph are shared if they represent the same nonterminal and thus can be expanded the same way) and “iterative graph unfolding” which is somewhat like a beam search over the program derivation process, narrowing down the earlier choices using a guess for their quality, resulting in less combinatorial explosion (higher efficiency) at the cost of a fully complete search. As a final step, an A* search is used to choose a single complete program with high accuracy and low cost. Experiments on 4 sequence classification datasets show that dPads performs better than prior work NEAR, but worse than plain RNNs (which are not interpretable programs).