Searching for More Efficient Dynamic Programs

Tim Vieira, Ryan Cotterell, Jason Eisner

Abstract: This paper introduces an automated system for optimizing dynamic programming (DP) algorithms, a task traditionally left to human "algorithmists." By treating program optimization as a heuristic search over semantically equivalent program transformations, the authors successfully rediscover decades of classic speedups in Natural Language Processing (NLP) automatically.

Introduction

In fields like Natural Language Processing (NLP), researchers frequently solve combinatorial problems—such as parsing or sequence labeling—using dynamic programming. However, when a new DP algorithm is first proposed, it is often suboptimal. Historically, faster versions are published years later after researchers manually apply clever algebraic transformations. This manual process is laborious, error-prone, and requires deep expertise. The authors address a fundamental question: Can we automate the discovery of these efficient algorithms?

The primary challenge in automation is that reaching a faster version often requires "uphill" moves—transformations that temporarily increase program complexity or runtime before a subsequent step unlocks a massive speedup. Simple greedy optimization strategies are therefore insufficient.

The authors frame algorithmic optimization as a graph search problem. In this framework, the search space is defined as follows:

  • Nodes: Programs expressed in Dyna, a declarative language for dynamic programming.
  • Edges: Semantics-preserving transformations, including Fold (eliminating variables by creating intermediate sub-problems), Unfold (inlining a definition), and Rule Elimination (removing redundancy).
  • Cost Function: The "degree" of the program, defined as the maximum number of variables in any single rule. This serves as a computationally cheap proxy for asymptotic runtime (e.g., a degree of 3 implies $O(n^3)$).
The optimization process framed as a search over program transformations, showing transitions between program states and their associated costs.

To navigate this massive search space, the system employs Beam Search and Monte Carlo Tree Search (MCTS). To make the search tractable, the authors introduced Macro Folding, a technique that allows the system to optimize individual rules independently and memoize the results, exponentially shrinking the global search space.

Experimental Evaluation

The system was evaluated using two distinct approaches:

  1. Unit Tests: A collection of classic NLP algorithms with known optimal runtimes, such as CKY parsing, Viterbi, Eisenr & Satta’s dependency parsing, and the Bar-Hillel construction.
  2. Stress Tests: To simulate a "naive programmer," the authors took optimal programs and applied random transformations to make them highly inefficient. They then tested whether the search algorithms could recover the original, optimal versions.

Key Results and Insights

The system successfully rediscovered several famous speedups from the literature without human intervention:

  • Projective Dependency Parsing: Improved from $O(n^5)$ to $O(n^4)$.
  • Split-head Factored Parsing: Improved from $O(n^5)$ to $O(n^3)$.
  • CKY Parsing: Optimized the grammar constant from $K^3$ to $K^2$.
  • Inversion Transduction Grammars (ITG): Improved from $O(n^7)$ to $O(n^6)$.

In stress tests, Beam Search generally outperformed MCTS when provided with a sufficiently large beam. The results highlighted that optimization is search: algorithmic discovery is essentially a pathfinding problem in the space of equivalent logic. Furthermore, the necessity of "uphill" moves was confirmed; reaching an $O(n^3)$ state often required passing through intermediate states with higher degrees.

Limitations and Future Work

While successful, the current system uses a coarse cost metric (degree) that ignores constant factors, data sparsity, and hardware-specific concerns like cache locality. Additionally, folding reduces runtime but often increases memory usage—a tradeoff the current system does not yet optimize. Future work aims to develop a hybrid cost function that combines asymptotic analysis with empirical timing on sample data to refine the search further.

Summary updated

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