Understanding Limitations of Large Language Models from First Principles

Computational Complexity Circuit Class TCk

Abstract

What exactly are the "theoretical limitations in the complexity of problems LRMs can solve, despite their structured reasoning approaches" and how exactly do tool augmentations ameliorate them?

The theoretical limitations of Large Reasoning Models (LRMs) in solving complex problems stem from their inherent computational constraints. Specifically, theoretical analyses based on circuit complexity suggest that a Transformer using k Chain-of-Thought (CoT) steps corresponds to the TCk circuit class. This implies that even multi-step CoT reasoning is limited in the complexity of problems it can solve, as it cannot exceed the computational power of this class. Additionally, LRMs often generate lengthy outputs filled with redundant or irrelevant tokens, which increases inference costs without improving task accuracy. These limitations hinder their ability to handle deeply recursive or highly complex reasoning tasks.