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