# FCoReBench: Can Large Language Models Solve Challenging First-Order Combinatorial Reasoning Problems?

arXiv: https://arxiv.org/abs/2402.02611 · HTML: https://mlsanity.com/paper/2402.02611/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Placed in Mathematical reasoning, one of 17 directions in LLM reasoning.
- Builds on 6 of its 52 references that are in the map.
- First posted on arXiv 4 Feb 2024.

## Placed in

- LLM reasoning / [Mathematical reasoning](https://mlsanity.com/lr/mathematical-reasoning/)

## Builds on (most cited first, 6 of 6)

- [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [FOLIO: Natural Language Reasoning with First-Order Logic](https://mlsanity.com/paper/2209.00840/) (2022)
- [ART: Automatic multi-step reasoning and tool-use for large language models](https://mlsanity.com/paper/2303.09014/) (2023)
- [Progressive-Hint Prompting Improves Reasoning in Large Language Models](https://mlsanity.com/paper/2304.09797/) (2023)
- [NPHardEval: Dynamic Benchmark on Reasoning Ability of Large Language Models via Complexity Classes](https://mlsanity.com/paper/2312.14890/) (2023)

## Built on by (most cited first, 16 of 16)

- [InternBootcamp: Boosting LLM Reasoning with Verifiable Task Scaling](https://mlsanity.com/paper/2508.08636/) (2025)
- [EnigmaEval: A Benchmark of Long Multimodal Reasoning Challenges](https://mlsanity.com/paper/2502.08859/) (2025)
- [ScholarEval: Research Idea Evaluation Grounded in Literature](https://mlsanity.com/paper/2510.16234/) (2025)
- [FINEREASON: Evaluating and Improving LLMs' Deliberate Reasoning through Reflective Puzzle Solving](https://mlsanity.com/paper/2502.20238/) (2025)
- [BeyondBench: Contamination-Resistant Evaluation of Reasoning in Language Models](https://mlsanity.com/paper/2509.24210/) (2025)
- [LABOR-LLM: Language-Based Occupational Representations with Large Language Models](https://mlsanity.com/paper/2406.17972/) (2024)
- [Reasoning LLMs are Wandering Solution Explorers](https://mlsanity.com/paper/2505.20296/) (2025)
- [Logic-of-Thought: Empowering Large Language Models with Logic Programs for Solving Puzzles in Natural Language](https://mlsanity.com/paper/2505.16114/) (2025)
- [PuzzlePlex: Benchmarking Foundation Models on Reasoning and Planning with Puzzles](https://mlsanity.com/paper/2510.06475/) (2025)
- [LR^2Bench: Evaluating Long-chain Reflective Reasoning Capabilities of Large Language Models via Constraint Satisfaction Problems](https://mlsanity.com/paper/2502.17848/) (2025)
- [Large Language Models in Numberland: A Quick Test of Their Numerical Reasoning Abilities](https://mlsanity.com/paper/2504.00226/) (2025)
- [Can Language Models Rival Mathematics Students? Evaluating Mathematical Reasoning through Textual Manipulation and Human Experiments](https://mlsanity.com/paper/2412.11908/) (2024)
- [Mind the Gap Between Spatial Reasoning and Acting! Step-by-Step Evaluation of Agents With Spatial-Gym](https://mlsanity.com/paper/2604.09338/) (2026)
- [Language Complexity Measurement as a Noisy Zero-Shot Proxy for Evaluating LLM Performance](https://mlsanity.com/paper/2502.11578/) (2025)
- [Lyria: A Genetic Algorithm-Driven Neuro-Symbolic Reasoning Framework for LLMs](https://mlsanity.com/paper/2507.04034/) (2025)
- [The Percept-V Challenge: Can Multimodal LLMs Crack Simple Perception Problems?](https://mlsanity.com/paper/2508.21143/) (2025)

## Abstract (arXiv)

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.