acceptodds
Under review as a conference paper at ICLR 2027

Conditional Deontics Over Terminals: A Cross-subtree Reference Mechanism for Efficient yet Expressive Constrained Decoding

Abstract

As recent work has improved expressiveness in constrained decoding, a common component has begun to emerge: user-defined functions that read and modify a constrainer's internal state. However, permissive access to a constrainer's internal state makes efficiency optimization difficult. In this work we offer a sharpened contract for such user-defined functions, decomposing them into simpler functions that require minimal access to the constrainer's internal state, which we call deontic functions, and providing mechanisms for aggregating and anchoring deontic functions within grammar structures. Using our formalism, we implement the unit-propagation algorithm within a chain of thought, enabling a smaller model to achieve a high solve rate and reduced token consumption on a SAT-style logic puzzle called “Knights and Knaves”. Utilizing a GPU-based backend for our formalism, we replicate constrainers such as type checking and e-graph enforcement found in prior works and achieve substantial efficiency gain.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
constrained decoding, GPU acceleration

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_whkBOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Constrained decoding is a generation scheme that enforces a model to generate an output that satisfies certain formal constraints. However, CFG constraints have a limitation that it cannot express some context sensitive information (e.g. variable consistency.), and the operation is often conducted on CPU which can limit the throughput. The paper proposes a new type of grammar named CDoT and the corresponding parser, which extends CFGs by combining deontic functions. Furthermore, the designed parser is based on the incremental CYK parser, and can utilize GPU acceleration. Compared with three baselines, the experimental results on four tasks demonstrate the decoding efficiency of the proposed methods. However, the correctness of the proposed parser, the overall complexity with and without GPU acceleration, and the expressive power of proposed grammar are insufficiently discussed.

Critical strengths

1. The proposed grammar addresses the direct limitation of context-free grammars.

The proposed grammar is clearly more expressive than CFGs, allowing it to enforce context-sensitive constraints variable coherency.

2. The proposed parser benefits from GPU acceleration.

The proposed incremental CYK parser can exploit GPU acceleration for efficient decoding. Experimental results demonstrate that CDoT achieves substantially lower decoding latency than other baselines across multiple tasks.

Critical weaknesses

1. The proposed parser does not guarantee the correctness of the generated output.

The correctness relies on uniform-coverage assumptions, which is not always true. Indeed, the paper itself already provides a counterexample in the appendix B. Thus, the paper should further discuss how often these false positives occur and how they can be addressed in practice.

2. The grammar itself is not formally defined.

Although the paper introduces a new grammar combining deontic functions and anchoring mechanism, a complete formal definition of the grammar is missing.

3. The complexity analysis is insufficiently discussed.

While the paper provides a bound on the number of deontic function calls, it does not discuss or prove the overall time complexity of the proposed parser. The space complexity and memory usage are also missing. Furthermore, the computational complexity with and without GPU parallelization should be clearly analyzed.

4. The initialization cost is insufficiently discussed.

While the per-step preprocessing operations are described in Appendix H, the initialization overhead of the parser is insufficiently discussed, making it difficult to assess its end-to-end efficiency.

5. Some experimental settings are not fully controlled.

LLGuidance and XGrammar enforce only CFG constraints, while CDoT additionally enforces deontic constraints. The additional constraints may reduce the number of possible completions, potentially making the decoding faster by restricting the search space. Thus, an ablation study of using the skeleton CFG grammar with the proposed parser would strengthen the analysis. Furthermore, in the experiments on Spider, the paper uses the grammar that is the union of all schemas, although each schema is associated with a specific question. It only gives unnecessary processing overhead and allows the incorrect output to be generated.

Questions for authors

Questions

Q1. Could the authors provide further discussion on the correctness of the proposed parser? How can violations of the uniform-coverage assumption be addressed in practice?

Q2. Could the authors provide the formal definition of CDoT?

Q3. Could the authors analyze the worst-case time complexity of the proposed parser in terms of input length, grammar size, the number of anchors, and vocabulary size?

Q4. Could the authors describe the space complexity and memory usage of the proposed parser?

Q5. Could the authors discuss the relationship between CDoT and other classes of formal grammars such as context-sensitive grammar and attribute grammars?

Q6. Could the authors provide an ablation study using only CFG skeleton grammar with and without GPU acceleration? Furthermore, it would benefit from adding the results of CDoT without GPU acceleration through isolating the effects of parallelism.

