PaperlayerView exact revision on arXiv

Source-linked AI summary

PuzzlePlex: Benchmarking Foundation Models on Reasoning and Planning with Puzzles

Yitao Long, Yuru Jiang, Hongjun Liu, Yilun Zhao, Jingchen Sun, Yiqiu Shen, Chen Zhao, Arman Cohan, Dennis Shasha

arXiv:2510.06475v1cs.AIcs.CL

TL;DR

The paper asks how foundation models perform at sustained reasoning and planning in complex, dynamic environments. It introduces PuzzlePlex and finds that reasoning models do best in instruction-based settings, while code-based play is more challenging but scalable and computationally efficient.

  • Problem

    The paper asks how far foundation models can push problem-solving in scenarios requiring sustained, structured reasoning, including puzzles with evolving constraints and long-horizon interactions.

    Source: §1 · p. 1

  • Method

    PuzzlePlex is a benchmark of 15 novel puzzles spanning text and vision, deterministic and stochastic dynamics, and single- and two-player settings, evaluated through instruction-based and code-based approaches.

    Source: §1 · pp. 1–2

  • Results

    Reasoning models perform best in instruction-based settings, while code-based evaluation is more challenging due to program synthesis, though best-of-n sampling significantly improves performance there.

    Source: §1 · p. 2, §5 · p. 8

  • Takeaways & Limitations

    Code-based evaluation offers lower computational cost and scalability, making it a promising direction for evaluating foundation models.

    Source: §5 · p. 8

    The 15-puzzle benchmark is modest in size, so results may be sensitive to puzzle mix and random seeds.

    Source: Limitations · p. 9

Abstract

from arXiv · show

This work investigates the reasoning and planning capabilities of foundation models and their scalability in complex, dynamic environments. We introduce PuzzlePlex, a benchmark designed to assess these capabilities through a diverse set of puzzles. PuzzlePlex consists of 15 types of puzzles, including deterministic and stochastic games of varying difficulty, as well as single-player and two-player scenarios. The PuzzlePlex framework provides a comprehensive environment for each game, and supports extensibility to generate more challenging instances as foundation models evolve. Additionally, we implement customized game-playing strategies for comparison. Building on this benchmark, we develop fine-grained metrics to measure performance and conduct an in-depth analysis of frontier foundation models across two settings: instruction-based and code-based. Furthermore, we systematically investigate their scaling limits. Our findings show that reasoning models outperform others in instruction-based settings, while code-based execution presents greater challenges but offers a scalable and efficient alternative. PuzzlePlex enables targeted evaluation and guides future improvements in reasoning, planning, and generalization for foundation models.

1 Introduction

The paper asks how far foundation models can extend sustained problem-solving in settings requiring structured reasoning. It introduces PuzzlePlex and evaluates models across complementary interaction modes.

1 Introduction

  • Puzzle solving combines logical, numerical, and spatial reasoning with long-horizon planning and strategic adaptation in interactive or dynamic environments.These settings test reasoning under evolving constraints and coherence across extended interactions.Source: §1 · p. 1
  • PuzzlePlex provides 15 novel, extensibly generated puzzles spanning text-only and text-image formats, single- and two-player play, and deterministic and stochastic environments.The benchmark targets long-horizon reasoning, planning, and strategic coherence.Source: §1 · p. 1
  • The evaluation compares instruction-based interaction with code-based execution and includes hand-crafted baselines, fine-grained metrics, and analysis of scaling and failure modes.Instruction-based models act through natural language; code-based models generate executable code to solve puzzles.Source: §1 · p. 2
  • Reasoning models outperform non-reasoning models in instruction-based settings, while code-based play is harder but offers a scalable, efficient alternative.The paper also reports that best-of-n sampling improves code-based performance.Source: §1 · p. 2
  • PuzzlePlex jointly evaluates interactive and executable reasoning across diverse puzzle types, with support for textual and visual puzzles and deterministic and stochastic dynamics.The benchmark is designed to assess reasoning and planning capabilities.Source: §1 · p. 2

2 Related Work

The related work distinguishes rule-based puzzles from tasks without explicit rules and traces puzzle-solving approaches from classical algorithms to foundation-model prompting. PuzzlePlex focuses on rule-based settings and evaluates both prompted reasoning and executable code.

