acceptodds
Under review as a conference paper at ICLR 2027

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

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://anonymous.4open.science/r/NCO-B64D/.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Language models, Constrained decoding, Regular constraints

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_VBcXOpenReview ↗
Rating
2
Confidence
3(+1)
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper proposes NCO, an inference-time constrained decoding framework for preventing forbidden strings and regular-expression matches from appearing as substrings in LLM outputs. NCO uses Aho–Corasick (AC) matching for finite forbidden strings and per-DFA active-state-set simulation for forbidden regexes. It precomputes token-level transition and blocking tables using BPE merge structure and combines regex blocking masks through GPU matrix multiplication. Experiments on RealToxicityPrompts and Enron PII suppression report zero constraint violations and near-base-model generation throughput across nine models.

Critical strengths
  1. The AC-state and DFA active-state-set invariants are appropriate for substring avoidance, and the correctness arguments are sound under the stated assumptions.
  2. The BPE-aware composition of token transition and blocking tables is simple, elegant, and correct.
  3. The open-source implementation, with support for batching and multiple decoding strategies, is a useful contribution to practitioners.
  4. Evaluation across nine models and multiple batch sizes is extensive, and the near-zero decoding overhead is encouraging.
Critical weaknesses

1. Limited algorithmic novelty and insufficient separation of preprocessing and decoding efficiency.

For finite forbidden strings, Aho–Corasick already constructs a deterministic automaton recognizing substring occurrences in a finite pattern set, with O(L)O(L) states for total pattern length LL. Complementing its accepting condition yields an avoidance automaton without state explosion. Thus, the AC-based approach is essentially a standard global avoidance automaton for finite strings, despite the paper's emphasis on avoiding such constructions.

For regex constraints, automata-based token filtering and precomputed token transitions have substantial precedent in Outlines (Willard & Louf, 2023), Koo et al. (2024), and XGrammar (Dong et al., 2025). Maintaining sets of active states is also a standard way to simulate nondeterministic matching without explicit determinization.

The BPE-aware table composition appears to be the clearest algorithmic contribution. However, Table 3 indicates that this optimization primarily reduces preprocessing time, rather than improving decoding throughput. The authors should distinguish this contribution from the runtime benefits of AC matching and GPU-parallel mask aggregation, and explain what is new relative to existing automata-based decoding engines.

2. Important existing implementations and baselines are missing.

The paper's abstract claims that standard regex engines do not readily support complement and intersection. This claim is too broad. For example, llguidance explicitly supports regex intersection (&) and complement (~), including constructions that exclude forbidden substrings. While these operations can be computationally expensive, their availability weakens the paper's motivation that such constraints lack practical implementation support.

llguidance is particularly relevant because it provides an existing high-performance constrained decoding engine, yet neither it nor its implementation is discussed. The authors should compare NCO against llguidance on equivalent negative substring constraints and distinguish differences in preprocessing, mask computation, and end-to-end inference throughput.

For finite forbidden strings, Hugging Face Transformers' bad_words_ids / NoBadWordsLogitsProcessor is also a natural practical baseline. Although token-sequence blocking is not generally equivalent to character-level substring avoidance, this distinction itself deserves discussion and empirical evaluation.

3. The XGrammar results in Appendix E.6 weaken the efficiency claims.

Appendix E.6 indicates that XGrammar achieves competitive inference throughput on both RTP and Enron, while requiring substantially less preprocessing in the reported comparisons. This is especially relevant because NCO's BPE-based acceleration primarily targets preprocessing.

The authors should explain under what conditions NCO is preferable to XGrammar, and report end-to-end latency including preprocessing, particularly when constraints are constructed dynamically or reused for only a small number of generations. Without such analysis, the practical efficiency advantage is less convincing than the main results suggest.

