PaperlayerView exact revision on arXiv

Source-linked AI summary

Puzzle Solving using Reasoning of Large Language Models: A Survey

Panagiotis Giadikiaroglou, Maria Lymperaiou, Giorgos Filandrianos, Giorgos Stamou

arXiv:2402.11291v3cs.CLcs.AI

TL;DR

LLMs have demonstrated deductive reasoning, but their puzzle-solving capabilities and limitations have not been thoroughly synthesized. This survey categorizes puzzles and reviews methods and benchmarks; it finds persistent difficulty on complex puzzles and gaps from human-level performance in some categories.

  • Problem

    LLMs have demonstrated deductive-reasoning abilities but face limitations in inductive reasoning, and their puzzle-solving application has not been thoroughly summarized.

    Source: §1 · p. 1

  • Method

    The survey distinguishes rule-based and rule-less puzzles and reviews puzzle-solving methods, benchmarks, and reasoning approaches.

    Source: §1 · p. 1, §3 · p. 3

  • Results

    LLMs trail human performance on riddles and commonsense puzzles, struggle with complex multi-step settings and programming puzzles, and find free-text formats harder than multiple choice.

    Source: §5 · p. 9

  • Takeaways & Limitations

    The survey identifies a need for advanced methods and diverse datasets to improve LLM puzzle-solving proficiency.

    Source: §6 · p. 9

    The review covers methods from the past four years, primarily from ACL, EMNLP, NAACL, NeurIPS, ICLR, and arXiv.

    Source: Limitations · p. 10

Abstract

from arXiv · show

Exploring the capabilities of Large Language Models (LLMs) in puzzle solving unveils critical insights into their potential and challenges in AI, marking a significant step towards understanding their applicability in complex reasoning tasks. This survey leverages a unique taxonomy -- dividing puzzles into rule-based and rule-less categories -- to critically assess LLMs through various methodologies, including prompting techniques, neuro-symbolic approaches, and fine-tuning. Through a critical review of relevant datasets and benchmarks, we assess LLMs' performance, identifying significant challenges in complex puzzle scenarios. Our findings highlight the disparity between LLM capabilities and human-like reasoning, particularly in those requiring advanced logical inference. The survey underscores the necessity for novel strategies and richer datasets to advance LLMs' puzzle-solving proficiency and contribute to AI's logical reasoning and creative problem-solving advancements.

1 Introduction

The survey addresses the limited synthesis of LLM puzzle-solving research by distinguishing rule-based from rule-less puzzles and reviewing methods, benchmarks, challenges, and research opportunities.

1 Introduction

  • LLMs have shown deductive-reasoning capabilities, but face limitations in inductive reasoning, and their application to puzzle solving has not been thoroughly summarized.Source: §1 · p. 1
  • The survey distinguishes rule-based puzzles, which require following explicit rules, from rule-less puzzles, which draw on models’ inherent knowledge.Its categorization emphasizes cognitive processes and skills rather than question format or reasoning type.Source: §1 · p. 1
  • The survey analyzes methods across puzzle categories, compares them with conventional approaches, reviews benchmarks, and outlines obstacles and future research directions.Source: §1 · p. 1
  • The review excludes puzzles that cannot be expressed in text, puzzles requiring multimodal understanding, and mathematical puzzles.Mathematical puzzles are excluded because Liu et al. (2023c) recently covered that area.Source: §1 · p. 2

2 Categorization of Puzzle Problems

The taxonomy separates puzzles by their reliance on formal rules or broader world knowledge, linking each category to distinct reasoning demands.

2 Categorization of Puzzle Problems

  • The taxonomy groups puzzles by reliance on formal rules or broader world knowledge and inferential skills, distinguishing closed-environment deduction from everyday contextual inference.Source: §2 · p. 2

2.1 Rule-based Puzzles

  • Rule-based puzzles specify victory conditions, legal moves, or state transitions; stochastic variants add uncertainty, hidden information, and risk management.Deterministic games yield the same successor state for a given state and action, whereas stochastic games can yield different probability distributions over next states.Source: §2.1 · p. 2

