NCO: A Versatile Plug-in for Handling Negative Constraints in Decoding

• URL: http://arxiv.org/abs/2605.10065v1
• Date: Mon, 11 May 2026 06:43:42 GMT
• Title: NCO: A Versatile Plug-in for Handling Negative Constraints in Decoding
• Abstract summary: Large Language Models (LLMs) to prevent the generation of undesirable content, such as profanity and PII, has become increasingly critical.<n>We propose NCO, a decoding strategy that performs online pattern matching over finite hard constraints and constraints.<n>We empirically demonstrate its effectiveness across practical tasks, including PII and suppression.
• Score: 9.328325284438595
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Controlling Large Language Models (LLMs) to prevent the generation of undesirable content, such as profanity and personally identifiable information (PII), has become increasingly critical. While earlier approaches relied on post-processing or resampling, recent research has shifted towards constrained decoding methods that control outputs during generation to mitigate high computational costs and quality degradation. However, preventing multiple forbidden hard constraints or regex constraints from appearing anywhere in the output is computationally challenging. A straightforward solution is to convert these constraints into a single automaton that tracks all forbidden patterns during decoding, but this often becomes impractically large. Standard regex engines also do not readily support the operations needed to build such a constraint, such as complement and intersection. In order to address these limitations, we propose NCO, a decoding strategy that performs online pattern matching over finite hard constraints and regex constraints, reducing computational overhead without inducing state explosion. NCO is fully compatible with standard inference strategies, including various sampling methods and beam search, while also supporting soft masking for probabilistic suppression. We empirically demonstrate its effectiveness across practical tasks, including PII and profanity suppression. Our implementation is available at https://github.com/hyundong98/NCO-Decoding.git .

Related papers

• Constraint-First Reasoning: A Training-Free Protocol for Exploiting Answer-Space Constraints in Mathematical Problem Solving [11.900982999786287]
  Routed-CFR activates the two-stage protocol only when a text-only router detects restrictive cues.<n>Across AIME, CMIMC, BRUMO, and AIMO_AMC, the method improves direct CoT on multiple backbones.
  arXiv  Detail & Related papers  (2026-08-05T16:18:41Z)
• Constrained Decoding for Diffusion Language Models via Efficient Inference over Finite Automata [57.27430779838529]
  We present an exact and tractable algorithm for sampling from the constrained mean-field posterior under any constraint expressible as a finite automaton.<n>The approach guarantees constraint satisfaction by construction, supports both greedy and sampling-based decoding, and is compatible with parallel and block-wise decoding.<n> Empirical evaluations on Dream-7B and LLaDA-8 show substantial accuracy gains across various tasks.
  arXiv  Detail & Related papers  (2026-07-08T05:48:57Z)
• Compact Constraint Encoding for LLM Code Generation: An Empirical Study of Token Economics and Constraint Compliance [0.0]
  We investigate whether compact, structured constraint headers can reduce prompt token consumption without degrading constraint compliance.<n>We find that compact headers reduce constraint-portion tokens by approximately 71% and full-prompt tokens by 25-30%, replicated across three independent rounds.
  arXiv  Detail & Related papers  (2026-04-08T15:18:33Z)
• Near-Optimal Sample Complexity for Online Constrained MDPs [10.479589616736193]
  Constrained Markov Decision Processes (CMDPs) are commonly used to enforce safety constraints while optimizing performance.<n>Existing methods often suffer from significant safety violations or require a high sample complexity to generate near-optimal policies.<n>We propose a model-based primal-dual algorithm that balances regret and bounded constraint violations.
  arXiv  Detail & Related papers  (2026-02-16T05:16:13Z)
• Programming over Thinking: Efficient and Robust Multi-Constraint Planning [54.77940831026738]
  SCOPE is a framework that disentangles query-specific reasoning from generic code execution.<n>SCOPE achieves state-of-the-art performance while lowering cost and latency.
  arXiv  Detail & Related papers  (2026-01-14T02:58:07Z)
• Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling [90.86991492288487]
  evaluating constraint on every token can be prohibitively expensive.<n> LCD can distort the global distribution over strings, sampling tokens based only on local information.<n>We show that our approach is superior to state-of-the-art baselines.
  arXiv  Detail & Related papers  (2025-04-07T18:30:18Z)
• Limitations of the decoding-to-LPN reduction via code smoothing [59.90381090395222]
  Researchers have attempted to demonstrate the algorithmic hardness of the Learning Parity with Noise problem.<n>We characterize the efficiency of the reduction in terms of the parameters of the decoding and primitive problems.
  arXiv  Detail & Related papers  (2024-08-07T12:54:43Z)
• Guiding LLMs The Right Way: Fast, Non-Invasive Constrained Generation [7.687678490751105]
  We present a novel decoding algorithm, DOMINO, that can enforce constraints in a fully subword-aligned fashion, while leveraging pre-computation and speculative decoding to achieve virtually no overhead and in some cases even almost 2$times$ speedup over unconstrained decoding -- thereby outperforming existing approaches by a wide margin.
  arXiv  Detail & Related papers  (2024-02-07T13:36:02Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  Constrained optimization problems abound in industry, from portfolio optimization to logistics. One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space. In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
  arXiv  Detail & Related papers  (2022-11-16T18:59:54Z)
• NeuroLogic Decoding: (Un)supervised Neural Text Generation with Predicate Logic Constraints [75.66980495245926]
  Conditional text generation often requires lexical constraints, i.e., which words should or shouldn't be included in the output text. We propose NeuroLogic Decoding, a simple yet effective algorithm that enables neural language models -- supervised or not -- to generate fluent text. Our results suggest the limit of large-scale neural networks for fine-grained controllable generation and the promise of inference-time algorithms.
  arXiv  Detail & Related papers  (2020-10-24T11:55:22Z)

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.