title: CRANE: Reasoning with constrained LLM generation
summary: Code generation, symbolic math reasoning, and other tasks require LLMs to
  produce outputs that are both syntactically and semantically correct.
  Constrained LLM generation is a promising direction to enforce adherence to
  formal grammar, but prior works have empirically observed that strict
  enforcement of formal constraints often diminishes the reasoning capabilities
  of LLMs. In this work, we first provide a theoretical explanation for why
  constraining LLM outputs to very restrictive grammars that only allow
  syntactically valid final answers reduces the reasoning capabilities of the
  model. Second, we demonstrate that by augmenting the output grammar with
  carefully designed additional rules, it is always possible to preserve the
  reasoning capabilities of the LLM while ensuring syntactic and semantic
  correctness in its outputs. Building on these theoretical insights, we propose
  a reasoning-augmented constrained decoding algorithm, CRANE, which effectively
  balances the correctness of constrained generation with the flexibility of
  unconstrained generation. Experiments on multiple open-source LLMs and
  benchmarks show that CRANE significantly outperforms both state-of-the-art
  constrained decoding strategies and standard unconstrained decoding, showing up
  to 10% points accuracy improvement over baselines on challenging symbolic
  reasoning benchmarks GSM-symbolic and FOLIO.
paper_authors._id: 67b401de3995f28d45c212d6
paper_authors.name: Debangshu Banerjee
paper_authors.status: admin_assigned
paper_authors.statusLastChangedAt: 2025-02-19T15:24:10.076Z
paper_authors._id: 675f9306e0b5cb5bc241e8cc
paper_authors.avatarUrl: /avatars/566385d2049b353ea38ddbb9f9105dd0.svg
paper_authors.fullname: Debangshu Banerjee
paper_authors.type: user
paper_authors.user: debangshubanerjee
paper_authors._id: 67b401de3995f28d45c212d7
paper_authors.name: Tarun Suresh
paper_authors.status: admin_assigned
paper_authors.statusLastChangedAt: 2025-02-19T15:24:17.773Z
paper_authors._id: 65e7bb35e5e78134ab049942
paper_authors.avatarUrl: /avatars/3c0972f0d59e51ebb5c218ee736d4458.svg
paper_authors.fullname: Tarun Suresh
paper_authors.type: user
paper_authors.user: tarsur909
paper_authors._id: 67b401de3995f28d45c212d8
paper_authors.name: Shubham Ugare
paper_authors.status: admin_assigned
paper_authors.statusLastChangedAt: 2025-02-19T15:24:24.384Z
paper_authors._id: 656c29ed271c5c4e3308a008
paper_authors.avatarUrl: /avatars/9b58072230baf3ac941d476d69356fda.svg
paper_authors.fullname: Shubham Ugare
paper_authors.type: user
paper_authors.user: shubhamugare
paper_authors._id: 67b401de3995f28d45c212d9
paper_authors.name: Sasa Misailovic
paper_authors._id: 67b401de3995f28d45c212da
paper_authors.name: Gagandeep Singh
paper_title: CRANE: Reasoning with constrained LLM generation
paper_summary: Code generation, symbolic math reasoning, and other tasks require LLMs to
  produce outputs that are both syntactically and semantically correct.
  Constrained LLM generation is a promising direction to enforce adherence to
  formal grammar, but prior works have empirically observed that strict
  enforcement of formal constraints often diminishes the reasoning capabilities
  of LLMs. In this work, we first provide a theoretical explanation for why
  constraining LLM outputs to very restrictive grammars that only allow
  syntactically valid final answers reduces the reasoning capabilities of the
  model. Second, we demonstrate that by augmenting the output grammar with
  carefully designed additional rules, it is always possible to preserve the
  reasoning capabilities of the LLM while ensuring syntactic and semantic
  correctness in its outputs. Building on these theoretical insights, we propose
  a reasoning-augmented constrained decoding algorithm, CRANE, which effectively
  balances the correctness of constrained generation with the flexibility of
  unconstrained generation. Experiments on multiple open-source LLMs and
  benchmarks show that CRANE significantly outperforms both state-of-the-art
  constrained decoding strategies and standard unconstrained decoding, showing up
  to 10% points accuracy improvement over baselines on challenging symbolic
  reasoning benchmarks GSM-symbolic and FOLIO.
paper_ai_summary: A reasoning-augmented constrained decoding algorithm balances syntactic and semantic correctness in LLM outputs without reducing their reasoning capabilities.
paper_ai_keywords: LLMs constrained generation formal grammar reasoning capabilities constrained decoding CRANE symbolic reasoning GSM-symbolic FOLIO