Amortizing Pragmatic Program Synthesis with Rankings

• URL: http://arxiv.org/abs/2407.02499v1
• Date: Sat, 1 Jun 2024 22:55:33 GMT
• Title: Amortizing Pragmatic Program Synthesis with Rankings
• Authors: Yewen Pu, Saujas Vaduguru, Priyan Vaithilingam, Elena Glassman, Daniel Fried,
• Abstract summary: The usage of Rational Speech Acts (RSA) framework has been successful in building emphpragmatic program synthesizers. We present a general method of amortizing the slow, exact RSA synthesizer.
• Score: 17.775664476910247
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The usage of Rational Speech Acts (RSA) framework has been successful in building \emph{pragmatic} program synthesizers that return programs which, in addition to being logically consistent with user-generated examples, account for the fact that a user chooses their examples informatively. We present a general method of amortizing the slow, exact RSA synthesizer. Our method first query the exact RSA synthesizer to compile a communication dataset. The dataset contains a number of example-dependent rankings of subsets of programs. It then distills a \textit{single} global ranking of all programs as an approximation to every ranking in the dataset. This global ranking is then used at inference time to rank multiple logically consistent candidate programs generated from a fast, non-pragmatic synthesizer. Experiments on two program synthesis domains using our ranking method resulted in orders of magnitudes of speed ups compared to the exact RSA synthesizer, while being more accurate than a non-pragmatic synthesizer when communicating with humans. Finally, we prove that in the special case of synthesis from a single example, this approximation is exact.

Related papers

• Training Language Models on Synthetic Edit Sequences Improves Code Synthesis [33.13471417703669]
  Language models (LMs) autorely synthesize programs in a single pass. While high-quality instruction data for code synthesis is scarce, edit data for synthesis is even scarcer. We develop a synthetic data generation algorithm called LintSeq to fill this gap.
  arXiv  Detail & Related papers  (2024-10-03T17:57:22Z)
• SynthesizRR: Generating Diverse Datasets with Retrieval Augmentation [55.2480439325792]
  We study the synthesis of six datasets, covering topic classification, sentiment analysis, tone detection, and humor. We find that SynthesizRR greatly improves lexical and semantic diversity, similarity to human-written text, and distillation performance.
  arXiv  Detail & Related papers  (2024-05-16T12:22:41Z)
• Guiding Enumerative Program Synthesis with Large Language Models [15.500250058226474]
  In this paper, we evaluate the abilities of Large Language Models to solve formal synthesis benchmarks. When one-shot synthesis fails, we propose a novel enumerative synthesis algorithm. We find that GPT-3.5 as a stand-alone tool for formal synthesis is easily outperformed by state-of-the-art formal synthesis algorithms.
  arXiv  Detail & Related papers  (2024-03-06T19:13:53Z)
• Generating Pragmatic Examples to Train Neural Program Synthesizers [20.819451354452085]
  A good synthesizer must choose the intended program from the many that are consistent with the given set of examples. We propose a novel way to amortize this search with neural networks.
  arXiv  Detail & Related papers  (2023-11-09T20:53:00Z)
• Amortizing Pragmatic Program Synthesis with Rankings [19.070549715732483]
  In program synthesis, an intelligent system takes in a set of user-generated examples and returns a program that is logically consistent with these examples. The usage of Rational Speech Acts (RSA) framework has been successful in building emphpragmatic program synthesizers. This work presents a novel method of amortizing the RSA algorithm by leveraging a emphglobal pragmatic ranking -- a single, total ordering of all the hypotheses.
  arXiv  Detail & Related papers  (2023-09-01T20:12:01Z)
• ExeDec: Execution Decomposition for Compositional Generalization in Neural Program Synthesis [54.18659323181771]
  We characterize several different forms of compositional generalization that are desirable in program synthesis. We propose ExeDec, a novel decomposition-based strategy that predicts execution subgoals to solve problems step-by-step informed by program execution at each step.
  arXiv  Detail & Related papers  (2023-07-26T01:07:52Z)
• 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)
• Efficient Pragmatic Program Synthesis with Informative Specifications [13.234975857626752]
  We show that it is possible to build a program synthesizer that is both pragmatic and efficient by approximating the joint distribution of programs with a product of independent factors. We find that the synthesizer assuming a factored approximation performs better than a synthesizer assuming an exact joint distribution when evaluated on natural human inputs.
  arXiv  Detail & Related papers  (2022-04-05T21:25:58Z)
• Latent Execution for Neural Program Synthesis Beyond Domain-Specific Languages [97.58968222942173]
  We take the first step to synthesize C programs from input-output examples. In particular, we propose La Synth, which learns the latent representation to approximate the execution of partially generated programs. We show that training on these synthesized programs further improves the prediction performance for both Karel and C program synthesis.
  arXiv  Detail & Related papers  (2021-06-29T02:21:32Z)
• Representing Partial Programs with Blended Abstract Semantics [62.20775388513027]
  We introduce a technique for representing partially written programs in a program synthesis engine. We learn an approximate execution model implemented as a modular neural network. We show that these hybrid neuro-symbolic representations enable execution-guided synthesizers to use more powerful language constructs.
  arXiv  Detail & Related papers  (2020-12-23T20:40:18Z)
• Synthesize, Execute and Debug: Learning to Repair for Neural Program Synthesis [81.54148730967394]
  We propose SED, a neural program generation framework that incorporates synthesis, execution, and debug stages. SED first produces initial programs using the neural program synthesizer component, then utilizes a neural program debugger to iteratively repair the generated programs. On Karel, a challenging input-output program synthesis benchmark, SED reduces the error rate of the neural program synthesizer itself by a considerable margin, and outperforms the standard beam search for decoding.
  arXiv  Detail & Related papers  (2020-07-16T04:15:47Z)

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.