mlsanityData to 7 Oct 2026

Learning How Hard to Think: Input-Adaptive Allocation of LM Computation

arXiv 2410.04707 ↗First posted 7 Oct 2024cs.LG cs.AI cs.CLcited by 67

On the map: LLM reasoning → Test-time compute and efficient thinking

Abstract (arXiv)

Computationally intensive decoding procedures--including search, reranking, and self-critique--can improve the quality of language model (LM) outputs in problems spanning code generation, numerical reasoning, and dialog. Existing work typically applies the same decoding procedure for every input to an LM. But not all inputs require the same amount of computation to process. Can we allocate decoding computation adaptively, using more resources to answer questions whose answers will be harder to compute? We present an approach that predicts the distribution of rewards given an input and computation budget, then allocates additional computation to inputs for which it is predicted to be most useful. We apply this approach in two decoding procedures: first, an adaptive best-of-k procedure that dynamically selects the number of samples to generate as input to a reranker; second, a routing procedure that dynamically responds to a query using a decoding procedure that is expensive but accurate, or one that is cheaper but less capable. Across a suite of programming, mathematics, and dialog tasks, we show that accurate computation-allocation procedures can be learned, and reduce computation by up to 50% at no cost to response quality, or improve quality by up to 10% at a fixed computational budget.

Key facts. Cited by 67 papers in the map (data through 7 Oct 2026). Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning. Builds on 23 of its 27 references that are in the map. First posted on arXiv 7 Oct 2024.

Builds on

23 of 27 references.

Closest ancestors · 3

Same direction, newest first

  1. 2024Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters6 Aug
  2. 2024Theoretical guarantees on the best-of-n alignment policy3 Jan
  3. 2023Tree of Thoughts: Deliberate Problem Solving with Large Language Models17 May

Other references · 20

  1. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,302
  2. 2022Self-Consistency Improves Chain of Thought Reasoning in Language Modelscited by 5,601
  3. 2021Measuring Mathematical Problem Solving With the MATH Datasetcited by 5,203
  4. 2022Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedbackcited by 3,634
  5. 2023Mistral 7Bcited by 3,065
  6. 2023Improving Factuality and Reasoning in Language Models through Multiagent Debatecited by 1,739
  7. 2022Competition-Level Code Generation with AlphaCodecited by 1,427
  8. 2022Least-to-Most Prompting Enables Complex Reasoning in Large Language Modelscited by 1,397
  9. 2022Scaling Laws for Reward Model Overoptimizationcited by 1,056
  10. 2024Large Language Monkeys: Scaling Inference Compute with Repeated Samplingcited by 946
  11. 2021Show Your Work: Scratchpads for Intermediate Computation with Language Modelscited by 871
  12. 2018Universal Transformerscited by 613
8 more
  1. 2016Adaptive Computation Time for Recurrent Neural Networkscited by 479
  2. 2023LMSYS-Chat-1M: A Large-Scale Real-World LLM Conversation Datasetcited by 449
  3. 2021PonderNet: Learning to Pondercited by 156
  4. 2023TACO: Topics in Algorithmic COde generation datasetcited by 150
  5. 2023Don't throw away your value model! Generating more preferable text with Value-Guided Monte-Carlo Tree Search decodingcited by 59
  6. 2024Value Augmented Sampling for Language Model Alignment and Personalizationcited by 49
  7. 2023The Consensus Game: Language Model Generation via Equilibrium Searchcited by 35
  8. 2024SED: Self-Evaluation Decoding Enhances Large Language Models for Better Generationcited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 7; 2025: 34; 2026: 26.

67 papers.

Sort:

By area:

  1. 2024Do NOT Think That Much for 2+3=? On the Overthinking of o1-Like LLMscited by 564
  2. 2025Reasoning Models Know When They're Right: Probing Hidden States for Self-Verificationcited by 154
  3. 2025Between Underthinking and Overthinking: An Empirical Study of Reasoning Length and correctness in LLMscited by 115
  4. 2024The Surprising Effectiveness of Test-Time Training for Few-Shot Learningcited by 88
  5. 2024A Unified Approach to Routing and Cascading for LLMscited by 71
  6. 2025Budget-Aware Tool Use Enables Effective Agent Scalingcited by 42
  7. 2025A Survey of Test-Time Compute: From Intuitive Inference to Deliberate Reasoningcited by 40
  8. 2025Think or Not? Exploring Thinking Efficiency in Large Reasoning Models via an Information-Theoretic Lenscited by 32
  9. 2025Dynamic Scaling of Unit Tests for Code Reward Modelingcited by 31
  10. 2025Reasoning on a Budget: A Survey of Adaptive and Controllable Test-Time Compute in LLMscited by 31
  11. 2025BudgetThinker: Empowering Budget-aware LLM Reasoning with Control Tokenscited by 27
  12. 2025AI Agentic Programming: A Survey of Techniques, Challenges, and Opportunitiescited by 26
