Navigating the Labyrinth: Evaluating and Enhancing LLMs' Ability to Reason About Search Problems

最近，大型语言模型在数学和推理基准测试中取得了令人瞩目的表现。然而，它们在逻辑问题和谜题方面仍然经常遇到困难，而这些问题对于人类来说相对容易。为了进一步研究这个问题，我们引入了一个新的基准测试SearchBench，其中包含11种独特的搜索问题类型，每种类型都配备了自动化流水线，以生成任意数量的实例并分析LLM生成的解决方案的可行性、正确性和最优性。我们发现，即使是最先进的LLM在文本中也无法完全解决这些问题，例如，GPT4仅解决了1.4％。SearchBench问题需要考虑多个解决方案路径以及回溯，对自回归模型构成了重大挑战。指示LLM生成解决问题的代码有所帮助，但只有轻微的作用，例如，GPT4的表现提高到11.7％。在这项工作中，我们展示了与A*算法实现相关的上下文学习如何提高性能。当结合我们提出的多阶段多次尝试方法时，这种推广方法的全部潜力就显现出来了，该方法将算法实现分解为两个阶段，并针对第一个阶段进行单元测试验证，将GPT-4的性能提高到57％以上。

SearchBench: A Benchmark for End-to-End Learning and Multi-Stage Reasoning in Complex Search Problems

使用A*算法实现上下文学习，提高大语言模型在复杂搜索问题中的表现。提出了多阶段多尝试方法，将算法实现分为两个阶段，并针对第一阶段进行单元测试验证，将GPT-4的性能提高到57%以上。

论文提出了一个新的基准测试SearchBench，包含11种独特的搜索问题类型，并自动化生成任意数量的实例和分析解决方案的可行性、正确性和最优性。论文使用A*算法实现上下文学习来提高大语言模型在复杂搜索问题中的表现，并提出了多阶段多尝试方法来进一步提高性能。

最近的相关研究包括：1. Learning to Search Better Than Your Teacher，2. Neural Guided Constraint Logic Programming for Program Synthesis，3. Learning to Solve NP-Complete Problems: A Graph Neural Network for Decision TSP。