How Well Do LLMs Perform on the Simplest Long-Chain Reasoning Tasks: An Empirical Study on the Equivalence Class Problem
Authors: Chun Zheng, Lianlong Wu, Bingqian Li et al.
Summary
The authors test LLMs on the Equivalence Class Problem (ECP): given random equivalence relations like "A=B" and "B=C", can the model determine if two variables are equal? This is conceptually simple but requires long chains of reasoning. They test both reasoning (e.g., o1) and non-reasoning models across various problem sizes and configurations. Non-reasoning models fail entirely, while reasoning models do much better but still struggle to fully solve the problem. Interestingly, the hardest instances for non-reasoning models occur at the phase-transition point (ln n / (n-1)), while for reasoning models the hardest cases coincide with maximum graph diameter (longest reasoning chain required).
Main takeaways:
- The Equivalence Class Problem is the simplest possible long-chain reasoning task: deciding if two variables are equal given random equivalence relations
- Non-reasoning LLMs fail completely at ECP, while reasoning models are significantly better but still struggle
- For non-reasoning models, difficulty peaks at the phase-transition connectivity probability (ln n / (n-1)), suggesting they're sensitive to problem chaos
- For reasoning models, difficulty peaks when the equivalence graph has maximum diameter (longest chain needed), suggesting they struggle with reasoning length
- This simple problem reveals fundamental differences in how reasoning vs. non-reasoning models handle long-chain inference
Relevance
Not directly related to my persona/midtraining work. This is about reasoning capabilities and chain length, whereas I'm studying how behaviors are installed and conditioned. Potentially relevant if I ever need to test whether certain personas exhibit different reasoning capabilities or if reasoning ability is affected by persona-conditioning.
Abstract
arXiv:2605.06882v1 Announce Type: new 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.