{
  "id": "2310.04327",
  "version": "v1",
  "published": "2023-10-06T15:44:47.000Z",
  "updated": "2023-10-06T15:44:47.000Z",
  "title": "Program Synthesis with Best-First Bottom-Up Search",
  "authors": [
    "Saqib Ameen",
    "Levi H. S. Lelis"
  ],
  "comment": "Published at the Journal of Artificial Intelligence Research (JAIR)",
  "doi": "10.1613/jair.1.14394",
  "categories": [
    "cs.LG"
  ],
  "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-10-06T15:44:47.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "cost function",
      "bee search",
      "program synthesis",
      "search performs best-first search",
      "best-first bottom-up search algorithm"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}