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

Authors: Nasim Borazjanizadeh, Roei Herzig, Trevor Darrell, Rogerio Feris, Leonid Karlinsky
Primary area: datasets and benchmarks
Keywords: Mathematical & reasoning benchmark, Search & Combinatorial problems, A* algorithm

Abstract:
Recently, Large Language Models (LLMs) attained impressive performance in math and reasoning benchmarks. However, they still often struggle with multi-step reasoning which is relatively easy for humans. To further investigate this, we introduce a new benchmark, SearchBench, containing 11 unique combinatorial problems that avoid training contamination (each equipped with automated pipelines to generate an arbitrary number of instances) and analyze the feasibility, correctness, and optimality of LLM-generated solutions. We show that even the most advanced LLMs fail to solve these problems end-to-end in text, e.g., GPT4 and o1-preview respectively solve only 1.4% and 18.6% correctly. SearchBench problems require considering multiple pathways to the solution and backtracking, posing a significant challenge to auto-regressive models. Instructing LLMs to generate code that solves the problem helps only slightly. We next introduce an in-context learning approach that prompts the model to implement A*, an informed search algorithm, to comprehensively traverse the problem state space, improving the performance of models. We further extend this approach and propose the Multi-Stage-Multi-Try inference method which breaks down the A* algorithm implementation into two stages and auto-verifies the first stage against unit tests, raising GPT-4's performance above 57%.

Decision: reject
Reviewer scores: 3, 5, 3

Reviews and discussion:
<thread>
creation date:
1730400510812

thread_type:
official_review

<thread_object>
creator: reviewer_fqts

<content>
summary:
This paper presents SearchBench, a benchmark evaluating large language models (LLMs) on complex combinatorial search tasks that require multi-step reasoning and backtracking. With 11 unique problem types across five categories, SearchBench challenges LLMs by avoiding training contamination and requiring reasoning-intensive solutions. The authors introduce A* search prompting and a Multi-Stage-Multi-Try (MSMT) strategy, which breaks A* implementation into verifiable steps, improving GPT-4’s success rate to over 57% on some tasks. Despite these advances, results reveal LLM limitations in achieving optimal solutions in multi-hop complex problem-solving.

strengths:
1. The use of classic optimization problems with unique rule modifications to prevent LLM familiarity from pre-training is well-designed.
2. SearchBench is a legit benchmark for evaluating LLMs on complex tasks; commendable effort in its generation and diversity.

weaknesses:
1. Using demonstrations from other problem categories deviates from the few-shot learning definition and may serve as distractors[1], which could lower baseline performance.
2. MSMT A* lacks novelty, as combining code generation with external feedback (e.g., compiler feedback and unit test filtering) is now a standard technique in LLM optimization.
3. Presentation could improve: font issues in Figure 3, misuse of "accuracy" on the y-axis of Figure 5, and some redundancy in explanations.

[1] Shi, F., Chen, X., Misra, K., Scales, N., Dohan, D., Chi, E. H., ... & Zhou, D. (2023, July). Large language models can be easily distracted by irrelevant context. In International Conference on Machine Learning (pp. 31210-31227). PMLR.

questions:
1. [Figure3] Are there results for GPT-o1 with A* and MSMT A*, and Code Llama with 0-shot text?
2. Line 268 suggests that models capable of solving SearchBench can generalize to other combinatorial problems; are there experimental results supporting this claim?
3. MSMT A* benefits from multiple tries and unit test prefiltering, which naturally boosts feasibility rates. Would giving other methods an equivalent number of trials make for a fairer comparison?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730660237933

thread_type:
official_review

<thread_object>
creator: reviewer_1qot

<content>
summary:
The work investigates the ability of Large Language Models (LLMs) to solve complex combinatorial search problems that require multi-step reasoning and backtracking. The paper introduces a new benchmark referred as to SearchBench. This new benchmark dataset has 11 unique combinatorial problems that examines LLMs with tasks involving state-based search and backtracking. The authors analyze the feasibility, correctness, and optimality of solutions generated by LLMs. They reported that even advanced models like GPT-4 severely struggle with such tasks.
The authors then propose an A* prompting strategy to guide LLMs in implementing an informed search algorithm (A*). They also presented a Multi-Stage-Multi-Try (MSMT) approach that decomposes the A* algorithm into two stages with unit test verifications, significantly improving model performance. Experimental results show that the MSMT method helps models achieve higher accuracy. Despite these improvements, the authors still observed challenges in optimality and broader reasoning persist. 
Overall, the work contributes SearchBench as a robust benchmark and MSMT A* prompting as an effective strategy for enhancing LLM reasoning capabilities on complex search problems.

