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

arXiv:2605.10065 · cs.CL, cs.AI · Submitted 2026-05-11 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Today's paper: "NCO: A Versatile Plug-in for Handling Negative Constraints in Decoding".

Jane: The gist: NCO, a decoding-time plug-in for enforcing multiple negative substring constraints without modifying the model or constructing a global avoidance automaton, reduces computational overhead while preserving generation efficiency.

Tom: First, who's behind it and why it matters.

Title and authors: Tom: We’ve talked about what it does generally, but let's nail down who wrote this and what they are calling this new approach. The paper is titled "NCO: A Versatile Plug-in for Handling Negative Constraints in Decoding," and it comes from Hyundong Jin Yo-Sub Han at Yonsei University in Seoul.

Jane: It’s interesting that they frame it as a plug-in because it suggests you can integrate this into existing generation pipelines without needing to retrain the entire model or do any kind of heavy fine-tuning.

Lu: The paper introduces NCO as a logit-level intervention, meaning it works by adjusting the scores for which tokens get picked at every step of generation, rather than changing the model’s weights themselves.

Meng: So it's not retraining; it's just a layer on top that filters bad options while we're running inference. That makes sense from an engineering standpoint because we don't want to take down the whole infrastructure for this.

Lalam: It sounds like they are trying to solve the issue where standard regex engines don’t handle things like complements and intersections easily, which is a common hurdle when you try to build one big avoidance automaton.

The paper's summary: Tom: Now let's look at the core summary of this work. Essentially, NCO addresses the challenge that preventing multiple forbidden hard constraints or regex constraints from appearing anywhere in the output is computationally difficult because building a single global automaton becomes impractically large.

Jane: The key innovation here is how NCO handles this by maintaining these constraints separately and composing their per-token masks at each step during decoding. This avoids the state explosion we usually see when you try to track everything at once.

Lu: For finite hard constraints, they use an Aho-Corasick trie to track partial matches compactly, and for regex constraints, they simulate their respective DFAs in parallel. That’s a clever way to manage complexity without building the massive product automaton.

Meng: So, instead of one huge structure that explodes in size as you add more rules, they keep the constraint data separate and run things in parallel during generation. That sounds like a practical way to handle high constraint complexity.

Lalam: And they show that this method works for both types of constraints; theorem four point one confirms it for finite hard constraints, saying no string in P appears if we use the Aho-Corasick mask, and theorem four point two handles the regex constraints similarly with their DFA simulation <ref:2605.10065#pg1>.

The paper's improvements: Tom: Beyond just what they propose, the authors detail several specific improvements over existing methods. They show that NCO is formulated as a logit-level intervention, which means it integrates into the generation pipeline without any retraining or fine-tuning required for the base model.

Jane: They also present two distinct decoding mechanisms: one based on an Aho-Corasick trie strategy for those finite hard constraints, and another based on a parallel DFA simulation approach for handling regex constraints. This gives them flexibility depending on the type of constraint they are dealing with.

Lu: The implementation involves BPE-aware preprocessing, which helps with the finite hard constraints by using the compositional property of AC-trie transitions, making that precomputation much more efficient.

Meng: From an engineering standpoint, this means they build these constraint automata once during precomputation and then reuse them throughout decoding rather than recalculating them every single time a token is generated. That reuse should significantly speed things up in practice.

Lalam: And they also show how this framework supports both strict enforcement and probabilistic suppression using the same online constraint states, which is a big plus because it lets us choose between hard blocking or softer discouragement.

Conclusion: Tom: So, to wrap up on "NCO: A Versatile Plug-in for Handling Negative Constraints in Decoding," the paper shows how you can enforce multiple negative substring constraints by performing online pattern matching over finite hard constraints and regex constraints using compact online matching states.

Jane: The main implication is that we can control outputs during generation while keeping the computational cost low, preserving generation efficiency close to the unconstrained base model. This is particularly useful when dealing with safety concerns like PII or profanity patterns.

Lu: For those of us looking at future possibilities, the ability to handle these constraints in a plug-in format suggests that this logic could be generalized to other types of complex pattern matching problems across different generative models.