2.1 Puzzles and Relevant Benchmarks

  • Rule-based puzzles have explicit rules, goals, and state transitions, while rule-less puzzles lack explicit action spaces or clear objectives; PuzzlePlex focuses on rule-based puzzles and excludes knowledge-heavy puzzles.The authors motivate these scope choices as enabling objective evaluation in competitive, dynamic settings and avoiding tasks dependent on external knowledge.Source: §2.1 · p. 2
  • Prior puzzle benchmarks mostly cover single-player, short-horizon tasks, while competitive multi-turn games, stochastic environments, and multimodal puzzles are less explored (Mittal et al., 2025; Gui et al., 2024a; Zhao and Anderson, 2023; Wu et al., 2024a; Liu et al., 2023; Wang et al., 2025; Ren et al., 2025).Table 1 compares PuzzlePlex with recent puzzle benchmarks.Source: §2.1 · p. 2

2.2 Evolution of Puzzle Solving Techniques

  • Classical puzzle solvers use dynamic programming, alpha–beta pruning, and heuristic search, while neurosymbolic methods address single-player puzzles (Ahmed et al., 2023).Some such puzzles can be reduced to SAT or SMT formulations.Source: §2.2 · pp. 2–3
  • Later approaches include reinforcement learning and foundation-model prompting; Chain-of-Thought outperforms direct prompting, and Self-Refine, Tree-of-Thought, and Everything-of-Thoughts further enhance deterministic-puzzle reasoning (dos Santos et al., 2019; Huang et al., 2024; Wei et al., 2023; Madaan et al., 2023; Yao et al., 2023; Ding et al., 2024).The authors adopt CoT-style prompting and add code-based execution for direct interaction with puzzle environments.Source: §2.2 · p. 3

3 PUZZLEPLEX

PuzzlePlex provides a framework for generating and evaluating puzzle instances, with customized strategies and separate instruction-based and code-based evaluation protocols. Its metrics support comparisons across single-player and two-player games.

3 PUZZLEPLEX

  • The framework instantiates puzzle templates, records moves, shares state information, and evaluates game states; its pipeline generates instances, checks moves, scores terminal games, and otherwise updates state.A Simulator web interface supports visual observation of state transitions and model reasoning steps.Source: §3 · p. 3, §3.1 · p. 3

3.1 Puzzle Generation Framework

  • Puzzle instances are generated from templates using randomness, with difficulty adjusted by varying puzzle size; each generated instance is the game's initial state.The state-transition module maps a state and move to a new state plus feedback on move legality, termination, and position information.Source: §3.1 · p. 3

3.2 PUZZLEPLEX Benchmark Construction

  • The 15 puzzles cover single-player and two-player deterministic and stochastic games; text-based puzzles span all four types, while text-image puzzles are limited to two-player deterministic games.Puzzles are drawn from a published column or curated by the authors; the authors also simplified some rules to lower the entry barrier.Source: §3.2 · pp. 3–4

3.3 Customized Strategies

  • Customized puzzle strategies include brute-force search, BFS and DFS, Monte Carlo Tree Search, dynamic programming, greedy algorithms, backtracking, and simulated annealing.The selected strategy depends on puzzle properties, such as whether exhaustive search fits time constraints or subproblems overlap.Source: §3.3 · p. 4

3.4 Evaluation Protocols

  • Instruction-based evaluation uses fixed-seed instances for deterministic puzzles and excludes stochastic puzzles because of their variance and the cost of robust evaluation; code-based evaluation samples 32 programs per puzzle and evaluates stochastic games over multiple seeds.Instruction protocols use 10 instances for single-player deterministic puzzles and five two-player instances with alternating first-player order; code protocols use 100 runs for single-player stochastic puzzles and 50 for two-player stochastic puzzles.Source: §3.4 · pp. 4–5

3.5 Evaluation Metrics

  • Raw scores reflect puzzle outcomes or objectives; single-player scores are normalized to [0, 1], and Elo ratings enable comparisons across both single-player and two-player settings.For single-player Elo matchups, the model with the higher normalized score is treated as the winner.Source: §3.5 · p. 5

4 Experiments

The experiments compare foundation models in instruction-based and code-based puzzle solving, with additional analyses of prompting, multimodal inputs, and scaling. Reasoning models lead in instruction-based evaluation, while code-based evaluation is harder and model performance varies with prompting, modality, and task.

