Automating the Analysis and Improvement of Dynamic Programming Algorithms with Applications to Natural Language Processing

• URL: http://arxiv.org/abs/2603.13242v1
• Date: Fri, 20 Feb 2026 02:01:27 GMT
• Title: Automating the Analysis and Improvement of Dynamic Programming Algorithms with Applications to Natural Language Processing
• Abstract summary: This thesis develops a system for automatically analyzing and improving dynamic programs.<n>Finding a correct program with the optimal runtime can be unintuitive, time-consuming, and error-prone.<n>We show that, in practice, automated search can find substantial improvements to the initial program.
• Score: 10.169706093621421
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This thesis develops a system for automatically analyzing and improving dynamic programs, such as those that have driven progress in natural language processing and computer science, more generally, for decades. Finding a correct program with the optimal asymptotic runtime can be unintuitive, time-consuming, and error-prone. This thesis aims to automate this laborious process. To this end, we develop an approach based on 1. a high-level, domain-specific language called Dyna for concisely specifying dynamic programs 2. a general-purpose solver to efficiently execute these programs 3. a static analysis system that provides type analysis and worst-case time/space complexity analyses 4. a rich collection of meaning-preserving transformations to programs, which systematizes the repeated insights of numerous authors when speeding up algorithms in the literature 5. a search algorithm for identifying a good sequence of transformations that reduce the runtime complexity, given an initial, correct program 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. We provide a freely available prototype system at https://github.com/timvieira/dyna-pi.

Related papers

• Grammar-Guided Evolutionary Search for Discrete Prompt Optimisation [63.97051732013936]
  We propose an evolutionary search approach to automated discrete prompt optimisation consisting of two phases.<n>In the first phase, grammar-guided genetic programming is invoked to synthesise prompt-creating programmes.<n>In the second phase, local search is applied to explore the neighbourhoods of best-performing programmes.
  arXiv  Detail & Related papers  (2025-07-14T14:34:15Z)
• LLM Program Optimization via Retrieval Augmented Search [71.40092732256252]
  We propose a blackbox adaptation method called Retrieval Augmented Search (RAS) that performs beam search over candidate optimizations.<n>We show that RAS performs 1.8$times$ better than prior state-of-the-art blackbox adaptation strategies.<n>We also propose a method called AEGIS for improving interpretability by decomposing training examples into "atomic edits"
  arXiv  Detail & Related papers  (2025-01-31T06:34:47Z)
• Searching Latent Program Spaces [0.0]
  We propose the Latent Program Network (LPN), a new architecture that builds in test-time search directly into neural models.<n>It searches through a compact latent space at test time and bypasses the need for pre-defined domain-specific languages.<n>Tested on the ARC-AGI benchmark, we demonstrate that can both learn a compact program space and search through it at test time to adapt to novel tasks.
  arXiv  Detail & Related papers  (2024-11-13T15:50:32Z)
• Improved Tree Search for Automatic Program Synthesis [91.3755431537592]
  A key element is being able to perform an efficient search in the space of valid programs. Here, we suggest a variant of MCTS that leads to state of the art results on two vastly different DSLs.
  arXiv  Detail & Related papers  (2023-03-13T15:09:52Z)
• Genetic Micro-Programs for Automated Software Testing with Large Path Coverage [0.0]
  Existing software testing techniques focus on utilising search algorithms to discover input values that achieve high execution path coverage. This paper outlines a novel genetic programming framework, where the evolved solutions are not input values, but micro-programs that can repeatedly generate input values. We argue that our approach can be generalised such as to be applied to many different software systems, and is thus not specific to merely the particular software component on which it was trained.
  arXiv  Detail & Related papers  (2023-02-14T18:47:21Z)
• Searching for More Efficient Dynamic Programs [61.79535031840558]
  We describe a set of program transformations, a simple metric for assessing the efficiency of a transformed program, and a search procedure to improve this metric. We show that in practice, automated search can find substantial improvements to the initial program.
  arXiv  Detail & Related papers  (2021-09-14T20:52:55Z)
• Recent Developments in Program Synthesis with Evolutionary Algorithms [1.8047694351309207]
  We identify the relevant evolutionary program synthesis approaches and provide an in-depth analysis of their performance. The most influential approaches we identify are stack-based, grammar-guided, as well as linear genetic programming. For future work, we encourage researchers not only to use a program's output for assessing the quality of a solution but also the way towards a solution.
  arXiv  Detail & Related papers  (2021-08-27T11:38:27Z)
• Leveraging Language to Learn Program Abstractions and Search Heuristics [66.28391181268645]
  We introduce LAPS (Language for Abstraction and Program Search), a technique for using natural language annotations to guide joint learning of libraries and neurally-guided search models for synthesis. When integrated into a state-of-the-art library learning system (DreamCoder), LAPS produces higher-quality libraries and improves search efficiency and generalization.
  arXiv  Detail & Related papers  (2021-06-18T15:08:47Z)
• Automated Aggregator -- Rewriting with the Counting Aggregate [0.0]
  We present an automated rewriting system that produces a family of equivalent programs with complementary performance. We propose the system's use in automated answer set programming solver selection tools.
  arXiv  Detail & Related papers  (2020-09-22T00:48:33Z)
• BUSTLE: Bottom-Up Program Synthesis Through Learning-Guided Exploration [72.88493072196094]
  We present a new synthesis approach that leverages learning to guide a bottom-up search over programs. In particular, we train a model to prioritize compositions of intermediate values during search conditioned on a set of input-output examples. We show that the combination of learning and bottom-up search is remarkably effective, even with simple supervised learning approaches.
  arXiv  Detail & Related papers  (2020-07-28T17:46:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.