Research map / Large language models / Reasoning and chain of thought

Towards Theoretical Understanding of Transformer Test-Time Computing: Investigation on In-Context Linear Regression

ICML 2026 · Large language models › Reasoning and chain of thought · approach: Test-time compute scaling · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Models transformer test-time computation as noisy/sampled chain-of-thought in in-context linear regression, and theoretically analyzes ensembling, best-of-N, and majority vote against greedy/deterministic GD.

Problem

Prior theory on transformer in-context learning and chain-of-thought assumes deterministic decoding, leaving sampling-based test-time computation (ensembling, BoN, majority vote) theoretically unexplained.

Approach

Introduce a randomized inference mechanism for a one-layer linear-attention transformer that implements noisy gradient descent via noise injection (continuous coefficients) or binary coefficient sampling, then analyze how aggregating N sampled reasoning paths reduces excess risk or improves exact recovery.

Key results

• Ensembling with linear noise transformation reduces excess risk to (ηd)^{-r/(r+1)}, while constant noise and vanilla GD overfit to label noise as CoT length grows (theory).
• For binary sparse regression with n=1, greedy decoding recovers the truth with probability at most 1/2^{d-1}+2/d, while majority vote reaches at least 1-1/2^{d-1} (theory); experiments show greedy around 0.2 accuracy at d=10 versus high accuracy for majority vote.
• A fitted exponential law Acc(T,N) ≈ α − β e^{−Δ_T² N/2} predicts high-cost GSM8K/MATH accuracy from low-cost data with Llama3.1-8b-instruct (no numeric prediction error reported in the extracted text).

Surprising findings

• Constant-noise sampling gives no benefit over vanilla GD in the ensemble setting, and vanilla GD overfits label noise as reasoning length grows.

Limitations

• Analysis limited to a one-layer linear-attention transformer that is assumed (not trained) to implement the sampling-based inference mechanism.
• Only two simple noise transformations and a simplified binary sparse setting with k=1 and n=1 for the strongest results.
• Real-LLM extrapolation relies on heuristic conjectures and fitted curves rather than derived results.

Experimental setup

Datasets: GSM8K MATH (level 1 integer-answer subset, 309 problems)

Benchmarks: GSM8K MATH subset synthetic in-context linear regression

Metrics: excess risk recovery accuracy accuracy vs tokens

Baselines: multi-step GD with CoT greedy decoding

Builds on: Transformers learn in-context by gradient descent / CoT in-context linear regres Best-of-N sampling majority voting (self-consistency)

Closest papers by meaning

• Efficient Test-Time Scaling via Hierarchical Search and Self-Verification for Discrete Diffusion Language Models (ICML 2026 · similarity 0.89)
• Sample Smart, Not Hard: Correctness-First Decoding for Better Reasoning in LLMs (ICLR 2026 · similarity 0.89)
• Scaling Up, Speeding Up: A Benchmark of Speculative Decoding for Efficient LLM Test-Time Scaling (ICLR 2026 · similarity 0.89)
• Understanding the Role of Training Data in Test-Time Scaling (ICLR 2026 · similarity 0.89)
• A Theoretical Study on Bridging Internal Probability and Self-Consistency for LLM Reasoning (NeurIPS 2025 · similarity 0.89)
• Test-Time Scaling in the Wild: Why Exploitation, Not Exploration, Is the Bottleneck (NeurIPS 2026 · similarity 0.89)