Guaranteed Generation from Large Language Models

• URL: http://arxiv.org/abs/2410.06716v1
• Date: Wed, 9 Oct 2024 09:39:55 GMT
• Title: Guaranteed Generation from Large Language Models
• Authors: Minbeom Kim, Thibaut Thonet, Jos Rozen, Hwaran Lee, Kyomin Jung, Marc Dymetman,
• Abstract summary: Large language models (LLMs) are increasingly used across various applications. We propose GUARD, a simple yet effective approach that combines an autoregressive proposal distribution with rejection sampling. These experiments show that GUARD achieves perfect constraint satisfaction while almost preserving the ideal distribution with highly improved inference efficiency.
• Score: 28.157857382660563
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: As large language models (LLMs) are increasingly used across various applications, there is a growing need to control text generation to satisfy specific constraints or requirements. This raises a crucial question: Is it possible to guarantee strict constraint satisfaction in generated outputs while preserving the distribution of the original model as much as possible? We first define the ideal distribution - the one closest to the original model, which also always satisfies the expressed constraint - as the ultimate goal of guaranteed generation. We then state a fundamental limitation, namely that it is impossible to reach that goal through autoregressive training alone. This motivates the necessity of combining training-time and inference-time methods to enforce such guarantees. Based on this insight, we propose GUARD, a simple yet effective approach that combines an autoregressive proposal distribution with rejection sampling. Through GUARD's theoretical properties, we show how controlling the KL divergence between a specific proposal and the target ideal distribution simultaneously optimizes inference speed and distributional closeness. To validate these theoretical concepts, we conduct extensive experiments on two text generation settings with hard-to-satisfy constraints: a lexical constraint scenario and a sentiment reversal scenario. These experiments show that GUARD achieves perfect constraint satisfaction while almost preserving the ideal distribution with highly improved inference efficiency. GUARD provides a principled approach to enforcing strict guarantees for LLMs without compromising their generative capabilities.

Related papers

• Constrained Auto-Regressive Decoding Constrains Generative Retrieval [71.71161220261655]
  Generative retrieval seeks to replace traditional search index data structures with a single large-scale neural network. In this paper, we examine the inherent limitations of constrained auto-regressive generation from two essential perspectives: constraints and beam search.
  arXiv  Detail & Related papers  (2025-04-14T06:54:49Z)
• Constrained Language Generation with Discrete Diffusion Models [61.81569616239755]
  We present Constrained Discrete Diffusion (CDD), a novel method for enforcing constraints on natural language by integrating discrete diffusion models with differentiable optimization. We show how this technique can be applied to satisfy a variety of natural language constraints, including (i) toxicity mitigation by preventing harmful content from emerging, (ii) character and sequence level lexical constraints, and (iii) novel molecule sequence generation with specific property adherence.
  arXiv  Detail & Related papers  (2025-03-12T19:48:12Z)
• DiOpt: Self-supervised Diffusion for Constrained Optimization [46.75288477458697]
  DiOpt is a novel diffusion paradigm that systematically learns near-optimal feasible solution distributions through iterative self-training. To our knowledge, DiOpt represents the first successful integration of self-supervised diffusion with hard constraint satisfaction.
  arXiv  Detail & Related papers  (2025-02-14T17:43:08Z)
• Deep Generative Models with Hard Linear Equality Constraints [24.93865980946986]
  We propose a probabilistically sound approach for enforcing the hard constraints into DGMs to generate constraint-compliant data. We carry out experiments with various DGM model architectures over five image datasets and three scientific applications. Ours not only guarantees the satisfaction of constraints in generation but also archives superior generative performance than the other methods across every benchmark.
  arXiv  Detail & Related papers  (2025-02-08T02:53:32Z)
• Controllable Generation via Locally Constrained Resampling [77.48624621592523]
  We propose a tractable probabilistic approach that performs Bayesian conditioning to draw samples subject to a constraint. Our approach considers the entire sequence, leading to a more globally optimal constrained generation than current greedy methods. We show that our approach is able to steer the model's outputs away from toxic generations, outperforming similar approaches to detoxification.
  arXiv  Detail & Related papers  (2024-10-17T00:49:53Z)
