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

• URL: http://arxiv.org/abs/2402.02611v3
• Date: Sat, 01 Mar 2025 12:46:25 GMT
• Title: FCoReBench: Can Large Language Models Solve Challenging First-Order Combinatorial Reasoning Problems?
• Authors: Chinmay Mittal, Krishna Kartik, Mausam, Parag Singla,
• Abstract summary: First-order reasoning problems can be instantiated with infinite number of problem instances of varying sizes.<n>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.<n>We propose 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.
• Score: 25.352721856952655
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• MetaLadder: Ascending Mathematical Solution Quality via Analogical-Problem Reasoning Transfer [37.81465564673498]
  Large Language Models (LLMs) have demonstrated promising capabilities in solving mathematical reasoning tasks. We propose textbfMetaLadder, a framework that explicitly prompts LLMs to recall and reflect on meta-problems. Our experiments on mathematical benchmarks demonstrate that our MetaLadder significantly boosts LLMs' problem-solving accuracy.
  arXiv  Detail & Related papers  (2025-03-19T04:36:35Z)
• EHOP: A Dataset of Everyday NP-Hard Optimization Problems [66.41749917354159]
  Everyday Hard Optimization Problems (EHOP) is a collection of NP-hard optimization problems expressed in natural language. EHOP includes problem formulations that could be found in computer science textbooks, versions that are dressed up as problems that could arise in real life, and variants of well-known problems with inverted rules. We find that state-of-the-art LLMs, across multiple prompting strategies, systematically solve textbook problems more accurately than their real-life and inverted counterparts.
  arXiv  Detail & Related papers  (2025-02-19T14:39:59Z)
• Prompting Strategies for Enabling Large Language Models to Infer Causation from Correlation [68.58373854950294]
  We focus on causal reasoning and address the task of establishing causal relationships based on correlation information. We introduce a prompting strategy for this problem that breaks the original task into fixed subquestions. We evaluate our approach on an existing causal benchmark, Corr2Cause.
  arXiv  Detail & Related papers  (2024-12-18T15:32:27Z)
• Gap-Filling Prompting Enhances Code-Assisted Mathematical Reasoning [0.0]
  Chain-of-thought (CoT) and program-of-thought (PoT) fine-tuning are common methods to transfer LLM knowledge to small language models (SLMs) This paper introduces Gap-Filling Prompting (GFP), a novel two-step prompting strategy designed to enhance the problem-solving process for SLMs.
  arXiv  Detail & Related papers  (2024-11-08T08:52:59Z)
• Not All LLM Reasoners Are Created Equal [58.236453890457476]
  We study the depth of grade-school math problem-solving capabilities of LLMs. We evaluate their performance on pairs of existing math word problems together.
  arXiv  Detail & Related papers  (2024-10-02T17:01:10Z)
• Graph Reasoning with Large Language Models via Pseudo-code Prompting [25.469214467011362]
  This paper investigates whether prompting via pseudo-code instructions can improve the performance of large language models (LLMs) in solving graph problems. Our experiments demonstrate that using pseudo-code instructions generally improves the performance of all considered LLMs.
  arXiv  Detail & Related papers  (2024-09-26T14:52:40Z)
• Step-by-Step Reasoning to Solve Grid Puzzles: Where do LLMs Falter? [36.14795256060537]
  We develop GridPuzzle, an evaluation dataset comprising 274 grid-based puzzles with different complexities. Second, we propose a new error taxonomy derived from manual analysis of reasoning chains from LLMs including GPT-4, Claude-3, Gemini, Mistral, and Llama-2. Third, we develop an LLM-based framework for large-scale subjective evaluation (i.e., identifying errors) and an objective metric, PuzzleEval, to evaluate the correctness of reasoning chains.
  arXiv  Detail & Related papers  (2024-07-20T07:43:07Z)
• Solving for X and Beyond: Can Large Language Models Solve Complex Math Problems with More-Than-Two Unknowns? [57.80779199039929]
  Large Language Models (LLMs) have demonstrated remarkable performance in solving math problems. This paper introduces a novel benchmark, BeyondX, designed to address these limitations by incorporating problems with multiple unknowns. Empirical study on BeyondX reveals that the performance of existing LLMs, even those fine-tuned specifically on math tasks, significantly decreases as the number of unknowns increases.
  arXiv  Detail & Related papers  (2024-07-06T17:01:04Z)
