Searching for More Efficient Dynamic Programs

Tim Vieira, Ryan Cotterell, Jason Eisner

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 common speed-ups described in the NLP literature could have been discovered automatically by our system.

Introduction

Dynamic programming (DP) is the backbone of natural language processing (NLP), powering essential tasks from parsing to sequence labeling. However, designing an optimal DP algorithm is a significant challenge. When a new problem is introduced, the initial published algorithm is often suboptimal (e.g., $O(n^6)$). Over time, researchers manually "binarize" rules or apply "variable elimination" to reduce complexity, eventually reaching more efficient bounds like $O(n^3)$ or $O(n^4)$.

This manual optimization process is slow, error-prone, and requires deep algorithmic intuition. This research introduces an "automated algorithmist" that optimizes DP routines by representing them as declarative programs and applying a sequence of semantics-preserving transformations to discover more efficient versions automatically.

The authors frame the optimization task as a graph search problem. The states in this search space are programs written in Dyna, a declarative language designed for specifying DP recursions. Transitions between states consist of semantics-preserving transformations, including:

  • Fold: Eliminating a variable by creating an intermediate "memoized" item (analogous to binarization in parsing).
  • Unfold: The inverse of folding, which "inlines" a definition to potentially reveal better folding opportunities later.
  • Rule Elimination: Removing redundant or specialized rules.
A search space of program transformations where nodes represent Dyna programs and edges represent semantics-preserving transformations like folding and unfolding.

To navigate this massive search space, the system employs Beam Search and Monte Carlo Tree Search (MCTS). The cost function used is the "degree" of the program—the maximum number of variables in any single rule—which serves as a proxy for asymptotic complexity.

Key Insights

One of the critical findings is the "uphill" nature of optimization. Often, the system must apply an "unfold" transformation that temporarily increases the program's complexity (the degree) before finding a subsequent "fold" that drops the complexity significantly. This non-monotonic progress explains why simple greedy search fails and why more robust methods like MCTS are necessary.

Additionally, the authors introduced "Macro-folding," which treats the optimization of a single rule as a sub-problem. This allows the system to solve and reuse results, providing an exponential reduction in the search space.

Empirical Results

The system was evaluated on a suite of benchmarks, including classic algorithms like CKY parsing, Viterbi, and HMMs, as well as complex projective dependency parsing models.

  • Rediscovering History: The system successfully rediscovered several famous speedups from NLP literature. For example, it automatically transformed a naive $O(n^5)$ projective dependency parser into the $O(n^4)$ version originally published by Eisner and Satta (1999).
  • Search Performance: In stress tests involving randomly constructed, semantically equivalent versions of benchmark programs, both Beam Search and MCTS consistently found the optimal degree.
  • Ablation Studies: Results showed that macro-folding and the use of a "to-do list" for rules were critical for performance; without these, the search often timed out or became trapped in local optima.

Limitations and Future Work

While the current system effectively optimizes for time complexity (degree), it does not yet account for space-time tradeoffs. Folding often introduces new intermediate tables, increasing memory usage. Future work could aim to optimize for a Pareto frontier of both space and time. Furthermore, the current degree-based analysis assumes acyclic DP state-spaces; handling cyclic programs would require more sophisticated cost functions. Finally, incorporating empirical timing could help account for constant factors and hardware-specific optimizations that asymptotic analysis ignores.

Summary updated

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 common speed-ups described in the NLP literature could have been discovered automatically by our system.
BibTeX
@inproceedings{vieira2021searching,
  author = {Tim Vieira and Ryan Cotterell and Jason Eisner},
  title = {{Searching for More Efficient Dynamic Programs}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2021},
  url = {https://openreview.net/forum?id=_r0gZBG4jos},
}
Figure