Automating the Analysis of Parsing Algorithms (and other Dynamic Programs)

Tim Vieira, Ryan Cotterell, Jason Eisner · 2025

Read Automating the Analysis of Parsing Algorithms (and other Dynamic Programs) by Tim Vieira, Ryan Cotterell, Jason Eisner (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-23665.txt.

Introduction

Tim Vieira, Ryan Cotterell, and Jason Eisner build tooling that analyzes algorithms the way compilers analyze code. Researchers in natural language processing routinely design dynamic programming algorithms over rich formal structures. They then prove by hand that the running time is bounded, that derived quantities have the right types, and that no part of the computation is dead or redundant. Those proofs are tedious and error-prone.

Their system automates much of that analysis, inferring types, flagging dead and redundant code, and deriving parametric runtime and space bounds for the algorithm as written. Applied to a range of NLP algorithms, it reproduced the analyses their designers had done by hand, sparing each new tool's author weeks of checked proofs. The manuscript dates from 2021 and was accepted by the Transactions of the Association for Computational Linguistics, though it was not revised for publication.

Catalog record

CREATORTim Vieira, Ryan Cotterell, Jason Eisner
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE79 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-23665

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Automating the Analysis of Parsing Algorithms (and other Dynamic Programs) Tim Vieira, Ryan Cotterell, Jason Eisner Abstract Much algorithmic research in NLP aims to efficiently manipulate rich formal structures. An algorithm designer typically seeks to provide guarantees about their proposed algorithm—for example, that its running time or space complexity is upper-bounded as a certain function of its input size. They may also wish to determine the necessary properties of the quantities derived by the algorithm to synthesize efficient data structures and verify type errors. In this paper, we develop a system for helping programmers to perform these types of analyses. We apply our system to a number of NLP algorithms and find that it successfully infers types, dead and redundant code, and parametric runtime and space complexity bounds. https://github.com/timvieira/dyna-pi 1 Introduction The goal of this work is to further the pursuit of declarative programming for NLP ( 30 ; 16 ) . The promise of declarative programming is that it enables the programmer to specify their algorithm in a high-level language without worrying about low-level implementation details and instead focus on the correctness of the algorithm itself. This paper focuses on Dyna ( 12 ) , a declarative programming language that was designed to appeal to NLP researchers. Dyna is a concise language for implementing dynamic programs, which have long been the workhorse of structured prediction in many NLP problems. Specifically, NLP makes heavy use of probabilistic models based on rich linguistic formalisms, e.g. finite-state transduction 29 , context-free parsing 17 , dependency parsing 13 and mildly context-sensitive parsing 40 , in which inference requires dynamic programming. Such algorithms are often difficult to implement correctly and efficiently. 1 1 1 These classical NLP algorithms are still often used for deep structured prediction, when the score of a structure decomposes into local terms that are computed by neural networks ( 8 ; 34 ; 25 ; 23 ; 32 ; 36 ) . Now we turn to static analysis of these declarative programs—e.g., type analysis, runtime complexity analysis, and space complexity analysis ( 6 ; 31 ) . Such analysis is important for understanding the space of possible program behaviors on unknown input data. 2 2 2 Although we do not explore it in this paper, we also mention that static program analysis is essential for compiling efficient code. Type inference, for example, allows the compiler to synthesize efficient data structures for representing internal objects and efficient code for pattern-matching against them. Automated program analysis aids programmers because manual program analysis may be tedious and error-prone. In the context of NLP, automated program analysis of dynamic programs (for instance, as specified in Dyna) has the potential to help NLP algorithms researchers correctly and speedily analyze their creations. Indeed, the NLP literature provides examples where such automated analysis could have been of use. For example, 18 derive a projective dependency parsing algorithm with a stated complexity of \mathcal{O}\!\left(n^{7}\right) ; subsequent work 38 improved the analysis to discover the complexity is actually \mathcal{O}\!\left(n^{6}\right) . Our automated system correctly gives the \mathcal{O}\!\left(n^{6}\right) analysis. As another example, 24 discovered a surprising property of their tabular dependency parsing algorithm. Their initial naive analysis gave time complexity of \mathcal{O}\!\left(n^{5}\right) and space complexity of \mathcal{O}\!\left(n^{3}\right) , but they were able to tighten this analysis to a time complexity of \mathcal{O}\!\left(n^{3}\right) and space complexity of \mathcal{O}\!\left(n^{2}\right) , after noticing that the objects built by their transition system always had two equal variables (which could be proved inductively). They then revised their program formulation to eliminate the redundant variable. Our system automatically discovers the redundancy and the tighter analysis when run on the relevant program. 10 noted that Dyna programs can be automatically transformed in various ways that preserve their semantics but might affect their worst-case runtime. To automatically search for sequences of transformations that improve worst-case runtime, we would need to ascertain what that worst-case runtime is, e.g., by obtaining an asymptotic bound that is as tight as possible. This paper provides a theory for the automated analysis of Dyna programs as well as a working system for performing that analysis. Again, in the context of NLP, our automated analysis yields big- \mathcal{O} bounds on runtime and space complexity—the sort of bounds that were obtained manually by many NLP authors. Concretely, this paper makes the following contributions: (i) a notation for specifying and reasoning about types ( section 3 ), (ii) a novel algorithm for type inference for Dyna programs ( section 4 ), (iii) a notation for specifying input size, (iv) a time and space complexity analyzer ( section 5 ) that automates and refines the prevalent runtime and space analysis technique in the NLP literature, which is based on 28 . Our paper also contains numerous examples from the NLP literature rewritten in Dyna and presents them in a unified manner in order to demonstrate that our proposed algorithm arrives at the same analysis as attested in the literature. 2 Dynamic Programming in Dyna Dyna is a high-level, domain-specific language for concisely expressing dynamic programs as recurrence relations. We briefly describe the language here, but refer the reader to 12 for a proper presentation. We will start with simple or familiar computations as examples. Example 1 . Matrix–matrix multiplication plus the identity matrix. ⬇ 1 a ( I , K ) += b ( I , J ) * c ( J , K ). 2 a ( I , I ) += 1. This program defines a collection of derived items a ( I , K ) in terms of other items b ( I , J ) and c ( J , K ) , which may themselves be derived from similar expressions or inputs. For any {{(\texttt{\text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language\footnotesize{\@listingGroup{ltx_lst_keywords3}{\color[rgb]{0,0.5,0.18}{I}}}}}}}},\texttt{\text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language\footnotesize{\@listingGroup{ltx_lst_keywords3}{\color[rgb]{0,0.5,0.18}{K}}}}}}}}) pair, the program defines the value a ( I , K ) to be {\big(\sum_{\texttt{\text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language\footnotesize{\@listingGroup{ltx_lst_keywords3}{\color[rgb]{0,0.5,0.18}{J}}}}}}}}} b ( I , J ) \cdot c ( J , K ) {{\big)+1[\texttt{\text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language\footnotesize{\@listingGroup{ltx_lst_keywords3}{\color[rgb]{0,0.5,0.18}{I}}}}}}}}=\texttt{\text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language\footnotesize{\@listingGroup{ltx_lst_keywords3}{\color[rgb]{0,0.5,0.18}{K}}}}}}}}] . The rules’ use of += means that the value is being defined as a summation. The first rule contributes one summand for each possible value of J , since J appears only on the right-hand side of that rule. The second rule contributes the additional summand 1 in the case where {{\texttt{\text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language\footnotesize{\@listingGroup{ltx_lst_keywords3}{\color[rgb]{0,0.5,0.18}{I}}}}}}}}=\texttt{\text{\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@numbers\lst@@@set@language\footnotesize{\@listingGroup{ltx_lst_keywords3}{\color[rgb]{0,0.5,0.18}{K}}}}}}}} . Dyna rules may be recursive: Example 2 . Minimum-cost path in a graph. ⬇ 2 beta ( J ) min = stop ( J ). 3 beta ( I ) min = cost ( I , J ) + beta ( J ). This program defines \mathgtt{b} ( I ) to be the cost of the minimum-cost path in a graph from the node I to any terminal node J . Here stop ( J ) must first be defined to be the cost of stopping at J when J is a terminal node (and should be left undefined otherwise). Also, cost ( I , J ) must first be defined to be the cost of the directed edge from I to J (and should be left undefined if there is no such edge). Example 3 . Weighted context-free parsing with CKY ( 4 ; 43 ; 22 ) , or, more precisely, the inside algorithm ( 2 ; 20 ) : ⬇ 3

Read the complete text