mlsanityData to 7 Oct 2026

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

arXiv 2508.07571 ↗First posted 11 Aug 2025cs.LG cs.AIcited by 1

Not on the map. Why?

Abstract (arXiv)

Using more test-time computation during language model inference, such as generating more intermediate thoughts or sampling multiple candidate answers, has proven effective in significantly improving model performance. This paper takes an initial step toward bridging the gap between practical language model inference and theoretical transformer analysis by incorporating randomness and sampling. We focus on in-context linear regression with continuous/binary coefficients, where our framework simulates language model decoding through noise injection and binary coefficient sampling. Through this framework, we provide detailed analyses of widely adopted inference techniques. Supported by empirical results, our theoretical framework and analysis demonstrate the potential for offering new insights into understanding inference behaviors in real-world language models.

Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 50 of its 59 references that are in the map. First posted on arXiv 11 Aug 2025.

Builds on

50 of 59 references.

References · 50

  1. 2017Attention Is All You Needcited by 59,932
  2. 2020Language Models are Few-Shot Learnerscited by 32,199
  3. 2023GPT-4 Technical Reportcited by 18,132
  4. 2024The Llama 3 Herd of Modelscited by 14,192
  5. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,302
  6. 2021Training Verifiers to Solve Math Word Problemscited by 9,743
  7. 2020Scaling Laws for Neural Language Modelscited by 6,411
  8. 2025DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learningcited by 6,146
  9. 2022Scalable Diffusion Models with Transformerscited by 5,931
  10. 2022Self-Consistency Improves Chain of Thought Reasoning in Language Modelscited by 5,601
  11. 2021Measuring Mathematical Problem Solving With the MATH Datasetcited by 5,203
  12. 2022Large Language Models are Zero-Shot Reasonerscited by 4,323
38 more
  1. 2023Self-Refine: Iterative Refinement with Self-Feedbackcited by 3,317
  2. 2023Tree of Thoughts: Deliberate Problem Solving with Large Language Modelscited by 3,155
  3. 2020Learning to summarize from human feedbackcited by 2,562
  4. 2024Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameterscited by 1,928
  5. 2021WebGPT: Browser-assisted question-answering with human feedbackcited by 1,722
  6. 2023SGLang: Efficient Execution of Structured Language Model Programscited by 1,107
  7. 2025Cosmos World Foundation Model Platform for Physical AIcited by 833
  8. 2022Transformers learn in-context by gradient descentcited by 714
  9. 2022What Can Transformers Learn In-Context? A Case Study of Simple Function Classescited by 700
  10. 2023RAFT: Reward rAnked FineTuning for Generative Foundation Model Alignmentcited by 672
  11. 2022What learning algorithm is in-context learning? Investigations with linear modelscited by 671
  12. 2023Language Agent Tree Search Unifies Reasoning Acting and Planning in Language Modelscited by 551
  13. 2019Benign Overfitting in Linear Regressioncited by 544
  14. 2024Training Language Models to Self-Correct via Reinforcement Learningcited by 405
  15. 2022Self-critiquing models for assisting human evaluatorscited by 372
  16. 2023Trained Transformers Learn Linear Models In-Contextcited by 331
  17. 2023Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selectioncited by 291
  18. 2023Transformers learn to implement preconditioned gradient descent for in-context learningcited by 274
  19. 2020Benign overfitting in ridge regressioncited by 152
  20. 2023Linear attention is (maybe) all you need (to understand transformer optimization)cited by 97
  21. 2023How Many Pretraining Tasks Are Needed for In-Context Learning of Linear Regression?cited by 93
  22. 2023How Do Transformers Learn In-Context Beyond Simple Functions? A Case Study on Learning with Representationscited by 72
  23. 2024Training Dynamics of Multi-Head Softmax Attention for In-Context Learning: Emergence, Convergence, and Optimalitycited by 71
  24. 2023Auto-Regressive Next-Token Predictors are Universal Learnerscited by 65
  25. 2024Inference Scaling for Long-Context Retrieval Augmented Generationcited by 65
  26. 2024Transformers Provably Solve Parity Efficiently with Chain of Thoughtcited by 49
  27. 2023Memorization Capacity of Multi-Head Attention in Transformerscited by 39
  28. 2023Approximation and Estimation Ability of Transformers for Sequence-to-Sequence Functions with Infinite Dimensional Inputcited by 32
  29. 2025Transformers Learn to Implement Multi-step Gradient Descent with Chain of Thoughtcited by 32
  30. 2024From Sparse Dependence to Sparse Attention: Unveiling How Chain-of-Thought Enhances Transformer Sample Efficiencycited by 28
  31. 2024Unveiling the Statistical Foundations of Chain-of-Thought Prompting Methodscited by 27
  32. 2024How Well Can Transformers Emulate In-context Newton's Method?cited by 23
  33. 2024What Can Transformer Learn with Varying Depth? Case Studies on Sequence Learning Taskscited by 19
  34. 2024How Transformers Utilize Multi-Head Attention in In-Context Learning? A Case Study on Sparse Linear Regressioncited by 13
  35. 2022Risk Bounds of Multi-Pass SGD for Least Squares in the Interpolation Regimecited by 8
  36. 2024On the Learn-to-Optimize Capabilities of Transformers in In-Context Sparse Recoverycited by 6
  37. 2025On the Robustness of Transformers against Context Hijacking for Linear Classificationcited by 4
  38. 2025Transformer Learns Optimal Variable Selection in Group-Sparse Classificationcited by 2

Built on by

Cited by year

Citing papers per year: 2025: 1.

1 paper.

  1. 2025Best-of-Majority: Minimax-Optimal Strategy for Pass@k Inference Scalingcited by 8