Sample Complexity and Representation Ability of Test-time Scaling Paradigms

This paper investigates the theoretical underpinnings of test-time scaling methods used to enhance Large Language Models (LLMs) for complex tasks. It compares the sample efficiency of self-consistency and best-of-n strategies, demonstrating that best-of-n requires significantly fewer samples to identify the correct answer. The work then explores the expressiveness of Transformers in a multi-task setting, showing how self-correction mechanisms can enable a single Transformer to simulate online learning and solve various tasks without prior task knowledge. The paper presents theoretical proofs for its findings and provides empirical validation through experiments, highlighting the benefits of self-correction for improving LLM performance.