Puzzle Solving using Reasoning of Large Language Models: A Survey (2024)

Abstract: 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.

## introduction recent developments in llms such as @xcite and @xcite have showcased their logical reasoning abilities across various domains @xcite @xcite . despite these advances and their demonstrated capabilities in deductive reasoning @xcite , llms face limitations in inductive reasoning settings, as analyzed by @xcite ; @xcite . the specific application of llms to puzzle solving, has not been thoroughly summarized. our main contributions are as follows: 1 we introduce a distinction between rule-based and ruleless puzzles ( §2), highlighting the varied knowledge demands necessary to tackle them. @xcite we analyze the methodologies llms use to solve puzzles ( §3), assessing their impact on each category and comparing them with conventional problemsolving methods. 3 a detailed exploration of existing benchmarks that gauge models' reasoning abilities is conducted ( §4). 4 finally, this paper offers a detailed view of the present obstacles faced in puzzle-solving with llms and highlights a wide array of prospects for future research ( §5). our categorization diverges from existing logical reasoning taxonomies by emphasizing on the underlying cognitive processes and the skills required for puzzle solving, rather than the question format @xcite or the nature of reasoning (deductive, inductive, abductive) @xcite @xcite @xcite . for instance, the existence of rules in puzzles such as sudoku, crosswords, or minesweeper necessitates additional skills (e.g. strategy development) to correctly understand the game's rules or the ability to correctly format the output. in contrast, rule-less puzzles, such as riddles (figure 1 ), programming challenges, and commonsense reasoning problems, leverage the model's inherent knowledge for solution derivation. in our work, we define puzzles as problems that test cognitive abilities including logical reasoning, spatial cognition, and creative thinking by requiring the solver to discern patterns, apply deduction, and combine insights from available information in order to arrive at the correct solution. notably, ## categorization of puzzle problems in assessing llms' reasoning capabilities, it is essential to categorize puzzles into coherent groups. we distinguish puzzles by their reliance on formal rules or broader world knowledge accompanied by general inferential skills, as illustrated in figure 2 . this categorization not only highlights the cognitive diversity puzzles present, but also aligns with distinct reasoning challenges: rule-based puzzles demand logical deduction and strategic foresight within closed environments with defined parameters, whereas rule-less puzzles require general reasoning abilities, interpreting situations and explaining events by drawing inferences based on practical knowledge about the everyday world. by separating puzzles into these categories, we aim to provide a nuanced analysis of llms' problem-solving abilities, reflecting on both structured challenges and those necessitating broader inferential reasoning. ## methods and strategies in applying llms to puzzle solving, a wide array of methods and strategies enhances complex reasoning and performance. this section outlines the approaches used to address puzzles, aiming to highlight their application within this unique context. 2021 ), we concentrate on the techniques most prevalent for puzzle solving, instead of describing each method separately. we divide existing methods into prompting techniques, neuro-symbolic approaches for puzzle translation and fine-tuning for specific domains. a detailed overview of the methods utilized across different puzzle categories is presented in ## datasets, benchmarks and tasks exploring diverse datasets, benchmarks, and tasks is crucial for evaluating llms in puzzle-solving. this section examines datasets within our puzzle taxonomy, encompassing formats, evaluation metrics, and methodologies. figure 2 provides a detailed summary of datasets utilized across the taxonomy's categories, organized according to puzzle type. the analysis demonstrates llms' versatility and the impact of techniques discussed in §3. ## discussion and future directions applied methods and dataset gaps: across our puzzle taxonomy, methods such as few-shot prompting, cot, use of introductions and finetuning are commonly employed across most categories. rule-based deterministic and rule-less commonsense puzzles show the greatest methodological variety, while riddles are also see diverse approaches. in contrast, rule-based stochastic and rule-less programming puzzles exhibit less variety, likely due to fewer studies in these areas. figure 2 reveals that a substantial number of datasets are available for rule-based deterministic puzzles, such as sudoku and rubik's cube, as well as a variety of rule-less riddles. this indicates a strong research interest and resource availability in these domains. however, there appears to be a scarcity of datasets for rule-based stochastic puzzles and rule-less programming puzzles. this gap highlights an opportunity for further research and dataset creation to introduce more diverse challenges for advancing the problem-solving capabilities of llms. the lack of benchmarks for stochastic puzzles led us to include tasks like card and social deduction games, which share core characteristics with traditional puzzles involving incomplete information. additionally, neuro-symbolic techniques that translate natural language into code remain notably underutilized in puzzle benchmarks, suggesting a potential area for future exploration. comparatively, prompting methods like cot and tot enhance complex reasoning abilities without altering the underlying model parameters, yet their effectiveness on smaller llms requires further exploration. moreover, methods such as tot or got necessitate a greater number of model invocations compared to cot and xot, which could impact their efficiency and scalability @xcite . fine-tuning, while fundamentally enhances reasoning by altering model parameters, is constrained by its specificity to particular tasks. for instance, models fine-tuned on csqa have been observed to perform worst on the riddlesense dataset than models fine-tuned directly on riddlesense @xcite , and a model fine-tuned on poker games may not perform well on tasks like solving a rubik's cube. finally, puzzle translation methods primarily test the model's ability to interpret and rephrase problems rather than directly solve them, which tends to have a more limited impact on complex reasoning compared to the other two categories of methods. ## conclusion in this survey, we propose a taxonomy of puzzles for evaluating llms, categorizing them into rulebased (deterministic and stochastic) and rule-less puzzles (riddles, programming, and commonsense reasoning puzzles). we explore a spectrum of methods for llm-based puzzle solving, ranging from prompting techniques to neuro-symbolic strategies and fine-tuning. by collating existing datasets in this domain, we provide a comprehensive overview of the resources available for such evaluations. our analysis identifies current challenges, revealing a difficulty of most methods to successfully solve puzzles, while we outline future directions, emphasizing the need for advanced methodologies and diverse datasets to enhance llms' proficiency in puzzle solving.