FCoReBench: Can Large Language Models Solve Challenging First-Order Combinatorial Reasoning Problems?
This work addresses the problem of improving LLMs' reasoning capabilities on complex, scalable combinatorial tasks for AI researchers, though it is incremental as it builds on existing methods with symbolic solvers.
The authors tackled the challenge of large language models (LLMs) solving first-order combinatorial reasoning problems like graph coloring and knapsack, which are NP-hard and vary in size, by introducing FCoReBench, a dataset of 40 problems, and proposing SymPro-LM, a method combining LLMs with symbolic solvers and program interpreters to achieve huge performance gains without LLM calls during inference.
Can the large language models (LLMs) solve challenging first-order combinatorial reasoning problems such as graph coloring, knapsack, and cryptarithmetic? By first-order, we mean these problems can be instantiated with potentially an infinite number of problem instances of varying sizes. They are also challenging being NP-hard and requiring several reasoning steps to reach a solution. While existing work has focused on coming up with datasets with hard benchmarks, there is limited work which exploits the first-order nature of the problem structure. To address this challenge, we present FCoReBench, a dataset of 40 such challenging problems, along with scripts to generate problem instances of varying sizes and automatically verify and generate their solutions. We first observe that LLMs, even when aided by symbolic solvers, perform rather poorly on our dataset, being unable to leverage the underlying structure of these problems. We specifically observe a drop in performance with increasing problem size. In response, we propose a new approach, SymPro-LM, which combines LLMs with both symbolic solvers and program interpreters, along with feedback from a few solved examples, to achieve huge performance gains. Our proposed approach is robust to changes in the problem size, and has the unique characteristic of not requiring any LLM call during inference time, unlike earlier approaches. As an additional experiment, we also demonstrate SymPro-LM's effectiveness on other logical reasoning benchmarks.