Meng: From a practical view, the runtime analysis is what really matters; they show that for finite hard constraints, NCO updates the constraint state in O(one) time per generated token and O(N) over the full sequence <ref:2605.10065#pg1>. For regex constraints, it’s O(M) per token where M is the total number of states across all automata.

Lalam: And because they showed it works for both hard constraints and regex, it means we can use this same online state mechanism to provide graded suppression instead of just completely blocking things.

Tom: So that's what NCO is: a way to enforce complex negative constraints without the massive state explosion you get from trying to build one big avoidance automaton. We’ll be looking at how this approach scales in our next session, so stick around for that.

Hyundong Jin Yo-Sub Han

Yonsei University

cs.CL, cs.AI

Submitted: 2026-05-11

Updated: 2026-10-04

Code: https://github.com/hyundong98/NCO-Decoding

License: http://creativecommons.org/licenses/by-nc-nd/4.0/

Importance score: 90/100

The gist: The gist: NCO, a decoding-time plug-in for enforcing multiple negative substring constraints without modifying the model or constructing a global avoidance automaton, reduces computational overhead

Key concepts

NCO: A decoding plug-in that enforces negative substring constraints during text generation. It works by intervening at the logit level to mask invalid next-token candidates based on precomputed constraint masks, allowing it to maintain generation efficiency without retraining the main model.
Finite Hard Constraints: Constraints that specify exact forbidden substrings. NCO uses an Aho-Corasick trie structure for these. This structure is built once during preprocessing and used online to compactly track partial matches, enabling O(1) state updates per token during decoding.
Regex Constraints: Constraints defined by regular expressions. For these, NCO maintains separate constraint DFAs and simulates their active states in parallel. This approach allows the system to check for multiple complex pattern matches simultaneously during the decoding process.

Terminology

Ablation — 19× in this paper · explained in 1 episode
Perplexity — 17× in this paper · explained in 3 episodes
Tokenization — 8× in this paper · explained in 2 episodes
Aggregation — 6× in this paper · explained in 1 episode
Decode — 6× in this paper · explained in 2 episodes
Fine-Tuning — 4× in this paper · explained in 5 episodes
Ablation study — 3× in this paper · explained in 1 episode
Computational overhead — 3× in this paper · explained in 2 episodes
Large Language Models (LLMs) — 3× in this paper · explained in 6 episodes
Personally Identifiable Information — 3× in this paper
Transformer — 3× in this paper · explained in 2 episodes
Benchmark — 2× in this paper · explained in 2 episodes
Core — 2× in this paper · explained in 2 episodes
Ablation Studies — 1× in this paper · explained in 1 episode
Consistency — 1× in this paper · explained in 3 episodes
Generative Model — 1× in this paper · explained in 2 episodes
Generative Models — 1× in this paper · explained in 2 episodes
Redundancy — 1× in this paper · explained in 2 episodes

Summary

The gist: NCO, a decoding-time plug-in for enforcing multiple negative substring constraints without modifying the model or constructing a global avoidance automaton, reduces computational overhead while preserving generation efficiency.

Problem Definition

Constrained decoding enforces formal constraints by filtering invalid tokens during generation, and the main computational problem is to compute ΓC(Yt) efficiently at every decoding step without constructing an impractically large global automaton. The paper considers two forms of negative substring constraints: Problem 2: Forbidden Regex Constraints.

Proposed Methods

NCO is formulated as a logit-level intervention that integrates with existing generation pipelines without requiring retraining, fine-tuning, or modifying the model. It performs online multi-pattern matching during decoding by maintaining the constraints separately and composing their per-token masks at each step. For finite hard constraints, NCO uses an Aho-Corasick trie to track partial matches compactly. For regex constraints, NCO keeps the constraint DFAs separate and simulates their active states in parallel.

Implementation Details