Q7. Could the authors provide the experimental results on Spider using individual schemas?

Suggestions

Although it is clear that every context-free language can be expressed by CDoT, the paper would benefit from including a formal proof that the class of languages that can be expressed by CDoT strictly includes the class of context-free languages.

4 comments

Q1. Could the authors provide further discussion on the correctness of the proposed parser? How can violations of the uniform-coverage assumption be addressed in practice?

When the uniform-coverage assumption is violated, some invalid sequences may be allowed to pass through, but no valid sequences will ever be excluded. In our experiments, the uniform-coverage assumption was never violated, so we never observed invalid sequences being produced. For applications where the uniform-coverage assumption is violated and invalid sequences are not tolerable, additional safeguards can be employed:

  • Post-generation validation: Model outputs can be checked against the specified constraints using an independent validator, which can be implemented in a conventional programming language without the challenges associated with constrained decoding.

  • Verification of stronger sufficient conditions: One can automatically check whether the grammar satisfies more restrictive conditions that guarantee uniform coverage. For example, LL grammars may serve as a sufficient condition, since their predictive parsing structure eliminates ambiguity in production selection.

Q2. Could the authors provide the formal definition of CDoT?

It is now provided in appendix I (page 31).

Q3. Could the authors analyze the worst-case time complexity of the proposed parser in terms of input length, grammar size, the number of anchors, and vocabulary size?

The worst case time per decoding step is O(n2(∣R∣+∣D∣)+n(∣Vnt∣2+∣D∣ρ)+∣D∣f)O\big(n^2(|\mathcal{R}|+|D|) + n(|V_{\mathrm{nt}}|^2+|D|\rho) + |D|f\big) Here nn is the number of terminal instances committed so far, R\mathcal{R} is the set of binary productions and VntV_{\mathrm{nt}} the set of nonterminals of the grammar in Chomsky normal form, DD is the set of anchors (the deontic rules attached to productions), ρ\rho is the size of one activation record (the permitted set and witness sets returned for one antecedent instance, which is also the cost of testing one terminal instance against it), and ff is the cost of one deontic function call. We offer the break down in appendix H.2 (page 27).

However, the cubic worst-case complexity is unlikely to arise in typical workloads, and pathological cases can be detected and rejected using mechanisms already employed by existing constrained decoders. Our measurements suggests near-linear growth on our data, as shown in Figure 5.

Practical complexity is expected to be substantially lower. In practice, CYK parsing charts are inherently sparse. Even in challenging domains such as natural language, much of the syntactic ambiguity is localized within smaller structural units, such as sentences. Thus the O(n3)O(n^3) behavior is not to be expected over long sequences. Bernardy and Claessen [1] formalize a related intuition, demonstrating that a sparse implementation of Valiant's parsing algorithm (which reformulates CYK using matrix multiplication) can achieve (O(n)O(n)) total sequential complexity under assumptions satisfied by many practical, hierarchically structured inputs. Although they used a tree-like structure unsuitable for GPU. For a GPU-based variant, Azimov and Grigorev [2] provide empirical measurements demonstrating that it can outperform CPU-based GLL parsers, which can achieve lower complexity bounds on simpler grammar classes.

Pathological cases can be detected and rejected by simply monitoring the number of items in the parsing chart. LLGuidance imposes a conservative cutoff that can be triggered even on grammars belonging to the LR class, well before cubic worst-case behavior is observed (Table 2, Li et al. [3]).

Q4. Could the authors describe the space complexity and memory usage of the proposed parser?

Memory consumption grows quadratically with sequence length in the worst case, as shown in Appendix H.2 (page 30). However, as with time complexity, empirical memory usage is substantially lower when sparsity is exploited (Table 11).

Per-sequence GPU memory consumption ranges from 259 MB to 565 MB under standard workloads. In stress tests with sequences containing up to 8K terminal instances, memory usage ranges from 1.8 GB to 2.9 GB per sequence. These figures reflect our current conservative memory allocation strategy, and more careful memory management could further improve efficiency.

Additionally, the engine itself consumes 206 MB of GPU memory, while the average per-grammar memory cost ranges from 78 MB to 1,060 MB, depending on the dataset.

Q5. Could the authors discuss the relationship between CDoT and other classes of formal grammars such as context-sensitive grammar and attribute grammars?

