Chain-of-Thought Needs Omega(n) Tokens for Graph and Matching Tasks

Using the BAPO theoretical framework, the paper proves that binary majority, triplet matching, and graph reachability each require at least Omega(n) reasoning tokens as input size grows, with frontier model experiments confirming approximately linear scaling and failures under token constraints. Upper bounds via explicit constructions match or nearly match the lower bounds.