Constrained Decoding for Fill-in-the-Middle Code Language Models via Efficient Left and Right Quotienting of Context-Sensitive Grammars

• URL: http://arxiv.org/abs/2402.17988v2
• Date: Wed, 4 Sep 2024 18:50:25 GMT
• Title: Constrained Decoding for Fill-in-the-Middle Code Language Models via Efficient Left and Right Quotienting of Context-Sensitive Grammars
• Authors: Daniel Melcer, Nathan Fulton, Sanjay Krishna Gouda, Haifeng Qian,
• Abstract summary: This paper contributes an incremental synthesis that allows early rejection of syntactically incorrect code. We extend the Earley parsing algorithm to allow for left and right quotients of context-free grammars.
• Score: 11.279507894576213
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Large Language Models are powerful tools for program synthesis and advanced auto-completion, but come with no guarantee that their output code is syntactically correct. This paper contributes an incremental parser that allows early rejection of syntactically incorrect code, as well as efficient detection of complete programs for fill-in-the-middle (FIM) tasks. We extend the Earley parsing algorithm to allow for left and right quotients of context-free grammars, and develop methods to handle quotienting of several context-sensitive features present in the grammars of many common programming languages. The result of these contributions is an efficient, general, and well-grounded method for left and right quotient parsing. To validate our theoretical contributions -- and the effectiveness of certain design decisions -- we evaluate our method on the particularly difficult case of FIM completion for Python 3, with syntax-correctness constraints. Our results demonstrate that constrained generation can significantly reduce the incidence of syntax errors in recommended code.

Related papers

• Improving LLM Reasoning through Scaling Inference Computation with Collaborative Verification [52.095460362197336]
  Large language models (LLMs) struggle with consistent and accurate reasoning. LLMs are trained primarily on correct solutions, reducing their ability to detect and learn from errors. We propose a novel collaborative method integrating Chain-of-Thought (CoT) and Program-of-Thought (PoT) solutions for verification.
  arXiv  Detail & Related papers  (2024-10-05T05:21:48Z)
• A Comprehensive Solution to Connect Speech Encoder and Large Language Model for ASR [14.380210167130032]
  Recent works have shown promising results in connecting speech encoders to large language models (LLMs) for speech recognition. However, several limitations persist, including limited fine-tuning options, a lack of mechanisms to enforce speech-text alignment, and high insertion errors. This paper presents a comprehensive solution to address these issues.
  arXiv  Detail & Related papers  (2024-06-25T04:35:50Z)
• SparseCL: Sparse Contrastive Learning for Contradiction Retrieval [87.02936971689817]
  Contradiction retrieval refers to identifying and extracting documents that explicitly disagree with or refute the content of a query. Existing methods such as similarity search and crossencoder models exhibit significant limitations. We introduce SparseCL that leverages specially trained sentence embeddings designed to preserve subtle, contradictory nuances between sentences.
  arXiv  Detail & Related papers  (2024-06-15T21:57:03Z)
• Grammar-Aligned Decoding [30.972850034752884]
  Large Language Models (LLMs) struggle with reliably generating highly structured outputs, such as program code, mathematical formulas, or well-formed markup. Constrained decoding approaches mitigate this problem by greedily restricting what tokens an LLM can output at each step to guarantee that the output matches a given constraint. In this paper, we demonstrate that GCD techniques can distort the LLM's distribution, leading to outputs that are grammatical but appear with likelihoods that are not proportional to the ones given by the LLM.
  arXiv  Detail & Related papers  (2024-05-31T17:39:15Z)
• Understanding and Mitigating Classification Errors Through Interpretable Token Patterns [58.91023283103762]
  Characterizing errors in easily interpretable terms gives insight into whether a classifier is prone to making systematic errors. We propose to discover those patterns of tokens that distinguish correct and erroneous predictions. We show that our method, Premise, performs well in practice.
  arXiv  Detail & Related papers  (2023-11-18T00:24:26Z)
• Tokenization with Factorized Subword Encoding [2.538209532048867]
  We propose a novel tokenization method that factorizes subwords onto discrete triplets using a VQ-VAE model. Results indicate that this method is more appropriate and robust for morphological tasks than the commonly used byte-pair encoding (BPE) tokenization algorithm.
  arXiv  Detail & Related papers  (2023-06-13T13:27:34Z)
• Weak Disambiguation for Partial Structured Output Learning [8.239028141030621]
  We propose a novel weak disambiguation for partial structured output learning (WD-PSL) Each candidate label is assigned with a confidence value indicating how likely it is the true label. The experimental results on several sequence labeling tasks of Natural Language Processing show the effectiveness of the proposed model.
  arXiv  Detail & Related papers  (2022-09-20T02:12:31Z)
• Lexically Aware Semi-Supervised Learning for OCR Post-Correction [90.54336622024299]
  Much of the existing linguistic data in many languages of the world is locked away in non-digitized books and documents. Previous work has demonstrated the utility of neural post-correction methods on recognition of less-well-resourced languages. We present a semi-supervised learning method that makes it possible to utilize raw images to improve performance.
  arXiv  Detail & Related papers  (2021-11-04T04:39:02Z)
• CodeBLEU: a Method for Automatic Evaluation of Code Synthesis [57.87741831987889]
  In the area of code synthesis, the commonly used evaluation metric is BLEU or perfect accuracy. We introduce a new automatic evaluation metric, dubbed CodeBLEU. It absorbs the strength of BLEU in the n-gram match and further injects code syntax via abstract syntax trees (AST) and code semantics via data-flow.
  arXiv  Detail & Related papers  (2020-09-22T03:10:49Z)
• Contextualized Perturbation for Textual Adversarial Attack [56.370304308573274]
  Adversarial examples expose the vulnerabilities of natural language processing (NLP) models. This paper presents CLARE, a ContextuaLized AdversaRial Example generation model that produces fluent and grammatical outputs.
  arXiv  Detail & Related papers  (2020-09-16T06:53:15Z)

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.