In Appendix J (page 34), we show that CDoT and mildly context-sensitive grammar formalisms (LCFRS, MCFG, and TAG) are incomparable in expressive power: neither subsumes the other. We also examine CDoT's relationship with CFGs and Turing transducers.

Regarding attribute grammars, CDoT can be viewed as a specialized variant designed for constrained decoding. In particular, constrained decoding requires frequent branching and rollback during parsing, which complicates the use of general attribute grammars, where user-defined attribute evaluation and aggregation functions may operate at multiple levels of the parse tree.

CDoT addresses this challenge by restricting user-defined functions to the leaf level, while automatically managing branching and rollback and enabling GPU-accelerated execution. This design reduces the implementation burden on users while supporting efficient constrained decoding.

In relative to attribute grammar, CDoT is a restricted version of it with a special

Q6. Could the authors provide an ablation study using only CFG skeleton grammar with and without GPU acceleration? Furthermore, it would benefit from adding the results of CDoT without GPU acceleration through isolating the effects of parallelism.

CDoT vs. CDoT Skeleton: We have added this comparison to Table 2 (page 9). Our full constrainer is generally twice as fast as the skeleton-only variant, requiring approximately half the processing time.

The concern that restricting the constraint space may affect latency is valid. Both XGrammar and LLGuidance achieve speedups by exploiting simpler, more restricted constraint classes, while also dedicating substantial engineering effort to handling large LLM vocabularies. However, the latter challenge is largely mitigated by GPU parallelism. Once the eligible terminal instances and their deontic specifications are determined, the entire LLM vocabulary can be checked efficiently in parallel on the GPU. This is an additional advantage of CDoT's design, which applies constraints at the terminal level rather than the nonterminal level.

Effect of Parallelism: Azimov et al. [2] provide a dedicated study of GPU- and CPU-based CYK implementations, including dense and sparse variants, with a GLL parser as a reference baseline. Our parser introduces only minor modifications to the CYK merge operation without changing its asymptotic complexity. The added factors within complexity analysis arises from maintaining an ensemble of CYK parsers. Consequently, the analysis by Azimov et al. remains relevant to our approach.

Q7. Could the authors provide the experimental results on Spider using individual schemas?

Under Individual schemas, the model generated 285 correct queries, similar to 286 correct queries generated under union schema.

The initialization cost is insufficiently discussed

The average initialization time ranges from 438 ms to 1,134 ms per fresh grammar, depending on the dataset (updated Table 2, page 9). This is roughly comparable to the time required for an LLM to prefill a prompt.

[1] https://www.cambridge.org/core/journals/journal-of-functional-programming/article/efficient-parallel-and-incremental-parsing-of-practical-contextfree-languages/4D620F0BFADE2B588F854AAAEA252F5C

[2] https://dl.acm.org/doi/10.1145/3210259.3210264

[3] https://arxiv.org/abs/2608.03065

Thanks for the detailed response. In the revised paper, the formal definition, complexity analysis, and discussion on expressive power have been well addressed, corresponding to Q2-Q5. However, my concerns on Q1, Q6, and Q7 remain. Please correct me if I am mistaken.

Q1. Soundness

A constrained decoder should not accept a string outside of the language of the grammar. The uniform coverage assumption depends on the grammar, and it is unclear how violations can be avoided during the grammar construction. While the authors claim that the uniform coverage assumption was not violated in the experiments, it is unclear how this was verified. It is insufficient to inspect only the generated strings, since soundness must hold for all strings allowed by the constrainer.

Q6. Ablation and GPU acceleration

While the authors claim that full CDoT is faster than CDoT skeleton, Table 2 in the revised PDF shows opposite results. CDoT skeleton and LLGuidance are faster than full CDoT. Furthermore, the asymptotic complexity does not guarantee GPU acceleration in practice. Thus, considering that the main contribution of this work lies in GPU parallelism, a CPU/GPU comparison is still needed.

Q7. Experiments on Spider

I apologize for the confusing question. The question was not about the correctness of individual grammar but about the runtime analysis. Each query in Spider has a corresponding schema, and thus please report the latency of CDoT, CDoT (skeleton), LLGuidance, and XGrammar under the individual schema setting. I believe using the union of all schemas is unusual for experiments on Spider.

