Test-Time Compute in Chain-of-Thought and Looped Transformers: Simulation and Resource Trade-offs

Increasing test-time compute can improve the reasoning capabilities of large language models. Two prominent approaches are chain-of-thought (CoT), which generates intermediate tokens, and looped Transformers, which repeatedly update a latent workspace. We theoretically compare their execution efficiency at fixed correctness, allowing each architecture to choose its own algorithm. Our main contribution is a matching work–call trade-off for parity that accounts for workspace capacity and the concentration of access costs across rows. In a finite-precision hard-attention/ReLU model with a fixed finite alphabet for retained data, we show that, with sufficient workspace, polylogarithmic work overhead is insufficient to attain the fastest call order under balanced row costs. Concentrating costly reductions in fewer rows can attain this order at linear work. Work includes all evaluated rows, and the lower bound applies to all algorithms in the stated class. Supporting results establish mutual simulation of finite deterministic computations with explicit overhead and a linear-work separation allowing full admitted numerical states: CoT requires linearly many tokens, whereas a compact loop needs logarithmically many calls. A single-GPU study of the explicit constructions illustrates that reducing source reads does not necessarily reduce latency, with the outcome depending on batch size. Learned reasoning quality is outside the scope of this comparison.