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

A new empirical study evaluates how Large Language Models perform on the Equivalence Class Problem, a simple yet computationally demanding long-chain reasoning task. The research reveals that non-reasoning LLMs fail entirely at the task, while reasoning-capable models perform significantly better but still struggle with complete accuracy, with performance patterns differing based on problem complexity metrics.

This research addresses a fundamental gap in understanding LLM reasoning capabilities by testing them on the Equivalence Class Problem—a mathematically pure task requiring determining variable equality through transitive relations. Unlike benchmark datasets that conflate task difficulty with domain knowledge, ECP isolates pure logical reasoning, making it an ideal diagnostic tool for evaluating reasoning performance at scale.

The study's most significant finding is the divergence between reasoning and non-reasoning model families. Non-reasoning LLMs exhibit catastrophic failure, suggesting their pattern-matching architecture cannot handle systematic logical inference across chains. Conversely, models explicitly designed for reasoning substantially improve but still show gaps, indicating that current reasoning approaches remain incomplete even for theoretically simple problems.

The phase transition observation at ln n/(n-1) for non-reasoning models aligns with computational complexity theory, revealing that problem hardness follows predictable mathematical patterns rather than arbitrary difficulty. This contrasts with reasoning models, where diameter becomes the limiting factor—suggesting these models struggle with path-tracing rather than phase-space complexity. This distinction has broad implications for understanding where and why LLMs fail.

For AI development, this research highlights that achieving robust reasoning requires more than scale or instruction tuning. The persistence of failures in reasoning models on fundamentally simple tasks suggests current architectures hit hard ceilings on logical reasoning tasks. This could inform future model designs and prompt developers to rethink approaches to long-chain reasoning. Organizations deploying LLMs for critical reasoning tasks should recognize these limitations when designing safeguards and validation mechanisms.

• →Non-reasoning LLMs completely fail on the Equivalence Class Problem, while reasoning models show significant improvement but remain imperfect.
• →Problem hardness for non-reasoning models peaks at the mathematical phase transition point, suggesting algorithmic limitations rather than learned behavior.
• →Reasoning models struggle most with problems featuring the largest graph diameter, indicating path-tracing difficulty as a core bottleneck.
• →Current LLM reasoning capabilities remain fundamentally limited even on theoretically simple logical inference tasks.
• →The study provides a pure mathematical benchmark for evaluating reasoning without confounding factors from domain knowledge or language understanding.