The implementation involves two decoding mechanisms within this framework: an Aho-Corasick trie based strategy for finite hard constraints and a parallel DFA simulation based strategy for regex constraints, accelerated by a BPE-aware preprocessing procedure. The precomputation step involves building the corresponding constraint automata once during precomputation and reusing them throughout decoding. For finite hard constraints, the BPE-aware precomputation uses the compositional property of AC-trie transitions. Theorem 4.1 (Correctness for finite hard constraints) states that if NCO generates an output Y using the finite hard constraint mask induced by the Aho-Corasick trie of P, then no string in P appears in Y as a substring. Theorem 4.2 (Correctness for regex constraints) states that if NCO generates an output Y using the regex constraint mask induced by D, then no substring of Y is accepted by any automaton in D. The runtime analysis shows that for finite hard constraints, NCO updates the constraint state in O(1) time per generated token and O(N) over the full generated sequence. For regex constraints, NCO updates the regex constraint state in O(M) time per generated token, where M denotes the total number of states across all automata.

Experimental Results

Across both tasks, NCO achieves zero violation rate under the evaluated constraints. In terms of efficiency, NCO preserves relative throughput close to the unconstrained base model across batch sizes. The ablation study indicates that the acceleration components reduce different costs in the constraint enforcement pipeline, which explains why their benefits are complementary. NCO supports both strict enforcement and probabilistic suppression through the same online constraint states.

Limitations and Broader Impacts

NCO is designed for explicit negative substring constraints, but it does not address semantic variants that are not captured by the constraint specification. It intervenes by masking invalid next-token candidates during decoding, and if a forbidden or undesirable span has already been generated before the constraint is applied, NCO does not revise or remove that existing prefix. NCO may have positive societal impacts by helping reduce undesirable generations such as structured PII patterns, profanity, and other explicitly specified harmful strings or regular-expression patterns at decoding time.

This behavior is consistent with its design, where constraint-specific computation is largely moved to preprocessing and decoding uses compact online states and precomputed token-level masks. Overall, NCO maintains low decoding overhead across the tested settings while enforcing negative constraints throughout generation.

The paper is available at https://github.com/hyundong98/NCO-Decoding.git. The references are listed in Appendix A for formal background. The references are also provided in Appendix B and C. The references are further detailed in Appendix D. The references conclude with a list of assets used in the experiments. The final page contains additional experimental results and limitations. The final page also includes a list of references. The paper is available at arXiv:2605.10065v1 [cs.CL]

Improvements for AI systems

Bold header: Constraint enforcement via NCO decoding plug-in

NCO prevents multiple forbidden hard constraints or regex constraints from appearing anywhere in the output by performing online pattern matching over finite hard constraints and regex constraints and maintaining compact online matching states. This allows the system to enforce complex, multiple negative substring constraints without the state explosion associated with constructing a single global avoidance automaton.

Bold header: Enhanced efficiency under batched generation

NCO preserves relative throughput close to the unconstrained base model across batch sizes because it utilizes precomputed token-level transition and masking information and implements GPU parallel mask composition. This makes it suitable for batched deployment, where traditional methods like rejection sampling or GUARD show degradation as batch size increases.

Bold header: Support for probabilistic suppression

NCO supports a soft constraint mode where tokens that would complete a forbidden string or regex match receive an additive logit penalty of −λ instead of being fully masked. This allows the system to provide graded suppression instead of only hard blocking, enabling applications that prefer discourage undesirable patterns rather than completely rule them out.

Bold header: Scalability under high constraint complexity

NCO demonstrates superior scalability for regex constraints, maintaining stable throughput as the number and size of DFA constraints increase, unlike rejection sampling which suffers a sharp throughput drop as invalid candidates become more likely. This is achieved by avoiding explicit construction of the product automaton and using parallel DFA simulation with an additive state update that scales linearly with the total number of states.

Bold header: Robustness to constraint complexity scaling

The analysis shows that NCO's runtime cost is not highly sensitive to the tested increases in constraint scale for both finite hard constraints (increasing lexicon size/length) and regex constraints (increasing DFA count/size). This confirms that the cost of aggregating masks across many regex constraints is not negligible in this regime.

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.