4.1 Experimental Setup

  • The evaluation uses chat or instruct versions of 11 models, excluding four image-incapable models from text-image instruction tests.Results are reported for instruction-based and code-based settings, with normalized scores and additional per-puzzle breakdowns.Source: §4.1 · p. 5, §4.2 · p. 5

4.2 Main Results

  • 0.62 for DeepSeek-R1 exceeds Gemini-2.5-pro’s 0.58, while the custom strategy scores 0.70 on average; all top-five models use reasoning strategies.QwW-32B also surpasses GPT-4.1 and DeepSeek-V3, and leading models can match or outperform the custom strategy on two-player deterministic puzzles.Source: §4.2 · p. 6
  • In code-based evaluation, DeepSeek-R1’s easy-level score falls from 0.64 to 0.33 and its normal-level score from 0.48 to 0.25.Code-based play requires executable program synthesis rather than interactive adaptation; its best scores can approach or match the custom strategy, and generated code can be reused.Source: §4.2 · p. 6

4.3 More Instruction-based Analysis

  • Prompting effects are mixed: 1-shot changes little, ToT helps TIDYTOWER but not SUDOKILL, and omitting history boosts TIDYTOWER.Providing legal candidate moves consistently improves performance, with o4-mini benefiting more from these strategies than GPT-4.1.Source: §4.3 · pp. 6–7
  • Visual inputs help most models, but gains vary by model and task complexity.GPT-4.1 improves its SUPERPLYM (Normal) win rate by +0.38, while Phi-4-multimodal drops by -0.75 on SUPERPLYM Easy; benefits are more pronounced on simpler tasks.Source: Table 4 · p. 6, §4.3 · p. 7

4.4 Scaling Analysis

  • DeepSeek-R1’s scores generally rise with more generated tokens on single-player deterministic puzzles, while DeepSeek-V3’s trend is flatter or downward.R1 allocates more tokens to normal than easy instances; V3 shows little variation across difficulty levels.Source: §4.4 · p. 7, Figure 3 · p. 7
  • Reasoning models typically use over five times non-reasoning models’ tokens in instruction-based settings, and about ten times as many in code-based settings.o4-mini is an exception to the instruction-based pattern and uses similar token amounts across the two settings.Source: §4.4 · p. 8, Table 5 · p. 8
  • Reasoning models generally make fewer instruction-based errors, but code results are mixed: GPT-4.1 remains comparable to reasoning models and QwQ-32B has a low legal rate.QwQ-32B’s low legal rate is attributed to frequent syntax errors in code generation.Source: §4.4 · p. 8

5 Conclusion

The conclusion presents PUZZLEPLEX as a broad testbed for evaluating reasoning techniques across puzzle modalities, dynamics, and interaction horizons. Its findings distinguish instruction-based strengths from code-based challenges and identify prompting and multimodal gains alongside continuing reasoning limitations.

5 Conclusion

  • PUZZLEPLEX evaluates reasoning techniques across text and vision, deterministic and stochastic dynamics, and long-horizon interactions.The benchmark includes instruction-based and code-based settings.Source: §5 · p. 8
  • Reasoning models perform best in instruction-based settings, while code-based evaluation is harder but lower-cost and scalable.The conclusion attributes code-based difficulty to accurate program synthesis and notes that best-of-n sampling significantly improves performance.Source: §5 · p. 8
  • Multimodal inputs and legality-aware prompting help in specific scenarios, but models still struggle with multi-hop reasoning.In TIDYTOWER, removing prior reasoning history improves accuracy, suggesting current models may be misled by irrelevant context.Source: §5 · p. 8

Limitations

The study’s findings have several stated scope limits: the puzzle set is modest, the model evaluation may omit later releases, and fine-tuned models are not assessed.

Limitations

  • The 15-puzzle set is modest, so results may be sensitive to puzzle mix and random seeds.This constrains how broadly the reported results can be generalized across puzzle mixes and seeds.Source: Limitations · p. 9
  • Experiments may omit model releases that became available after the experiment period.The authors attribute this to rapid model evolution and budget constraints.Source: Limitations · p. 9
  • The study does not assess whether fine-tuned models can outperform existing LLMs.The authors identify this comparison as a source of additional insight not covered in the experiments.Source: Limitations · p. 9

Ethics Statement

The study uses rule-based puzzles and reports safeguards for puzzle licensing, generated-code execution, and data logging.

Ethics Statement

  • The study uses rule-based puzzles and no human subjects or personally identifiable information.All puzzles are original or permissively licensed.Source: Ethics Statement · p. 9
  • Model-generated code runs in a sandbox, and evaluation follows provider terms and safety policies.Source: Ethics Statement · p. 9
  • The study logs only nonsensitive metadata.Source: Ethics Statement · p. 9

A.1 Dataset Overview

The appendices provide an overview of the puzzle games, illustrate the simulator, describe puzzle types, and document model and strategy configurations.

A.1 Dataset Overview

A.2 Example of Simulator

  • The simulator presents a puzzle’s move history; the SuperplyM example shows alternating red and green moves in a four-move sequence.SuperplyM is described as a two-player puzzle with an arithmetic-teaching goal.Source: Figure 4 · p. 14

A.3 Breakdown Description of Puzzles

B.1 LLMs Configuration

  • Table 7 lists details of the LLMs evaluated in PuzzlePlex.Source: Table 7 · p. 23

B.2 Costomized Model Configuration

  • Table 8 overviews puzzle games and their basic strategies; text-image puzzles use strategies similar to corresponding text-only puzzles.Source: Table 8 · p. 23

B.3 Implementation Details of Model Inference

The evaluation uses APIs for several named models and Transformers inference on specified hardware for other models.

B.3 Implementation Details of Model Inference

  • The study evaluates Deepseek-R1, o4-mini, Gemini-2.5-pro, grok-3-mini, Deepseek-V3, GPT-4.1, and Phi-4-multimodal through APIs.Source: §B.3 · p. 24
  • Other models are run with Hugging Face Transformers inference on 8 × H100 and 8 × A100.The passage cites Wolf et al. (2020) for Transformers.Source: §B.3 · p. 24

B.4 Implementation Details of Elo Score

The appendix specifies Elo rating updates and move-format validation, and identifies the experiment-cost units and code-prompt template.

B.4 Implementation Details of Elo Score

  • Elo ratings start at 1000 and update using K = 32 times the difference between actual and expected scores.Actual scores are 1 for a win, 0.5 for a draw, and 0 for a loss; expected score is computed from both players’ ratings.Source: §B.4 · p. 24

B.5 Operation Extraction

  • LLMs get up to five attempts per turn to produce a correctly formatted move; failure to do so results in a loss.A regular-expression checker validates the format before the move is sent to the state-transition engine.Source: §B.5 · p. 24

B.6 The Cost of Experiments

  • Experiment costs are estimated in USD for API-based models and NVIDIA H100 GPU hours for GPU-based models.Source: Table 9 · p. 24

B.7 Code-based Prompt Template

C.1 Elo Score Results

The results appendix reports Elo ratings and normalized scores across deterministic puzzle types and difficulty, then covers prompting strategies, setting comparisons, play statistics, and head-to-head win rates.

C.1 Elo Score Results

  • Table 10 compares mean Elo scores with 95% confidence intervals across single-player and two-player deterministic puzzles by difficulty.Tables 11 and 12 further report Elo ratings for three single-player and five two-player deterministic puzzles, respectively.Source: Table 10 · p. 25, Table 11 · p. 25, Table 12 · p. 25

C.2 Results of Different Prompting Strategies

  • Table 13 compares prompting strategies for GPT-4.1 and o4-mini on TIDYTOWER and SUDOKILL.Source: Table 13 · p. 26

C.3 Breakdown Instruction-based Results of Puzzles

  • Tables 14 and 15 report instruction-based normalized scores by difficulty for single-player and two-player deterministic puzzles.Source: Table 14 · p. 26, Table 15 · p. 26

C.4 Instruction-based vs. Code-based

  • Table 16 reports instruction-based win rates against the custom strategy and shows instruction-minus-code win-rate differences in parentheses.The table covers two-player deterministic puzzles.Source: Table 16 · p. 27

C.5 Play Statistics

  • Table 17 summarizes play and legal-play statistics in the instruction-based setting, including turns per player.For two-player puzzles, rounds are the sum of both players’ turns.Source: Table 17 · p. 27

C.6 Win Probability Matrix

  • The win-rate heatmaps exclude ties: instruction-based GPT-4.1 beats o4-mini 28.6% of the time, while code-based results are 50.2% versus 49.8%.The figures show each row method’s win rate over the column method.Source: Figure 19 · p. 28, Figure 20 · p. 29
Loading 2510.06475v1…