38 more
  1. 2025Route to Reason: Adaptive Routing for LLM and Reasoning Strategy Selectioncited by 23
  2. 2025Trade-offs in Large Reasoning Models: An Empirical Analysis of Deliberative and Adaptive Reasoning over Foundational Capabilitiescited by 20
  3. 2025Emergent Response Planning in LLMscited by 17
  4. 2025SLOT: Sample-specific Language Model Optimization at Test-timecited by 17
  5. 2024Automatic Curriculum Expert Iteration for Reliable LLM Reasoningcited by 16
  6. 2024Scaling LLM Inference with Optimized Sample Compute Allocationcited by 16
  7. 2024Mind the Gap: Examining the Self-Improvement Capabilities of Large Language Modelscited by 16
  8. 2024Syzygy: Dual Code-Test C to (safe) Rust Translation using LLMs and Dynamic Analysiscited by 16
  9. 2025An Empirical Study of LLM Reasoning Ability Under Strict Output Length Constraintcited by 16
  10. 2025Taming the Titans: A Survey of Efficient LLM Inference Servingcited by 16
  11. 2026GlimpRouter: Efficient Collaborative Inference by Glimpsing One Token of Thoughtscited by 16
  12. 2026Calibrate-Then-Act: Cost-Aware Exploration in LLM Agentscited by 16
  13. 2025Self-Steering Language Modelscited by 13
  14. 2026Small Generalizable Prompt Predictive Models Can Steer Efficient RL Post-Training of Large Reasoning Modelscited by 11
  15. 2025AdaBoN: Adaptive Best-of-N Alignmentcited by 8
  16. 2025Strategic Scaling of Test-Time Compute: A Bandit Learning Approachcited by 8
  17. 2025Latency and Token-Aware Test-Time Computecited by 8
  18. 2026Adaptive Test-Time Compute Allocation for Reasoning LLMs via Constrained Policy Optimizationcited by 8
  19. 2025DynScaling: Efficient Verifier-free Inference Scaling via Dynamic and Integrated Samplingcited by 7
  20. 2025Dropping Just a Handful of Preferences Can Change Top Large Language Model Rankingscited by 7
  21. 2026On Calibration of Large Language Models: From Response To Capabilitycited by 5
  22. 2025Structured Pruning for Diverse Best-of-N Reasoning Optimizationcited by 4
  23. 2025Re-FORC: Adaptive Reward Prediction for Efficient Chain-of-Thought Reasoningcited by 4
  24. 2025Zero-Overhead Introspection for Adaptive Test-Time Computecited by 4
  25. 2026AVIS: Adaptive Test-Time Scaling for Vision-Language Modelscited by 4
  26. 2025DAST: Difficulty-Aware Self-Training on Large Language Modelscited by 3
  27. 2025Less is More Tokens: Efficient Math Reasoning via Difficulty-Aware Chain-of-Thought Distillationcited by 3
  28. 2025LATTS: Locally Adaptive Test-Time Scalingcited by 3
  29. 2026ATLAS: Agentic Test-time Learning-to-Allocate Scalingcited by 3
  30. 2026sGPO: Trading Inference FLOPs for Training Efficiency in RLVRcited by 3
  31. 2026Falsification, Not Exposure: An Internally Preregistered Placebo-Controlled Decomposition of Self-Repair Feedback in Frozen Small Code Modelscited by 3
  32. 2025Optimal Policy Minimum Bayesian Riskcited by 2
  33. 2025Choosing to Be Green: Advancing Green AI via Dynamic Model Selectioncited by 2
  34. 2025Boomerang Distillation Enables Zero-Shot Model Size Interpolationcited by 2
  35. 2025Reasoning Planning for Language Modelscited by 2
  36. 2026Predictive Scheduling for Efficient Inference-Time Reasoning in Large Language Modelscited by 2
  37. 2026Not All Errors Are Equal: Consequence-Aware Reasoning Compute Allocationcited by 2
  38. 2026A decodability criterion predicts when hidden-state selection beats majority voting in large language modelscited by 2

50 most cited of 67 All 67 (JSON)

Similar, not cited

Close in wording, no citation either way

  1. 2025Sample Smart, Not Hard: Correctness-First Decoding for Better Reasoning in LLMs
  2. 2026Compute Where it Counts: Self Optimizing Language Models
  3. 2026Think Twice Before You Write -- an Entropy-based Decoding Strategy to Enhance LLM Reasoning
  4. 2024Duo-LLM: A Framework for Studying Adaptive Computation in Large Language Models
  5. 2022Confident Adaptive Language Modeling
  6. 2025Can Multi-turn Self-refined Single Agent LMs with Retrieval Solve Hard Coding Problems?
  7. 2026Entropy-informed Decoding: Adaptive Information-Driven Branching
  8. 2026Adaptive Decoding via Test-Time Policy Learning for Self-Improving Generation