• DeAL: Decoding-time Alignment for Large Language Models [59.63643988872571]
  Large Language Models (LLMs) are nowadays expected to generate content aligned with human preferences. We propose DeAL, a framework that allows the user to customize reward functions and enables Detime Alignment of LLMs. Our experiments show that we can DeAL with fine-grained trade-offs, improve adherence to alignment objectives, and address residual gaps in LLMs.
  arXiv  Detail & Related papers  (2024-02-05T06:12:29Z)
• Source-Free Unsupervised Domain Adaptation with Hypothesis Consolidation of Prediction Rationale [53.152460508207184]
  Source-Free Unsupervised Domain Adaptation (SFUDA) is a challenging task where a model needs to be adapted to a new domain without access to target domain labels or source domain data. This paper proposes a novel approach that considers multiple prediction hypotheses for each sample and investigates the rationale behind each hypothesis. To achieve the optimal performance, we propose a three-step adaptation process: model pre-adaptation, hypothesis consolidation, and semi-supervised learning.
  arXiv  Detail & Related papers  (2024-02-02T05:53:22Z)
• f-FERM: A Scalable Framework for Robust Fair Empirical Risk Minimization [9.591164070876689]
  This paper presents a unified optimization framework for fair empirical risk based on f-divergence measures (f-FERM) In addition, our experiments demonstrate the superiority of fairness-accuracy tradeoffs offered by f-FERM for almost all batch sizes. Our extension is based on a distributionally robust optimization reformulation of f-FERM objective under $L_p$ norms as uncertainty sets.
  arXiv  Detail & Related papers  (2023-12-06T03:14:16Z)
• STEEL: Singularity-aware Reinforcement Learning [14.424199399139804]
  Batch reinforcement learning (RL) aims at leveraging pre-collected data to find an optimal policy. We propose a new batch RL algorithm that allows for singularity for both state and action spaces. By leveraging the idea of pessimism and under some technical conditions, we derive a first finite-sample regret guarantee for our proposed algorithm.
  arXiv  Detail & Related papers  (2023-01-30T18:29:35Z)
• Distributed Distributionally Robust Optimization with Non-Convex Objectives [24.64654924173679]
  Asynchronous distributed algorithm named Asynchronous Single-looP alternatIve gRadient projEction is proposed. New uncertainty set, i.e., constrained D-norm uncertainty set, is developed to leverage the prior distribution and flexibly control the degree of robustness. empirical studies on real-world datasets demonstrate that the proposed method can not only achieve fast convergence, but also remain robust against data as well as malicious attacks.
  arXiv  Detail & Related papers  (2022-10-14T07:39:13Z)
• Toward Certified Robustness Against Real-World Distribution Shifts [65.66374339500025]
  We train a generative model to learn perturbations from data and define specifications with respect to the output of the learned model. A unique challenge arising from this setting is that existing verifiers cannot tightly approximate sigmoid activations. We propose a general meta-algorithm for handling sigmoid activations which leverages classical notions of counter-example-guided abstraction refinement.
  arXiv  Detail & Related papers  (2022-06-08T04:09:13Z)
• Modeling the Second Player in Distributionally Robust Optimization [90.25995710696425]
  We argue for the use of neural generative models to characterize the worst-case distribution. This approach poses a number of implementation and optimization challenges. We find that the proposed approach yields models that are more robust than comparable baselines.
  arXiv  Detail & Related papers  (2021-03-18T14:26:26Z)
• A Distributional Approach to Controlled Text Generation [3.279201607581627]
  We propose a Distributional Approach to address Controlled Text Generation from pre-trained Language Models (LMs) This view permits to define, in a single formal framework, "pointwise" and "distributional" constraints over the target LM. We then perform experiments over distributional constraints, a unique feature of our approach, demonstrating its potential as a remedy to the problem of Bias in Language Models.
  arXiv  Detail & Related papers  (2020-12-21T19:02:41Z)
• An Information Bottleneck Approach for Controlling Conciseness in Rationale Extraction [84.49035467829819]
  We show that it is possible to better manage this trade-off by optimizing a bound on the Information Bottleneck (IB) objective. Our fully unsupervised approach jointly learns an explainer that predicts sparse binary masks over sentences, and an end-task predictor that considers only the extracted rationale.
  arXiv  Detail & Related papers  (2020-05-01T23:26:41Z)

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.