Reinforcement Learning and Data-Generation for Syntax-Guided Synthesis
- URL: http://arxiv.org/abs/2307.09564v2
- Date: Fri, 5 Jan 2024 13:07:10 GMT
- Title: Reinforcement Learning and Data-Generation for Syntax-Guided Synthesis
- Authors: Julian Parsert and Elizabeth Polgreen
- Abstract summary: We present a reinforcement-learning algorithm for SyGuS which uses Monte-Carlo Tree Search (MCTS) to search the space of candidate solutions.
Our algorithm learns policy and value functions which, combined with the upper confidence bound for trees, allow it to balance exploration and exploitation.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Program synthesis is the task of automatically generating code based on a
specification. In Syntax-Guided Synthesis (SyGuS) this specification is a
combination of a syntactic template and a logical formula, and the result is
guaranteed to satisfy both.
We present a reinforcement-learning guided algorithm for SyGuS which uses
Monte-Carlo Tree Search (MCTS) to search the space of candidate solutions. Our
algorithm learns policy and value functions which, combined with the upper
confidence bound for trees, allow it to balance exploration and exploitation. A
common challenge in applying machine learning approaches to syntax-guided
synthesis is the scarcity of training data. To address this, we present a
method for automatically generating training data for SyGuS based on
anti-unification of existing first-order satisfiability problems, which we use
to train our MCTS policy. We implement and evaluate this setup and demonstrate
that learned policy and value improve the synthesis performance over a baseline
by over 26 percentage points in the training and testing sets. Our tool
outperforms state-of-the-art tool cvc5 on the training set and performs
comparably in terms of the total number of problems solved on the testing set
(solving 23% of the benchmarks on which cvc5 fails). We make our data set
publicly available, to enable further application of machine learning methods
to the SyGuS problem.
Related papers
- UnitCoder: Scalable Iterative Code Synthesis with Unit Test Guidance [65.01483640267885]
Large Language Models (LLMs) have demonstrated remarkable capabilities in various tasks, yet code generation remains a major challenge.
We introduce UnitCoder, a systematic pipeline leveraging model-generated unit tests to guide and validate the code generation process.
Our work presents a scalable approach that leverages model-generated unit tests to guide the synthesis of high-quality code data from pre-training corpora.
arXiv Detail & Related papers (2025-02-17T05:37:02Z) - A Systematic Examination of Preference Learning through the Lens of Instruction-Following [83.71180850955679]
We use a novel synthetic data generation pipeline to generate 48,000 instruction unique-following prompts.
With our synthetic prompts, we use two preference dataset curation methods - rejection sampling (RS) and Monte Carlo Tree Search (MCTS)
Experiments reveal that shared prefixes in preference pairs, as generated by MCTS, provide marginal but consistent improvements.
High-contrast preference pairs generally outperform low-contrast pairs; however, combining both often yields the best performance.
arXiv Detail & Related papers (2024-12-18T15:38:39Z) - ToolACE: Winning the Points of LLM Function Calling [139.07157814653638]
ToolACE is an automatic agentic pipeline designed to generate accurate, complex, and diverse tool-learning data.
We demonstrate that models trained on our synthesized data, even with only 8B parameters, achieve state-of-the-art performance on the Berkeley Function-Calling Leaderboard.
arXiv Detail & Related papers (2024-09-02T03:19:56Z) - Topological Guided Actor-Critic Modular Learning of Continuous Systems
with Temporal Objectives [2.398608007786179]
This work investigates the formal policy synthesis of continuous-state dynamic systems given high-level specifications in linear temporal logic.
We use neural networks to approximate the value function and policy function for hybrid product state space.
arXiv Detail & Related papers (2023-04-20T01:36:05Z) - Towards Automated Imbalanced Learning with Deep Hierarchical
Reinforcement Learning [57.163525407022966]
Imbalanced learning is a fundamental challenge in data mining, where there is a disproportionate ratio of training samples in each class.
Over-sampling is an effective technique to tackle imbalanced learning through generating synthetic samples for the minority class.
We propose AutoSMOTE, an automated over-sampling algorithm that can jointly optimize different levels of decisions.
arXiv Detail & Related papers (2022-08-26T04:28:01Z) - Network Support for High-performance Distributed Machine Learning [17.919773898228716]
We propose a system model that captures both learning nodes (that perform computations) and information nodes (that provide data)
We then formulate the problem of selecting (i) which learning and information nodes should cooperate to complete the learning task, and (ii) the number of iterations to perform.
We devise an algorithm, named DoubleClimb, that can find a 1+1/|I|-competitive solution with cubic worst-case complexity.
arXiv Detail & Related papers (2021-02-05T19:38:57Z) - Fast Few-Shot Classification by Few-Iteration Meta-Learning [173.32497326674775]
We introduce a fast optimization-based meta-learning method for few-shot classification.
Our strategy enables important aspects of the base learner objective to be learned during meta-training.
We perform a comprehensive experimental analysis, demonstrating the speed and effectiveness of our approach.
arXiv Detail & Related papers (2020-10-01T15:59:31Z) - 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) - Grammar Filtering For Syntax-Guided Synthesis [6.298766745228328]
We propose a system for using machine learning in tandem with automated reasoning techniques to solve PBE problems.
By preprocessing SyGuS PBE problems with a neural network, we can use a data driven approach to reduce the size of the search space.
Our system is able to run atop existing SyGuS PBE synthesis tools, decreasing the runtime of the winner of the 2019 SyGuS Competition for the PBE track by 47.65%.
arXiv Detail & Related papers (2020-02-07T16:35:50Z)
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.