title: ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning
summary: We investigate the logical reasoning capabilities of large language models
  (LLMs) and their scalability in complex non-monotonic reasoning. To this end,
  we introduce ZebraLogic, a comprehensive evaluation framework for assessing LLM
  reasoning performance on logic grid puzzles derived from constraint
  satisfaction problems (CSPs). ZebraLogic enables the generation of puzzles with
  controllable and quantifiable complexity, facilitating a systematic study of
  the scaling limits of models such as Llama, o1 models, and DeepSeek-R1. By
  encompassing a broad range of search space complexities and diverse logical
  constraints, ZebraLogic provides a structured environment to evaluate reasoning
  under increasing difficulty.
    Our results reveal a significant decline in accuracy as problem complexity
  grows -- a phenomenon we term the curse of complexity. This limitation persists
  even with larger models and increased inference-time computation, suggesting
  inherent constraints in current LLM reasoning capabilities. Additionally, we
  explore strategies to enhance logical reasoning, including Best-of-N sampling,
  backtracking mechanisms, and self-verification prompts. Our findings offer
  critical insights into the scalability of LLM reasoning, highlight fundamental
  limitations, and outline potential directions for improvement.
paper_authors._id: 67a1a649f4aecd0dfc96ebf4
paper_authors.name: Bill Yuchen Lin
paper_authors.status: claimed_verified
paper_authors.statusLastChangedAt: 2025-02-04T09:39:17.972Z
paper_authors._id: 607f666a4ad99100d63ce35c
paper_authors.avatarUrl: https://cdn-avatars.huggingface.co/v1/production/uploads/607f666a4ad99100d63ce35c/QxhxnvfeV6efkxwUFHwjI.png
paper_authors.fullname: Bill Yuchen Lin
paper_authors.type: user
paper_authors.user: yuchenlin
paper_authors._id: 67a1a649f4aecd0dfc96ebf5
paper_authors.name: Ronan Le Bras
paper_authors.status: extracted_pending
paper_authors.statusLastChangedAt: 2025-02-04T05:31:56.722Z
paper_authors._id: 635049104e753c9940fefd71
paper_authors.avatarUrl: https://cdn-avatars.huggingface.co/v1/production/uploads/635049104e753c9940fefd71/HgR43XIFw3dneY5ufrAE8.jpeg
paper_authors.fullname: Ronan Le Bras
paper_authors.type: user
paper_authors.user: ronanlb
paper_authors._id: 67a1a649f4aecd0dfc96ebf6
paper_authors.name: Kyle Richardson
paper_authors.status: claimed_verified
paper_authors.statusLastChangedAt: 2025-02-27T09:18:11.166Z
paper_authors._id: 659c6f5e1d398a238152227d
paper_authors.avatarUrl: /avatars/dba97fe8cb825102f1eae97104a71f64.svg
paper_authors.fullname: Kyle Richardson
paper_authors.type: user
paper_authors.user: yakazimir
paper_authors._id: 67a1a649f4aecd0dfc96ebf7
paper_authors.name: Ashish Sabharwal
paper_authors._id: 67a1a649f4aecd0dfc96ebf8
paper_authors.name: Radha Poovendran
paper_authors._id: 67a1a649f4aecd0dfc96ebf9
paper_authors.name: Peter Clark
paper_authors.status: admin_assigned
paper_authors.statusLastChangedAt: 2025-02-04T17:38:40.973Z
paper_authors._id: 64d265cfbe712cda5ab7cc3f
paper_authors.avatarUrl: /avatars/caab6fa5764a0271552ae589d352b592.svg
paper_authors.fullname: Peter Clarke
paper_authors.type: user
paper_authors.user: PeterClarke
paper_authors._id: 67a1a649f4aecd0dfc96ebfa
paper_authors.name: Yejin Choi
paper_authors.status: admin_assigned
paper_authors.statusLastChangedAt: 2025-02-04T17:38:53.950Z
paper_authors._id: 64d42729f63b01b7f676b176
paper_authors.avatarUrl: /avatars/52e54bdd6a1fb6c774a40cd70f3d7925.svg
paper_authors.fullname: Yejin Choi
paper_authors.type: user
paper_authors.user: yejinchoinka
paper_title: ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning
paper_summary: We investigate the logical reasoning capabilities of large language models
  (LLMs) and their scalability in complex non-monotonic reasoning. To this end,
  we introduce ZebraLogic, a comprehensive evaluation framework for assessing LLM
  reasoning performance on logic grid puzzles derived from constraint
  satisfaction problems (CSPs). ZebraLogic enables the generation of puzzles with
  controllable and quantifiable complexity, facilitating a systematic study of
  the scaling limits of models such as Llama, o1 models, and DeepSeek-R1. By
  encompassing a broad range of search space complexities and diverse logical
  constraints, ZebraLogic provides a structured environment to evaluate reasoning
  under increasing difficulty.
    Our results reveal a significant decline in accuracy as problem complexity
  grows -- a phenomenon we term the curse of complexity. This limitation persists
  even with larger models and increased inference-time computation, suggesting
  inherent constraints in current LLM reasoning capabilities. Additionally, we
  explore strategies to enhance logical reasoning, including Best-of-N sampling,
  backtracking mechanisms, and self-verification prompts. Our findings offer
  critical insights into the scalability of LLM reasoning, highlight fundamental
  limitations, and outline potential directions for improvement.
paper_ai_summary: LLMs exhibit decreased accuracy in complex non-monotonic reasoning, as demonstrated through the ZebraLogic framework assessing logic grid puzzles.
paper_ai_keywords: large language models (LLMs) non-monotonic reasoning ZebraLogic evaluation framework logic grid puzzles constraint satisfaction problems (CSPs) logical reasoning Best-of-N sampling backtracking mechanisms self-verification prompts