PuzzlePlex: A Benchmark to Evaluate the Reasoning and Planning of Large Language Models on Puzzles

Thank you for your thoughtful feedback. I'm pleased to address each point below.

Weaknesses

W1. Lack of CIs or SEs

Thank you for your suggestion. We have added confidence intervals and standard errors for the results in Appendix C.2 in the revised version. This addition should make it easier to judge the statistical significance of the results.

W2. Lack of Agent Baselines and Advanced Prompting Strategies

We have included experiments regarding Tree-of-Thought (ToT) prompting and one-shot prompting in Section 4.4 of the revised paper. These techniques demonstrated improvements for smaller sizes of each puzzle but showed minimal benefit for larger sizes of those same puzzles. This demonstrates the needs for future work to develop better prompting strategies for larger scale puzzles.

Regarding agent baselines like ReAct and Reflexion,we agree that they can be helpful to determine feasible continuations. We have approximated this interaction by providing legal moves to the LLMs, simulating the effect of agents querying the environment for valid actions. Unfortunately, even with this list of legal moves, the models performed poorly when the puzzle size was large.

W3. Paper Refinement

We appreciate your feedback on the presentation. We have carefully proofread the manuscript and made several refinements in the revised version.

W4. Quantitative Analysis of Error Types

In Section 4.5 (now Section 4.6 in the revision), we have conducted a detailed quantitative analysis of the error types encountered by all models. This includes metrics on the frequency of each error type and identification of the most common issues. The analysis reveals that reasoning errors are the most prevalent. Furthermore, even when models successfully complete puzzles, a significant proportion of their reasoning steps contain errors, highlighting a gap in their reasoning capabilities.

Questions

Q1. Evaluator System

The term "Evaluator" refers to puzzle-specific evaluation functions that compute raw scores for each game. For instance, in the game Max Target, the evaluator calculates the coins collected by a player at each turn. These raw scores are subsequently normalized to a 0–1 range for cross-model comparison.

Q2. Adversarial vs. Competitive Games

The terms "adversarial games" and "competitive two-player games" are interchangeable in our benchmark. While two-player games can include cooperative scenarios, our benchmark focuses exclusively on competitive games, which we refer to as adversarial.

Q3. Win Rate Computation in Figures 2 and 3

In the tables on the right of Figures 2 and 3 (now Figures 2 and 29 in the revision), the win rate represents how frequently a model wins when competing against all other models. The corresponding figures display one-to-one win rates for each model pairing.

Q4. Context Window Length

We have included details about context window usage in Appendix C.3. Token consumption for gameplay varies, ranging from a few hundred tokens to approximately 64k tokens per game. However, multi-turn games significantly increase token usage cumulatively, with total consumption reaching several million tokens for games involving longer runs. While models can handle large context windows, the associated costs become prohibitively high in these scenarios.

Q5. Table Reference Error

Thank you for pointing out this error. We have corrected the reference in the revised manuscript (Section 4.1).

Thank you for the detailed response! I appreciate the efforts to address a lot of my concerns and have hence increased my score.

The term "Evaluator" refers to puzzle-specific evaluation functions that compute raw scores for each game. For instance, in the game Max Target, the evaluator calculates the coins collected by a player at each turn. These raw scores are subsequently normalized to a 0–1 range for cross-model comparison.

Thanks for clarifying! It would be great if the authors could add this to the paper.

The terms "adversarial games" and "competitive two-player games" are interchangeable in our benchmark. While two-player games can include cooperative scenarios, our benchmark focuses exclusively on competitive games, which we refer to as adversarial.

Thanks for clarifying. I think it would be better if the authors used "competitive 2-player" instead of "adversarial". The reason for this is that "adversarial" usually refers to something that's not only competitive/hard, but is so in an extreme way. Using this term here is confusing for people who might expect it to mean something more than "competitive 2-player".

In the tables on the right of Figures 2 and 3 (now Figures 2 and 29 in the revision), the win rate represents how frequently a model wins when competing against all other models.

So is this a row-wise average of the matrix on the left?

My main concern remaining with the paper is the evaluation section. I appreciate the authors' efforts to quantify the errors into different categories. However, it would be great if the authors could add clear criteria for when something is counted as a reasoning error vs. a memorization error or a comprehension error so that this becomes less subjective. These criteria could be added to the appendix if space is limited in the main paper. Finally, the writing still feels a bit rushed.

