Program Synthesis with Best-First Bottom-Up Search

• URL: http://arxiv.org/abs/2310.04327v1
• Date: Fri, 6 Oct 2023 15:44:47 GMT
• Title: Program Synthesis with Best-First Bottom-Up Search
• Authors: Saqib Ameen and Levi H. S. Lelis
• Abstract summary: We show that current state-of-the-art cost-guided BUS algorithms suffer from a common problem: they can lose useful information. We introduce a novel best-first bottom-up search algorithm, which we call Bee Search, that does not suffer information loss and is able to perform cost-guided bottom-up synthesis in a best-first manner.
• Score: 14.146892127555217
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Cost-guided bottom-up search (BUS) algorithms use a cost function to guide the search to solve program synthesis tasks. In this paper, we show that current state-of-the-art cost-guided BUS algorithms suffer from a common problem: they can lose useful information given by the model and fail to perform the search in a best-first order according to a cost function. We introduce a novel best-first bottom-up search algorithm, which we call Bee Search, that does not suffer information loss and is able to perform cost-guided bottom-up synthesis in a best-first manner. Importantly, Bee Search performs best-first search with respect to the generation of programs, i.e., it does not even create in memory programs that are more expensive than the solution program. It attains best-first ordering with respect to generation by performing a search in an abstract space of program costs. We also introduce a new cost function that better uses the information provided by an existing cost model. Empirical results on string manipulation and bit-vector tasks show that Bee Search can outperform existing cost-guided BUS approaches when employing more complex domain-specific languages (DSLs); Bee Search and previous approaches perform equally well with simpler DSLs. Furthermore, our new cost function with Bee Search outperforms previous cost functions on string manipulation tasks.

Related papers

• EcoSearch: A Constant-Delay Best-First Search Algorithm for Program Synthesis [4.523850593225294]
  We present a new best-first search algorithm called EcoSearch, which is the first constant-delay algorithm for pre-generation cost function. We observe that EcoSearch outperforms its predecessors on two classic domains.
  arXiv  Detail & Related papers  (2024-12-23T06:48:47Z)
• A Three-Stage Algorithm for the Closest String Problem on Artificial and Real Gene Sequences [39.58317527488534]
  Closest String Problem is an NP-hard problem that aims to find a string that has the minimum distance from all sequences that belong to the given set of strings. In this paper, we introduce a three-stage algorithm that comprises the following process: first, we apply a novel alphabet pruning method to reduce the search space for effectively finding promising search regions. Second, a variant of beam search to find a solution is employed. This method utilizes a newly developed guiding function based on an expected distance score of partial solutions.
  arXiv  Detail & Related papers  (2024-07-17T21:26:27Z)
• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  This study introduces a novel guided tree search algorithm with dynamic node selection and node-level exploration budget. Experiments conducted on the GSM8K and TabMWP datasets demonstrate that our approach enjoys significantly lower computational costs compared to baseline methods.
  arXiv  Detail & Related papers  (2024-06-29T05:14:04Z)
• Bayesian Program Learning by Decompiling Amortized Knowledge [50.960612835957875]
  We present a novel approach for library learning that directly leverages the neural search policy, effectively "decompiling" its amortized knowledge to extract relevant program components. This provides stronger amortized inference: the amortized knowledge learnt to reduce search breadth is now also used to reduce search depth.
  arXiv  Detail & Related papers  (2023-06-13T15:35:01Z)
• Best-$k$ Search Algorithm for Neural Text Generation [118.02691398555781]
  We propose a deterministic search algorithm balancing both quality and diversity. The proposed algorithm is parameter-free, lightweight, efficient, and easy to use.
  arXiv  Detail & Related papers  (2022-11-22T00:26:13Z)
• CrossBeam: Learning to Search in Bottom-Up Program Synthesis [51.37514793318815]
  We propose training a neural model to learn a hands-on search policy for bottom-up synthesis. Our approach, called CrossBeam, uses the neural model to choose how to combine previously-explored programs into new programs. We observe that CrossBeam learns to search efficiently, exploring much smaller portions of the program space compared to the state-of-the-art.
  arXiv  Detail & Related papers  (2022-03-20T04:41:05Z)
• Contrastive Self-supervised Neural Architecture Search [6.162410142452926]
  This paper proposes a novel cell-based neural architecture search algorithm (NAS) Our algorithm capitalizes on the effectiveness of self-supervised learning for image representations. An extensive number of experiments empirically show that our search algorithm can achieve state-of-the-art results.
  arXiv  Detail & Related papers  (2021-02-21T08:38:28Z)
• 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)
• Best-First Beam Search [78.71330480725668]
  We show that the standard implementation of beam search can be made up to 10x faster in practice. We propose a memory-reduced variant of Best-First Beam Search, which has a similar beneficial search bias in terms of downstream performance.
  arXiv  Detail & Related papers  (2020-07-08T05:56:01Z)

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.