Grammar-Constrained Decoding Makes Large Language Models Better Logical Parsers

Large Language Models (LLMs) have shown capabilities in various natural language processing tasks, yet they often struggle with logical reasoning, particularly when dealing with complex natural language statements. To address this challenge, approaches that combine LLMs with symbolic reasoners have been proposed, where the LLM translates the natural language statements into symbolic representations, which are then verified by an external symbolic solver. However, ensuring syntactic correctness in these translations remains a significant challenge. To address this, we propose to constrain the outputs of the LLMs using Grammar Constrained Decoding (GCD), showing that it consistently improves both syntactic correctness and accuracy in logical parsing tasks. Our findings demonstrate that grammar constraints can complement in-context examples, especially beneficial for resourceconstrained applications using smaller models. However, we observe that while GCD ensures syntactic validity, semantic errors not captured by Context-Free Grammars continue to pose challenges. Additionally, our results reveal a trade-off for larger models where unconstrained generation occasionally outperforms constrained decoding, aligning with recent theoretical work on bias introduced by constrained decoding. Our code and data is publicly available at: https://github.com/ federaspa/gcd-llm-logical-parsing