Overall, I believe the claimed strength is not yet sufficiently established, and thus I will keep my original score.

Q1. Soundness

...  While the authors claim that the uniform coverage assumption was not violated in the experiments, it is unclear how this was verified.

We explain the soundness of each experiment grammar in Appendix K (page 36).

A constrained decoder should not accept a string outside of the language of the grammar.

Soundness and completeness are certainly expected of for context-free grammars. However, more expressive formalisms sometimes lack such formal guarantees.

For example, parsing expression grammars (PEGs), used by Python interpreter since version 3.9, can be non-halting, and determining whether an arbitrary PEG grammar always terminates is undecidable (Ford [1], Section 3.5). Thus detection can only be achieved with test cases. Nevertheless, Guido van Rossum [2], the Python creator, highlights the practical advantages of PEGs over the previously used LL(1) grammars.

Q6. Ablation and GPU acceleration

While the authors claim that full CDoT is faster than CDoT skeleton, Table 2 in the revised PDF shows opposite results. CDoT skeleton and LLGuidance are faster than full CDoT. Furthermore, the asymptotic complexity does not guarantee GPU acceleration in practice. Thus, considering that the main contribution of this work lies in GPU parallelism, a CPU/GPU comparison is still needed.

We have added Appendix L (page 37) for CPU vs GPU implementation of CDoT. Our GPU implementation is 4.6×4.6\times (KNK) to 31.4×31.4\times (e-graph) faster on p50, and 1.3×1.3\times (KNK) to 72.9×72.9\times (e-graph) faster on p99.

While the authors claim that full CDoT is faster than CDoT skeleton, Table 2 in the revised PDF shows opposite results.

We apologize for the confusion; our original response was unclear. Full CDoT is indeed slower than its skeleton-only variant due to the additional overhead of processing deontic semantics. Our speedup claim instead refers to the behavior of context-free constrained decoding engines such as LLGuidance and XGrammar.

Q7. Experiments on Spider

... each query in Spider has a corresponding schema

This comparison is now provided in Appendix M (page 38).

Full CDoT's performance remains largely unchanged, while the skeleton grammars experience a slowdown for CDoT and LLGuidiance. This is because the original skeleton grammars were generic SQL grammars that did not encode database schema information, so the per-database skeleton grammar is in fact more complicated.

[1] https://bford.info/pub/lang/peg.pdf [2] https://medium.com/@gvanrossum_83706/peg-parsers-7ed72462f97c

Reviewer_MR11OpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper presents Conditional Deontics over Terminals (CDoT), a novel abstraction for constraining LLMs with user-defined functions. It introduced deontic functions, those functions that require minimal access to the constrainer’s internal state, and relating those to the grammar structures. The authors implemented a GPU version of their solver, showing the speed and effectiveness of CDoT on logical puzzles like Knights and Knaves, and SQL formula generation.

Critical strengths
  • The paper shows that it is feasible to constrain large language models with more expressive formal grammars. The evaluation also shows that such approach can be practical.

  • GPU acceleration is interesting conceptually and practically. It also shows that the definition of the algorithm exposes significant parallelism that results in realistic latency reduction.

  • The evaluation shows some encouraging results: (a) the constraint latency results show that CDoT is significantly faster than ChopChop, and is comparable to LLGuidance and XGrammar, demonstrating the efficiency of CDoT. (b) The output quality results (Table 5 in Section G) show that the output quality of CDoT is the same as or even outperforms ChopChop, presenting the effectiveness of CDoT for enforcing constraints.

Critical weaknesses
  • The paper aims to introduce the technical core informally (Section 3), which succeeds only half-way in conveying the intuition of deontic functions. However, the informal style also leaves open the question of what exactly this formalism is and what its expressive power is. From the rules, it appears to be more powerful than context free grammars, but it does not precisely specify which classes of semantic properties it supports.

  • The key properties in Section 4, namely completeness and soundness are hard to follow without introducing the appropriate level of formalism. Currently, the two subsections (Completeness/soundness) contain a proof sketch, but it is difficult to discern what the statements of these properties are. A precise definition of completeness/soundness should be specified. Some key terms such as “permitted instances” and “witnesses” used in this section were not defined in the paper; witnesses were mentioned only in the Appendix. Clear definitions and precise algorithm descriptions would increase this reviewer's confidence in the paper.

  • The utility of the first study “Knights and Knaves” should be better motivated, e.g., expressing the key challenges for using LLMs in this space. More generally, these problems can be represented as logical formulas and solved with logical solvers, e.g. SMT, most likely in less time. So the paper should emphasize either the practical value or the accuracy jump even over frontier LLMs. In comparison, the other case study on Spider is more practically driven and shows direct benefits.

  • Other minor issues:

  1. Table 5 claims that ChopChop was not run on Spider because of its slowness, but it does not specify the computational budget (e.g., end-to-end latency) of the experiments.
  2. Table 5, the description in the paper should identify the main reasons why CDoT was better on TypeScript.
  3. Missing reference: “The full implementation of the constrainer is in ??”