Questions for authors
  1. How does NCO compare with llguidance when both are configured to enforce identical negative substring constraints? Please report preprocessing time, decoding throughput, and end-to-end latency.
  2. What is the main algorithmic novelty beyond standard AC matching, active-state-set simulation, and precomputed automata-token transitions?
  3. Given the XGrammar results in Appendix E.6, under what workload characteristics—number of constraints, regex complexity, batch size, or constraint reuse—does NCO provide a meaningful performance advantage?
  4. Can the authors include Hugging Face's bad_words_ids as a finite-string baseline, while explicitly addressing its different token-level semantics?
4 comments

We thank the reviewer for the careful evaluation and constructive feedback.

W1. Algorithmic Novelty and Contributions to Preprocessing and Decoding Efficiency

We acknowledge that AC matching and active-state simulation are well-established, and the reviewer correctly points out that a modified AC automaton can handle finite forbidden strings without state explosion. While these techniques may appear straightforward to researchers familiar with automata theory, adapting and optimizing them to address a practical problem can itself constitute a meaningful contribution.

Our primary contribution is an efficient inference-time framework for negative substring constraints. Despite its practical importance in LLM deployments, where service providers must prevent prohibited expressions or sensitive information, this problem has received limited attention. Although such constraints can theoretically be expressed using positive constraints, constructing and efficiently enforcing them can be challenging.

We further clarify that while the BPE-aware transition composition improves preprocessing efficiency, GPU-parallel mask aggregation also reduces decoding-time masking overhead. Our runtime breakdown in W2-W4 demonstrates that NCO can achieve substantially lower masking overhead than existing decoding frameworks, particularly for larger constraints under batched inference.

Lastly, we clarify that our discussion of potential state explosion in global avoidance automata primarily concerns regex constraints, not finite forbidden strings. We have revised the corresponding descriptions to avoid suggesting that the AC-based finite-string construction suffers from the same difficulty.

W2-W4. Comparison with Practical Baselines

We acknowledge that LLguidance supports regex complement and intersection, and have revised our broad statement. However, constructing negative substring constraints through these operations can be still computationally expensive in practice. Our constraint grammar exceeded LLguidance's default complexity limits, resulting in a LexerTooComplex error. Successful execution required substantially increasing the lexer resource limits and disabling large-lexeme precomputation.

We evaluate LLguidance, XGrammar, and Hugging Face bad_words_ids (HF) on Enron and RTP using GPT-J 6B, and up to 128 generated tokens. XGrammar uses grammar-based constraints on Enron and native string exclusion on RTP. For LLguidance, we constructed equivalent negative-substring grammars using the complement of Σ∗(R1∣⋯∣Rn)Σ∗\Sigma^*(R_1|\cdots|R_n)\Sigma^* since it does not support an automaton or multiple regexes as an input. All methods except bad_words_ids achieved zero violations.

Enron four forbidden regexes

BatchMethodPreproc. (ms)Forward (ms)Masking (ms)# Tokens
1NCO3,250670,9019,03555.3k
1XGrammar383671,3338,22255.3k
1LLguidance210681,22915,69555.3k
8NCO3,209143,5261,71155.5k
8XGrammar381143,4181,77855.5k
8LLguidance211175,1098,71455.5k
32NCO3,201112,68645155.5k
32XGrammar382112,65990455.5k
32LLguidance214143,3857,42955.5k

RTP 403 forbidden strings

BatchMethodPreproc. (ms)Forward (ms)Masking (ms)# Tokens
1NCO23,248762,5731,70163.6k
1XGrammar789762,09213,20463.6k
1LLguidance242778,28326,82463.6k
1HF53763,2592,084,32163.6k
8NCO23,402107,46937763.7k
8XGrammar775107,4135,65263.7k
8LLguidance245107,69517,66763.7k
8HF50108,344266,44263.7k
32NCO23,39634,09318863.7k
32XGrammar78133,4124,80763.7k
32LLguidance25133,34216,46263.7k
32HF5133,46366,69763.7k