strengths:
The paper’s strengths are as follows:

1. The most important contribution of the paper is creation and introduction of SearchBench, presenting a broad set of combinatorial search problems dataset that extend beyond standard benchmarks. It assesses models based on feasibility, correctness, and optimality, providing a detailed assessment of LLM reasoning abilities in combinatorial problems.

2. The paper illustrates that LLMs often struggles in multi-step reasoning and backtracking tasks. As such, the paper underline major issues in current model capabilities. The challenges in SearchBench reflect real-world applications, such as pathfinding and puzzle-solving, that require systematic search and misstep correction.

3. The authors idea of using A* prompting strategy with a Multi-Stage-Multi-Try (MSMT) approach is interesting and shows substantial improvements relative to prompt based solutions alone.  MSMT’s staged and unit-tested code generation approach improves LLM performance, demonstrating a practical way to improve reasoning on complex tasks.

4. The paper provides evaluation of various large language models (e.g., GPT-4, Llama) and also studies various prompting techniques (e.g., 0-shot, Chain-of-Thought, A* prompting). Hence, the paper shows meaningful comparisons across models and prompt based strategies.

weaknesses:
The main weaknesses of the paper:

1. The paper does not consider recent advance works on multi-step reasoning techniques and code synthesis methods using LLM. Instead, the authors solely use prompt based approaches. It is unclear how those advance methods will perform on the proposed dataset.
2. The paper conclusions may not hold for problems that do not have code based solutions. As such it is limited to certain types of problems that can be solved through coding.
3. The evaluations are non comprehensive. The authors give unfair advantage to their MSMT method as the method has prior knowledge about the type of the code it needs to sysnthesize, i.e., code for A-search algorithm. The evaluations should have included recent LLM works who also can synthesis codes and provided with such prior that the code is for A*search. Only then one can better appreciate the proposed code synthesis method.
4. The scalability of Multi-Stage-Multi-Try (MSMT) method is unclear as the method is complex and computationally demanding. Moreover, the simulation-based experiments lack real-world variability, making it difficult to evaluate how well the proposed methods would generalize to other real world problems. 
5. This is less important in my overall rating. But, clearly, SearchBench is centered around combinatorial tasks. Although interesting dataset, it does not support how one could devise LLM methods with other reasoning challenges, such as open-domain problems.

questions:
1. As explained in weakness, the scalability of MSMT is unclear. Can the authors comment as to why this method will not suffer from state space expansion problem when the problem scales to practical scenarios? Since SearchBench is limited to those problems that human can solve correctly, it appears that the scale of the problems are too small for real world problems. 
2. It would be helpful to check and compare the performance of MSMT in other combinatorics tasks outside of the authors own SearchBench dataset.
3. The authors need to evaluate also the performance of other more recent methods in LLM reasoning that are not promote based solely, such as multistep reasoning, reward process modeling, planning with world model and deliberate reasoning techniques, on their SearchBench dataset and compare with those of MSMT. It is u fair to limit compare MSMT with prompt based approaches or LLM that is not boosted to synthesis codes. It is well known that LLm cannot do well in code generation for complex reasoning problems unless they are guided through multiple structured steps.
4. The paper could benefit from detailed analysis on error patterns, which could help identify specific failure areas in LLM reasoning and suggest targeted improvements.
5. What if we do not know the type of the problem and hence do not know if the A search algorithm is the solution. This limits the scope of the work. The paper does not address the issue of algorithm selection. In other words, the proposed MSMT method has the prior knowledge about the code type to generate.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730807297118

thread_type:
official_review

<thread_object>
creator: reviewer_pgfp

<content>
summary:
This paper introduces an approach to using LLM to solve search problems by prompting LLM to implement A*.

strengths:
- The proposed method performs better than directly prompting LLMs to solve the problem or generate code to solve the problem. 
- The paper also proposes a benchmark set with the hope of avoiding training contamination.

weaknesses:
- Using LLMs to generate the A* implementation sounds like an overkill. One could consider simply prompting LLMs to generate the inputs and heuristic function to an existing A* implementation and then prompting LLMs again to interpret the output of the A* algorithm. 
- It seems the paper transforms the effort of implementing the A* algorithm to the effort of implementing a prompting scheme to have LLM generate A*. From this perspective, I don't see a significant motivation to use the method proposed in the paper. On the other hand, if the motivation is to understand the capability of LLMs to solve these types of puzzles, it would be more interesting to consider the scenario where the LLM is not provided a hint about how the problem can be solved (i.e., with A*).

questions:
I would consider an approach that does not resynthesize code that already exists (e.g., like A*) but only prompt LLMs for parameters to the A*.
</content>
</thread_object>

</thread>


Metareview: