# Searching for More Efficient Dynamic Programs

arXiv: https://arxiv.org/abs/2109.06966 · HTML: https://mlsanity.com/paper/2109.06966/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 90 references that are in the map.
- First posted on arXiv 14 Sep 2021.

## Builds on (most cited first, 17 of 17)

- [Stanza: A Python Natural Language Processing Toolkit for Many Human Languages](https://mlsanity.com/paper/2003.07082/) (2020)
- [Deep Biaffine Attention for Neural Dependency Parsing](https://mlsanity.com/paper/1611.01734/) (2016)
- [Monte Carlo Tree Search: A Review of Recent Modifications and Applications](https://mlsanity.com/paper/2103.04931/) (2021)
- [Structured Attention Networks](https://mlsanity.com/paper/1702.00887/) (2017)
- [A Minimal Span-Based Neural Constituency Parser](https://mlsanity.com/paper/1705.03919/) (2017)
- [A General Framework for Multi-fidelity Bayesian Optimization with Gaussian Processes](https://mlsanity.com/paper/1811.00755/) (2018)
- [Torch-Struct: Deep Structured Prediction Library](https://mlsanity.com/paper/2002.00876/) (2020)
- [Best-First Beam Search](https://mlsanity.com/paper/2007.03909/) (2020)
- [Exact Hard Monotonic Attention for Character-Level Transduction](https://mlsanity.com/paper/1905.06319/) (2019)
- [Neural Architecture Search using Deep Neural Networks and Monte Carlo Tree Search](https://mlsanity.com/paper/1805.07440/) (2018)
- [Hard Non-Monotonic Attention for Character-Level Transduction](https://mlsanity.com/paper/1808.10024/) (2018)
- [Towards modular and programmable architecture search](https://mlsanity.com/paper/1909.13404/) (2019)
- [Neural CRF Parsing](https://mlsanity.com/paper/1507.03641/) (2015)
- [Global Neural CCG Parsing with Optimality Guarantees](https://mlsanity.com/paper/1607.01432/) (2016)
- [On the Complexity of CCG Parsing](https://mlsanity.com/paper/1702.06594/) (2017)
- [A Machine Learning guided Rewriting Approach for ASP Logic Programs](https://mlsanity.com/paper/2009.10252/) (2020)
- [Linear-Time Constituency Parsing with RNNs and Dynamic Programming](https://mlsanity.com/paper/1805.06995/) (2018)

## Built on by (most cited first, 1 of 1)

- [Dynamic Programming in Rank Space: Scaling Structured Inference with Low-Rank HMMs and PCFGs](https://mlsanity.com/paper/2205.00484/) (2022)

## Abstract (arXiv)

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.