Questions for authors
  • What is the expressive power of deontic functions? Which semantic properties can it describe and which can’t?


  • What are the precise definitions of completeness and soundness?


  • It is unclear what "mask-to-mask latency" measured in Table 2 means. Can you provide the definition?

2 comments

What is the expressive power of deontic functions? Which semantic properties can it describe and which can’t?


We have added Appendix J (page 34), which compares CDoT with CFGs, Turing transducers, and LCFRS/MCFGs. We also discuss the nuances of lexer behavior in the context of constrained decoding.

Intuitively, CDoT introduces two key capabilities:

  • Collective constraints over terminal instances: Terminal instances within a span can collectively satisfy necessary and permitted conditions. This remains within context-free expressiveness but provides a compact and tractable representation when the order in which the constraints are satisfied is irrelevant.

  • Cross-span references: The necessary and permitted conditions for a span can be determined by terminal instances in a preceding span, enabling dependencies that extend beyond context-free expressiveness.

Additionally, CDoT deliberately makes trade-offs between expressiveness and implementation efficiency, particularly regarding which capabilities are supported by the formalism and which are restricted by design.

For example, ChopChop theoretically supports infinite type hierarchies but finds them computationally expensive, ultimately adopting a finite implementation. CDoT instead explicitly restricts type hierarchies to be finite, enabling efficient GPU acceleration. On the other hand, CDoT permits an unbounded number of references to the same declared variable, a capability not generally supported by typical mildly context-sensitive grammar formalisms (Appendix J).

These design choices also introduce limitations. For example, our current implementation cannot distinguish identically named variables across nested scopes, where the same variable name may refer to different types in inner and outer scopes. This limitation arises from the design choices made to enable efficient GPU parallelization.

Overall, CDoT does not aim to maximize expressiveness in every dimension. Instead, it selectively supports capabilities that are valuable for constrained decoding while preserving opportunities for efficient parallel implementation.

What are the precise definitions of completeness and soundness?


Given a CDoT grammar (GG), let (L(G)L(G)) denote the set of valid outputs defined by the grammar, and (L(E,G)L(E,G)) denote the set of outputs permitted by a constrained decoding engine (EE).

  • Completeness: (L(G)⊆L(E,G))(L(G) \subseteq L(E,G)). Every valid output remains permissible; no valid output is incorrectly excluded.

  • Soundness: (L(E,G)⊆L(G))(L(E,G) \subseteq L(G)). Every permitted output is valid; no invalid output is incorrectly admitted.

We have updated manuscript with clarification.

An engine that is both sound and complete satisfies (L(E,G) = L(G)).

It is unclear what "mask-to-mask latency" measured in Table 2 means. Can you provide the definition?

It measures the elapsed time between the decoder selecting the previous LLM token and the completion of the current token mask computation. This definition avoids ambiguity arising from differences in engine APIs: some engines separate committing the previous token and computing the current mask into two API calls, with workloads that are not necessarily comparable across engines. Furthermore, some computations may be performed asynchronously. We have clarified in the text.

what exactly this formalism is

We have added formal semantics as appendix I (page31)

Table 5 claims that ChopChop was not run on Spider because of its slowness, but it does not specify the computational budget (e.g., end-to-end latency) of the experiments.

We allowed 150 sec per SQL query.

Table 5, the description in the paper should identify the main reasons why CDoT was better on TypeScript.

It was caused by time outs on TypeScript experiments. With time out removed, we observed steps over 2 min per token.

Missing reference: “The full implementation of the constrainer is in ??”

We have corrected the error, thank you for pointing it out.