The runtime breakdown reveals NCO's advantages under larger constraint sets and batched decoding. On RTP, NCO reduces masking time by 7.8--25.6x over XGrammar and 15.8--87.6x over LLguidance. Its speedup over XGrammar increases from 7.8x to 25.6x with batch size. On Enron, overall performance is comparable, but NCO achieves 2x lower masking overhead at batch size 32. These results suggest that NCO is more effective with larger constraint sets, although other factors may contribute.

NCO trades preprocessing time for decoding efficiency. Its additional preprocessing cost is amortized after approximately 2, 5, and 6 repeated runs at batch sizes 1, 8, and 32, respectively, assuming preprocessing is reused. This makes NCO well-suited to LLM serving environments where constraints are predefined and stable across many batched requests.

Finally, HF blocks token sequences rather than substrings, resulting in 15.0--15.6% violations on RTP despite substantially higher masking overhead.

AuthorsOpenReview ↗

Request for Discussion Engagement

Thank you for your time and constructive feedback. We have carefully addressed your concerns through detailed clarifications and additional experiments.

As the discussion period approaches its end, we would greatly appreciate it if you could review our responses and newly added results. In particular, we have:

  • W1: Clarified NCO's algorithmic contributions and distinguished BPE-aware preprocessing from GPU-parallel decoding-time mask computation.
  • W2: Added comparisons with llguidance under equivalent negative substring constraints, including preprocessing, masking, and inference costs.
  • W3: Provided detailed runtime breakdowns and preprocessing amortization analyses against XGrammar, clarifying when NCO offers practical advantages.
  • W4: Evaluated Hugging Face's bad_words_ids and clarified its token-level semantics and limitations for substring avoidance.

We hope these clarifications and results adequately address your concerns. If you find our responses satisfactory, we would be grateful if you could reconsider your evaluation, including the overall score.

Please let us know if any concerns remain. We would be happy to address them.

Thank you for the detailed response and the additional experiments. The new comparisons with llguidance and Hugging Face’s bad_words_ids address W2, and I appreciate the revised claims.

I will, however, keep my score, primarily because of W1. The response acknowledges that the core components are standard, and I still do not see a clear algorithmic contribution beyond existing automata-based constrained decoding.

As a minor remaining concern on W3, the new results show an end-to-end advantage over XGrammar only for finite forbidden strings, with parity on the regex constraints, and the amortization analysis does not cover the regex setting.

We thank the reviewer for the follow-up and for acknowledging our additional comparisons. We would like to further clarify two points.

W1. Algorithmic Contribution

As discussed in our previous response, we acknowledge that the underlying automata techniques are well established. We would like to further clarify that the contribution of NCO lies in addressing the distinct computational challenges of exact negative substring enforcement under subword tokenization, rather than introducing new automata primitives. This setting requires detecting forbidden matches that may begin at arbitrary positions, including within individual tokens, while efficiently handling multiple constraints without constructing a potentially large global avoidance automaton.

NCO addresses these challenges through a unified algorithmic design that combines independent DFA-state tracking, BPE-aware composition of token transitions and suffix-reachable states, and GPU-parallel mask aggregation. These components jointly enable exact substring-level enforcement with low decoding overhead, while addressing distinct computational bottlenecks demonstrated in our ablation studies. We believe that this problem-specific algorithmic design, together with its correctness guarantees and empirical efficiency, constitutes a meaningful contribution beyond the individual established techniques.

W3. Efficiency Under Regex Constraints

We further evaluated NCO and XGrammar with 8–32 forbidden regex constraints on Enron (500 prompts, batch size 32). NCO consistently achieves lower masking overhead, while overall generation throughput remains comparable. More importantly, NCO's preprocessing cost grows approximately linearly, whereas XGrammar's global grammar construction cost increases rapidly, reaching a comparable level at 24 regexes. At 32 regexes, the global grammar construction for XGrammar failed after two hours and approximately 85 GB of memory usage, while NCO completed preprocessing in 34 seconds. These results highlight NCO's scalability advantage in handling multiple forbidden regex constraints without constructing a global grammar.

