ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning
This addresses the scalability of LLM reasoning for AI researchers, highlighting fundamental limitations in complex non-monotonic reasoning, though it is incremental as it builds on existing evaluation methods.
The paper tackles the problem of logical reasoning capabilities in large language models (LLMs) by introducing ZebraLogic, an evaluation framework for logic grid puzzles, and finds a significant decline in accuracy as complexity grows, termed the curse of complexity, with models like Llama and o1 showing limitations even with larger sizes or increased computation.
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.