- 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
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.
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 (KNK) to (e-graph) faster on p50, and (KNK) to (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
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.
It is now provided in appendix I (page 31).
The worst case time per decoding step is O(n2(∣R∣+∣D∣)+n(∣Vnt∣2+∣D∣ρ)+∣D∣f) Here n is the number of terminal instances committed so far, R is the set of binary productions and Vnt the set of nonterminals of the grammar in Chomsky normal form, D is the set of anchors (the deontic rules attached to productions), ρ 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 f 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) 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)) 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]).
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.