# RegexMethodPreproc. (ms)Generation (ms)Forward (ms)Masking (ms)# Tokens
8NCO7,752129,779128,56648655,560
8XGrammar462130,063128,36096355,560
16NCO17,619130,072128,73960155,560
16XGrammar10,260130,320128,5501,01955,560
24NCO25,248131,362130,02863054,766
24XGrammar23,586131,356129,67496854,766
32NCO34,419129,907128,46272154,793
32XGrammar—————
Reviewer_8N28OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes a constraint decoding method called NCO, which performs online pattern matching for negative constraints (not including phrases or not matching regex) in a computationally efficient manner. The experiments demonstrate that the method is more efficient against several baselines, on PII and profanity suppression tasks.

Critical strengths
  • Well written and easy to follow.
  • Solid experiments to demonstrate computational efficiency of the method.
Critical weaknesses

Overall I think the paper did a good job. I only have a minor concern about the relevance of the study:

In my understanding, most of the constraint decoding methods use positive constraints because it is way more common to have need to enforce output to follow certain requirements (e.g., format adherence), and way harder to specify negative constraints as negative constraints are often semantic in nature - you could list almost infinite ways to break certain rules. So in a practical setting, to have a dictionary of forbidden words is probably the only case I could think of, although easily bypass-able by creative users anyway. Even for PII there are a lot more flexible ways to leak than what the method targets. The paper could motivate the relevance and applicability of such negative constraints better.

Questions for authors

How provenant is the need for negative constraints expressed in a strict setting that NCO targets?

2 comments

We thank the reviewer for this valuable comment. We acknowledge that negative constraints can be bypassed through alternative expressions. However, such circumvention does not diminish the practical value of explicitly blocking forbidden strings or patterns.

In real-world applications, both semantic safety and explicit pattern-level restrictions are important. Indeed, services such as Amazon Bedrock Guardrails, Azure AI Content Safety, and Google Cloud Sensitive Data Protection already provide filtering mechanisms based on forbidden words, phrases, custom blocklists, or regex patterns. These examples demonstrate the practical demand for explicit negative constraints.

Unlike positive constrained decoding, negative constraints selectively exclude forbidden patterns without imposing a fixed output format or grammar. While NCO alone cannot guarantee semantic safety, it can complement semantic safety mechanisms by enforcing explicit restrictions during generation. Its support for soft constraints further allows applications to adjust the trade-off between constraint satisfaction and generation quality. We believe these properties establish the practical relevance of negative constrained decoding despite its limitations in addressing semantic circumvention.

AuthorsOpenReview ↗

Request for Discussion Engagement

Thank you for your time and constructive feedback. We greatly appreciate your positive assessment of our work.

As the discussion period approaches its end, we would appreciate it if you could review our response and the revised manuscript. We have clarified the practical relevance of explicit negative constraints by discussing real-world filtering mechanisms used in commercial AI services. We have also acknowledged the limitations of pattern-level restrictions against semantic bypass and clarified how NCO can complement semantic safety mechanisms.

We hope our response adequately addresses your concern. We would appreciate it if you could confirm whether your concern has been resolved or let us know if any questions remain.

We would be happy to provide further clarification.

Reviewer_T9hpOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

NCO is a training-free decoding plug-in that prevents generated text from containing specified strings or substrings matching specified regular expressions. It uses an Aho–Corasick automaton for finite string sets and tracks active DFA states separately for each regex, avoiding a large global automaton. BPE precomputation and parallel GPU operations produce token masks.

Critical strengths

The problem definition is clear, with careful handling of edge cases. The method handles matches across token boundaries and matches starting within a token, with state invariants and correctness proofs.

Critical weaknesses