2.2 Rule-less Puzzles

  • Rule-less puzzles rely on flexible thinking and real-world knowledge, encompassing riddles, programming puzzles, and commonsense reasoning problems.They call for contextual interpretation, conceptual combination, or inference from code semantics and unstated assumptions.Source: §2.2 · p. 3

3 Methods and Strategies

The survey organizes puzzle-solving methods into prompting, neuro-symbolic translation, and fine-tuning, and summarizes how they perform across puzzle categories.

3.1 Prompting Methods

  • Intermediate reasoning prompts can improve performance across puzzle categories, but supplementary information is not uniformly helpful and can worsen results on Chinese riddles.Source: §3.1 · pp. 3–4
  • CoT-style chain prompting has demonstrated superiority over simple input-output prompts; Detective Thinking Prompt achieves the study’s best results, but does not exceed GPT-4’s best-model accuracy of 61.6%.Source: §3.1 · p. 3
  • Self-Consistency yields small gains over CoT on deterministic puzzles but no clear commonsense benefit, whereas Tree-of-Thoughts improves deterministic-puzzle success rates.Tree-of-Thoughts gains range from 26% to 70%, depending on the puzzle and tree depth, with increased LLM invocations.Source: §3.1 · p. 4
  • XoT achieves the strongest results among the tested graph methods, improving results from 53% to 69% compared to ToT while using the fewest LLM invocations.Source: §3.1 · p. 4

3.2 Puzzle Translation

  • Neuro-symbolic translation turns natural-language puzzles into logic rules for symbolic solvers, but the surveyed approaches do not test the LLM’s puzzle-solving capacity directly.GPT-4 reached 92% accuracy on a logic-puzzles dataset after translation to ASP, versus 7% in few-shot and 21% in zero-shot settings.Source: §3.2 · p. 4
  • The survey found no studies translating natural-language puzzles into code and no rule-less puzzle studies in this translation context.It points to Program of Thoughts and Program-Aided Language as techniques to explore for puzzle-solving tasks.Source: §3.2 · pp. 4–5

Logical Reasoning

  • Fine-tuning can transfer logical-reasoning knowledge across tasks, with LoGiPT mimicking symbolic solvers and LogiT5 using multi-task learning.Source: Logical Reasoning · p. 5

Rule-based Puzzles

  • Fine-tuning results vary across puzzle categories: proof- and CoT-based tuning performs strongly for rule-based puzzles, while transfer from CommonsenseQA improves ALBERT-XXL accuracy by 4% over simple fine-tuning on riddles.Other rule-based fine-tuning studies report suboptimal or mixed results; fine-tuning also applies to commonsense and programming puzzles.Source: Rule-based Puzzles · p. 5, Rule-less Puzzles · p. 5

4 Datasets, Benchmarks and Tasks

The survey reviews puzzle datasets and evaluation approaches across rule-based and rule-less categories, covering task formats, metrics, and reported model performance.

4 Datasets, Benchmarks and Tasks

  • The dataset review organizes benchmarks by puzzle type and examines their formats, metrics, and evaluation methods.Figure 2 summarizes datasets across the taxonomy’s categories.Source: §4 · p. 5

4.1 Rule-based Puzzles

  • Rule-based datasets cover deterministic puzzles and stochastic games, but research focuses predominantly on deterministic tasks, leaving uncertainty under-addressed.The review includes Sudoku, Rubik’s Cube, Crosswords, and 8-puzzle alongside Minesweeper, card games, and social deduction games.Source: §4.1 · p. 5

4.1.1 Deterministic Puzzles

  • Rule-based puzzle studies report strong XoT results: on 2×2×2 Rubik’s Cube, self-revision reaches 77.6% success, and on 419 8-Puzzles, revision achieves 93.2% accuracy; crossword clue-answer accuracy remains below 30%.In Sudoku, Tree-of-Thought is most effective, especially on smaller puzzles.Source: §4.1.1 · pp. 5–6