Thank you for the comments and the paper update. The response addresses several of my immediate concerns (expressive power, soundness/completeness definitions, evaluation setup details). Here, I acknowledge the authors' effort to distinguish their core abstraction from the other language abstractions. I hope the discussion of the soundness of the constraining for each problem can propagate from the appendix to the main paper. I still have some concerns about the extent of the evaluation, including new comparison in Table 2, which shows somewhat less clear results (including the new values in init vs per step columns).

Looking at the current version, I still see a challenge to represent the background and the approach in a sufficient level of details. Presenting the formalism that is currently in the appendix deserves to find its way to the main paper, perhaps in a longer-form version.

I will keep my current score.

Reviewer_jXQrOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

CDoT restricts user-defined constraint functions in grammar-constrained decoding to single-terminal functions returning necessary and permitted regex sets, attached by structural anchors and combined by union and conjunction, with a CYK-style incremental parser. It shows a unit-propagation chain of thought for Knights and Knaves and reimplements SQL scoping, e-graph and TypeScript constraints with latency far below ChopChop.

Critical strengths
  1. The problem is real: unbounded callbacks block optimization.
  2. The restriction to single terminals is a clean, motivated design choice.
  3. Latency on four tasks is measured against both expressive and fast systems, with p50 and p99.
  4. The paper is honest about its limits.
Critical weaknesses
  1. No formal semantics. The title promises one, but there is no definition of anchors, valid trees or the recognized language. Section 4’s soundness and completeness are one-paragraph sketches over undefined terms. Expressiveness is never characterized, only asserted through conjunctive grammars.
  2. Union-♢ is not sound in general. The paper’s own counterexample shows this, and soundness depends on a “uniform coverage” assumption. Every main application (scoping, SQL, e-graph, puzzle pivots) uses union-♢, so the guarantee does not cover the experiments.
  3. The puzzle result lacks the key control. The constrainer is generated per puzzle from the CNF and enforces forced literals, closure and a systematic pivot-flip search. If propagation fixes everything after one correct pivot, a coin-flip pivot succeeds half the time, so the correct null model is not a “uniformly random assignment”. Needed: a random-pivot policy under the same constrainer, a plain SAT solver, a few-shot DPLL-prompt baseline, and a grammar-only control.
  4. Token efficiency is confounded. The constrained model emits a solver-designed trace, while the baseline is free-form zero-shot thinking.
  5. Equivalence with ChopChop is not established. CDoT lacks shadowing. On TypeScript, CDoT compiles 61/74 against 48/74 for ChopChop (Table 5), which is unexplained, though the text says “behave similarly”. Spider gains are small (286 vs 275 of 1034, about 1 point) and ChopChop was not run there.
  6. Efficiency evidence has gaps.
  7. The hardware details are not stated.
  8. There is no preprocessing or per-puzzle compile time.
  9. There are no scaling curves in terminals, scopes or clauses, although nesting depth motivated the work.
  10. There is no end-to-end throughput.
  11. The H100 is only 25% faster than an RTX 3090, so “GPU acceleration” is weakly supported.
  12. SEM-CTRL is cited but not used in comparison.
  13. The manuscript looks unfinished. There are broken references (“??”), truncated sentences, and the AI-use statement is an unfilled template listing both used and unused activities.
Questions for authors
  1. What is the formal definition of the recognized language, and which class does it fall in?
  2. What solve rates and guess counts result from a random pivot under the constrainer?
  3. Why do CDoT and ChopChop differ on TypeScript?
  4. What are the compile and preprocessing costs, and how does latency scale with sequence length?
  5. How are non-terminating or expensive deontic functions prevented?
2 comments
  1. What is the formal definition of the recognized language, and which class does it fall in?

Formal semantics is now provided in Appendix I (page 31) We added Appendix J (page 34). Where we compare CDoT against CFG, Turing transducer, and LCFRS/MCFG. We further discuss nuances regarding lexer behavior and constrained decoding.

  1. What solve rates and guess counts result from a random pivot under the constrainer?

Random guessing achieves approximately half the solve rate of constrained LLMs. We further experimented with few-shot DPLL prompting, but it performed poorly, producing incorrect guesses in most cases.

We also compared constrained LLMs against MiniSat using the number of conflicts before finding a solution as a proxy for search effort. The results show that constrained LLMs make faster progress within the first four guesses but tend to stall afterward.

