mlsanityData to 7 Oct 2026

Pencil Puzzle Bench: A Benchmark for Multi-Step Verifiable Reasoning

arXiv 2603.02119 ↗First posted 2 Mar 2026cs.AI cs.GT cs.LGcited by 4

On the map: LLM reasoning → Reasoning benchmarks and evaluation

also in 1 more
Abstract (arXiv)

We introduce Pencil Puzzle Bench, a framework for evaluating large language model reasoning through pencil puzzles, a family of constraint-satisfaction problems closely related to NP-complete problems, with deterministic, step-level verification. From a database of 62,231 puzzles across 94 varieties with verified unique solutions, we select a benchmark of 300 puzzles spanning 20 varieties and evaluate 51 models from 11 providers in two modes: direct ask (single-shot) and agentic (multi-turn with iterative verification). A key differentiator of our benchmark is that every intermediate board state can be checked against variety-specific constraints, localizing errors to the exact rule violated, providing the infrastructure for dense, per-move reward signals for process supervision and reinforcement learning. Our evaluation reveals two distinct axes of capability: (1) reasoning effort scaling, where GPT-5.2 improves 81x from no reasoning to maximum effort; and (2) agentic iteration, where Claude Opus 4.6 rises from 0.3% to 30.0% through iterative checking, while GPT-5.2@xhigh improves from 20.2% to 56.0%. Agentic attempts span a median of 29 turns over 17 minutes, with the longest exceeding 1,221 turns and 14.3 hours - a demanding test of long-context utilization, not just reasoning.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Placed in Reasoning benchmarks and evaluation, one of 17 directions in LLM reasoning. Builds on 47 of its 51 references that are in the map. First posted on arXiv 2 Mar 2026.

Builds on

47 of 51 references.

Closest ancestors · 8

Same direction, newest first

  1. 2025RiddleBench: A New Generative Reasoning Benchmark for LLMs28 Oct
  2. 2025HardcoreLogic: Challenging Large Reasoning Models with Long-tail Logic Puzzle Games14 Oct
  3. 2025Enigmata: Scaling Logical Reasoning in Large Language Models with Synthetic Verifiable Puzzles26 May
  4. 2025Sudoku-Bench: Evaluating creative reasoning with Sudoku variants22 May
  5. 2025SATBench: Benchmarking LLMs' Logical Reasoning via Automated Puzzle Generation from SAT Formulas20 May
  6. 2025ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning3 Feb
  7. 2024Puzzle Solving using Reasoning of Large Language Models: A Survey17 Feb
  8. 2022ReAct: Synergizing Reasoning and Acting in Language Models6 Oct

Other references · 39

  1. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,302
  2. 2021Training Verifiers to Solve Math Word Problemscited by 9,743
  3. 2025DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learningcited by 6,146
  4. 2022Self-Consistency Improves Chain of Thought Reasoning in Language Modelscited by 5,601
  5. 2021Measuring Mathematical Problem Solving With the MATH Datasetcited by 5,203
  6. 2018Think you have Solved Question Answering? Try ARC, the AI2 Reasoning Challengecited by 4,710
  7. 2023Toolformer: Language Models Can Teach Themselves to Use Toolscited by 4,072
  8. 2023Let's Verify Step by Stepcited by 3,598
  9. 2023Generative Agents: Interactive Simulacra of Human Behaviorcited by 3,500
  10. 2023Self-Refine: Iterative Refinement with Self-Feedbackcited by 3,317
  11. 2023SWE-bench: Can Language Models Resolve Real-World GitHub Issues?cited by 3,193
  12. 2023Tree of Thoughts: Deliberate Problem Solving with Large Language Modelscited by 3,155