4.1.2 Stochastic Puzzles

  • Rule-based stochastic tasks expose uncertainty: missing information lowers fine-tuned BoardgameQA accuracy, GPT-4 struggles to finish Minesweeper boards, and Poker and social-game results vary by model or framework.Coordinate representations aid Minesweeper comprehension; Poker models grasp advanced strategies without reaching GTO play, while Werewolf and Avalon frameworks use interaction histories or social deduction.Source: §4.1.2 · pp. 6–7

4.2 Rule-less Puzzles

  • Rule-less puzzle coverage centers on riddles, programming puzzles, and commonsense reasoning, mostly evaluated as multiple-choice question-answering, with other formats noted.The survey excludes code-generation datasets as a distinct task type.Source: §4.2 · p. 7

4.2.1 Riddles

  • Riddle benchmarks reveal varied strengths and persistent limits: larger models often perform better, but lateral thinking, metaphor, counterfactual, and free-response puzzles remain difficult.BiRdQA finds a performance gap from human understanding, with context aids benefiting English but not Chinese riddles; MARB finds IEP combined with CoT most effective.Source: §4.2.1 · p. 7

4.2.2 Programming Puzzles

  • Programming-puzzle studies find that descriptive prompts aid solving, code inclusion increases complexity, and performance depends on question format and specialized coding capability.P3 relates puzzle difficulty for models and humans; code-completion-proficient models solve more puzzles with fewer tries.Source: §4.2.2 · pp. 7–8

4.2.3 Commonsense Reasoning Puzzles

  • Across commonsense puzzles, models face difficult inference: Golden-CoT raises detective-puzzle accuracy, hints help, and human-level performance remains a substantial gap.GPT-4 matches human solver results on True Detective with Golden-CoT; LatEval finds GPT-4 has the highest answer consistency, but question relevance remains limited.Source: §4.2.3 · p. 8

5 Discussion and Future Directions

The discussion finds uneven benchmark coverage and varied model performance across puzzle categories, while identifying method constraints, format effects, and limited puzzle-generation research.

Applied Methods and Dataset Gaps

  • Datasets are concentrated in deterministic rule-based puzzles and riddles, with scarcity in stochastic rule-based and programming puzzles; neuro-symbolic translation remains underused.The survey includes card and social deduction games because stochastic-puzzle benchmarks are scarce.Source: §5 · pp. 8–9

Method Limitations

  • ToT and GoT require more model invocations than CoT and XoT, smaller-model effectiveness needs further study, and fine-tuning is task-specific.Puzzle translation mainly tests interpretation and rephrasing rather than directly solving, with more limited impact on complex reasoning than other method categories.Source: §5 · p. 9

Performance Analysis

  • Performance remains uneven: complex stochastic tasks and rule-less riddles and commonsense puzzles challenge LLMs, while programming puzzles remain difficult for both models and humans.ToT and XoT typically improve reasoning as deterministic structure grows, but BoardgameQA and crossword results are generally poor; multiple-choice formats simplify tasks relative to free text.Source: §5 · p. 9

Question Format

  • Multiple-choice setups narrow the solution search space, whereas free-text formats increase puzzle difficulty.Source: §5 · p. 9

Puzzle Generation

  • Puzzle-generation research is limited and mixed: GPT-3.5 generation attempts perform poorly, while ACES uses LLM-produced semantic descriptors for diverse programming puzzles.The survey primarily focuses on puzzle solving and also notes work generating multilingual crossword puzzles.Source: §5 · p. 9

6 Conclusion

The survey proposes a rule-based and rule-less puzzle taxonomy, reviews LLM-solving methods and datasets, and identifies challenges and future directions.

6 Conclusion

  • The survey categorizes rule-based puzzles as deterministic or stochastic and rule-less puzzles as riddles, programming, or commonsense reasoning tasks.It reviews prompting, neuro-symbolic strategies, fine-tuning, and available evaluation datasets, finding that most methods struggle to solve puzzles successfully.Source: §6 · p. 9

Limitations

The survey's coverage is constrained by the field's rapid evolution, page limits, and a review window focused on recent work from selected sources. Its conclusions also reflect empirical analysis and the authors' interpretations.

