Sample Complexity and Representation Ability of Test-time Scaling Paradigms

• URL: http://arxiv.org/abs/2506.05295v2
• Date: Thu, 12 Jun 2025 16:25:06 GMT
• Title: Sample Complexity and Representation Ability of Test-time Scaling Paradigms
• Authors: Baihe Huang, Shanda Li, Tianhao Wu, Yiming Yang, Ameet Talwalkar, Kannan Ramchandran, Michael I. Jordan, Jiantao Jiao,
• Abstract summary: Test-time scaling paradigms have advanced the capabilities of large language models (LLMs) on complex tasks.<n>We study the sample efficiency of various test-time strategies, such as self-consistency, best-of-$n$, and self-correction.<n>A single Transformer architecture can provably solve multiple tasks without prior knowledge of the specific task associated with a user query.
• Score: 91.34339030453425
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Test-time scaling paradigms have significantly advanced the capabilities of large language models (LLMs) on complex tasks. Despite their empirical success, theoretical understanding of the sample efficiency of various test-time strategies -- such as self-consistency, best-of-$n$, and self-correction -- remains limited. In this work, we first establish a separation result between two repeated sampling strategies: self-consistency requires $\Theta(1/\Delta^2)$ samples to produce the correct answer, while best-of-$n$ only needs $\Theta(1/\Delta)$, where $\Delta < 1$ denotes the probability gap between the correct and second most likely answers. Next, we present an expressiveness result for the self-correction approach with verifier feedback: it enables Transformers to simulate online learning over a pool of experts at test time. Therefore, a single Transformer architecture can provably solve multiple tasks without prior knowledge of the specific task associated with a user query, extending the representation theory of Transformers from single-task to multi-task settings. Finally, we empirically validate our theoretical results, demonstrating the practical effectiveness of self-correction methods.

Related papers

• Mastering Multiple-Expert Routing: Realizable $H$-Consistency and Strong Guarantees for Learning to Defer [30.389055604165222]
  This paper introduces novel surrogate loss functions and efficient algorithms with strong theoretical learning guarantees.<n>We address open questions regarding realizable $H$-consistency, $H$-consistency bounds, and Bayes-consistency for both single-stage and two-stage learning scenarios.<n>We derive new surrogate losses that achieve realizable $H$-consistency, $H$-consistency bounds, and Bayes-consistency for the two-expert scenario and, under natural assumptions, multiple-expert scenario.
  arXiv  Detail & Related papers  (2025-06-25T17:48:58Z)
• S$^4$C: Speculative Sampling with Syntactic and Semantic Coherence for Efficient Inference of Large Language Models [38.784951111677856]
  Large language models (LLMs) exhibit remarkable reasoning capabilities across diverse downstream tasks.<n>Their autoregressive nature leads to substantial latency inference, posing challenges for real-time applications.<n>We propose a Speculative Sampling with Syntactic and Semantic Coherence framework, which extends speculative sampling by leveraging multi-head drafting.
  arXiv  Detail & Related papers  (2025-06-17T03:38:19Z)
• Learning Compositional Functions with Transformers from Easy-to-Hard Data [63.96562216704653]
  We study the learnability of the $k$-fold composition task, which requires computing an interleaved composition of $k$ input permutations and $k$ hidden permutations.<n>We show that this function class can be efficiently learned, with runtime and sample in $k$, by gradient descent on an $O(log k)$-depth transformer.
  arXiv  Detail & Related papers  (2025-05-29T17:22:00Z)
• IT$^3$: Idempotent Test-Time Training [95.78053599609044]
  Deep learning models often struggle when deployed in real-world settings due to distribution shifts between training and test data.<n>We present Idempotent Test-Time Training (IT$3$), a novel approach that enables on-the-fly adaptation to distribution shifts using only the current test instance.<n>Our results suggest that idempotence provides a universal principle for test-time adaptation that generalizes across domains and architectures.
  arXiv  Detail & Related papers  (2024-10-05T15:39:51Z)
• Training Nonlinear Transformers for Chain-of-Thought Inference: A Theoretical Generalization Analysis [82.51626700527835]
  Chain-of-shift (CoT) is an efficient method that enables the reasoning ability of large language models by augmenting the query using examples with multiple intermediate steps.<n>We show that despite the theoretical success of CoT, it fails to provide an accurate generalization when CoT does.
  arXiv  Detail & Related papers  (2024-10-03T03:12:51Z)
• Sampling Foundational Transformer: A Theoretical Perspective [12.7600763629179]
  We propose Foundational Sampling Transformer (SFT) that can work on multiple data modalities. SFT has achieved competitive results on many benchmarks, while being faster in inference, compared to other very specialized models.
  arXiv  Detail & Related papers  (2024-08-11T16:53:09Z)
• Single-Stage Visual Relationship Learning using Conditional Queries [60.90880759475021]
  TraCQ is a new formulation for scene graph generation that avoids the multi-task learning problem and the entity pair distribution. We employ a DETR-based encoder-decoder conditional queries to significantly reduce the entity label space as well. Experimental results show that TraCQ not only outperforms existing single-stage scene graph generation methods, it also beats many state-of-the-art two-stage methods on the Visual Genome dataset.
  arXiv  Detail & Related papers  (2023-06-09T06:02:01Z)
• Improved Active Multi-Task Representation Learning via Lasso [44.607652031235716]
  In this paper, we show the dominance of the L1-regularized-relevance-based ($nu1$) strategy by giving a lower bound for the $nu2$-based strategy. We also characterize the potential of our $nu1$-based strategy in sample-cost-sensitive settings.
  arXiv  Detail & Related papers  (2023-06-05T03:08:29Z)
• Semantic Self-adaptation: Enhancing Generalization with a Single Sample [45.111358665370524]
  We propose a self-adaptive approach for semantic segmentation. It fine-tunes the parameters of convolutional layers to the input image using consistency regularization. Our empirical study suggests that self-adaptation may complement the established practice of model regularization at training time.
  arXiv  Detail & Related papers  (2022-08-10T12:29:01Z)
• Lifelong Learning Without a Task Oracle [13.331659934508764]
  Supervised deep neural networks are known to undergo a sharp decline in the accuracy of older tasks when new tasks are learned. We propose and compare several candidate task-assigning mappers which require very little memory overhead. Best-performing variants only impose an average cost of 1.7% parameter memory increase.
  arXiv  Detail & Related papers  (2020-11-09T21:30:31Z)
• Laplacian Regularized Few-Shot Learning [35.381119443377195]
  We propose a transductive Laplacian-regularized inference for few-shot tasks. Our inference does not re-train the base model, and can be viewed as a graph clustering of the query set. Our LaplacianShot consistently outperforms state-of-the-art methods by significant margins across different models.
  arXiv  Detail & Related papers  (2020-06-28T02:17:52Z)
• A conditional one-output likelihood formulation for multitask Gaussian processes [0.0]
  Multitask Gaussian processes (MTGP) are the Gaussian process framework's solution for multioutput regression problems. Here we introduce a novel approach that simplifies the multitask learning. We show that it is computationally competitive with state of the art options.
  arXiv  Detail & Related papers  (2020-06-05T14:59:06Z)
• The Right Tool for the Job: Matching Model and Instance Complexities [62.95183777679024]
  As NLP models become larger, executing a trained model requires significant computational resources incurring monetary and environmental costs. We propose a modification to contextual representation fine-tuning which, during inference, allows for an early (and fast) "exit" We test our proposed modification on five different datasets in two tasks: three text classification datasets and two natural language inference benchmarks.
  arXiv  Detail & Related papers  (2020-04-16T04:28:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.