Differences under deterministic decoding need explanation. The appendix states that RS and NCO use the same greedy settings, with RS repeatedly excluding invalid tokens from the same logits. If their allowed-token sets are identical, both should select the same highest-scoring valid token. Yet Falcon3 has PPL values of 2.96 and 3.12, respectively, and discrepancies appear in other models too. Token-by-token output and mask comparisons are needed, or an explanation of numerical, configuration, or implementation differences. This does not establish a bug, but it affects confidence in the comparison.

The advantage over strong baselines depends on amortizing setup costs. For four PII-pattern types, NCO and XGrammar have nearly identical throughput, but setup takes roughly 3.2 and 0.4 seconds, respectively. NCO precomputation for 1,000 regexes takes about 470 seconds and 1.469 GB. These costs are disclosed, but the paper should show how often rules must be reused to justify them, especially when constraints change with each request.

Evidence that generation quality is largely unaffected remains limited. PPL, KL divergence, and repetition metrics cannot replace assessments of task completion, information retention, false blocking, and human-rated fluency. Under sampling, hard masking raises PPL from 4.38 to 5.74 in Table 16, suggesting a cost. Zero violations establish compliance with the specified patterns, but do not show that answers remain equally useful.

Questions for authors

Why are there differences under deterministic decoding?

3 comments

W1. Differences Under Deterministic Decoding

We thank the reviewer for identifying this inconsistency. We reexamined our implementation and identified two sources of inconsistency. First, RS omitted EOS tokens from the stored outputs, whereas NCO retained them, which explains the reported perplexity differences. Second, RS prohibited lexicon entries surrounded by whitespace, whereas NCO prohibited the lexicon entries themselves, resulting in different admissible token sets.

After correcting the constraint mismatch, we ran Falcon3 on all 500 RTP instances and confirmed that RS and NCO produced identical outputs under greedy decoding, resolving the reviewer's primary concern. Notably, the corrected RS implementation exhibited lower throughput, decreasing from 46.2 to 44.0 tokens/s at batch size 1 and from 573.5 to 441.9 tokens/s at batch size 16. This suggests that the original implementation underestimated RS's rejection overhead, favoring RS rather than NCO.

We will update the affected RS results after completing consistent reruns.

W2. Preprocessing Costs and Constraint Reuse

We thank the reviewer for highlighting the importance of preprocessing amortization. When constraints change frequently, NCO's preprocessing cost can limit its practical advantage. However, NCO deliberately trades preprocessing time for lower decoding overhead, making it particularly suitable for workloads where constraints are predefined and reused across many requests.

To quantify this trade-off, we conduct additional runtime breakdown experiments against XGrammar. On RTP with 403 forbidden strings, NCO reduces masking time by 7.8--25.6x across batch sizes 1, 8, and 32. Based on the measured generation times, its additional preprocessing cost is amortized after approximately 2, 5, and 6 repeated 500-prompt runs, respectively, assuming preprocessing is performed only once.

On Enron with four PII regexes, both methods exhibit comparable generation performance, although NCO achieves approximately 2x lower masking overhead at batch size 32. These results clarify that NCO is effective for batched generation with stable constraints, rather than short, one-off workloads.

Enron four forbidden regexes

BatchMethodPreproc. (ms)Forward (ms)Masking (ms)# Tokens
1NCO3,250670,9019,03555.3k
1XGrammar383671,3338,22255.3k
1LLguidance210681,22915,69555.3k
8NCO3,209143,5261,71155.5k
8XGrammar381143,4181,77855.5k
8LLguidance211175,1098,71455.5k
32NCO3,201112,68645155.5k
32XGrammar382112,65990455.5k
32LLguidance214143,3857,42955.5k

RTP 403 forbidden strings

