Let Me Think! A Long Chain-of-Thought Can Be Worth Exponentially Many Short Ones
This work addresses a key challenge in AI for improving reasoning efficiency in language models, though it is incremental as it focuses on specific graph-based scenarios rather than general reasoning.
The paper tackles the problem of optimizing inference-time computation for large language model reasoning by comparing sequential scaling (longer chains of thought) and parallel scaling (multiple short chains), demonstrating that sequential scaling can offer an exponential advantage in graph connectivity problems. The result is validated through experiments with various models, showing concrete performance gains in these settings.
Inference-time computation has emerged as a promising scaling axis for improving large language model reasoning. However, despite yielding impressive performance, the optimal allocation of inference-time computation remains poorly understood. A central question is whether to prioritize sequential scaling (e.g., longer chains of thought) or parallel scaling (e.g., majority voting across multiple short chains of thought). In this work, we seek to illuminate the landscape of test-time scaling by demonstrating the existence of reasoning settings where sequential scaling offers an exponential advantage over parallel scaling. These settings are based on graph connectivity problems in challenging distributions of graphs. We validate our theoretical findings with comprehensive experiments across a range of language models, including models trained from scratch for graph connectivity with different chain of thought strategies as well as large reasoning models.