Solving complex problems with LLMs: A new prompting strategy presented at NeurIPS

Since the debut of OpenAI’s ChatGPT two years ago and the subsequent boom in interest in large language models (LLMs), people have explored how these systems can be used for a variety of tasks beyond simply generating text, including those that require problem-solving abilities.

A team of researchers from the Mohamed bin Zayed University of Artificial Intelligence (MBZUAI) and King’s College London recently investigated how LLMs could be used to solve complex challenges known as combinatorial problems. The team developed a new prompting strategy called self-guided exploration that significantly improved the performance of LLMs on these questions. Their findings will be presented at the 38th Annual Conference on Neural Information Processing Systems (NeurIPS), which is being held in Vancouver.

What are combinatorial problems?

Combinatorial problems are difficult to solve and have been a subject of study by scientists for decades. One well-known example is the traveling salesman problem. The solution is to find the shortest route between a set of cities while starting and ending in the same city. The idea sounds straightforward enough, but it turns out that simply choosing to travel from one city to the closest next city doesn’t lead to the optimal solution.

The traveling salesman and other combinatorial problems are interesting for researchers because they are computationally complex and can’t be easily solved with a brute-force approach where all solutions are tried. For example, a traveling salesman problem with 18 cities has more than 6 quadrillion possible routes. Scientists have therefore turned to methods known as heuristics and metaheuristics, which use rules-of-thumb and short cuts to address these problems under certain constraints, making them faster to solve, explains Zangir Iklassov, a doctoral student at MBZUAI and co-author of the study. A trade-off is that heuristic- and metaheuristic-based methods don’t necessarily arrive at the optimal solution. And to be as effective as possible, these methods need to be tailored to the particulars of each situation.

While combinatorial problems are an area of theoretical research by mathematicians, they are also encountered in industries like logistics, planning and scheduling. Google offers a solution called Google-OR-Tools that is designed for industry use, but as Iklassov and his co-authors note in their study, the tool is not useful for highly complex problems. Scientists have also looked at how neural networks can be trained through reinforcement learning to solve combinatorial problems. But neural networks have yet to surpass the performance of traditional heuristics and metaheuristics. New methods that use LLMs to solve combinatorial problems, therefore, could have practical implications for a range of industries.

A new approach: self-guided exploration

Iklassov and his colleagues are the first to apply LLMs to several different kinds of combinatorial problems. Other studies have examined how prompting strategies can be used with LLMs to solve the traveling salesman problem. As more cities were added, however, these approaches struggled to produce adequate results. Additional combinatorial problems, like the vehicle routing and job scheduling problems that are examined in Iklassov’s and his co-authors’ study, hadn’t been previously addressed.

Previous studies applied techniques known as exploration-of-thought, decomposition and refinement to help LLMs break down combinatorial problems in a step-by-step manner. The self-guided exploration approach developed by Iklassov and his colleagues combines all three techniques and outperforms each individually by nearly 28%. The gap in performance between self-guided exploration and the other prompting methods also grew as problems became more difficult. “There isn’t a lot of research on these stochastic combinatorial problems, because they are so complex,” Iklassov says.

Self-guiding exploration creates “multiple thought trajectories” for each task in the process. It breaks down the tasks into subtasks that are solved individually and provides a final answer. The approach is composed of five steps: exploration, decomposition, subtask resolution, feedback and refinement, and integration. “We ask the LLM what it thinks would be the best heuristic or metaheuristic to solve a problem. It creates a trajectory for each one and we ask the LLM to split them into subproblems and they are then combined in a final answer,” Iklassov says.

The researchers tested self-guided exploration on several popular LLMs: OpenAI’s GPT-4 and GPT-3.5, Google’s Gemini-1.5 and Meta’s LLaMA 2. While self-guided exploration performed better across the different combinatorial problems, it was also more computationally costly. Self-guided exploration outperformed the decomposition approach by 27.84% but required 87.89% more function calls. For this reason, Iklassov and his co-authors note in the study that self-guided exploration may be beneficial in situations where performance is the priority above cost.

The performance of self-guided exploration (Ours) compared to other prompting techniques (chain-of-thought, refinement and decomposition) using OpenAI’s GPT-4 and Google’s Gemini-1.5 to solve various combinatorial problems. Self-guided exploration performed significantly better than the other methods with both models.

“We found that LLMs can help solve these problems by combining solutions from different heuristics,” Iklassov says. “We can make this process very fast using LLMs as they already know which heuristics and metaheuristics are good for different kinds of problems and conditions.”

Martin Takáč, deputy department chair of machine learning and associate professor of machine learning at MBZUAI and co-author of the study, adds: “LLMs seem to be able to select the best heuristic faster than a person. It’s hard for a person to read all the research, synthesize it and make sense of it all.”

The researchers also found that their approach improved the performance of LLMs on other reasoning tasks.

Real world impact

The study’s findings indicate that prompting methods like self-guided exploration can enable LLMs to tackle complex problem-solving tasks, significantly enhancing their utility in industries like logistics and resource management. In the real world, however, these problems are even harder to solve because there is randomness, such as traffic and bad weather, that can influence the solution, Takáč says.

The performance of the LLMs in providing solutions to these complex problems raises the question of whether they are truly reasoning. Takáč explains that even if an LLM isn’t technically reasoning when it is asked to solve these problems, it uses data it has memorized in training to provide valuable recommendations for which heuristics would be best to solve certain problems. “If you use a good LLM like GPT, it has seen in training a lot of information about heuristics and metaheuristics and then we can tune our prompt to use it properly,” he says.