27 more
  1. 2022Beyond the Imitation Game: Quantifying and extrapolating the capabilities of language modelscited by 1,970
  2. 2022Challenging BIG-Bench Tasks and Whether Chain-of-Thought Can Solve Themcited by 1,767
  3. 2016OpenAI Gymcited by 1,684
  4. 2022Least-to-Most Prompting Enables Complex Reasoning in Large Language Modelscited by 1,397
  5. 2024τ-bench: A Benchmark for Tool-Agent-User Interaction in Real-World Domainscited by 1,280
  6. 2024OpenAI o1 System Cardcited by 1,220
  7. 2022Program of Thoughts Prompting: Disentangling Computation from Reasoning for Numerical Reasoning Taskscited by 1,057
  8. 2023Graph of Thoughts: Solving Elaborate Problems with Large Language Modelscited by 873
  9. 2024Large Language Model based Multi-Agents: A Survey of Progress and Challengescited by 752
  10. 2021Did Aristotle Use a Laptop? A Question Answering Benchmark with Implicit Reasoning Strategiescited by 736
  11. 2023Plan-and-Solve Prompting: Improving Zero-Shot Chain-of-Thought Reasoning by Large Language Modelscited by 550
  12. 2025The Lessons of Developing Process Reward Models in Mathematical Reasoningcited by 402
  13. 2024TheAgentCompany: Benchmarking LLM Agents on Consequential Real World Taskscited by 306
  14. 2020Transformers as Soft Reasoners over Languagecited by 265
  15. 2024Benchmark Data Contamination of Large Language Models: A Surveycited by 138
  16. 2023Investigating Data Contamination in Modern Benchmarks for Large Language Modelscited by 136
  17. 2025A Survey of Frontiers in LLM Reasoning: Inference Scaling, Learning to Reason, and Agentic Systemscited by 108
  18. 2024Benchmarking Benchmark Leakage in Large Language Modelscited by 102
  19. 2024Inadequacies of Large Language Model Benchmarks in the Era of Generative Artificial Intelligencecited by 65
  20. 2025Recent Advances in Large Langauge Model Benchmarks against Data Contamination: From Static to Dynamic Evaluationcited by 38
  21. 2025A Survey of Process Reward Models: From Outcome Signals to Process Supervisions for Large Language Modelscited by 37
  22. 2024Step-by-Step Reasoning to Solve Grid Puzzles: Where do LLMs Falter?cited by 18
  23. 2025PuzzleBench: A Fully Dynamic Evaluation Framework for Large Multimodal Models on Puzzle Solvingcited by 15
  24. 2023Assessing Logical Puzzle Solving in Large Language Models: Insights from a Minesweeper Case Studycited by 14
  25. 2025FINEREASON: Evaluating and Improving LLMs' Deliberate Reasoning through Reflective Puzzle Solvingcited by 10
  26. 2025A Solver-in-the-Loop Framework for Improving LLMs on Answer Set Programming for Logic Puzzle Solvingcited by 4
  27. 2025JudgeAgent: Beyond Static Benchmarks for Knowledge-Driven and Dynamic LLM Evaluationcited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 4.

4 papers.

  1. 2026Probabilistic Tiny Recursive Modelcited by 16
  2. 2026Energy-guided Recursive Modelcited by 1
  3. 2026ComplexityWorld: Benchmarking Vision-Language Models on Verifiable Visual Decision Makingcited by 0
  4. 2026SMTrap: Cost-Effective DoS Attacks Against Large Reasoning Models via SMT Conflict Guidancecited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025VerifyBench: A Systematic Benchmark for Evaluating Reasoning Verifiers Across Domains
  2. 2026Recurrent Reasoning on Symbolic Puzzles with Sequence Models
  3. 2026Empirical Evidence of Complexity-Induced Limits in Large Language Models on Finite Discrete State-Space Problems with Explicit Validity Constraints
  4. 2025ReProbe: Efficient Test-Time Scaling of Multi-Step Reasoning by Probing Internal States of Large Language Models
  5. 2025EnigmaEval: A Benchmark of Long Multimodal Reasoning Challenges
  6. 2025Reasoning Large Language Model Errors Arise from Hallucinating Critical Problem Features
  7. 2024On the Self-Verification Limitations of Large Language Models on Reasoning and Planning Tasks
  8. 2026The Complexity Ceiling Benchmark: A Multi-Domain Evaluation of Sequential Reasoning Under Depth Scaling