Searching for More Efficient Dynamic Programs (2021)

Abstract: Computational models of human language often involve combinatorial problems. For instance, a probabilistic parser may marginalize over exponentially many trees to make predictions. Algorithms for such problems often employ dynamic programming and are not always unique. Finding one with optimal asymptotic runtime can be unintuitive, time-consuming, and error-prone. Our work aims to automate this laborious process. Given an initial correct declarative program, we search for a sequence of semantics-preserving transformations to improve its running time as much as possible. To this end, we describe a set of program transformations, a simple metric for assessing the efficiency of a transformed program, and a heuristic search procedure to improve this metric. We show that in practice, automated search—like the mental search performed by human programmers—can find substantial improvements to the initial program. Empirically, we show that many speed-ups described in the NLP literature could have been discovered automatically by our system.

## introduction algorithmic research in natural language processing (nlp) has focused-in large part-on developing dynamic programming solutions to combinatorial problems that arise in the field @xcite . such algorithms have been introduced over the years for countless linguistic formalisms, such as finite-state transduction @xcite @xcite , context-free parsing @xcite , dependency parsing @xcite @xcite and mildly context-sensitive parsing @xcite @xcite . in recent years, the same algorithms have often been used for deep structured prediction, using a neural scoring function that decomposes over the structure @xcite @xcite @xcite @xcite @xcite @xcite . when a dynamic programming algorithm for a new problem is first introduced in the literature, its runtime may not be optimal-faster versions are often published over time. indeed, the process of introducing a first algorithm and subsequently finding improvements is common throughout computer science. in the case of dynamic programming, there are program transformations that may be exploited to derive algorithms with a faster runtime @xcite . these transformations map a program to another program with the same meaning (given the same inputs, it will produce the same outputs), but with possibly different running time. this paper shows how to search over program transformation sequences in order to automatically discover faster algorithms, automating the work of the nlp algorithmist. consider the following instances 1 of published dynamic programs whose runtime bounds were later improved using specific applications of the program transformations mentioned above. o n 8 in vijay- @xcite , sped up to o n 7 by @xcite . in this paper, we ask a simple question: can we automatically discover these faster algorithms? typically, a dynamic programming algorithm can be regarded as performing inference in an semiring-weighted deduction system @xcite . @xcite provided a programming language, dyna, for expressing such deduction systems, along with a compiler that produced fast inference code. all of the runtime improvements mentioned above are examples of source-to-source program transformations @xcite ). 2 our work, depicted in fig. 1 , poses program optimization as a search over transformed versions of the initial program, an idea that was suggested as future work by @xcite . our contribution is to show that two classic search algorithmsbeam search (reddy, 1977; meister et al., 2 the closest work in the nlp literature is @xcite , who proposed the junction-tree minimization to speed up dynamic programs, which corresponds to only considering the fold transformation. outside of nlp, @xcite learn to fold in the context of answer set programs. our work considers a broader range of program transformations. 2020) and monte carlo tree search @xcite -are effective for this purpose, rapidly rediscovering many of the known optimizations listed above. to set up this solution, the following sections describe the elements of the search problem: our space of possible programs ( §2), a simple cost function that serves as a proxy for program runtime ( §3), and a set of directed edges that connect semantically equivalent programs ( §4). our search starts at the initial program and seeks a low-cost equivalent program that can be reached by traversing directed edges. in §5, we review the beam search and mcts algorithms that we will use for this purpose in the experiments of §6. ## our space of dynamic programs we will consider programs that are expressed in the original version of the dyna language @xcite , which is essentially a way of writing down the recurrence relations of a dynamic programming algorithm. in this section, we only briefly describe the language and refer the reader to @xcite for a more complete introduction. to start, consider the following examples. example 1. the total weight of length-4 paths in a graph with edge weights w: this program defines the value of a derived item z in terms of input items w(...). the value of z is y1 • • • y5 w(y1,y2)•w(y2,y3)•w(y3,y4)•w(y4,y5). 3 no-tice that there is no need to clutter the expression with explicit summations or control-flow constructs such as for-loops: all variables (denoted by capitalized letters) that appear only on the right-hand side of += are summed over. dyna programs elegantly enable recursive computation by allowing the value of an item to be defined in terms of other items of the same kind. example 2. the viterbi algorithm @xcite finds the most probable path in a graph from a node labeled "a" to a node labeled "z" with edge probabilities (or weights) w: 21 α("a") @xmath0. 23 z += α("z"). the second rule is recursive. for each possible value of j on the left-hand side, it defines α(j) by maximizing over assignments to the other variables on the right-hand side (namely i). maximization is specified by max=, whereas summation in example 1 was specified by +=. example 3. weighted context-free parsing with cky @xcite @xcite , or more precisely the inside algorithm @xcite ): foot_2 24 β(x,i,k) += β(y,i,j) * β(z,j,k) * γ(x,y,z). 25 β(x,i,k) += γ(x,y) * word(y,i,k). 26 z += β(root,0,n) * len(n). the values of the γ items should be defined to be the weights of the corresponding context-free grammar rules: for example, the item γ(s,np,vp) = 0.7 encodes the production s 0.7 --→ np vp). also, the item word(x, i, k) should be 1 if the input word x appears at position i of the input sentence and @xmath1, and should be 0 otherwise. then for any nonterminal symbol x and any substring spanning positions [i, k) of the input sentence, the item β(x,i,k) represents the total weight of all grammatical derivations of that substring from x. more generally, a dyna program p is a collection of rules, each rule having the form h ⊕= b 1 ⊗ • • • ⊗ b k . here ⊕, ⊗ can be any pair of operations that form a semiring (goodman, 1999; huang, 2009), such as +, * in example 1 and example 3, or max, * in example 2. 5 we call h the head, and b 1 , • • • , b k the body of the rule. each b k in the body is called a subgoal. let head(r) and body(r) denote the head and body terms in a rule r. we assume that all rules in the program use the same semiring. 6 the structured names of items are terms, which are nested typed tuples as in prolog. for example, f(g(z,h(3))) is a 1-tuple of type f, whose single element is a 2tuple of type g, and so on. the rules use captialized variables such as x to pattern-match against subterms, where a variable that is repeated in a rule must have the same value each time. let vars(•) denote the set of variables contained in a term, e.g., vars(f(g(x), 4, x)) → {x}. the dyna language allows logical side conditions on a rule, e.g., goal += f(x) for @xmath2. this is syntactic sugar for goal += f(x) * lessthan(x,10), where the value of each lessthan(a,b) term is the one or zero element of the semiring, according to whether @xmath3. ## program analysis our goal is to search for a fast dyna program. we will assume that the programs are executed using the forward chaining algorithm described by @xcite . 7 in principle, we could evaluate a candidate program's runtime by actually executing it, but this would be very expensive and would also require us to specify particular inputs to the program. instead, as our search objective, we will use a simple asymptotic upper bound on the program's runtime, based on a folk theorem from the datalog community that has a long history of use. many nlp papers have analyzed the runtime of their algorithms using either this folk theorem or a more refined version given by @xcite : @xcite ; @xcite ; @xcite ; @xcite ; @xcite ; @xcite ; @xcite ; @xcite ; @xcite . the folk theorem says that, under certain conditions (discussed later), the running time of forward chaining execution of a given program is at worst linear in the number of ways to instantiate its rules, i.e., bind the variables to constants. a relatively simple bound on rule instantiations is available if we can establish that each variable in the program can be bound in at most η different ways. in that case, given some other conditions discussed at the end of this section, the number of ways to instan-tiate a rule with k variables is bounded by o η k . program p's total runtime is o η degree(p ) where degree(p) is the maximum number of variables in any rule of p. we therefore take degree to be the cost function to minimize during search. consider example 1. evaluating this program under the forward-chaining algorithm will instantiate the rule by binding the 5 variables x 1 , x 2 , x 3 , x 4 , x 5 to constants. then, the number of rule instantiations is o η 5 . similarly, example 3 runs in o η 6 , as the first rule must sum over 6 variables, x, y, z, i, j, k. note that this is a coarse-grained analysis: the runtime is usually given more specifically as o n 3 k 3 where n is the number of sentence positions, and k is the number of grammar symbols. (this finergrained bound can be achieved by the theorem of @xcite : the intuition is that the variables i, j, k can each be bound in o(n) ways while x, y, z can each be bound in o(k) ways.) however, the simpler analysis o η 6 gives us a single exponent to reduce, namely 6. to see the cost function in action, consider that example 1 has a running time of o η 5 , whereas the following equivalent program runs in o η similarly, in example 3, we can sum over the variable y separately from k as follows: example 5. faster cky (example 3) 32 β(x,i,k) += tmp(i,j,x,z) * β(z,j,k). 33 tmp(i,j,x,z) += β(y,i,j) * γ(x,y,z). the degree analysis of a dyna program only leads to a valid o-expression under some conditions, which we will now discuss. (1) the degree bound requires the grounded program to be acyclic @xcite . cycles slow down forward chaining because it must iterate to a numerical fixed point. generally, the number of iterations required to reach a fixed-point is data dependent. 8 (2) the degree bound assumes that all of the relations in the program are bounded in size. the degree bound requires that terms are not nested; this prevents the user from encoding infinite sets, such as the peano integers. additionally, it assumes that the program's rules are all range-restricted (footnote 7). we will see in §6 that simply optimizing degree is sufficient to recover a number of asymptotic speedups noted in the nlp literature (see §1) as well as asymptotic speedups on synthetic programs. that said, the degree analysis might be loose for many reasons. the upper bounds derived using our methodology assume that relations are dense. often relations are statically known to be sparse. many low-level details affect actual execution time, but do not matter for asymptotic complexity. for example, memory layouts (e.g., row-order or column-order layout of a dense array in memory), sparse vs. dense representations of relations (e.g., hash tables vs. arrays), and indexes on relations (including sorted order) can have a dramatic effect on the running time in practice. however, they will not manifest in the degree analysis (e.g. an obvious alternative cost function would be the empirical execution time of executing the transformed program on a workload of representative inputs (e.g., running a transformed parser on actual sentences from the penn treebank @xcite ). but as we noted earlier, such a cost function might be impractically expensive. for example, evaluating the degree of a degree-1000 program is linear in the size of the program, whereas evaluating the wallclock time is o η 1000 . optimizing the program degree is a crucial design choice as it enables a more exhaustive search in practice. additionally, it sidesteps the need to optimize for a specific workload. however, in future work, we would like to investigate hybrid search algorithms (e.g., song et al. (2019) ) that do attempt to minimize empirical execution time, but replace some of the expensive evaluations of that with cheaper approxigeneral semirings. for example, the program a += r * a. a += 1. encodes a geometric series; it may take many iterations to converge if |r| is close to 1, and will diverge if |r| ≥ 1. the efficiency of this cyclic program thus depends on the value of the input parameter r. ## program transformations this section details the set of transforms that we consider in this paper. none of the transforms are novel to this work. they have been detailed and proved correct in @xcite . we include them in our discussion for completeness of presentation and to illuminate the challenges of our search problem. we provide pseudocode for the transforms in app. b, but defer to @xcite for a more thorough discussion. input and output declarations. we assume that the initial program declares some items as input and/or output items. the rest are considered intermediate items. a program transform must preserve the mapping from a valuation of the input items to a valuation of the output items. (a valuation is an assignment of a value to each item.) however, a program transform is free to introduce, destroy, or alter intermediate items. for example, for cky, the input and output items are declared as follows: 34 input word(x,i,k); γ(x,y,z); γ(x,y). ## program improvement our goal is to find a sequence of transformations to the user's program p 0 that gives the lowest cost, cost(p) @xmath4. in this section, we provide two effective search algorithms for approaching this goal: beam search and monte carlo tree search. ## experiments the goal of this paper was to devise a system for automatically improving typical dynamic programming problems. to evaluate whether we achieved this goal, we devised a set of unit tests and stress avg rel degree % optimal benchmark beam mcts beam mcts the percentage of the 10 random programs for which we find the optimal degree within the search budget (@xmath5, @xmath6. in many rows, this is 100%. however, in some recursive cases with two or more recursive subgoals, the randomly applied unfolds make the programs very big, which makes them difficult to optimize. both methods performed poorly on the cky+grammar benchmark, which is by far the longest program we consider as it contains 35 rules in its original form. unit tests. our unit tests include most of the faux pas mentioned in §1; the precise set of programs is provided in app. a. however, recovering these instances is relatively easy as they typically only require a few fold transformations. thus, they are not a good stress test for our automated system. in all of our test cases, we know the optimal degree, and we have verified that both mcts (with @xmath7. stress tests. the inspiration for our stress tests is to imagine that a naïve programmer produces a suboptimal program. for example, they may have chosen the poor variable-elimination order in example 6, and, now, we would like to "undo" their handiwork via unfold, elimination, and fold. we operationalize such a naïve programmer by imaging that they have applied a sequence of random we compare the search algorithms according to the percentage of stress tests that they are able to solve optimally. we also consider the relative degree, i.e., the fraction of the possible improvement that was actually achieved: degree(p 1 )-degree(p) ## conclusion we have presented a system for automatically analyzing and improving dynamic programming algorithms. expressing those algorithms in the dyna programming language allows us to successively apply program transformations introduced by @xcite . we showed that monte carlo tree search and beam search allows us to automatically discover asymptotically faster algorithms.