• Solving Zebra Puzzles Using Constraint-Guided Multi-Agent Systems [25.0042181817455]
  We introduce a multi-agent system, ZPS, that integrates Large Language Models with an off the shelf theorem prover. This system tackles the complex puzzle-solving task by breaking down the problem into smaller, manageable parts. We also introduce an automated grid puzzle grader to assess the correctness of our puzzle solutions and show that the automated grader is reliable by evaluating it in a user-study.
  arXiv  Detail & Related papers  (2024-07-04T14:22:25Z)
• MathOdyssey: Benchmarking Mathematical Problem-Solving Skills in Large Language Models Using Odyssey Math Data [20.31528845718877]
  Large language models (LLMs) have significantly advanced natural language understanding and demonstrated strong problem-solving abilities. This paper investigates the mathematical problem-solving capabilities of LLMs using the newly developed "MathOdyssey" dataset.
  arXiv  Detail & Related papers  (2024-06-26T13:02:35Z)
• Navigating the Labyrinth: Evaluating and Enhancing LLMs' Ability to Reason About Search Problems [59.72548591120689]
  We introduce a new benchmark, SearchBench, containing 11 unique search problem types. We show that even the most advanced LLMs fail to solve these problems end-to-end in text. Instructing LLMs to generate code that solves the problem helps, but only slightly, e.g., GPT4's performance rises to 11.7%.
  arXiv  Detail & Related papers  (2024-06-18T00:44:58Z)
• PECC: Problem Extraction and Coding Challenges [3.287942619833188]
  We introduce PECC, a novel benchmark derived from Advent Of Code (AoC) challenges and Project Euler. Unlike conventional benchmarks, PECC requires LLMs to interpret narrative-embedded problems, extract requirements, and generate code. Results show varying model performance between narrative and neutral problems, with specific challenges in the Euler math-based subset.
  arXiv  Detail & Related papers  (2024-04-29T15:02:14Z)
• Do Language Models Exhibit the Same Cognitive Biases in Problem Solving as Human Learners? [140.9751389452011]
  We study the biases of large language models (LLMs) in relation to those known in children when solving arithmetic word problems. We generate a novel set of word problems for each of these tests, using a neuro-symbolic approach that enables fine-grained control over the problem features.
  arXiv  Detail & Related papers  (2024-01-31T18:48:20Z)
• Thought Propagation: An Analogical Approach to Complex Reasoning with Large Language Models [62.96551299003463]
  We propose textbftextitThought Propagation (TP) to enhance the complex reasoning ability of Large Language Models. TP first prompts LLMs to propose and solve a set of analogous problems that are related to the input one. TP reuses the results of analogous problems to directly yield a new solution or derive a knowledge-intensive plan for execution to amend the initial solution obtained from scratch.
  arXiv  Detail & Related papers  (2023-10-06T01:40:09Z)
• Fill in the Blank: Exploring and Enhancing LLM Capabilities for Backward Reasoning in Math Word Problems [17.80128896525717]
  backward reasoning is relatively unexplored. backward reasoning can be seen as the ''inverse'' of forward reasoning. We propose variations of three different forward reasoning strategies to improve performance.
  arXiv  Detail & Related papers  (2023-10-03T12:03:06Z)
• Faith and Fate: Limits of Transformers on Compositionality [109.79516190693415]
  We investigate the limits of transformer large language models across three representative compositional tasks. These tasks require breaking problems down into sub-steps and synthesizing these steps into a precise answer. Our empirical findings suggest that transformer LLMs solve compositional tasks by reducing multi-step compositional reasoning into linearized subgraph matching.
  arXiv  Detail & Related papers  (2023-05-29T23:24:14Z)
• PAL: Program-aided Language Models [112.94785609781503]
  We present Program-Aided Language models (PaL) to understand natural language problems. PaL offloads the solution step to a programmatic runtime such as a Python interpreter. We set new state-of-the-art results in all 12 benchmarks.
  arXiv  Detail & Related papers  (2022-11-18T18:56:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.