Limitations

  • The rapidly evolving field may leave some recent developments out of the survey.The authors say they continuously add related approaches and analyses.Source: Limitations · p. 10
  • Page constraints limit the methods and technical details presented, which may reduce some readers' depth of understanding.The review covers methods within four years, primarily from ACL, EMNLP, NAACL, NeurIPS, ICLR, and arXiv.Source: Limitations · p. 10
  • The conclusions rely on empirical analysis and interpretations that may differ from those of other researchers.The authors note empirical analysis may not capture all aspects of the problem.Source: Limitations · p. 10

A.1 Prompting Topologies

Prompting topologies vary from stepwise or multiple-path reasoning to tree- and graph-structured exploration. Self-correction has mixed reported effects, while backtracking can improve correction when error locations are given.

Prompting Topologies

  • Chain-of-thought prompts stepwise explanatory reasoning, while self-consistency generates multiple paths and selects the most coherent one.The cited work describes chain-of-thought as bolstering zero-shot capabilities.Source: §A.1 · p. 15
  • Self-correction's broader gains are often elusive and some strategies reduce reasoning accuracy, whereas error-location-informed backtracking significantly boosts correction.The reported impact of automated feedback varies.Source: §A.1 · p. 15
  • TouT explores uncertain branches, ToT pursues a more linear coherent path, and GoT represents interconnected reasoning pathways.GoT allows exploration and evaluation of multiple solutions within a flexible, network-like framework.Source: §A.1 · pp. 15–16

A.2 Conventional Methods

The section contrasts conventional puzzle methods with LLM approaches, emphasizing reliable, interpretable solutions and a possible efficiency trade-off. It surveys examples across rule-based puzzles and notes that its comparison is not intended to identify a universally superior method.

A.2 Conventional Methods

  • The section focuses on rule-based puzzles because their structured environments call for systematic strategies, unlike rule-less puzzles without a clear stepwise path.Rule-less puzzles such as riddles test logical, commonsense reasoning and creativity, and are not analyzed here.Source: §A.2 · p. 16
  • Sudoku backtracking solves puzzles across difficulty levels but slowly, while constraint programming can deduce solutions in milliseconds; LLMs have not exceeded 80% on 5x5 puzzles.The cited conventional methods always find a solution.Source: §A.2 · p. 16
  • Rubik's Cube methods use search and group theory; Korf's method is noted for efficiency, while cited RL approaches take 38.7 to 75.6 seconds.DeepCubeA and other RL approaches find solutions in relatively few steps, with duration varying by method.Source: §A.2 · p. 16
  • Mazes can be solved with depth-first search, A*, or Trémaux's algorithm, while Minesweeper can be framed as a constraint satisfaction problem.The maze discussion also identifies spatial reasoning as a useful test for LLMs.Source: §A.2 · p. 16
  • MCTS surpassed many LLM techniques on Game of 24, 8-Puzzle, and Pocket Cube, while fine-tuned T5 performed best among the cited crossword baselines.The crossword comparison includes WordNet-based, K-nearest-neighbours bag-of-words, and rule-based models.Source: §A.2 · p. 16
  • Conventional rule-based methods reliably produce interpretable solutions, but can trade reliability for efficiency through increased time complexity.The section does not aim to determine the superior method for each puzzle.Source: §A.2 · p. 16

A.3 Tables

Table 1 maps methods to puzzle categories in the collected benchmarks. The survey uses that landscape to catalogue current applications and identify areas for further exploration.

A.3 Tables

  • The survey identifies neuro-symbolic techniques and selection-inference prompting as absent from the table's coverage and potential areas for expansion.The authors note the prospective benefits of these approaches for LLMs grounded in logical reasoning datasets.Source: §A.3 · p. 17
  • Chain-of-thought, few-shot learning, and fine-tuning appear across multiple puzzle types, reflecting the adaptability of these methods.The authors use the table to highlight opportunities for innovative research in unexplored areas.Source: §A.3 · p. 17
  • Table 1 organizes methods by puzzle category based on the collected benchmarks and shows extensive coverage across rule-based deterministic and rule-less commonsense puzzles.The table is used to catalogue method applications in puzzle-solving with LLMs.Source: Table 1 · p. 17, §A.3 · p. 17

Related papers

Loading 2402.11291v3…