BatchMethodPreproc. (ms)Forward (ms)Masking (ms)# Tokens
1NCO23,248762,5731,70163.6k
1XGrammar789762,09213,20463.6k
1LLguidance242778,28326,82463.6k
1HF53763,2592,084,32163.6k
8NCO23,402107,46937763.7k
8XGrammar775107,4135,65263.7k
8LLguidance245107,69517,66763.7k
8HF50108,344266,44263.7k
32NCO23,39634,09318863.7k
32XGrammar78133,4124,80763.7k
32LLguidance25133,34216,46263.7k
32HF5133,46366,69763.7k

W3. Generation Quality

We conduct additional LLM-as-a-judge and human evaluations of overall generation quality on 100 randomly sampled Enron instances generated by GPT-Neo 2.7B. We use a five-point rubric with GPT-5.4 and two independent human annotators with a shared five-point rubric that jointly assesses fluency, coherence and relevance to the prompt, preservation of meaning and informativeness, readability, and overall acceptability.

MethodGPT-5.4Annotator 1Annotator 2Average
Base2.652.873.392.97
NCO/RS2.222.533.312.69

The average quality score decreases from 2.97 to 2.69, indicating some degradation under strict negative constraints. Nevertheless, the results suggest that NCO can enforce substring restrictions without substantially compromising overall generation quality.

AuthorsOpenReview ↗

Request for Discussion Engagement

Thank you for your time and constructive feedback. We have carefully addressed your concerns through detailed clarifications and additional experiments.

As the discussion period approaches its end, we would greatly appreciate it if you could review our responses and newly added results. In particular, we have:

  • W1: Identified and corrected the inconsistencies between RS and NCO, confirming identical outputs under greedy decoding on all 500 Falcon3 evaluation instances.
  • W2: Added runtime breakdowns and preprocessing amortization analyses to clarify when NCO provides practical advantages over XGrammar.
  • W3: Conducted additional human and LLM-based evaluations to assess generation quality under negative constraints.

We hope these clarifications and results adequately address your concerns. If you find our responses satisfactory, we would be grateful if you could reconsider your evaluation, including the overall score.

Please let us know if any concerns remain. We would be happy to address them.

AuthorsOpenReview ↗

Update on the Revised Manuscript

We thank the reviewer again for the constructive feedback. We have updated the revised manuscript to incorporate the corrections and additional experimental results discussed in our responses.

In particular, we reran the rejection sampling (RS) experiments on RTP across all models and batch sizes using constraints consistent with NCO, and updated the corresponding throughput results. We also reevaluated perplexity for all methods. Our previous evaluation included prompt tokens in the perplexity calculation. To better assess the quality of the generated text, we now compute conditional perplexity only over the generated continuations, excluding prompt tokens. The updated results confirm that RS and NCO achieve identical perplexity under greedy decoding, resolving the previously reported discrepancy.

All revisions are highlighted in blue in the updated PDF for ease of reference. We hope these updates further address your concerns and appreciate your consideration.

Comments on the paper

2 comments

We thank the reviewers for their constructive feedback. We have revised the manuscript to clarify our algorithmic contributions, practical relevance, and limitations, including the possibility of semantic bypass. We also expanded comparisons with llguidance and Hugging Face's bad_words_ids, and added runtime breakdowns, preprocessing amortization analyses, and human and LLM-based quality evaluations. All revisions are highlighted in blue in the updated manuscript for ease of reference.

AuthorsOpenReview ↗

Update on the Revised Manuscript

We thank the reviewers for their constructive feedback. We have further revised the manuscript to address two important concerns.

First, we resolved the inconsistencies between RS and NCO under greedy decoding, conducted consistent reruns, and updated the corresponding throughput and perplexity results.

Second, we added scalability experiments against XGrammar with increasing numbers of forbidden regex constraints. These results further clarify NCO's practical advantages in handling multiple constraints without constructing a global grammar.

All new revisions are highlighted in blue in the updated manuscript for ease of reference. We hope these additional corrections and experiments address the remaining concerns, and we appreciate the reviewers' continued consideration.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.