SynCode: LLM Generation with Grammar Augmentation

• URL: http://arxiv.org/abs/2403.01632v4
• Date: Wed, 06 Nov 2024 18:04:35 GMT
• Title: SynCode: LLM Generation with Grammar Augmentation
• Authors: Shubham Ugare, Tarun Suresh, Hangoo Kang, Sasa Misailovic, Gagandeep Singh,
• Abstract summary: SynCode is a novel framework for efficient and generalal decoding with LLMs. It ensures soundness and completeness with respect to the CFG of a formal language, effectively retaining valid tokens while filtering out invalid ones. Our experiments demonstrate that SynCode eliminates all syntax errors and significantly outperforms state-of-the-art baselines.
• Score: 5.174301428591665
• License:
• Abstract: LLMs are widely used in complex AI applications. These applications underscore the need for LLM outputs to adhere to a specific format, for their integration with other components in the systems. Typically the format rules e.g., for data serialization formats such as JSON, YAML, or Code in Programming Language are expressed as context-free grammar (CFG). Due to the hallucinations and unreliability of LLMs, instructing LLMs to adhere to specified syntax becomes an increasingly important challenge. We present SynCode, a novel framework for efficient and general syntactical decoding with LLMs, to address this challenge. SynCode ensures soundness and completeness with respect to the CFG of a formal language, effectively retaining valid tokens while filtering out invalid ones. SynCode uses an offline-constructed, efficient lookup table, the DFA mask store, derived from the DFA of the language's grammar for efficient generation. SynCode seamlessly integrates with any language defined by CFG, as evidenced by experiments focusing on generating JSON, Python, and Go outputs. Our experiments evaluating the effectiveness of SynCode for JSON generation demonstrate that SynCode eliminates all syntax errors and significantly outperforms state-of-the-art baselines. Furthermore, our results underscore how SynCode significantly reduces 96.07% of syntax errors in generated Python and Go code, showcasing its substantial impact on enhancing syntactical precision in LLM generation. Our code is available at https://github.com/uiuc-focal-lab/syncode

Related papers

• Low-Cost and Comprehensive Non-textual Input Fuzzing with LLM-Synthesized Input Generators [25.199440800244442]
  We present a novel approach to enabling grammar-aware fuzzing over non-textual inputs. LLMs are good at synthesizing and mutating input generators and enabling jumping out of local optima. G2FUZZ outperforms SOTA tools such as AFL++, Fuzztruction, and FormatFuzzer in terms of code coverage and bug finding.
  arXiv  Detail & Related papers  (2025-01-31T16:45:16Z)
• 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)
• Case2Code: Scalable Synthetic Data for Code Generation [105.89741089673575]
  Large Language Models (LLMs) have shown outstanding breakthroughs in code generation. Recent work improves code LLMs by training on synthetic data generated by some powerful LLMs. We propose a textbfCase2Code task by exploiting the expressiveness and correctness of programs.
  arXiv  Detail & Related papers  (2024-07-17T11:35:00Z)
• Uncovering LLM-Generated Code: A Zero-Shot Synthetic Code Detector via Code Rewriting [78.48355455324688]
  We propose a novel zero-shot synthetic code detector based on the similarity between the original code and its LLM-rewritten variants. Our results demonstrate a significant improvement over existing SOTA synthetic content detectors.
  arXiv  Detail & Related papers  (2024-05-25T08:57:28Z)
• 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)
• CodecLM: Aligning Language Models with Tailored Synthetic Data [51.59223474427153]
  We introduce CodecLM, a framework for adaptively generating high-quality synthetic data for instruction-following abilities. We first encode seed instructions into metadata, which are concise keywords generated on-the-fly to capture the target instruction distribution. We also introduce Self-Rubrics and Contrastive Filtering during decoding to tailor data-efficient samples.
  arXiv  Detail & Related papers  (2024-04-08T21:15:36Z)
• 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)
• Assured LLM-Based Software Engineering [51.003878077888686]
  This paper is an outline of the content of the keynote by Mark Harman at the International Workshop on Interpretability, Robustness, and Benchmarking in Neural Software Engineering, Monday 15th April 2024, Lisbon, Portugal.
  arXiv  Detail & Related papers  (2024-02-06T20:38:46Z)
• LILO: Learning Interpretable Libraries by Compressing and Documenting Code [71.55208585024198]
  We introduce LILO, a neurosymbolic framework that iteratively synthesizes, compresses, and documents code. LILO combines LLM-guided program synthesis with recent algorithmic advances in automated from Stitch. We find that AutoDoc boosts performance by helping LILO's synthesizer to interpret and deploy learned abstractions.
  arXiv  Detail & Related papers  (2023-10-30T17:55:02Z)
• Is Your Code Generated by ChatGPT Really Correct? Rigorous Evaluation of Large Language Models for Code Generation [20.45045253933097]
  We propose EvalPlus -- a code synthesis evaluation framework to rigorously benchmark the functional correctness of LLM-synthesized code. EvalPlus augments a given evaluation dataset with large amounts of test-cases newly produced by an automatic test input generator. We show that HumanEval+ is able to catch significant amounts of previously undetected wrong code.
  arXiv  Detail & Related papers  (2023-05-02T05:46:48Z)

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.