Thank you for your thoughtful feedback. I'm pleased to address each point below.

Weaknesses

W1. Utility of PuzzlePlex vs. SmartPlay

When compared to SmartPlay, PuzzlePlex makes the following contributions:

1. Broader Scope: PuzzlePlex includes more games (24 versus 5 in SmartPlay).

2. Difficulty Levels: PuzzlePlex supports increasing difficulty levels, making it possible to adapt the benchmark as LLMs improve.

3. Adversarial Multi-turn Games: Unlike SmartPlay, PuzzlePlex incorporates true adversarial multi-turn games that evaluate interactive planning and strategy. This is in contrast to Rock Paper Scissors in SmartPlay which is evaluated against a fixed-pattern program (e.g. cycling regularly between rock, paper, and scissor).

Regarding the question of translating mage puzzles to text, we agree that OCR can extract state information. However, we have found that text descriptions of visual puzzles often fail to induce LLMs effectively to reason about important constraints. For instance, in Sudoku, representing states with a visual structure may help LLMs identify constraints like ensuring unique values in each subgrid.

W2. Puzzle Selection Criteria

Our puzzle selection was guided by the goal of ensuring diversity across several dimensions:

• Game Types: Single-player and two-player games, deterministic and stochastic games, single-turn and multi-turn scenarios.
• Rule Complexity: Games with both strict and loose rules.
• Challenge Level: We selected puzzles that are less common and therefore less likely to be present in LLMs' training corpora, making them more suitable for evaluating generalization and reasoning abilities.

In Appendix A1, we show puzzles requiring comprehensive reasoning, while Appendix C3 illustrates diverse turn structures and context lengths, ranging from short to very long. The goal is to create a robust and evolving benchmark for LLM evaluation.

Questions

Q1. Missing Numbers in Tables 4 and 5

The numbers are missing in Tables 4 and 5 (now Tables 14 and 15 in the revised version) because we evaluated only Pixtral and two Llama-3.2-Vision models on text-image puzzles, while GPT-4, Gemini-1.5-Pro, Gemini-1.5-Flash, and Claude-3.5-Sonnet were evaluated on both text and text-image puzzles.

Q2. Incorrect Citation in Line 197

Thank you for pointing this out. We have corrected these errors in the revised manuscript.

Thank you for your thoughtful feedback. I'm pleased to address each point below.

Weaknesses

W1. Simplistic Scoring System

Thanks for your suggestion! In the revision, we introduce an additional metric, strength, derived from the Bradley-Terry model [1]. This metric allows us to unify comparisons across puzzle types and provides a more detailed perspective on model performance. The results are consistent with the original scoring system, showing that GPT-4o and Claude-3.5-Sonnet are the top-performing proprietary models, while Qwen2-72B is the best-performing open-source model.

W2. Lack of Ablation Studies

As in most ablation studies, we consider which factors contribute to the performance of a given LLM with respect to each puzzle. Two are most prominent: the size of the puzzle and the legality of moves. In section 4.4, we show that the size of the puzzle strongly influences the win ratio of the LLMs in two person games and in one person games – LLMs do better on smaller game sizes. We treat legality in section 4.5 where we show that simply giving the LLMs a set of legal moves increases their win ratio.

W3. Lack of Discussion on Computational Resources

Thanks for your suggestion. We have added a discussion on computational resources and runtime comparisons in Appendix B.3 of the revised paper.

W4. Visualization of Puzzles

Thank you for your suggestion. Upon publication we will provide a project page that includes visualization for each puzzle. This will enhance the understanding of the puzzles and make the benchmark more accessible to the community.

Questions

Q1. Fine-tuning on the Benchmark

Thanks for your insightful question. We have not performed fine-tuning in this paper because we have focused on the creation of the benchmark. In future work, we plan to do tuning on reasoning steps as illustrated in Figure 30, where the red text reflects reasoning mistakes. Eventually, we believe LLMs will improve their performance on benchmarks like PuzzlePlex by fine tuning on reasoning steps.

Q2. Few-shot Prompting

