- 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
- The AC-state and DFA active-state-set invariants are appropriate for substring avoidance, and the correctness arguments are sound under the stated assumptions.
- The BPE-aware composition of token transition and blocking tables is simple, elegant, and correct.
- The open-source implementation, with support for batching and multiple decoding strategies, is a useful contribution to practitioners.
- 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 states for total pattern length . 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
- 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.
- What is the main algorithmic novelty beyond standard AC matching, active-state-set simulation, and precomputed automata-token transitions?
- 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?
- Can the authors include Hugging Face's
bad_words_idsas a finite-string baseline, while explicitly addressing its different token-level semantics?
4 comments
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.
| # Regex | Method | Preproc. (ms) | Generation (ms) | Forward (ms) | Masking (ms) | # Tokens |
|---|---|---|---|---|---|---|
| 8 | NCO | 7,752 | 129,779 | 128,566 | 486 | 55,560 |
| 8 | XGrammar | 462 | 130,063 | 128,360 | 963 | 55,560 |
| 16 | NCO | 17,619 | 130,072 | 128,739 | 601 | 55,560 |
| 16 | XGrammar | 10,260 | 130,320 | 128,550 | 1,019 | 55,560 |
| 24 | NCO | 25,248 | 131,362 | 130,028 | 630 | 54,766 |
| 24 | XGrammar | 23,586 | 131,356 | 129,674 | 968 | 54,766 |
| 32 | NCO | 34,419 | 129,907 | 128,462 | 721 | 54,793 |
| 32 | XGrammar | — | — | — | — | — |
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)Σ∗ 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
RTP 403 forbidden strings
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.