CRANE: Reasoning with constrained LLM generation

Dear reviewer 6Prs,

Thanks for your constructive feedback.

Q1. In CRANE, these two are freely interleaved with multiple constrained decoding parts. Do the results in Proposition 3.3 generalize naturally to this case? Is it always true that the final answer is at the end?

R1: Proposition 3.3 shows that an ideal LLM (i.e., with a perfect set of parameters) can use constrained decoding with the augmented grammar $G_a$ (without any unconstrained steps) to simulate the steps of a given Turing machine and produce the final output only at the end. This result also naturally extends to CRANE, which interleaves unconstrained and constrained generation using $G' \to S_1GS_2$, where $G$ is the output grammar and $S_1, S_2$ are delimiters. The only modification needed in the proof is to configure the ideal LLM from Proposition 3.3 to wrap the final output in delimiters $S_1$ and $S_2$. In this case, the ideal LLM with CRANE can simulate the Turing machine’s steps and write the answer at the end. We will include a formal proof in the revised version of the paper.

Practical LLMs may not have the specific set of parameters for the theoretical construction as in the ideal LLM and may not strictly follow this ideal format, where the output is generated only at the end. Instead, they may generate multiple strings that are parsable within the grammar (e.g., syntactically valid mathematical expressions). In such cases, following the common practice for CoT [1,2,3], for both CRANE and unconstrained reasoning, we greedily select the last parsable string to compute the functional accuracy. It is possible that the final answer is not generated at the end, and better selection algorithms could further improve the functional accuracy of CRANE. However, we leave this for future work.

Nevertheless, our experiments demonstrate that CRANE, even with this simple selection strategy, outperforms direct final answer generation (whether in constrained or unconstrained modes) and unconstrained reasoning.

[1] "Large Language Models are Zero-Shot Reasoner", Advances in Neural Information Processing Systems 35 (NeurIPS 2022)
[2] "GSM-Symbolic: Understanding the Limitations of Mathematical Reasoning in Large Language Models", The Thirteenth International Conference on Learning Representations (ICLR 2025)
[3] https://huggingface.co/datasets/apple/GSM-Symbolic#answer-extraction-heuristic

Q2. Doesn't the grammar of the constrained generation also need to be modified to include the delimiters, like in C.5.1?

R2: The constrained decoding algorithm must be initialized with the augmented grammar that includes the delimiter symbols. We mentioned this in the pseudocode (Algorithm 1, lines 3 and 4). The grammars in C.5.1 also include the delimiter symbols. For example, line 916 of the GSM-Symbolic grammar includes << and >>. We will update the paper to clarify this detail.

Q3. Typos and writing suggestions.

R3: Thanks for pointing this out. We will fix them in revised version of the paper.

Dear reviewer jTKi,

Thanks for your constructive feedback.

Q1. The paper provides a theoretical explanation of why COT is essential for LLMs across various tasks. However, COT has recently become a widely adopted technique. The proposed method integrates CoT with output constraints and thus has limited novelty.

R1: Although Chain-of-Thought (CoT) is a popular technique, to the best of our knowledge, we are the first to formally show that constrained decoding with restrictive grammars can limit the ability of large language models (LLMs) to perform CoT. This, for the first time, provides a theoretical justification for earlier empirical evidence [1] showing that the functional accuracy of LLMs for certain tasks decreases under constrained decoding. More importantly, we show that the lack of expressive power arises only when the output grammar is overly restrictive, and this limitation can be easily mitigated by augmenting the output grammar with additional production rules for any given task. This insight leads to our proposed adaptive decoding algorithm, CRANE, which improves performance over both baseline constrained and unconstrained decoding methods.

Our primary contribution is not just the combination of CoT with constrained decoding but:

1. Identifying and formally establishing the potential limitations of constrained decoding with restrictive grammars for any LLM, including more advanced models developed in the future.
2. Providing both -- a theoretical augmented grammar construction for any task (Turing Machine) and a simple, practical algorithm—CRANE—that simultaneously preserves reasoning capabilities and reduces structural errors (syntax and semantic errors) in generated outputs, thereby enhancing overall LLM performance.

[1] "Let Me Speak Freely? A Study on the Impact of Format Restrictions on Performance of Large Language Models", Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing: Industry Track.

Dear reviewer ssfH,

Thanks for the constructive feedback. We have included additional experiments with different delimiters and larger and newer reasoning models. All experiments below use the same setup as Section 5. In all cases, CRANE consistently outperformed the baselines. We will add these results in the revised version.

Q1. Experiments with different delimiters.

R1: We use << and >> as the delimeter for GSM-Symbolic following the original paper (see Figure 1) [1]. We will make this detail more clear in the revised version of the paper.

Furthermore, to highlight CRANE's effectiveness across different delimeters, we have performed an ablation study on the GSM-symbolic dataset. We use ## ## and !! !! in place of << >> and report comparison against unconstrained CoT, which always performed the best among all three baselines.

Q2. Experiments with larger and advanced reasoning models.

R2: We add experiments for newly released reasoning and larger models on GSM-symbolic. CRANE consistently outperforms the baselines on all models.

Q3. Advances in Reasoning Models and Grammar-Constrained Generation

R3: CRANE's effectiveness is maintained with the latest reasoning models. Larger, more advanced reasoning models are still susceptible to syntactic and semantic errors. Additionally, when recent reasoning models generate lengthy reasoning traces, enforcing output constraints from the start—as done in baseline constrained decoding algorithms—significantly degrades LLM performance. CRANE addresses both of these challenges by dynamically enforcing constraints. Notably, with DeepSeek-R1-Distill-LLaMA-8B, CRANE achieves the highest performance gains, improving by 10% points. Therefore, for future reasoning models that generate reasoning traces and require final results to provably satisfy structural constraints, CRANE remains a valuable tool.

Q4. Finite Grammars.

R4: Both the gsm-symbolic and FOLIO grammars permit infinite strings. The experiments demonstrate that CRANE significantly enhances the performance of practical LLMs, even when the output grammar allows infinite strings. Finite output grammars $G$ are just a special case used to theoretically establish the negative result, highlighting the limitations of constrained decoding when using highly restrictive grammars for any constant-layer LLM. Overall, CRANE remains a valuable framework for improving the performance of practical LLMs, even with infinite output grammars.

On the other hand, Proposition 3.3 already provides a positive result for the ideal setting. It shows that an ideal LLM (with perfect parameter values) can always simulate any Turing machine using constrained decoding alone. This is possible when the output grammar $G$ is augmented with additional rules, as done in $G_a$. However, the currently available LLMs may not possess the perfect set of parameters.

Q5. Typos.

R5: Thanks for pointing this out. We will fix them in the revised version.

[1] "GSM-Symbolic: Understanding the Limitations of Mathematical Reasoning in Large Language Models", ICLR, 2025.