How Well Do LLMs Perform on the Simplest Long-Chain Reasoning Tasks: An Empirical Study on the Equivalence Class Problem

• URL: http://arxiv.org/abs/2605.06882v1
• Date: Thu, 07 May 2026 19:31:43 GMT
• Title: How Well Do LLMs Perform on the Simplest Long-Chain Reasoning Tasks: An Empirical Study on the Equivalence Class Problem
• Abstract summary: We evaluate Large Language Models' performance on the simplest yet long-chain reasoning task.<n>Non-reasoning models fail ECP, while reasoning models are significantly better but still struggle to completely solve this problem.
• Score: 5.006638589584725
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: Large Language Models (LLMs) have achieved great improvements in recent years. Nevertheless, it still remains unclear how good LLMs are for reasoning tasks, especially for long-chain ones. In this paper, we evaluate LLMs' performance on the simplest yet long-chain reasoning task, namely the Equivalence Class Problem (ECP), i.e., determining whether two variables are equal given a set of randomly generated equivalence relations. We consider both reasoning and non-reasoning representative LLMs over a large variety of problem instances, ranging over different numbers of variables, connectivity probabilities, prompts, and other factors. The experimental results show that non-reasoning LLMs fail ECP, while reasoning models are significantly better but still struggle to completely solve this problem. Interestingly, considering various connectivity probabilities with a fixed number of variables, we observe that, for non-reasoning models, the hardest problem instances coincide with the phase transition point of ln n/(n-1), suggesting the chaos of the problem; in contrast, for reasoning models, the hardest ones coincide with the biggest diameter, suggesting the reasoning difficulty of the problem.

Related papers

• A State-Transition Framework for Efficient LLM Reasoning [58.18141262230392]
  Long Chain-of-Thought (CoT) reasoning significantly improves Large Language Models (LLMs) performance on complex reasoning tasks.<n>Existing studies usually enhance the reasoning efficiency of LLMs by compressing CoT sequences.<n>We propose an efficient reasoning framework that models the reasoning process of LLMs as a state-transition process.
  arXiv  Detail & Related papers  (2026-02-01T12:40:40Z)
• Frontier LLMs Still Struggle with Simple Reasoning Tasks [53.497499123166804]
  This work studies the performance of frontier language models on a broad set of "easy" reasoning problems.<n>We create a suite of procedurally generated simple reasoning tasks, including counting, first-order logic, proof trees, and travel planning.<n>We show that even state-of-the-art thinking models consistently fail on such problems and for similar reasons.
  arXiv  Detail & Related papers  (2025-07-09T22:22:49Z)
• Have Large Language Models Learned to Reason? A Characterization via 3-SAT Phase Transition [11.422434149376478]
  Large Language Models (LLMs) have been touted as AI models possessing advanced reasoning abilities.<n>In theory, autoregressive LLMs with Chain-of-Thought (CoT) can perform more serial computations to solve complex reasoning tasks.<n>Recent studies suggest that, despite this capacity, LLMs do not truly learn to reason but instead fit on statistical features.
  arXiv  Detail & Related papers  (2025-04-04T20:57:36Z)
• A Knapsack by Any Other Name: Presentation impacts LLM performance on NP-hard problems [64.05451567422342]
  We introduce the dataset of Everyday Hard Optimization Problems (EHOP), a collection of NP-hard problems expressed in natural language.<n>EHOP includes problem formulations that could be found in computer science textbooks (e.g., graph coloring), versions that are dressed up as problems that could arise in real life.<n>We find that state-of-the-art LLMs, across multiple prompting strategies, solve textbook problems more accurately than their real-life and inverted counterparts.
  arXiv  Detail & Related papers  (2025-02-19T14:39:59Z)
• CounterBench: A Benchmark for Counterfactuals Reasoning in Large Language Models [5.409370027524351]
  We evaluate the performance of large language models (LLMs) in counterfactual reasoning.<n>We introduce a new benchmark dataset, CounterBench, comprising 1K counterfactual reasoning questions.
  arXiv  Detail & Related papers  (2025-02-16T06:19:37Z)
• 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)
• Order Matters in Hallucination: Reasoning Order as Benchmark and Reflexive Prompting for Large-Language-Models [0.0]
  Large language models (LLMs) have generated significant attention since their inception, finding applications across various academic and industrial domains.<n>LLMs often suffer from the "hallucination problem", where outputs, though grammatically and logically coherent, lack factual accuracy or are entirely fabricated.
  arXiv  Detail & Related papers  (2024-08-09T14:34:32Z)
• Aggregation of Reasoning: A Hierarchical Framework for Enhancing Answer Selection in Large Language Models [84.15513004135576]
  Current research enhances the reasoning performance of Large Language Models (LLMs) by sampling multiple reasoning chains and ensembling based on the answer frequency. This approach fails in scenarios where the correct answers are in the minority. We introduce a hierarchical reasoning aggregation framework AoR, which selects answers based on the evaluation of reasoning chains.
  arXiv  Detail & Related papers  (2024-05-21T17:12:19Z)
• FCoReBench: Can Large Language Models Solve Challenging First-Order Combinatorial Reasoning Problems? [25.352721856952655]
  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.
  arXiv  Detail & Related papers  (2024-02-04T20:56:09Z)
• Can Large Language Models Infer Causation from Correlation? [104.96351414570239]
  We test the pure causal inference skills of large language models (LLMs) We formulate a novel task Corr2Cause, which takes a set of correlational statements and determines the causal relationship between the variables. We show that these models achieve almost close to random performance on the task.
  arXiv  Detail & Related papers  (2023-06-09T12:09:15Z)

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.