We regenerated the puzzles with more characters and greater freedom of choice. In the original dataset, unit propagation determines nearly all remaining character roles once the role of a single character is assigned, leaving little room for model-driven reasoning.

Section 5 has been substantially rewritten to reflect these changes and additional experiments.

  1. Why do CDoT and ChopChop differ on TypeScript?

It was caused by time outs on TypeScript experiments. With time out removed, we observed steps over 2 min per token.

  1. What are the compile and preprocessing costs, and how does latency scale with sequence length?

The average initialization time ranges from 438 ms to 1,134 ms per fresh grammar, depending on the dataset (updated Table 2, page 9). This is roughly comparable to the time required for an LLM to prefill a prompt.

We now measure and report latency scaling with sequence length in Figure 5. The empirical per-step latency scales approximately linearly with sequence length, consistent with the scaling of self-attention during autoregressive decoding. To evaluate longer sequences, we constructed extended sequences by repeating the e-graph and TypeScript workloads, reaching up to 8K grammar terminal instances.

  1. How are non-terminating or expensive deontic functions prevented?

Constraint authors could indeed choose to write non-terminating or expensive functions, though of course they would then incur the costs of doing so. Looking from the perspective of an inference provider, it would be inadvisable to incorporate deontic functions from untrusted third parties. If truly necessary, standard security practices should be applied, such as isolated execution with timeouts of untrusted deontic functions, with CDoT falling back to purely context-free constraints when untrusted code fails. That said, a nice aspect of CDoT's design is that deontic functions ARE separated from the rest of inference, and could be sandboxed as described, unlike in prior work where constraints are not easily disentangled from the rest of inference.

Ideally, deontic functions should be simple primitives provided and certified by the inference provider, while more sophisticated behavior is achieved by composing these primitives through CDoT's deontic semantics (necessary and permitted sets) and context-free grammar rules.

Indeed, all deontic functions used in our paper can be characterized as generic pass-through operations or table lookups. These could be efficiently implemented as lightweight on-GPU operations, eliminating the expensive data conversion and transfer pipeline in our current implementation: GPU token IDs → CPU token IDs → strings → opaque deontic functions → sets of regular expressions → CPU finite-state machines → GPU finite states. We nevertheless implement and measure deontic functions as opaque in this initial study to preserve flexibility for future applications, such as querying external APIs, databases, or ontologies.

Additionally, because deontic functions depend only on small, localized text segments (individual terminal instances), their results can be readily cached and reused.

Furthermore, because deontic functions only affect terminals rather than nonterminals, their results are not needed until the parser determines that the corresponding terminal type is eligible for generation. This may occur several LLM decoding steps after the function becomes invocable, providing opportunities to execute expensive functions asynchronously without necessarily adding to per-token latency. This is a case-dependent optimization, thus not included in our study.

In summary, CDoT separates deontic computation from the core constrainer and encourages the use of simple, composable primitives. This modular design enables implementation-specific optimizations. Exploring these optimizations in depth is beyond the scope of this initial study, but the framework is designed to accommodate them.

In regard to your other concerns

No formal semantics.

Added as appendix I (page 31)

Union-♢ is not sound in general. ... so the guarantee does not cover the experiments.

It was explained under the third paragraph of "soundness", that variable scoping style problem satisfies the soundness assumption.

Token efficiency is confounded. The constrained model emits a solver-designed trace, while the baseline is free-form zero-shot thinking.

We have removed the claim in the rewritten section

The hardware details are not stated.

Clarified in section 5.2.1.

There is no preprocessing or per-puzzle compile time.

Added in the updated table 2.

There are no scaling curves in terminals, scopes or clauses, although nesting depth motivated the work.

Added as Figure 5.

The H100 is only 25% faster than an RTX 3090, so “GPU acceleration” is weakly supported.

We have only utilized the core CUDA functionalities in our implementation. Nvidia chips requires specialized implementation depends on architecture, for example, the matrix multiplication algorithm is different for each generation.

SEM-CTRL is cited but not used in comparison.

SEM-CTRL is focused on sampling technique. It does not provide a formalism to compare against.

The manuscript looks unfinished. There are broken references (“??”), truncated sentences, and the AI-use statement is an unfilled template listing both used and unused activities.

We have corrected the editorial errors. Thank you for pointing them out. AI-use statement was filled correctly.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.