ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning
Authors: Bill Yuchen Lin
Ronan Le Bras
Kyle Richardson
Ashish Sabharwal
Radha Poovendran
Peter Clark
Yejin Choi
Venue: ICML 2025 poster (2025)
Keywords: LLM
Reasoning
Scaling
Primary area: deep_learning->large_language_models

Abstract: We investigate the logical reasoning capabilities of Large Language Models (LLMs) and their scalability across complex deductive tasks. Using ZebraLogic, a newly developed benchmark dataset of logic grid puzzles derived from constraint satisfaction problems (CSPs), we systematically evaluate LLM performance. ZebraLogic spans a broad range of search space complexities and incorporates diverse logical constraints, providing a controlled environment to assess reasoning abilities. Our results reveal a significant decline in accuracy as problem complexity increases—a phenomenon we term the “curse of complexity.” Notably, this limitation persists even with scaling model size and inference-time computation, suggesting fundamental constraints in current LLM reasoning capabilities. Additionally, we explore strategies such as Best-of-N sampling, backtracking mechanisms, and self-verification prompts to enhance logical reasoning performance. Our findings provide critical insights into the scaling behavior of LLMs, highlight their limitations, and outline potential directions for advancing their reasoning capabilities.

ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning
Bill Yuchen Lin
Ronan Le Bras
Kyle Richardson 2
Ashish Sabharwal 2
Radha Poovendran
Peter Clark?
Yejin Choi
'University of Washington
Allen Institute for AI
Stanford University
byuchen@uw.c edu ht co/ spaces /Wildva
romanlb@allensi.
yejinc@stanford..et
Abstract
1. Introduction
Logical reasoning stands as a cornerstone of human intel- ligence and remains a central challenge AI. While re- cent advances have demonstrated promise in tasks requiring common sense and general knowledge (Brown et al., 2020; Chowdhery et al., 2022; Bubeck et al., 2023), the capabili- ties of Large Language Models (LLMs) in handling complex deductive problems remain uncertain. This limitation in our understanding is especially critical as systematic reasoning underpins many real-world applications. To systematically study LLMs' logical reasoning capabilities and their scal- ing limits, ideal evaluation framework must: (1) isolate
We investigate the logical reasoning capabilities of large language models (LLMs) and their seal- ability in complex non-monotonic reasoning. To this end, we introduce ZebraLogic, comprehen- sive evaluation framework for assessing LLM rea- soning performance logic grid puzzles derived from constraint satisfaction problems (CSPs), Ze- braLogic enables the generation of puzzles with controllable and quantifiable complexity, facili- tating a systematic study of the scaling limits of models such as Llama, ol models, and DeepSeek- RI. By encompassing broad range of search space complexities and diverse logical constraints, ZebraLogic provides structured environment to evaluate reasoning under increasing difficulty. Our results reveal 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 fun- damental limitations, and outine potential direc- tions for improvement.
pure logical reasoning from domain knowledge; (2) enable precise control over problem complexity; (3) minimize data leakage to prevent training data memorization; (4) provide objective metrics for assessing an LLM's reasoning results.
Constraint satisfaction problems (CSPs) offer such con- trolled framework (Dechter, 2003): they are mathematically well-defined, scalable in both complexity and search space, and have solutions that can be automatically verified. By for- mulating logical tasks as CSPs, we can rigorously evaluate how well LLMs adhere to logical constraints, independent of domain -spciffc data or heavy numerical computation. As a representative class of CSPs, logic grid puzzles (specif- ically Zebra Puzzles or Einstein's Riddle, (Prosser, 1993)) are particularly suitable as they require pure formal rea- soning, remain accessible enough serve as effective testbed, and embody core skills relevant to real-world ap- plications such as task planning, scheduling, and resource allocation. Hence, we introduce Zebral.ogic, an evaluation framework for creating logic puzzles with controllable, and quantifiable complexity, thus improving our understanding the scaling limits of L.MMs including Llama (AI @ Meta, 2024), ol (OpenAI, 2024) and R1 (DeepSeek-AI, 2025).
University of Washington Allen Institute for AI Sttanford University. Correspondence to: Bill Yuchen Lin @byuchen@uw.cdee
Through extensive evaluation of various LLMs across di-
'The closest related effort is by Tyagi al. (2024), who focused on detailed analysis of the kinds errors LLMs make when solving grid puzzles using reasoning chains; more details in $7.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

ZebraLogic:: On the Scaling Limits of LLMs for Logical Reasoning
Scaling Model Size
Scaling CoT Tokens
Scaling Sample Size
100
100
100
Model
Model
Model
Liama-3.2 3.2-3B 0etee33.------rruee -a-sinstucct
apt-4o-mini (pass@11
80
80
deepseek-r1
80
gpt 4o minl (pass@4)
Liama-3.1 1.1-770--nnsrree
ol-preview
gpt-4o-mini (pass@0)
Accuracy (%)
Llamne 1airaa-.1-405B--nsttte
ol-mini
gpt-4o-mini (pass@16)
60
Q11
gpt-4o
60
gpt-4o-mini (pass@32)
4058
gpt-4o-mini
gpt-4o-mini (pess@64)
R1
gpt-4o-mini (pass@
40
70B
40
40
01-mini (pass@11
The curse of complexity!
BB
20
3B
20
provlow
G1-
20
O1-mini
01
Z3 conflicts
0-
10
20
30
40
0
20
40
60
80
20
40
60
80
Figure 1: Accuracy vs number of Z3 conflicts for Llama-3 (left), showing the size scaling effect on the reasoning performance. The middle figure shows the curves for gpt-4o(-mini) vs ol and R1, showing the scaling effect of model size and test-time compute. The right figure shows the scaling effect of repeated sampling by pass @k k metric with different sample sizes.
verse architectures and sizes, we observe a dramatic de- cline in performance as puzzle complexity increases-a phenomenon we term the "curse of complexity for reason- ing." Most models struggle once the puzzle's search space exceeds 10" possibilities (e.g., for puzzles with 4x5 grid size) or when the number of logical conflicts in widely used SMT solver named Z3 (de Moura & Bjørner, 2008) surpasses 20. These findings suggest that limited reason-
cannot be resolved by model scaling alone ($3 and $4). We scale the test-time compute of LLMs by increasing the number of generation samples, revealing that it has both promise and challenges. While Best-of-N sampling can improve potential performance, practical selection meth- ods like majority voting or reward models show limited improvement. Additionally, even pass @ 128 cannot break the curse of complexity (65).
ing in current LLMs are not solely a matter of model- or sample-size scaling, but also arise from insufficient test-time compute. This shortfall underscores the need to train LLMs to reason step by step (Wei et al., 2022) explicitly (e.g., via reinforcement learning (Lambert et al., 2024a)), as exem- plified by emerging reasoning models such as ol and R1. Specifically, we conduct systematic investigation into the scaling behavior of LLMs in logical reasoning, focusing on three key dimensions: model size ($4), sampling ($5), and test-time compute ($6). Understanding scaling behavior of LLMs in reasoning critical to identify the most promising directions for advancing LLMs' reasoning capabilities and to guide future research efforts more effectively.
We find that it's much more promising to scale up the reasoning tokens (i.e., cfain-of-thoughhs: CoT's) generated during inference with a backtracking mechanism. We take OpenAl's ol models as typical example and show that they generate significantly more, nearly 10x (hidden) reasoning tokens than others, which scale properly with problem complexity. Based on our empirical results, we also find that there exists an optimal ratio of reasoning tokens to 73 conflicts, but Ol-li models cannot always reach this optimal ratio when the complexity is extremely high, thus not achieving perfect reasoning ($6).
Moreover, we explore the potential of using self- verification prompting improve LLMs ($6.2). We find that such methods can help LLMs improve their perfor- mance, but the improvement is very marginal. We fur- ther analyze the reasoning process of ol and discuss its strengths and weakness in logical reasoning (SD).
Our work makes the following key contributions:
We create the ZebraLogic dataset, a benchmark of 1,000 logic grid puzzles spanning multiple complexity levels, designed to evaluate L.MMs logical reasoning capabilities systematically with two complexity metrics: search space size and Z3 conffict count ($2).
2. Problem Formulation of Logical Reasoning
We report "the curse of complexity" in logical reason- ing with LLMss the performance dramatically declines as the problem complexity increases and after a certain threshold, most models struggle to solve any logical puz- zle. This limitation persists even when scaling to signifi- cantly larger models (such as Llama-3.1 1 1-405B) or using enhanced training data, indicating deeper challenge that
Constraint Satisfaction Problems (CSPs) provide power- ful framework for modeling and solving logical reasoning tasks. In CSPs, solutions must satisfy a set of constraints over variables and their possible values. This framework is particularly valuable for evaluating systematic reason- ing capabilities, as it requires explicit handling of logical relationships and dependencies. We leverage this frame-
2

---

ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning
Clue + Clue
There are houses, numbered to from left to right, as seen from across the street. Each house occupied by a different person. Each house has a unique value for each of the following attributes:
Eric
milk
Each person has unique name: Eric, Peter, Arnold
?
Arnold
water
Each person has unique favorite drink: milk, water, tea
Uniqueness
Each person has unique hobby: photography, cooking, gardening
Background
Peter
tea
Clue
Clues
Solution
1,3
Eric
milk
1. Arnold is not in the first house.
Houses
Name
Drink
Hobby
cooking
2. The person who likes milk is Eric.
3. The photography enthusiast is nat in the first house.
Peter
tea
gardening
Eric
milk
4. The person who loves cooking is directly (eft of the person who likes milk,
proof by contradiction
2
Arnold
water
cooking
Clue
Arnold
5. The one who only drinks water Arnold.
Clue
3
photography
6. The person who likes milk is not in the second house.
3
Eric
milk
photography
Uniqueness
Solution
This example of ZebraLogic features 3 houses (N=3) and 3 attributes (M=3), with 6 clues (K=6). The Background outlines the attributes, their possible values, and the uniqueness constraints. The Clues provide additional constraints regarding the attributes. The task for the model is to determine the correct assignment of attributes to each house based on these clues, illustrated in the Solution grid.
Figure 2:
work through logic grid puzzles in our ZebraLogic dataset to assess L.LMs' deductive reasoning abilities.
example, for the attribute Name, we might have VNaam (Fric, Peter, Arnold) in puzzle with N = 3 houses. As illustrated in Fig. 2, other attributes might include Drink with values like milk, water, and tea, or Hobby with val- ues like photography, cooking, and gardening. To model the puzzle as a Constraint Satisfaction Problem, we define variables representing the assignment of values to attributes for each house.
2.1. Logic Grid Puzzles
Each puzzle in ZebraLogic consists of N houses (numbered 1 to N from left to right) and M different attributes for each house. There are N distinct values for each attribute, and each house must have a unique value for each attribute. Given a list of K clues, one must use logical deduction to determine the unique correct assignment of values. Figure illustrates an example of such a puzzle, as well as reason- ing chain for solving it. Importantly, while some ZebraLogic puzzles can be solved through straightforward linear deduc- tion, many require more complex non non-monotonic reasoning strategies, such as counterfactual reasoning that involves backtracking and revising assumptions. This is particularly true as the search space grows larger and the clues become more intricate key aspect of our study on the scaling behavior of L.Mss.
..... } be the set houses, |H| =N. Let H 31,2,3,....
Let = [Name, Drink,... be the set attributes, |AI = M. Define Fa, e Va for each attribute E A and house k E H.
Uniqueness Constraints: The constraints ensure that each value is assigned exactly once, as described in the Back- ground part in Figure 2. For each attribute, the set of as- signed values across all houses must exactly match the set of possible values. That is: {Io,k k E |H=-1
Clue-Basee Constraints: Each clue in the puzzle intro- duces additional constraints that must be satisfied by any valid assignment. Note that there are also several implicit positional constraints that must be considered. For example, the leftmott house cannot be on the right of any other house, and the rightmost house cannot be on the left of any other house (as relevant in Clue 4). These spatial constraints, combined with the explicit clues, translate the verbal de- scriptions into precise logical conditions to be satisfied.. Under the hood, these clues are translated into formal logic formulas that constrain the relationships between variables. For our example puzzle in Figure 2, the constraints can be formulated as follows:
2.2. Problem Formulation
We provide detailed mathematical formulation of logic grid puzzles as CSP. This formulation not only clarifies the underlying structure of the puzzles in ZebraLogic but also highlights how our study can be generalized to various reasoning problems. The example shown in Fig. 2 illustrates this formulation.
Background. Consider N houses numbered I to N. Each house has a different occupant with a set A of M unique attributes such as name, favorite drink, hobby, etc. Each attribute E A represents category of characteristics and takes values in set V4 of N possible values. For
3

---

ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning
Clue-based Constraints (Example in Figure?
Algorithm ZebraLogic Puzzle Generation.
Clue 1. "Aroold is not in the first house"; 1NName,1 of Arnold
Require: A set of possible attributes Aan and their value sets V. for each E Aall
Clue 2. "The person who likes milk is Eric": 'ik E H, (3xame.A = Eric) = (Zamak,k milk)
Require: Clue types
(cL.....c.) with templates T(c) for
each c C C
Clue 3. "The photography enthusiast is not in the first house": 21bobby.1 + photography
Require: Number of houses N, number of attributes M 1: Sample M attributes from A. to form A {aa...., d.s)
Clue 4. "The person who loves cooking is directly left of the person who likes milk": ; vk E HeN. (Tiuaby. cooking)
Initialize solution
Unea Va randomly I/ Initialize clue set
3: C' + ClueGenerationfs
= k=1 = milk)
4: while C' do
5:
p S=mppleclue(()
I/ Sample a clue to remove
Clue 5. "The one who only drinks water is Arnold": Vk E (#Drink.k = water)
C' C' {p}
H. (#Name, = Amold) b
7:
if [SSolltiioss C*) (=)==1 then
Clue 6. "The person who likes milk is in the second house" : 20iikk22 & milk
8:
C C²
// Remove until S is the unique solution
9:
break
10: end if
11:
end while
Task. The task is find assignment of attributes to houses via assigning values to variables Fa,kk that is consis- tent with all constraints. These constraints, defined above, include both the uniqueness requirements for attribute val- ues and the logical conditions derived from the specific clues provided. The result is guaranteed to be unique, and can be usually presented as a table as shown in Fig.
12: return (S, C)
I/ Return solution and minimal clue set
Task Generation Algorithm. Algo. I outlines our approach for generating ZebraLogic puzzles. The process starts by sampling M attributes from the full attribute set and creating an initial solution grid S through random value assignments. From this solution, we generate a comprehensive set of clues C that capture all valid relationships between values in the grid. The algorithm then employs an iterative minimization procedure at each step, it randomly samples clue p and attempts to remove it. Using SAT solver, it verifies whether the reduced clue set C' = C \ {p) still uniquely determines the original solution S. If uniqueness is pre- served, is permanently removed and the process continues. This iteration terminates when no any additional clue can be removed without augmenting the solution space.
2.3. ZobraLogic Dataset Creation
To create puzzles, we first define a set of attributes and their corresponding value sets. We also establish some clue types, each with its own language templates containing placeholders for values.
Attributes and Values. We construct the attribute set A, which includes the many elements (see Appendix B). Each attribute is associated with a minimum of 6 possible values, ensuring a rich and diverse set of puzzles. Importantly, we always include the Name attribute in our samples, as it serves crucial element in the puzzle-solving process.
We employ weighted sampling during clue selection, assign- ing higher probabilities simpler clue types (e.g.. FOUN- DAT-type clues are more likely to be sampled than NOTAT) to balance puzzle complexity, such that we can efficiently reduce the clue set while maintaining the difficulty of the puzzles. The result is a minimal set of clues that, when combined with the background information about the at- tributes and their possible values, forms logically sound puzzle with single, unique solution. This approach sures that each generated puzzle is both solvable and chal- lenging, requiring a combination of logical deduction and non-monotonic reasoning strategies to solve. Finally, we use predefined one-shot prompting templates to format the puzzle and instruct the LLMS to generate their reasoning steps and final results in JSON format (see Appendix D.
The possible clue types are categorized into several types, including FOUNDAT, SAMEHoUSE, NOTAT, DIRECTLAAT/RIGHT, SIDE LEFT/RIGHTOF, and ONE/TWOBETWEEN. Each clue type captures a specific relationship between variables, providing a diverse set of constraints for the puzzles. More details are in Appendix B.
Clue Types.
Clue Types and Illustrative Examples.
FOUNDAT: The tea drinker lives House
SAMEHOUSE: The musician drinks tea.
NOTAT:
The musician does not drink tea (not the same house).
DIRECTLEFT/RIGHTT The greenhouse directly the left/right of the white house.
Dataset Statistics. The dataset consists of 1,000 puzzles where the size of the search space varies significantly. The puzzles are based on N x M grids where N, M E {,.... 6} (i.e., 25 sizes in total, with 40 puzzles per size), covering a wide range of complexity. The average and median number of clues per instance is 10.4 and 9, respectively.
SIDEBYSIDE: The coffee drinker and the tea drinker are next to each other.
LEFT/RIGHTOF: A is somewhere to the left/right of B. ONE/TWOBETWEEN 1/2 houses are between A & B.
4

---

ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning
2.4. Theoretical Problem Complexity
Together, these metrics offer a complementary view of how the difficulty of the puzzles scales with the problem size. Appendix B provides additional details on how these two metrics vary as function of the puzzle parameters (N, M).
By reduction from the Quasigroup (or Latin square) Com- pletion Problem (QCP) (Colbourn, 1984; Gomes& & Shmoys, 2002), the ZebraLogic problem is proven to be NP-complete (Sempolinski, 2009). While the problem definition includes a rich set of clue types that can be further expanded, suffi- cient condition for the NP-completeness result is to at least include the FOUNDAT and NOTAT clue types, As a result, while a solution a ZebraLogic puzzle can be easily ver- ified, solving Zebral Logic puzzles for large instances may become intractable within reasonable time frames using cur- rent computational methods. This implies that, for a fixed LLM size, the required number of reasoning tokens may increase exponentially with the size of the puzzle.
3. Evaluation
Setup and Metrics. Our evaluation is done in one-shot in-context learning setting, where we provide the models with a single example of how to solve a ZebraLogic puzzle and present the solution in JSON format, and we instruct the LLMs to output their reasoning and solution in the same format, thus making it easier to parse and evaluate their an- swers. We mainly look at the puzzle-level accuracy, mean- ing that only when all cells in the grid are filled correctly, the model is considered to have solved the puzzle. In addition to that, also report the cell-level accuracy.
2.5. Measuring Effective Instance Complexity
Search space size. We define the solution space of a Ze- bral.ggic puzzle as the total number of possible configu- rations that can satisfy the uniqueness constraints of the puzzle. That is, a N M grid has a solution space of (N!) where N is the number of houses and M is the number of attributes. The complexity of the search space increases factorially with the size of the grid, leading to a combinatorial explosion in the number of possible con- figurations? To better group the puzzles based on their complexity, we categorize them into four groups based on the size of the search space |
Evaluated models. We evaluate both open- geen-weight LLMs (e.g., Llama and Qwen) and proprictary LLM APIs includ- ing GPT-4o, O1 and Claude models. All evaluated models are prompted in the same way (see Appendix D.1), and we use the same greedy decoding and prompts and parsing script across all models to ensure a fair comparison, except for OI, which does not only greedy decoding we run it three times and take the best result.
3.1. Main results
Table shows the performance of various models. ol out- performs all other models, achieving an overall accuracy of 81.0%, and DeepSeck-R1, an open-weight reasoning LLM achieves 78.7%, with a slightly better performance on Small and Medium- size puzzles than ofllll.. However, Rl's performance on Large and X-Large puzzles is worse than ol- full. ol ol-preview and ol m1mmi achieve 71.4% and 59.7% ac- curacy, respectively. In contrast, the best-performing open- weight non-reasoning LLM, Sonnet-3.5-1022, only reaches 36.2%. The performance gap is even more pronounced in larger search spaces, where O1-Preview maintains a 17.0% accuracy in the X-Large category, while other models strug- gle to achieve any correct solutions.
Small ([S) < 10"): 2x2, 2x3, 2x4, 2x5, 2x66, 3x2, 3x3, 4x2
Medium (10* [8] < 10 i 3x4, 3x5, 3x6, 4x3, 40c4, 5w2, 6x2
Large (10" < [S] < 100 10 4x5, 5x3, 4x6, 5x4, 6x3
X-Large ([5) 2 10a0): 5x65, 6xx4, Sxci, 6sc5, 6x66
73 confticts. While search space size provides useful mea- sure of puzzle scale, is not the only indicator of complexity. To complement it, we also use the Z3 SMT solver's conflict metric. Z3 (de Moura& & Bjørner, 2008) uses the Conflict Driven Clause Learning (CDCL) algorithm, a backtracking Pai---uuna---mme-eee Loveland) algorithm. When solving a puzzle, Z3 records the number of conflicts encountered situations where the solver must backtrack due to contradictions in its current assignment. We run Z3 on each puzzle for 32 times and take the average number of conflicts as a measure of com- plexity. Puzzles with zero conflicts can typically be solved through simple forward chaining, whereas puzzles with more conflicts require extensive backtracking, indicating higher logical complexity.
approach based on the DPLL
We find that our ranking and scoring of these models are aligned with other reasoning benchmarks such as MATH (Hendrycks et al., 2021) for mathematical reasoning and LiveCodeBench (Jain et al., 2024) for competitive pro- gramming. This suggests that the logical reasoning ability of LLMs is highly correlated with their performance on other types of reasoning tasks.
While search space size captures the number of candidate assignments (given uniqueness constraints), Z3 conflicts quantify the solver's difficulty in reaching valid solution.
3.2. Curse of Complexity in Reasoning with LLMs
We observe that the performance of LLMs drops signifi- cantly as the search space size increases, as shown in Fig. 1 and Fig. 3 (in Appendix). We find that for models that are
For example, a 3x4 grid has solution space of (31)a 1296. while a 4x3 grid has a solution space of (4t)* = 13824.
5

---

ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning
Overall noc.
Small
Medium 10
Large 10
X-Large
Cell-Ievel
Model Names
10
10
10
10
Acc.
ol-full
81.0
97.2
92.1
78.0
42.5
78.7
DeepSeek-RI P
78.7
98.4
95.7
73.5
28.5
80.5
ol-preview
71.4
98.1
88.2
59.5
17.0
75.1
ol-mini
59.7
87.5
76.8
39.0
12.0
70.3
Claude Sonnet 3.5
36.2
84.7
28.9
4.0
1.0
54.3
Llama-3.1-405B
32.6
81.3
22.5
1.5
0.0
45.8
GPT-4o
31.7
80.0
50.3
Gemini-1.5-Pro
30.5
75.3
20.7
3.0
0.0
50.8
Mistral-Large-22
29.0
75.9
15.0
2.5
0.0
47.6
Qwen2.5-72BB,
26.6
72.5
12.1
40.9
Gemini-L.5-Flast
25.0
65.0
13.6
2.0
0.0
43.6
Llama-3.1-705
24.9
67.8
10.4
1.5
0.0
28.0
DeepSeck-v2.5
22.1
62.2
7.9
0.0
38.0
GPT-4o-mini
20.1
58.8
4.6
0.0
0.0
41.3
Gemma-2-27BB
16.3
46.6
5.0
0.0
0.0
41.2
Llama-3,1-81
12.8
39.4
0.7
0.0
0.0
13.7
Phi-3.5-4B
6.4
19.4
0.7
0.0
0.0
6.0
Table 1: Performance of LLMs on Logra The overall accuracy is calculated based on the number of puzzles solved correctly. We also report the accuracy on small, medium, large, and x-large groups based on the size of the search space (see Sec. 2.3). The cell accuracy indicates the percentage of individual cells filled correctly. See Appx. A for more model results.
overall worse than GPT-4o-mini can hardly solve puzzles beyond the Small category - less than 5% accuracy in Medium -ize puzzles and almost no correct solutions in Large and X-Larre puzzles. We can see that even the largest open-weight LLM, -Jama-3.1-40SB, only achieves 32.6% overall accuracy. Although 405B has 22.5% accuracy in Medium-size puzzles, it quickly also drops to 1.5% in the Large category and 0.0% in the X-Large category.
the sample size for repeated sampling.
4. Scaling Model Size Can Hardly Break the Curse of Complexity in Reasoning
The Curse of Complexity in Reasoning for non-reasoning LLMs. In addition to the search space size, we also use Z3-conflict as the complexity measure to study the scaling behavior LLMss. Fig. (left) highlights a key observation regarding the performance of various Llama models with different model sizes across increasing complexity in terms of how many Z3 conflicts average encountered when solving the ZebraLogic puzzles. A notable finding is that all model sizes experience rapid decline in accuracy as the complexity increases, illustrating the challenge posed by complex reasoning tasks. This trend emphasizes the inherent difficulty models face in maintaining high accuracy beyond certain threshold of search complexity, irrespective of their size. The phenomenon termed the "curse of complexity" becomes evident as even the largest models, such as the Llama-3. 1....-44BB,,, cannot sustain high accuracy once the search space surpasses a certain scale. As shown in Fig. 3, we see similar trend
The best non-reasoning LLM, Sonnet 3.5, has 36.2% ac- curacy in the overall evaluation, but it also drops to 4.0% in the Large category and 1.0% in the X-Large category. This indicates that the logical reasoning tasks in ZebraLogic extremely challenging for LLMs, especially for puzzles with more complexity with larger search spaces or harder clues. We can also see that scaling up the model size does not necessarily improve the performance of L.LMs logical reasoning tasks with large search spaces.
3.3. Scaling Behavior of LLMSs in Logical Reasoning
In the following sections, we study the scaling behavior of LLMs in logical reasoning, as illustrated Fig. 1. Our analysis focuses on two primary types of scaling: 1) scaling model size and 2) scaling test-time compute. For test-time compute, further explore three sub-dimensions: 1) the number of candidate samples, 2) the number of reasoning tokens (i.e., CoT tokens) generated during inference, and 3)
search space size.
Scaling model size is only effective for smaller search spaces. However, it is important note the significant bene- fits of scaling model size when the search space is relatively small (e.g., S 10%). In these cases, larger models like the
6

---

ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning
100
Model
100
Model
4058
Uame 3.2-38-22m--m -2-stuct
gpt-4o-m (pass
80
Scaling
Uama 3.1-708 Instrucct
80-
gpt-4o 4o m ni (pessg4)
gpt 4o nl (passga)
Accurary (%6
Model
O1-mini
9pt-4o-m in (pass@16)
60
8B
Sizes
60
Scaling CoTs
gpt-fo-m nn (pess@32)
gpt-4o.m (pess@e4)
gpt-4p-m in (nassg128)
40
40
ol a1-mini (passd91)
3B
The curse of complexity
4o-mini
20
20
(pass@k)
Scaling
0-
Samples
10a
10
10
10a
10a
10:0
16
10
1026
10th
10P
102
1.0
1049
1022
1024
10t
1015
Search Space Size flog stale)
Search Space Size (log scale)
Figure 3: Accuracy vs Search Space Size (log scale) comparing multiple scaling behavior of LLMs on ZebraLogic. Left: Scaling model sizes. Right: Scaling test-time compute through two approaches increasing sample size (via pass @ k evaluation) and extending chain-of-thought reasoning length. Both model size and test-time compute show diminishing returns search space complexity grows beyond certain complexity. More results are presented in Sec. 3.
Llama-3. 3.1-05B and 1lama-3.1-70B demonstrate substan- tial improvements in accuracy compared to smaller models such as the 3B and 8B versions. This suggests that scal- ing up the model size is an effective strategy for enhancing performance and tackling reasoning tasks in simpler search spaces. Yet, as the complexity of the search space grows beyond 10", the advantages of larger model sizes diminish, and scaling up the model size proves be less impactful. This finding underscores the limited utility of model scaling when dealing with highly complex reasoning tasks, as the accuracy plateaus regardless of model size.
answer to choose the best candidate from the sample pool equivalent to the pass @k k metric in our evaluation (see the right-most plot in Fig. 1 and Fig.3).
GPT-4o with Best-of-N sampling and oracle selections can achieve nearly ol performance. To understand the potential improvement of scaling test-time compute for logi- cal reasoning. we sample 128 candidates from GPT-4o-mini and GPT-4o and study the coverage of the correct answer in the sampled candidates. In Table 2, we refer to this coverage metric as BoN-Oracke meaning that the best-of-N (BoN) selection is performed given the oracle knowledge of the correct answer, i.e., the pass@k metric.
Model Size Scaling Limitations. This analysis reveals that scaling up model sizes eventually reaches a point of dimin- ishing returns in complex search spaces. Beyond a certain complexity threshold, increasing model parameters is insuf- ficient to prevent performance decline. This highlights critical boundary for current scaling strategies. suggesting that new approaches are needed to overcome the limitations imposed by high search space complexity and to advance reasoning capabilities further.
We observe that the BoN-Oracle selection can significantly improve the performance of GPT-4o-mini and GPT--4o. For example, GPT-4o with BoN-Oracle achieves an over- all accuracy of 69.1 %, which is higher than O1-mini's ac- curacy of 59.7% and a potential scaling effect that can also outperform O1-preview's s accuracy of 71.4% if we keep en- larging the sampling size. Note that on the Medium-size examples, we can already see a higher accuracy of 92.9% for BoN-Oraclew=122 compared Ol-preview's 88.2%, and the trend shown in the curves indicates that the performance of GPT-4o can be further improved with more test-time compute. Fig. 6 in Appendix provides further analysis on how sampling affects model performance.
5. Scaling Test-Time Compute with Repeated Sampling: Promises & Challenges
We examine the impact of scaling test-time compute, a cru- cial factor affecting LLM performance on logical reasoning tasks. Specifically, here we investigate how increasing the number of candidate samples influences model performance. We begin by employing Best-of-N (BoN) sampling, where we repeatedly sample N candidates from the model for each puzzle. From these candidates, we can select the best an- swer using various strategies, including majority voting and existing reward models. To understand the theoretical upper bound of this approach, we also analyze BoN sampling with oracle selection, where we use knowledge of the correct
Majority Voting is simple yet effective. For majority vot- ing, we rank the candidates based on the frequency of each cell in their solution grid, and select the candidate with the highest sum of frequencies. As for the Reward Model (RM), we choose the one that ranks to the top on Ai2's RewardBench leaderboard (Lambert et al., 2024b), named 1-8B-v0. (Liu et al., 2024). We find that using Majority Voting for GPT-4o can improve from 31.7 to 38.0 (for the overall accuracy) when the sam-
Skywork-
7

---

ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning
20000
20000
20000
#Hidden CoT Tolkens
17500
37500
17500
15000
15000
15000
12500
12500
12500
7500
7500
7500
5000
Sourtion Status
Conrect
5000
Solutor Status
Conrect
5000
Solution Status
Cornect
01-mini
Average
incormect
2500
01 11-reeieww
Incommet
2500
0 full
Average
Incorrect
Conflicss
Conticts
23 Conficts
Figure 4: The ol models' hidden CoT tokens vs. the number 23 conflicts. Each point is an example with a certain number of 23 conflicts. Larger number of Z3 conflicts are associated with harder reasoning problems.
Model & Methods
Overall
Small
Medium
Large
X-Large
6.1. ol Generates More Hidden Reasoning Tokens
GPTT40
31.7
80.0
19.6
2.5
0.5
ol generates large-scale hidden reasoning tokens. One of the key differences between ol and other LLMs is the way they use more test-time compute to decode much more hid- den chain-of- thotuughss (CoT) tokens during inference time, which are not directly visible to users. Our analysis shows that ol models scale their hidden CoT tokens with puzzle complexity producing on average 5,144.6 (ol-mini) and 5,346.3 (ol-preview) hidden reasoning tokens compared to 502.9 and 543.7 for GPT-4o-mini and GPT-4o respectively. This order of magnitude difference in reasoning steps ap- pears to contribute to ol's superior performance on logical reasoning tasks. For detailed analysis of how hidden CoT tokens vary with puzzle complexity, see Appendix C.3.
BoN- 119
69.1
99.7
92.9
49.0
7.0
BoN-Oracloy=sa2
60.3
98.4
81.1
28.0
2.5
Majorit.Vottngg-1zz
37.6
32.1
7.5
0.0
Majority Nating
38.0
84,1
34.3
7.0
0.5
BoN-RMx=sz
33.9
77.8
28.9
4.5
0.0
Self-Vorify (Oracle)
34.8
83.8
24.6
5.0
0.5
Self Verify
33.0
82.2
22.1
2.5
0.0
Veriff (x2)
32.1
80.0
21.4
2.5
0.0
@ GPT-4o-mini
20.1
58.8
4.6
0.0
0.0
BoN 11s
51.2
99.7
61.8
10.0
0.0
BoN-Oradleyissa
42.7
97.8
39.3
2.0
0.0
Majority- wot
25.0
69.4
8.9
1.5
0.0
Majority- Vating wada
24.5
8.2
0.5
0.0
BoN-RMx-32
22.5
62.2
9.3
0.0
0.0
Self-Verify (Oracle)
22.3
65.0
5.4
0.0
0.0
Figure 4 reveals a positive correlation between the number of hidden reasoning tokens generated by ol -preview and Z3 conflicts, aligning with our earlier observation that ol allocates more reasoning tokens to more complex puzzles. For puzzles with fewer than 20 Z3 conflicts, we observe a consistent ratio of approximately 400 hidden reasoning tokens per conflict. However, this scaling pattern plateaus when Z3 conflicts exceed 30, suggesting that ol op-eevieww may have reached its maximum reasoning capacity at the current model size. This suggests that while ol -previeww can effectively leverage more reasoning tokens for com- plex puzzles, there is limit to the extent to which it can scale reasoning tokens to address highly complex reasoning tasks. With the recent release of ol-full, we find that our previous estimation is consistent with the actual number of hidden reasoning tokens generated by ol-full, which is around 5,000 on average. This further confirms the scaling behavior of ol models in generating more hidden reasoning tokens for complex puzzles.
Self- Verify
21.1
60.9
5.7
0.0
0.0
Table 2: Comparison of various test-time compute scaling methods applied to GPT-4o and GPT-4o-mini. We evalu- ate several approaches: BoN-Oracle (selection using ora- cle knowledge to verify correct answers among samples), BoN-RM (selection using reward model), Eajority-Voting (selecting the most common answer across samples), and Self- Verify (using multi-turn prompting for self-reflection and correction, with and without oracle knowledge). We use to denote the use of oracle knowledge.
ple size N=32, while keep increasing the sample size does not necessarily improve the performance any more. Also, the performance of GPT-4o with BoN-RMN=32 33.9,
which is worse than majority voting, suggesting that the current reward models that are mainly designed for chat or general instruction following tasks may not be directly applicable to (logical) reasoning tasks.
We also find that when ol ol-preview make mistakes, they usually generate more hidden reasoning tokens than when they solve the puzzles correctly, which is consistent with the observation that ol tends to generate more reasoning tokens for more complex puzzles that are harder to solve.
6. Scaling Test-Time Compute with Extensive Shain-of-Thougght Tokens
Another approach of scaling test-time compute is to increase the number of reasoning tokens (i.e., chain-of-thun ofotthughtts to- kens) that the model generates during inference.
8

---

ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning
6.2. Self-Refinement is Limited but Promising
formal specification, Dziri al. (2023) that investigated compositionality in LLMs grid-based puzzles, well as Tyagi et al. (2024) that provided a new error laxonomy to evaluate the correctness of the reasoning chains of LLMs.
The other feature of ol's hidden reasoning process is the ability to reflect its own reasoning process and refine its answer. From our observation on the summary of their hidden reasoning process, we can see that ol often revisits the clues and constraints to verify its previous reasoning and fix the errors if there are any, which is similar to the Z3 solver's conflict-driven clause learning mechanism. In order to elicit such self-refinement behavior from LLMs, we add follow-up queries to ask the model to review its initial answer and check the clues and constraints again in multi-turn conversation setting. There are two settings for the self refineeetnment process: one with the oracle knowledge of the correct answer and the other without the oracle knowl- edge. Results in Table 2 show modest improvements with self-verification, particularly without oracle knowledge (40 improves from 31.7 to 33.0, then decreases to 32.1).
Approaches to Logical Reasoning in LLMs. Several lines of research propose methods to augment or refine LLMs for stronger logical reasoning. Clark al. (2020) demonstrated that transformers can emulate logical reason- ing over natural language sentences--ervee serving "soft the- orem provers." Pan et al. (2024) showed that a decoder- only Transformer could tackle SAT problems, paralleling the Lariis-uuaaa-LLemann-Looooe thereby expanding the role of LLMs to more complex problem-solving domains. Alternatively, neuro-symbolic systems like CLOVER (Ryu et al., 2024) integrate LLMs with symbolic solvers to better capture the translation of intricate logical semantics from text.
(DPLL) algorithm,
Self- Verification Prompt
Empirical Evidence of LLM Limitations. Despite these promising developments, LLMs face persistent hurdles as logical problem complexity increases. Yan et al. (2024) contended that models may rely heavily on probabilistic correlations rather than genuinely understanding logical rules. Similarly, Xie et al. (2024) highlighted the complex interplay between training data memorization and genuine reasoning abilities of LLMs. Additionally, Schlegel et al. (2022) conducted an extensive empirical study to investi- gate the detection of formally valid inferences in controlled fragments of natural language, revealing that transformers often overfit to superficial patterns rather than acquiring logical principles. Lam et al. (2024) showed the impact of the choice of symbolic solvers on the effectiveness of LLMs in deductive reasoning tasks, calling for more consistent comparative studies. Further empirical evidence from Dziri et al. (2023) and Parmar et al. (2024) demonstrated that even ostensibly simple logical tasks continue to challenge these models. Finally, Madusanka et al. (2023) investigated the limits of transformers on solving the problem of model- checking with natural language and the significant impact of the language fragment on the performance of transformers.
Self-Verify:
Your answer may be incorrect! Identify any mistakes in your reasoning and answer, if any Correct them to ensure they align with the given information. Present your updated response in the same JSON format mentioned in the initial prompt. Self- Verify (Oracle !)
For incorrect results: Your answer incorrect! Re-examing the clues, correct the mistakes, and then provide the revised solution in the original JSON format.
For correct results: Your answer is correct.
Please repeat the joon-formatted output again.
7. Related Work
Logical Reasoning Benchmarks and Dataset Creation Logical reasoning has long been a critical area of AI, but only recently have LLMs been subjected to rigorous testing in this domain. LogiQA (Liu et al., 2020) emerged early on to evaluate complex logical comprehension in question- answering formats; and subsequent efforts by (Liu et al., 2023) reframed it as a Natural Language Inference (NLI) task to further stress-test LLMs' capabilities. Researchers have also explored generating more dynamic or granular datasets to push the limits of reasoning systems. For in- stance, Madusanka et al. (2024) investigated satisfiability tasks formulated in natural language, studying how vary- ing computational complexity influences LLM inference performance. Similarly, Richardson & Sabharwal (2022) in- troduced a systematic methodology for building challenging reasoning datasets, exposing robustness gaps in transformer- based models when tasked with increased complexity. Prior work on logic grid puzzles include Mitra & Baral (2015) that proposed a grid-based puzzle dataset prior to the LLM era and focused on automatic translation from language to
8. Conclusion
We introduce Zebralogic,, a controlled benchmark of logic grid puzzles that highlights the scaling limits of LLM-based reasoning through carefully adjustable complexity. Our ex- periments reveal pronouneed drop in performance com- plexity increases, overshadowing gains from model growth or training data expansions. While increasing the generation sample size yields modest improvements, a backtracking- based approach with expanded reasoning steps significantly boosts accuracy. These results spotlight the importance of non-monotonic reasoning and provide a valuable framework for advancing logical reasoning research.

---

ZebraLogic:: On the Scaling Limits of LLMs for Logical Reasoning
Impact Statement
periments with gpt-4. arXiv preprint urXiv:2303.12712. 2023.
Our work introduces a novel, systematically controlled eval- uation framework for LLMs based on logic grid puzzles. This framework enables rigorous assessment of logical rea- soning capabilities, independent of domain knowledge or data leakage.
Chowdhery, A., Narang, S., Devlin, J., Bosma, M., Mishra, G., Roberts, A., Barham, P., Chung, H. W. Sutton, C., Gehrmann, S., Schuh, P., Shi, K., Tsvyashchenko,
S., Maynez, J., Rao, A., Barnes, P., Tay, Y., Shazeer, N. M., Prabhakaran, V., Reif, E., Du, N., Hutchinson, B., Pope, R., Bradbury, J. Austin, J., Isard, M., Gur-Ari, G., Yin, P., Duke, T., Levskaya, A., Ghemawat, S., Dev, S., Michalewski, H., García. X., Misra, V., Robinson, K., Fedus, L., Zhou, D., Ippolito, D., Luan, D., Lim, H., Zoph, B., Spiridonov, A., Sepassi, R., Dohan, D., Agrawal, S., Omernick, M., Dai, A. M., Pillai, T. S., Pel- lat, M., Lewkkwwwk. A., Moreira, E., Child, R., Polozov, O., Lee, K., Zhou, Z., Wang. X., Saeta, B., Díaz, M., Fi- rat, O., Catasta, M., Wei, J., Heciie-Hellstem,, K. S., Eck, D., Dean, J., Petrov, S., and Fiedel, N. Palm: Scaling lan- guage modeling with pathways. ArXiv, abs/2204.02311, 2022. URL https: / api. www.ateiscceeeeeeeeeeeeeeeeeeeee org/ //r///orrss.. 247951931.
A key finding is the "curse of complexity," where LLM accu- racy significantly declines as problem complexity increases.
This limitation persists despite scaling model size, chal- lenging the notion that larger models inherently improve complex logical reasoning. It suggests inherent architec- tural constraints in handling non-monotonie reasoning and extensive backtracking.
We also explore test-time compute scaling. While some sampling strategies show diminishing returns, the observa- tion that models like ol utilize significantly more hidden ofain- (CoT) tokens, scaling with problem com- plexity, crucial. This highlights the importance of explicit, structured reasoning processes with backtracking. It redi- rects future research towards developing LLMs specifically trained for deliberate, comprehensive reasoning steps, poten- tially via reinforcement learning, rather than solely relying on increased model size.
Clark, P., Tafjord, O., and Richardson, K. Trans- formers as soft reasoners over language. In Inter- national Joint Conference on Artificial Intelligence, 2020. URL
semanticscholar. org/CorrputD:22112665
ZebraLogie serves as valuable benchmark, offering a quan- tifiable environment push LLM reasoning boundaries. Our results provide a critical roadmap for advancing AI, guiding the development of more capable, reliable, and in- terpretable LLMs for complex logical challenges.
Colbourn, C. J. The complexity of completing par- tial latin squares. Discret, Appl. Math., 8:25-30, 1984. URL ptttpp:///pi.ssee weeanticccholet ozg/CorpusID:33II1
Acknowledgments
de Moura, L. M. and Bjømerr N. S. 73: An efficient smt solver. In International Conference on Tools and Algorithmss for Construction and Analysis of Systems, 2008. URL https: //pps:://pp... semanticscholar. org/ /CCCCopTT:::1119955555
Yejin Choi's research supported in part by the National Science Foundation under Grant DMS-2134012.
References
Dechter, R. Constraint Processing. Morgan Kaufmann, 2003.
Meta. The llama 3 herd of models. 2024. URL https: //arxiv. wwgg abs//a41 21783.
DeepSeck-AL. DeepSeck-R1: Incentivizing reasoning ca- pability in LLMs via reinforcement learning. arXiv, 122/25 2025.
Brown, T. B., Mann. B., Ryder, N., Subbiah, M., Kaplan, J. Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., Agarwal, S., Herbert- Voss, A., Krueger, G., Henighan, T., Child, R., Ramesh, A., Ziegler, D. M., Wu, J., Winter, C., Hesse, C., Chen, M., Sigler, E., Litwin, M., Gray, S., Chess, B., Clark, J., Berner, C., McCandlish, S., Radford, A., Sutskever, I., and Amodei, D. Language models are few-shot learners, 2020.
Dziri, N., Lu, X., Sclar, M., Li, X. L., Jian, L., Lin, B. Y., West, P., Bhagavatula, C., Le Bras, R., Hwang, J. D., Sanyal, S., Welleck, S., Ren, X., Ettinger, A., Har- chaoui, Z., and Choi, Y. Faith and fate: Limits of trans- formers on compositionallty. ArXiv, 0bs/2305.186544 2023. URL https: / sewant org/ /
Bubeck, S., Chandrasckaran, V., Eldan, R., Gehrke, J., Horvitz, E., Kamar, E., Lee, P., Lee, Y. T., Li, Y., Lund- berg. S., Nori, H., Palangi. H., Ribeiro, M. T., and Zhang, Y. Sparks of artificial general intelligence: Early ex-
Gomes, C. P. and Shmoys, D. B. Completing quasigroups or latin squares: A structured graph coloring problem. 2002. URL https: //ppp.pp..////////aaa org/CoorpusTD::441055.
http://.aaa.aa.....e..//////aa.. semant icstttlar.....
10

---

ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning
Hendrycks, D., Burns, C., Kadavath, S., Arora, A., Basart, S., Tang, E.,, Song, D., and Steinhardt, J. Measuring math- ematical problem solving with the math dataset. NeurIPS, 2021.
and Augenstein, I. (eds.), Proceedings of the 17th Confer- ence of the European Chapter of the Association for Com- putational Linguistics, pp. 3539-3550, Dubrovnik, Croa- tia, May 2023, Association for Computational Linguistics. doi: 10. 1 eacl mmain.main...m 257.
URL https:
Jain, N., Han, K., Gu, A., Li, W.-D., Yan, F., Zhang, T., Wang, S., Solar-Lezama, A., Sen, K., and Stoica, I. Livecodebench: Holistic and contamination free eval- uation of large language models for code. arXiv preprint arXiv:2403.07974, 2024.
wwg. //aclant hrgelaaattoooog..orgg22222.3... eac.:
Madusanka, T., Pratt-Hartmann, I., and Batista-Navaree R. Natural language satisfiability: Exploring the prob- lem distribution and evaluating transformer-basee lan- guage models. In Ku, L.-W., Martins, A., and Srikumar, V. (eds.), Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume I: Long Pupers), pp. 15278-15294, Bangkok, Thailand, August 2024. Association for Computational Linguis- tics. doi: 10. 10.186633///2222..oooooo / //aclanthology org www//ogg/////.. acl socl-looe acl-long. 815.
Lam, L. H. M. Thatikonda, R. K., and Shareghi, E. A closer look at logical reasoning with Ilms: The choice of tool matters. 2024. URL https: //api. www.ilseaanttiiio seemanticscholar. org/CorpusID: 270219 9176.
URL https:
Lambert, N., Morrison, J. D., Pyatkin, V., Huang, S., Ivison, H., Brahman, F., Miranda, L. J. V., Liu, A., Dziri, N., Lyu, X., Gu, Y. Malik, S., Graf, V., Hwang, J. D., Yang, J., Le Bras, R., Tafjord, O., Wilhelm, C., Soldaini, L., Smith, N. A., Wang, Y., Dasigi, P., and Hajishirzi, H. Tülu 3: Pushing frontiers in open language model post-training. ArXiv, abs/2411.15124, 2024a. URL https:tttt//.... /api...p.... semanticachon att/Co:puuSD::2711985555
Mitra, and Baral, C. Learning automatically solve logic grid puzzles. In Conference on Empirical Methods in Nat- ural Language Processing, 2015. URL ht /api. semanticscholes Ortg/Corpus1::26445350
OpenAL. Openai ol system card. arXiv, abs2241..16700 2024.
Lambert, N., Pyatkin, V., Morrison, D., Miranda, L. J. V., Lin, B. Y., Chandu, K. R., Dziri, N., Ku- mar, S., Zick, T., Choi, Y., Smith, N. A, and Ha- jishirzi, H. Rewardbench: Evaluating reward mod- els for language modeling. ArXiv, abs/2403.13787, 2024b. URL //api.
Pan, L., Ganesh, V., Abernethy, J., Esposo, C., and Lee, W. Can transformers reason logically? a study sat solving. 2024. URL https: /api iesmanticschol org/ htsp/CooppuID::73334111111
ht..cp/s//ppp...mmttccccoooooo www.nticschoole...............ee 268537409.
Parmar, M., Patel, N., Varshney, N., Nakamura, M., Luo, M., Mashetty, S., Mitra, A., and Baral, C. Log- ichench: Towards systematic evaluation of logical rea- soning ability of large language models. In Annual Meet- ing of the Association for Computational Linguistics, 2024. URL https: // /ppi. www.nnticcchoii
Liu, C. Y., Zeng, L., Liu, J., Yan, R., He, J., Wang, C., Yan, S., Liu, Y., and Zhou, Y. Skywork-reward: Bag of tricks for reward modeling in llms. arXiv preprint 2rXiv:2410.18455 2024.
269330143.
Liu, H., Liu, J., Cui, L., Teng, Z. Duan, N., Zhou, M., and Zhang, Y. Logiqa 2n0-an an im- proved dataset for logical reasoning in natural lan- guage understanding. IEEE/ACM Transactions on Au- dio, Speech, and Language Processing, 31:2947-2962. 2023. URL https: pettp::/app..sematttt semant iischola..cccc....... org/CorpusID. 1t:0opppuI::25911155 259515154.
Prosser, P. Hybrid algorithms for the constraint sat- isfaction problem. Computational Intelligence, 9, 1993. URL https:/ www.ssseeatniccchoooeeeeee org/CorpusTD:369511
Richardson, K. and Sabharwal, A. Pushing the limits of rule reasoning in transformers through natural language satis- fiability. In AAAI Conference on Artificial Intelligence, 2022. URL https: appi. semant csscholar. http:/CoouD:::5511110
Liu, J., Cui, L., Liu, H., Huang, D., Wang, Y., and Zhang, Y. Logiqa: A challenge dataset for machine reading compre- hension with logical reasoning. ArXiv, 18144, 2020. URL https: wttpppsssmmaatisscs....mo org/Corpus 220483148.
Ryu, H., Kim, G., Lee, H. S., and Yang, E. Divide and translate: Compositional first-order logic trans- lation and verification for complex logical reasoning. 2024. URL httpp://aap htttts/s///pp.smmtttttteeeet www.sssesaacccoll............. org//oorpust::27323377
Madusanka, T., Batista-navare R., and
Identifying the limits of transformers when performing model-checking with natural language. Vlachos, A.

---

ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning
Schlegel, V., Pavlov, K. V., and Pratt-Hartmann, Can transformers reason in fragments of natural language? In Conference Empirical Methods in Natural Language Processing. 2022. URL https: weriiiiseaaaniiccicc wtw.ccccal.....rorrrrssss....... org/CorpusTD; 253446947.
Sempolinski, P. Automatic solutions of logic puzzles.
2009. URL https::/api.set Bttp/CorrusSD:2253C.
Tyagi, N., Parmar, M., Kulkarni, M., Rrv, A., Pa- tel. N., Nakamura, M., Mitra, A., and Baral, C. Step-by-step reasoning to solve grid puzzles: Where do Iims falter? In Conference on Em- pirical Methods in Natural Language Processing, 2024. URL https:/ seaattsssmmtcccoo......... org/CorpusID:2211229
Wei, J. Wang, X., Schuurmans, D., Bosma, M., Chi, E. H., Xia, F. Le, Q. and Zhou, D. Chain thought prompting clicits reasoning in large language models. ArXiv, abs/2201.11903, 2022. URL ptttp::/api.ssmmatiic. semanticschola.r 2tt//orpusID:224611222
Xie, C., Huang, Y., Zhang, C., Yu, D., Chen, X., Lin, B. Y., Li, B., Ghazi, B., and Kumar, On memo- rization of large language models in logical reasoning.
2024. URL https:/ /tapps::///p..../ www.ntemassttsseeeeeee wew.:eesaaaatiicolll...e #re//corpusTD:2736555
Yan, J., Wang. C., Huang, J., and Zhang, W. Do large language models understand logic or just mimick context? ArXiv, abs/2402.12091, 2024. URL
sta.pp.ssmmttttscolll...r.r ott//corpustD::277551444
12

---

ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning
A. Additional Experimental Results and Analysis
Please find the additional analysis and results below figures.
20000
Solution
doe seive 24030000 30000000
Salution Status Incoreet Correct
Hidden Ressoning Tokens
17500
Incorrect
Hidden Reasoning Tokans
17500
Correct
SPOR 900 P9 %
www.oooeee MIDE
15000
15000
12500
G eesu Migh
GOCDNN AODDOO
10000
10000
6% 09
MWX
7500
5000
earonse
2500
01 Mini
2500
O1
Preview
10
10a
10a
107
10"
10ah
10th
10
10
10a
10a
10a
10'
101s
1015
1017
Search Space Size (Log Scale)
Space
(Log Scale)
Model
* Visible Reasoning Tokens
1200
a1 7074-09-12
GPT-4o,
ol-mini- 11-mini-2024-09-12
1000
GPT-4o-miní
gpt 4o 2024 08 06
gnt-4o-minl-2224-07-11
800
01 Preview
600
01 Mini
200
Search Space Size (Log Scale)
Small (<10*3)
Medium (<10'6)
Large (410~10)
X-Large (>10~10)
10
10a
10
106
10a
10
1012
10M
2036
Figure 5: Top: Distribution of hidden reasoning tokens generated by ol-mini and ol -revviww models. Bottom: Distribution of visible reasoning tokens across GPT-4o-mini, GPT-4o, ol-mini, and ol -p-eeviw models. Mean hidden reasoning tokens per model: ol-mini generates 5, 144.6 tokens and ol opreevew generates 5.346.3 tokens. Mean visible reasoning tokens per model: GPT-4o-mini (502.9), GPT-4o (543.7), o1-mini (305.7), and ol ol-preview (402.4).
B. Details of the ZebraLogic Dataset
All possible attribute types: Name, Color, Nationality, Animal, Drink, Cigar, Food, Flower, PhoneModel, Children, Smoothie, Birthday, Occupation, Height, CarModel, FavoriteSport, MusicGenre, BookGenre, HairColor, Mother, HouseStyle, Education, Hobby, Vacation, Pet
Each problem instance is characterized by two complimentary complexity metrics: the search space size as well as the average number of Z3 conflicts that the SMT solver takes to solve puzzle. Figure 7 illustrates how both metrics vary across different number of houses (N) and number of attributes (M).
C. Additional Analysis
GPT-40 tends generate more visible reasoning tokens than ol. Interestingly, we find that the GPT4o model tends generate visible reasoning tokens than ol, especially when the search space is large, which is shown in the lower part of Figure 5. The visible reasoning tokens are generated by the model and displayed in their outputs before the final solution grids. We can see that until the search space reaches the Large category (especially when the search space size is < 10 the four models generate similar numbers of visible reasoning tokens. However, when the search space size is larger, GPT4o generates more visible reasoning tokens yet still fails to solve the puzzles. ol models, which have used more hidden CoT tokens, tend to output fewer visible reasoning tokens for describing their reasoning process.
13

---

ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning
Small Search Space
Medium Search Space
Accuracy (%)
60
60
40
o1-preview (ref)
0l-mini (ref)
40
gpt-4o BoN-Oracle
gpt-4o-mini BoN-Oracle
20
gpt-4o BoN-RM
gpt-4o-mini BoN-RM
20
gpt-4o Majority
gpt-4o-mini Majority
16
32
64
128
1
8
16
32
64
128
Large Search Space
X-Large Search Space
ol-preview (ref)
o1-mini (ref)
ol-preview (ref)
ol-mini (ref)
35
gpt-4o BoN-Oracle
gpt-4o-mini BoN-Oracle
gpt-4o BoN-Orack
gpt-4o-mini BoN-Oracle
Accuracy (%)
gpt-4o BoN-RM
gpt-4o-mini BoN-RM
gpt-4o BoN-RM
gpt-4o-mini BoN-RM
60
gpt-4o Majority
gpt-4o-mini Majority
25
gpt-4o Majority
gpt-4o-mini Majority
40
15
20
5
0
16
32
64
128
16
32
64
128
Number of Samples
Number of Samples
Figure 6: Analysis inference-time time compute scaling using Best-of-N (BoN) sampling across different ZebraLogic puzzle size groups. The curves demonstrate how increasing the number of samples affects model performance, with separate plots for Small, Medium, Large, and X-Larre puzzle categories.
ed Grid Space Visualization 6x6)
Conflicts by Problem Size (2x2
0.6 Small
16
Small
Smal
Small
Small
Small
Small
Sma
Smail
Small
14
Average Number of 22 Conflicts
Logio of Search Space Size
Number of Houses (N)
Small
Small
Medium
Medium
Medium
-12
Number of Houses (N)
Smell
Small
Medium
Medium
Medium
60
10
Small
Medium
Modium
Medium
Mcdium
40
4.2
2
10:4
21 Lange
55 X-Large
Large
X-Lenge
Lerge
20
5-7 Modiuu
8.6 Large
11.4 Large
14.3 Largg
17.1
10.61
23.94 Large
37 Large
49.9
97.22 Large
-2
2
3 Number Attributes (M)
5
Number Attributes (M)
Figure 7: Heatmaps illustrating puzzle complexity metrics across different ZebraLogic problem sizes. The left heatmap represents the log-scaled search space size, categorized from Small to X-Large based on the grid configurations (houses x attributes). The right heatmap shows the average number of Z3 confficts encountered during solving, with higher counts indicating greater logical complexity.
C.1. Human Evaluation of ol's Reasoning
Here we present several case studies to understand the reasoning process of ol. We selected a few representative examples from the ZebraLoggt Logic dataset and analyzed the reasoning steps taken by ol -preview to arrive the final solution.
14

---

ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning
C.2. Comparison with LMSYS Arena Rankings.
While the overall performance rankings on ZebraLogic generally align with those from the LMSYS Arena (a platform for evaluating LLMs across various tasks), we observe some notable discrepancies that highlight ZebraLogic's 's distinct evaluation perspective. For instance, GPT-4o-mini-0771 achieves higher Elo score (1273) in LMSYS Arena (24-11-11) compared to Llama-3. 1-005B (1266), (0044000006126)4) Mistral-Large (1251), and Llama-3. 1-7B (1247). However, on ZebraLogic, GPT-4o-mini only achieves 20.1% % accuracy while Llama-3. 1-405B reaches 32.6%. These differences suggest that ZebraLogic offers a more focused assessment of logical reasoning capabilities, providing valuable insights that complement seneral-purposs. evaluations.
C.3. ol generates large-scale hidden reasoning tokens.
One of the key differences between ol and other LLMs is the way they use more test-time compute to decode much more hidden chain-of- of-ttoughtss (CoT) tokens during inference time, which are not directly visible to users. Figure shows how the number of hidden CoT tokens varies with the search space size for both ol o1-mini and ol ol-preview. In each sub-figure on the top, we plot 1,000 points, each representing puzzle. The color and shape of the points indicate whether the model produced correct solution (blue dots) an incorrect one (red crosses). The y-axis shows the number of hidden CoT tokens generated by the model, while the x-axis shows the search space size in logarithmic scale. The definition of search space size is provided in Section 2.3, and a larger search space usually indicates a more complex puzzle.
We can see that the number of hidden CoT tokens generated by ol is scaling with the search space size, indicating that ol is able to leverage more reasoning steps when faced with more complex puzzles. On average, we find that ol o1-mini generates 5, 5,144.6 hidden reasoning tokens, while ol -preview generates 5,346.3 hidden reasoning tokens. Both are about 10 times more than the average number of reasoning tokens generated by GPT-4o-mini (502.9) and GPT-4o (543.7), showing that scaling reasoning tokens can be effective way to improve the performance of LLMs on logical reasoning tasks.
D. Further Discussion on ol's Reasoning
We have seen that ol generates more hidden reasoning tokens than other LLMs, and the hidden reasoning tokens scale up with search space size, indicating that ol is able to leverage more reasoning steps when faced with more complex puzzles. Since the hidden reasoning tokens are not accessible, we investigate whether ol's visible output tokens or its summary of hidden tokens can explain its higher performance.
Visible outputs from ol cannot fully explain its reasoning for complex problems. To understand how ol reasons, we have to focus on their public reasoning steps that we can extract from the model's visible outputs. From our human evaluation on their reasoning steps, we find that ol's 's reasoming steps are not necessarily rigorous or complete, even when they arrive at the correct solution. For momll-m search spaces, ol -p-eevessw's 's reasoning chains tend to be complete, while ol -l-mi sometimes can skip some steps to directly reach the solution. For problems with larger search spaces, ol's visible reasoning chains tend to be very incomplete, and sometimes even incorrect, especially when the reasoning process requires backtracking. For example, ol's al's visible reasoning may contain steps such as "Bob cannot be in Houses 1, 4, or 5, so he must be in House 3" without explaining why Bob cannot be in House 2, although it will indeed lead to the correct solution. Note that such cases also happen for other LLMs such as GPT-4o. We thus describe that the reasoning process of LLMS and ol models are sometimes based on guessing without formal logic, especially for complex problems with large search spaces, rather than rigorous logical reasoning.
Such incomplete reasoning steps are very common in ol's outputs, especially for puzzles with larger search spaces, leading to unreliable explanations of their reasoning process. Thus, we argue that the visible reasoning steps from ol cannot help us understand how ol reasons for complex problems. Furthermore, knowledge distillation from ol's ll's reasoning steps is not necessarily helpful for improving the performance of other LLMs, as the reasoning steps are often incomplete and sometimes incorrect. This raises questions about the concern of hidden CoT tokens in their reasoning process that are not visible in the output.
Will the summary of hidden tokens help us understand ol's reasoning? Although the hidden CoT tokens are not visible from the OpenAl APIs, we can see an overview summary of the hidden reasoning tokens on ChatGPT's user interface for ol's 's hidden reasoning steps. By manually analyzing the overview summary of hidden reasoning tokens, we find it is still hard to clearly understand how ol reasons for complex problems. We can sometimes see some intermediate results in the overview but not any explanations for the decision. Interestingly, we can see some behaviors of recognizing the
15

---

ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning
contradictions of previous assumptions and revisiting the clues refine the solution. Such in-context reflection behavior hardly noticeable in other L.LMs such GPT-4o's reasoning, and it may be key factor for ol's success in solving complex problems. Typical steps in ol is hidden reasoning include: "Laying out the options", "Piecing together clues", "Pinpointing the clues", "Reevaluating assumptions", "Revisiting clues.", "Mapping out connections", "Tracking movement", etc. We provide case studies in the Appendix to better understand how ol reasons.
D.1. Prompt template to evaluate ZebraLogic
Example Fuzzle
There are 3 houses, numbered to from left to right, seen from across the street. Rach house occupied by different person. Rach house has unique attribute for each of the follewing characteristics:
Each person has a unique name: "Peter', 'Bric', 'Arnold", Each person has unique favorite drink: "tea', "water', "milk'
# clues for the Example Puzzle
1. Peter is in the seccnd house.
2. Arnold is directly left of the one who only drinks water.
3. The one who only drinks water is directly left of the person who likes milk.
## Answer to the Example Puzzle
"reasoning": "Given Clue we know Peter is in House 2. According to Clue 2, Arnold is di rectly left of the one who only drinks water. The person in House 3 cannot be on the left of anyone, so Arnold must be in House 1. Thus, Peter drinks water, and Eric lives House 3. Then, according to Clue Bric drinks milk. Cherefore, Arnold drinks tea.",
"solution:
"House 1s:
"Name"; "Arneid", "Drink": "tea"
House 2": "Name" "Peter", "riik": "water"
"ousse 3";
"Name" "; "Eric" "Drink": "milk"
Puzzle to Solve
There are 3 houses, numbered 1 to from left to right, seen from across the street. Each house is occupied by different person. Each house has a unique attribute for each of the follcwing characteristics:
Each person has unique name: 'Eric', "Peter', 'Aroold"
Each person has unique favorite drink: "milk' "water", "tea"
Each person has unique hobby: "photography", "cooking", "gardening"
#1 clues:
1. Arnold is not in the first house.
2. The person who likes milk is Eric.
The photography enthusiast
not in the first house.
4. The person who loves cooking is rectly left of the person who likes mi milk.
5. The one who only drinks water Arnold.
6. The person who likes milk is not in the secend house.
Instruction
Now please solve the abeve puzzle. Present your reasoning and solution in the following json format:
"reasoning":
"solution "House
Name
Drink
"Hobby"
fouse 2nd
Name"
16

---

ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning
"Drink":
"
"Hobby": ;
House 3 Name "Drink": "Hobby":
17


Reviews:
[{"review_id": "8ByuBgupAj", "reviewer": "Reviewer_zqZW", "summary": "This paper investigates the logical reasoning capabilities of large language models (LLMs) by introducing ZebraLogic, a benchmark dataset of 1,000 logic grid puzzles. These puzzles are formulated as constraint satisfaction problems (CSPs) with controlled complexity levels, allowing for systematic evaluation of LLMs' reasoning abilities across varying difficulties. The authors use two key metrics to measure puzzle complexity: search space size and Z3 conflict count (the number of conflicts encountered by an SMT solver). The research also describes what the authors call the \"curse of complexity,\" a considerable loss in LLM performance as issue complexity grows, even when expanding to bigger models.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your thoughtful review! We address each of the concerns and questions raised, and we will incorporate these clarifications and additional analyses into revision of the paper. We hope our responses adequately resolve the issues highlighted and kindly ask for your reconsideration of the scores if appropriate.\n\n#### W1: The analysis of o1's reasoning process relies on limited visibility into its hidden reasoning tokens\n\nWe recognize that OpenAI's restrictions on raw reasoning tokens limited our o1 analysis. To gain deeper insights, we will analyze DeepSeek's R1 model's visible reasoning tokens in the revised paper.\n\n#### W2: The self-verification experiments could be expanded to explore more sophisticated reflection mechanisms\n\nThank you for this insightful suggestion. We recognize the value of exploring more advanced reflection mechanisms to enhance our analysis. To address this, we will conduct a detailed investigation into sophisticated reflection approaches and incorporate the findings into the  version of the paper, ensuring a more comprehensive evaluation of their impact.\n\n#### W3 & Q3: The paper doesn't extensively analyze what specific types of reasoning failures occur as complexity increases\n\nThank you for your valuable suggestion regarding the analysis of reasoning failure modes. We acknowledge that the page constraints of the initial submission limited our ability to include a comprehensive discussion on this topic. To address this concern thoroughly in the revised paper, we will incorporate a detailed examination of specific failure modes, including:\n\n- A quantitative breakdown of the number and types of constraints (e.g., uniqueness, clue-based, positional) that remain unsatisfied in LLM outputs, identifying prevalent error patterns such as failures in handling non-monotonic reasoning or spatial constraints as complexity scales.\n- An examination of how the sequence and presentation of clues influence solution accuracy, testing for systematic biases or dependencies in the reasoning process, such as over-reliance on early clues or misinterpretation of later ones.\n- Case studies from our human evaluation (Appendix C.1) featuring specific examples of reasoning breakdowns, such as incomplete backtracking or incorrect counterfactual assumptions, particularly in puzzles with large search spaces or high Z3 conflict counts.\n\nOur analysis of the o1 outputs reveals two predominant failure modes that significantly impact its reasoning performance:\n1) **Lazy Mode (Most Prevalent):** The model often uses brief summaries instead of detailed step-by-step reasoning (e.g., \"going step-by-step\" or \"cycling through possibilities\"), reducing solution robustness.\n2) **Incorrect Proof of Impossibility:** The model wrongly claims clues are unsatisfiable, misinterpreting constraints like adjacency, leading to premature, incorrect conclusions and exposing limitations in complex constraint handling.\n\nThanks again for your valuable suggestion! We will address this in revision.\n\n#### Q1: The paper shows that o1 models generate ~10x more hidden reasoning tokens than standard models....\n\nThanks for the great question! We think the model architecture (i.e., the number of parameters, the number of layers, the number of attention heads, etc.) is not a key factor but still the data distribution and training methods are important. DeepSeek's R1 vs V3 is a good example for this. Training the base model with longer CoT data for triggering self-verification and self-correction is what enables R1 to outperform V3 on the ZebraLogic benchmark. Recent paper [1] also suggests that keeping appending the token \"Wait\" to force the model to think more is effective for improving the reasoning performance of the model.\n\n[1] s1: Simple test-time scaling\n\n\n#### Q2: How might the findings from ZebraLogic generalize to other formal reasoning domains beyond logic grid puzzles? Do you expect similar complexity scaling behaviors for tasks like mathematical reasoning or program synthesis?\n\nYes, we believe ZebraLogic's findings apply to other formal reasoning domains like mathematical reasoning and code generation, as many reasoning challenges are constraint satisfaction problems, central to our research. Although quantifying complexity in math or coding is harder than in our grid size and Z3 conflict measures, constraint-based reasoning principles suggest strong generalization potential.\n\n#### Q3: Have you analyzed what specific types of reasoning errors or failure modes emerge as puzzle complexity increases?\n\nPlease refer to the answer for W3 for this question.\n\n\n\n\n---\n\nThank you for your review! We will address your suggestions in the  version. We hope these clarifications and additional analyses adequately resolve the issues highlighted and kindly ask for your reconsideration of the scores if appropriate.", "claims_and_evidence": "1. **Performance decline with complexity:** The authors demonstrate this through comprehensive evaluations across various model sizes and architectures, showing consistent performance drops as complexity increases.\n2. **Limitations of model scaling:** The experiments show that even the largest models (e.g., Llama-3.1-405B) achieve near-zero accuracy on highly complex puzzles, supporting the claim that model scaling alone cannot overcome reasoning limitations.\n3. **Optimal reasoning token ratio:** The claim that there exists an optimal ratio of reasoning tokens to Z3 conflicts is supported by their analysis of o1 models, though this evidence is more correlational than causal.", "methods_and_evaluation_criteria": "1. The two complexity metrics (search space size and Z3 conflicts) provide complementary views of problem difficulty.\n2. The categorization of puzzles into four complexity groups enables a clear analysis of performance trends.\n3. The evaluation across multiple model architectures and sizes allows for robust comparative analysis.\n4. The puzzle generation methodology using clue types and templates is sound, ensuring puzzles have unique solutions while maintaining varied difficulty levels.", "theoretical_claims": "There are no theoretical proofs to verify in this paper. The authors establish that ZebraLogic is NP-complete through reduction from the Quasigroup Completion Problem. The paper primarily focuses on empirical evaluation rather than theoretical derivations.", "experimental_designs_or_analyses": "1. The authors evaluate a diverse set of models spanning different architectures, sizes, and both open-weight and proprietary systems.\n2. One potential limitation is that the analysis of o1's hidden reasoning tokens relies on estimates since these tokens aren't directly accessible. However, the authors acknowledge this limitation and verify their estimates once o1-full is released.\n3. The Best-of-N sampling experiments are insightful, though the choice of majority voting and reward models for candidate selection could be expanded to explore other selection strategies.", "relation_to_broader_scientific_literature": "The paper's core contribution of showing how performance scales across multiple dimensions (model size, sampling, reasoning tokens) provides a more comprehensive picture. The paper builds on prior work on logical reasoning benchmarks like LogiQA [1] and related investigations of LLM reasoning limits. It extends previous research on grid puzzles [2, 3, 4] by systematically controlling for complexity.\n\n[1] Logiqa: A challenge dataset for machine reading comprehension with logical reasoning. Liu et. al, IJCAI 2020.\n[2] Learning to Automatically Solve Logic Grid Puzzles, Mitra et al, EMNLP 2015\n[3] Faith and Fate: Limits of Transformers on Compositionality, Dziri et al, NeurIPS 2023.\n[4] Step-by-Step Reasoning to Solve Grid Puzzles: Where do LLMs Falter?, Tyagi et al, EMNLP 2024.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "**Strengths:**\n1. The multi-dimensional analysis of scaling behavior (model size, sampling, reasoning tokens).\n2. The inclusion of both open-weight and proprietary models for comprehensive evaluation.\n\n**Weaknesses:**\n1. The analysis of o1's reasoning process relies on limited visibility into its hidden reasoning tokens\n2. The self-verification experiments could be expanded to explore more sophisticated reflection mechanisms\n3. The paper doesn't extensively analyze what specific types of reasoning failures occur as complexity increases", "other_comments_or_suggestions": "1. A more detailed discussion of how these findings might inform training objectives for future models would strengthen the paper.", "questions_for_authors": "1. The paper shows that o1 models generate ~10x more hidden reasoning tokens than standard models. Have you explored whether standard models could benefit from being allowed to generate similarly extensive reasoning steps, or are there architectural differences that make this approach uniquely effective for o1?\n2. How might the findings from ZebraLogic generalize to other formal reasoning domains beyond logic grid puzzles? Do you expect similar complexity scaling behaviors for tasks like mathematical reasoning or program synthesis?\n3. Have you analyzed what specific types of reasoning errors or failure modes emerge as puzzle complexity increases? This could provide insights into targeted interventions for improving reasoning capabilities.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WmtW7enL7l", "reviewer": "Reviewer_KS5B", "summary": "The paper introduces ZebraLogic, a benchmark of logic grid puzzles derived from constraint satisfaction problems (CSPs), to evaluate the logical reasoning capabilities of LLMs. Key findings include:\n\n1. Curse of Complexity: LLM performance declines sharply as puzzle complexity (measured by search space size and Z3 solver conflicts) increases, even with model scaling or test-time compute.\n\n2. Scaling Limitations: Larger models (e.g., Llama-3.1-405B) improve performance on simpler puzzles but fail in highly complex scenarios, suggesting fundamental reasoning limitations.\n\n3. Hidden Reasoning Tokens: Models like o1 generate significantly more hidden chain-of-thought (CoT) tokens during inference, correlating with improved performance, though scaling plateaus at high complexity.\n\n4. Test-Time Compute: Best-of-N sampling and self-verification prompts yield marginal gains but fail to overcome the curse of complexity.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your thoughtful review! We address each of the concerns and questions raised, and we will incorporate these clarifications and additional analyses into revision of the paper. We hope our responses adequately resolve the issues highlighted and kindly ask for your reconsideration of the scores if appropriate.\n\n#### W1: Lack of evaluation on the latest models like o3-mini\nThank you very much for the suggestion! The O3-mini APIs were not stable at the time of our experiments, which often leads to timed out errors and refusals such as \"Invalid prompt: your prompt was flagged as potentially violating our usage policy.\" The O3-mini-high model was particularly unstable.\nWe recently re-ran the experiments and will include the results in the  version. The current results are as follows:\n\n| MODEL                  | XL   | Large | Medium | Small | Cell Acc |\n|------------------------|------|-------|--------|-------|----------|\n| o3-mini-2025-01-31-high | 75.5 | 87.5  | 97.1   | 99.7  | 95.7    |\n| o1-2024-12-17          | 42.5 | 78    | 92.1   | 97.2  | 78.7     |\n| deepseek-R1            | 28.5 | 73.5  | 95.7   | 98.4  | 80.5     |\n| o3-mini-2025-01-31-low | 23   | 64.5  | 91.1   | 99.4  | 72.6     |\n| o1-preview-2024-09-12  | 17   | 59.5  | 88.2   | 98.1  | 75.1     |\n| o1-mini-2024-09-12     | 12   | 39    | 76.8   | 87.5  | 70.3     |\n\nWe will include the results in the camera-ready version.\n\n#### Q1: Could the authors expand their analysis to include newer models (e.g., o3-mini high/medium/low, Gemini 2.0 Flash Thinking, Grok-3, and QwQ-32B) to provide additional data points for validating the curse of complexity and hidden reasoning token dynamics? Such comparisons would strengthen the generalizability of the findings, particularly for scaling trends and hidden token analysis.\n\nYes, we are more than happy to expand the analysis to include newer models and do more analysis with their reasoning process, and find the common failure modes for suggesting the future direction of the research. Please satey tuned for our leaderboard website for the latest results and an easy-to-use tool for evaluating all LLMs.\n\n\n#### Typo: \"rater\" → \"rather\"\n\nThank you for pointing out! We will fix it in the camera-ready version, and will carefully proofread the paper to avoid similar typos.\n\n---\n\nThank you so much for your review! We will address your suggestions in the  version. We hope these clarifications and additional analyses adequately resolve the issues highlighted.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "- ZebraLogic is well-designed, using CSPs to isolate logical reasoning from domain knowledge.\n- Complexity metrics (search space size, Z3 conflicts) are appropriate.\n- Prompting / Best-of-N sampling / Voting / Self-Verify metrics are common practice.", "theoretical_claims": "The paper focuses on empirical findings.", "experimental_designs_or_analyses": "- Broad evaluation of open/closed-source models across complexity levels.\n- Lack latest models like o3-mini.", "relation_to_broader_scientific_literature": "The work aligns with prior studies on LLM benchmarking, especially for reasoning (like MATH).", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "None", "other_comments_or_suggestions": "1. Typo: \"rater\" → \"rather\" (Page 13).\n2. Consider evaluating newer models (e.g., o3-mini) to strengthen claims like scalability and token efficiency.", "questions_for_authors": "Could the authors expand their analysis to include newer models (e.g., o3-mini high/medium/low, Gemini 2.0 Flash Thinking, Grok-3, and QwQ-32B) to provide additional data points for validating the curse of complexity and hidden reasoning token dynamics? Such comparisons would strengthen the generalizability of the findings, particularly for scaling trends and hidden token analysis.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MPaXctHKvc", "reviewer": "Reviewer_gf4p", "summary": "The paper introduces ​ZebraLogic, a benchmark dataset of 1,000 logic grid puzzles derived from constraint satisfaction problems (CSPs), to evaluate the scalability of large language models (LLMs) in complex non-monotonic reasoning. Key findings include the curse of complexity, and scaling model size or test-time compute (e.g., sampling, backtracking) offering limited improvements. The study evaluates GPT-4o, Llama-3, and specialized reasoning models (o1, R1).", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your thoughtful review! We address each of the concerns and questions raised, and we will incorporate these clarifications and additional analyses into the camera-ready version of the paper. We hope our responses adequately resolve the issues highlighted and kindly ask for your reconsideration of the scores if appropriate.\n\n\n#### W1: The paper does not deeply analyze why scaling fails\nDue to page constraints, our initial submission focused on empirical observations, but we plan to enhance the revised paper with a detailed examination of failure modes. This will include: (1) analysis of the number and types of unsatisfied constraints in model outputs, and (2) investigation of the correlation between clue ordering and solution correctness. These additions will provide deeper insights into the limitations of scaling for logical reasoning in LLMs. We also did qualitative analysis and discussed them in the response to W2.\n\n\n#### W2: The paper lacks a qualitative analysis of model errors\n\nThanks for the suggestion! While we included some failure case studies (e.g., Appendix C.1), page limits constrained a full qualitative analysis in the main text. We will address this in the revised version by integrating key error patterns:\n\n- **Non-Reasoning Models:** Frequent hallucinations in initial and later steps (e.g., Llama-3.1-405B) lead to inconsistent deductions and incorrect outputs.\n- **Reasoning Models:** Fewer early hallucinations (e.g., o1, R1), but errors persist in later steps due to incomplete backtracking.\n- **Self-Verification:** Reasoning models excel with self-correction (e.g., R1’s “Wait”/“Correct” markers, o1’s clue revisits), absent in non-reasoning models.\n- **Clue Rephrasing:** Periodic rephrasing of clues by reasoning models enhances constraint understanding and reduces errors.\n\n\n\n#### W3: The paper assumes that Z3 conflicts correlate with reasoning difficulty but does not experimentally validate this claim\n\nThanks for the question. We recognize that \"reasoning difficulty\" has no universal definition and appreciate concerns about Z3 conflicts as a general indicator beyond Z3. To clarify, Z3 conflicts reflect the \"reasoning difficulty of Z3,\" a leading systematic heuristic solver, though not fully solver-agnostic like search space size. Still, we find it insightful. Search space size, like grid size in our study, indicates challenges for uninformed reasoners, where a 10x increase means 10x more brute-force effort. Likewise, Z3 conflicts gauge difficulty for advanced solvers like Z3. Although we didn't quantitatively validate Z3 conflicts' correlation with perceived reasoning difficulty, our results using Z3 conflicts and grid size as proxies match scaling trends in benchmarks like AIME regarding model size and inference cost.\n\n\n#### W4: The paper only evaluates models in a one-shot setting, which might not be optimal for logical reasoning\n\nIn our preliminary experiments, we find that providing more few-shot examples do not improve the performance. We will include the results in the revised paper. It is indeed more likely to improve the performance for smaller non-reasoning models. However, our focus in the paper is to study the scaling behavior of reasoning models, instead of finding the best prompting strategies or exact few-shot examples to get state-of-the-art performance on reasoning benchmarks.\n\n#### W5: The supplementary material lacks environment requirements and a readme file, making it hard to reproduce\nThanks for pointing out! We will add a README file to the repository to help the readers to reproduce the results. We believe the code is not too complicated to run. The only complex part is to parse model outputs and calculate the metrics, while the other parts are standard LLM inference and data processing.\n\n#### Q1: Can you briefly discuss why scaling fails?\nPlease refer to the answer for W1.\n\n#### Q2: Does the number of hidden reasoning tokens generated by o1 models correlate with puzzle difficulty?\n\nYes, as shown in Figure 6 and discussed in Section 6.1, the number of hidden reasoning tokens generated by o1 models is positively correlated with puzzle difficulty, where difficulty is reflected by the Z3 conflict metric as an indicator of the reasoning challenges faced by Z3.\n\n#### Q3: Why does Best-of-N sampling with oracle selection significantly improve performance, while reward models fail to be as effective?\n\nOracle selection picks the model output closest to the ground truth, boosting performance as it mimics using ground truth as a reward signal, which is impractical. We study reward models to explore their limits in evaluating LLM reasoning performance.\n\n---\n\nThank you for your review! We will address your suggestions in the revised version. We hope these clarifications and additional analyses adequately resolve the issues highlighted and kindly ask for your reconsideration of the scores if appropriate.", "claims_and_evidence": "Mostly yes.", "methods_and_evaluation_criteria": "Yes. The evaluation criteria are reasonable, including both puzzle and cell-level accuracy.", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "Yes.\nThe main experiment and test-time scaling experiment are reasonable.\nHowever, the paper lacks error analysis, such as qualitative failure case studies.", "relation_to_broader_scientific_literature": "The paper is related to LogiQA (QA-style logical reasoning) and CLOVER (Neuro-symbolic LLM-solver integration).", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths:\n1. The paper isolates logical reasoning from domain knowledge, ensuring a controlled evaluation.\n2. The paper uses two complementary metrics to define problem complexity: search space size and Z3 conflicts.\n3. The experiments test on a broad range of models. The curse of complexity is effectively demonstrated.\n4. Various inference-time strategies are tested, including Best-of-N sampling, majority voting, and self-verification. Results find that scaling alone is insufficient.\n\nWeaknesses:\n1. The paper does not deeply analyze why scaling fails.\n2. The paper lacks a qualitative analysis of model errors.\n3. The paper assumes that Z3 conflicts correlate with reasoning difficulty but does not experimentally validate this claim.\n4. The paper only evaluates models in a one-shot setting, which might not be optimal for logical reasoning.", "other_comments_or_suggestions": "1. Figure 3 needs more captions to describe the results briefly.", "questions_for_authors": "1. Can you briefly discuss why scaling fails?\n2. Does the number of hidden reasoning tokens generated by o1 models correlate with puzzle difficulty?\n3. Why does Best-of-N sampling with oracle selection significantly improve performance, while reward models fail to be as effective?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LmADEkggZM", "reviewer": "Reviewer_LkaF", "summary": "The paper proposes ZebraLogic, a newly developed benchmark dataset of logic grid puzzles derived from constraint satisfaction problems.  The authors systematically evaluate LLM performance across different levels of problem complexity. The authors show \"curse of complexity\", where model accuracy declines significantly as puzzle complexity increases. The study also explores some strategies to improve reasoning performance, including Best-of-N sampling. The results suggest that scaling model size and test-time compute is insufficient to achieve reasoning in current LLMs.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review! We value your constructive feedback and will address your suggestions in the revised version.\n\n\n---\n#### Q1: Why Self-Refinement is promising? ...\n\nBoth self-refinement and majority voting are methods aimed at enhancing the reasoning performance of LLMs, and they are orthogonal to each other. For instance, self-refinement can be used to generate multiple outputs, which can then be evaluated through majority voting to select the most likely output. However, our goal is not to develop a state-of-the-art model for solving these puzzles but to demonstrate that all commonly used approaches, including self-refinement and majority voting, struggle to some extent with these challenges.\n\nThe reason we explore self-refinement is that reasoning models like O1 and R1 indicate that LLMs exhibit stronger reasoning capabilities when allowed to reflect on their previous steps, identify errors, and self-correct. Our focus is on understanding the scaling behavior of self-refinement (with multi-turn prompting) and how it compares to majority voting, highlighting the limitations shared across these approaches.\n\n---\n\n#### W1\n\nWe believe our insights will encourage the development of better logical reasoning models, and we will discuss their implications for future research in the revised version.\n\nHere are key points and experiments we will add:\n\n- **Improved Training:** We will generate numerous training examples and explore reinforcement learning methods like GRPO to boost model reasoning. We will also test if training on ZebraLogic puzzles generalizes to domains like math and code generation.\n\n- **Improved Inference:** We will investigate inference techniques to enhance reasoning, such as forced re-verification prompting and refined best-of-N sampling strategies.\n\n---\n\n#### W2\nWe agree that Best-of-N sampling with oracle selection has limited practical value and do not propose it as a solution for reasoning improvement. Instead, we aim to highlight the difficulty of these reasoning tasks by testing the limits of repeated sampling, even with a perfect oracle. This shows that current models struggle under ideal conditions, underscoring the tasks' challenge. We respectfully disagree that this is a paper weakness but will clarify this point to avoid confusion.\n\n---\n\n#### W3\n\nWe recognize that LLM reasoning includes domains like spatial, causal, and analogical reasoning beyond logical reasoning. However, we argue that logical reasoning is a foundational aspect of intelligence, justifying it as a critical starting point. Its structured nature enables precise evaluation and controlled experiments, vital for broader reasoning insights.\n\nAdditionally, our methodology for creating controllable reasoning problems is adaptable to other domains. For example, in spatial reasoning, we could generate grids with constraints for models to infer relationships. Many reasoning tasks share a logical basis involving constraint-solving, suggesting our approach provides a versatile framework for advancing various LLM reasoning types.\n\n---\n\n#### W4\n\nWe appreciate the feedback and agree that performance drops with task complexity across domains. However, we contend that the extent and nature of this decline in logical reasoning for LLMs are underexplored, which our work systematically examines.\n\nOur paper provides new insights into LLM scaling limits in logical reasoning, including:\n\n1. **Quantifiable Complexity Metrics:** We introduce ZebraLogic, a 1,000-puzzle benchmark, using search space size and Z3 conflict count to explain performance drops, offering insights beyond prior studies (Sec. 2.3, Fig. 8).\n\n2. **Scaling Behavior Analysis:** We examine model size, sampling, and test-time compute, showing that even advanced methods (e.g., Llama-3.1-405B, pass@128) fail past certain complexity levels, questioning the \"more scale\" assumption (Sec. 4-6, Fig. 1).\n\n3. **Reasoning Token Insights:** Our analysis of OpenAI’s o1 reveals heavy use of hidden chain-of-thought tokens (up to 10x more than GPT-4o), yet performance plateaus at high complexities, indicating inference-time reasoning trade-offs (Sec. 6, Fig. 3).\n\n4. **Practical Implications:** We evaluate strategies like Best-of-N sampling and self-verification, noting their limits and proposing explicit step-by-step reasoning to enhance LLM capabilities (Sec. 5-6).\n\n\nIn summary, while the performance drop with complexity may align with general expectations, our work offers a rigorous, systematic dissection of this trend in logical reasoning, uncovering its boundaries and underlying causes. These contributions provide deeper insights that extend well beyond common observations, positioning ZebraLogic as a valuable tool for both understanding and addressing the reasoning limitations of LLMs.\n\n---\n\nThank you again for the review! We will address your suggestions in the revised version. Please contact us with any further questions.", "claims_and_evidence": "Why Self-Refinement is promising? It seems that majority voting (or self consistency) has better results than self-refinement.", "methods_and_evaluation_criteria": "The paper doesn't provide new methods.", "theoretical_claims": "There is no theoretical claim.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "The paper proposes a new dataset for evaluating LLM reasoning capabilities.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "S1. The paper systematically evaluates various LLMs through extensive experiments.\n\nS2. The proposed dataset is engaging and valuable.\n\nS3. The paper is well-structured and easy to follow.\n\nW1. Introducing a novel method inspired by the experimental results would strengthen the paper.\n\nW2. The Best-of-N sampling with oracle selection has limited practical value. In most reasoning tasks, obtaining an oracle verifier is challenging.\n\nW3. Reasoning capabilities in LLMs encompass various aspects, but the paper primarily focuses on logical reasoning. It would be beneficial to discuss other perspectives.\n\nW4. Many observations in the paper align with well-known trends. For example, the significant performance drop as task complexity increases is expected. Providing deeper insights beyond these common trends would enhance the contribution.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper presents a synthetic Logical benchmark with increasing complexity. Reviewers appreciated the insights on language models' accuracy as the problem complexity is increased and the limitations of model scaling. The paper also studies the effects of scaling test-time compute and how it may not be enough to solve the hardest problems. The evaluation is comprehensive and the results useful for the reasoning community, with the inclusion of both open-weight and proprietary models.
The paper is timely and presents a useful benchmark.
Decision: Accept (poster)