We include results of one-shot prompting in Section 4.5. Our results show that it provides a performance boost only in scenarios where the state space is small. For larger puzzles, the benefits of one-shot prompting are minimal, suggesting (though not proving) that it is not a scalable solution for more complex tasks. This is a promising direction for future work.

Q3. Better Planning Techniques

We agree that better planning techniques would significantly help. Additionally, we believe two complementary approaches are important:

1. Agent-based methods: For example, a program could assist LLMs by checking the legality of moves, thereby eliminating the need for repeated reasoning about legality during every step.

2. Fine-tuning on reasoning steps: This approach would directly enhance the LLMs' ability to plan and reason effectively, as demonstrated by our error analysis in Section 4.6, which highlights the prevalence of flawed reasoning steps.

[1] Roger R Davidson. On extending the bradley-terry model to accommodate ties in paired comparison experiments. Journal of the American Statistical Association.

Thank you for your thoughtful feedback. I'm pleased to address each point below.

Weaknesses

W1. Lack of Analysis

Thank you for your suggestion. In the revised manuscript, We have added a quantitative error analysis in Sections 4.5 and 4.6, identifying common errors made by LLMs.

We detail our findings as follows: The most frequent issue is that they fail to follow the rules or fail to choose advantageous moves. These issues become more prominent in puzzles with stricter rules. For example, in SudoKill, a player’s next move must be on a cell in the same row or column as the opponent's previous move, and the value chosen to fill in must comply with Sudoku rules. All the LLMs had trouble following that rule. Regarding different LLMs, we observed distinct patterns. For instance, in board games, most LLM models fill in cells sequentially, starting from the first empty cell in the top-left corner and progressing row by row, with Claude-3.5-Sonnet being an exception. For example, in Sudoku, Claude strategically fills cells that are easier to solve first, enabling subsequent moves to be more predictable and improving the overall problem-solving process. While proprietary LLM models (e.g. GPT-4o) generally outperform open-source models, the open-source models demonstrate a better understanding of rules in some games. For example, in the games of Max Target and Larger Target, only the Llama-3.1-405B model recognizes that the provided bags are randomized, which is illustrated in Figure 33.

We think these insights can provide actionable guidance for future research and LLM training. Specifically, fine tuning models with scenarios that reward valid rule-following actions or penalize deviations may help models internalize stricter compliance. Additionally, incorporating curriculum learning approaches—starting with simpler puzzles and progressively introducing more complex ones—could improve both rule adherence and strategic decision-making over time. Our benchmark will thus encourage such improvements.

W2. Insufficient Prompting Strategy

We have incorporated Tree-of-Thought (ToT) and one-shot prompting techniques in the revision (see Section 4.4). Both approaches lead to performance improvements, with ToT showing more significant gains. However, the experimental results demonstrate that the effectiveness of ToT is closely related to the size of the state space: it provides significant benefits in smaller-scale scenarios (e.g. board sizes of 4x4 in the Sudoku game) but little benefit as the problem scale increases (e.g. when board sizes increase from 4x4 to 9x9). This shows that while existing advanced prompting methods can enhance performance, they alone are insufficient to address the fundamental challenges posed by puzzle-solving tasks. We expect our benchmark to encourage research in this direction.

W3. Failure to Show How to Improve

Our findings indicate that simply generating data is not an effective solution. Fine-tuning LLMs on state-change data alone does not enable them to generalize well to new puzzles. As discussed in the paper, the primary reasoning limitations of current LLMs remain: difficulties in identifying legal moves and making optimal decisions when faced with multiple candidate actions.

To address these issues, we believe that adopting an agent-based approach represents an exciting direction for future research. For example, agents could be equipped with mechanisms (e.g., programmatic checks) to verify the legality of each move based on the game's rules. This verification can be reused across different turns, reducing the need for repeated reasoning about legality for every candidate move. Additionally, fine-tuning directly on reasoning steps—not just state changes—will enable LLMs to improve their planning and reasoning capabilities.

Moreover, our error analysis in Section 4.6 reveals that a significant proportion of reasoning errors occur even when the final results are correct by chance, because the moves decided by the LLMs cannot be supported by their reasoning steps. Improving the quality and reliability of reasoning steps is critical for better puzzle-solving and represents a promising direction for our future work.

Question

Thank you for the suggestion. We have included the AgentBench paper as a reference in our revised manuscript.