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

arXiv: https://arxiv.org/abs/2410.04707 · HTML: https://mlsanity.com/paper/2410.04707/

## Key facts

- Cited by 70 papers in the map (data through 14 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.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 23 of 23)

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2204.05862/) (2022)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Mistral 7B](https://mlsanity.com/paper/2310.06825/) (2023)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [Improving Factuality and Reasoning in Language Models through Multiagent Debate](https://mlsanity.com/paper/2305.14325/) (2023)
- [Competition-Level Code Generation with AlphaCode](https://mlsanity.com/paper/2203.07814/) (2022)
- [Least-to-Most Prompting Enables Complex Reasoning in Large Language Models](https://mlsanity.com/paper/2205.10625/) (2022)
- [Scaling Laws for Reward Model Overoptimization](https://mlsanity.com/paper/2210.10760/) (2022)
- [Large Language Monkeys: Scaling Inference Compute with Repeated Sampling](https://mlsanity.com/paper/2407.21787/) (2024)
- [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021)
- [Universal Transformers](https://mlsanity.com/paper/1807.03819/) (2018)
- [Adaptive Computation Time for Recurrent Neural Networks](https://mlsanity.com/paper/1603.08983/) (2016)
- [LMSYS-Chat-1M: A Large-Scale Real-World LLM Conversation Dataset](https://mlsanity.com/paper/2309.11998/) (2023)
- [PonderNet: Learning to Ponder](https://mlsanity.com/paper/2107.05407/) (2021)
- [TACO: Topics in Algorithmic COde generation dataset](https://mlsanity.com/paper/2312.14852/) (2023)
- [Theoretical guarantees on the best-of-n alignment policy](https://mlsanity.com/paper/2401.01879/) (2024)
- [Don't throw away your value model! Generating more preferable text with Value-Guided Monte-Carlo Tree Search decoding](https://mlsanity.com/paper/2309.15028/) (2023)
- [Value Augmented Sampling for Language Model Alignment and Personalization](https://mlsanity.com/paper/2405.06639/) (2024)
- [The Consensus Game: Language Model Generation via Equilibrium Search](https://mlsanity.com/paper/2310.09139/) (2023)
- [SED: Self-Evaluation Decoding Enhances Large Language Models for Better Generation](https://mlsanity.com/paper/2405.16552/) (2024)

## Built on by (most cited first, 30 of 70)

- [Do NOT Think That Much for 2+3=? On the Overthinking of o1-Like LLMs](https://mlsanity.com/paper/2412.21187/) (2024)
- [Reasoning Models Know When They're Right: Probing Hidden States for Self-Verification](https://mlsanity.com/paper/2504.05419/) (2025)
- [Between Underthinking and Overthinking: An Empirical Study of Reasoning Length and correctness in LLMs](https://mlsanity.com/paper/2505.00127/) (2025)
- [The Surprising Effectiveness of Test-Time Training for Few-Shot Learning](https://mlsanity.com/paper/2411.07279/) (2024)
- [A Unified Approach to Routing and Cascading for LLMs](https://mlsanity.com/paper/2410.10347/) (2024)
- [Budget-Aware Tool Use Enables Effective Agent Scaling](https://mlsanity.com/paper/2511.17006/) (2025)
- [A Survey of Test-Time Compute: From Intuitive Inference to Deliberate Reasoning](https://mlsanity.com/paper/2501.02497/) (2025)
- [Think or Not? Exploring Thinking Efficiency in Large Reasoning Models via an Information-Theoretic Lens](https://mlsanity.com/paper/2505.18237/) (2025)
- [Dynamic Scaling of Unit Tests for Code Reward Modeling](https://mlsanity.com/paper/2501.01054/) (2025)
- [Reasoning on a Budget: A Survey of Adaptive and Controllable Test-Time Compute in LLMs](https://mlsanity.com/paper/2507.02076/) (2025)
- [BudgetThinker: Empowering Budget-aware LLM Reasoning with Control Tokens](https://mlsanity.com/paper/2508.17196/) (2025)
- [AI Agentic Programming: A Survey of Techniques, Challenges, and Opportunities](https://mlsanity.com/paper/2508.11126/) (2025)
- [Route to Reason: Adaptive Routing for LLM and Reasoning Strategy Selection](https://mlsanity.com/paper/2505.19435/) (2025)
- [Trade-offs in Large Reasoning Models: An Empirical Analysis of Deliberative and Adaptive Reasoning over Foundational Capabilities](https://mlsanity.com/paper/2503.17979/) (2025)
- [Emergent Response Planning in LLMs](https://mlsanity.com/paper/2502.06258/) (2025)
- [Mind the Gap: Examining the Self-Improvement Capabilities of Large Language Models](https://mlsanity.com/paper/2412.02674/) (2024)
- [SLOT: Sample-specific Language Model Optimization at Test-time](https://mlsanity.com/paper/2505.12392/) (2025)
- [An Empirical Study of LLM Reasoning Ability Under Strict Output Length Constraint](https://mlsanity.com/paper/2504.14350/) (2025)
- [GlimpRouter: Efficient Collaborative Inference by Glimpsing One Token of Thoughts](https://mlsanity.com/paper/2601.05110/) (2026)
- [Calibrate-Then-Act: Cost-Aware Exploration in LLM Agents](https://mlsanity.com/paper/2602.16699/) (2026)
- [Automatic Curriculum Expert Iteration for Reliable LLM Reasoning](https://mlsanity.com/paper/2410.07627/) (2024)
- [Scaling LLM Inference with Optimized Sample Compute Allocation](https://mlsanity.com/paper/2410.22480/) (2024)
- [Syzygy: Dual Code-Test C to (safe) Rust Translation using LLMs and Dynamic Analysis](https://mlsanity.com/paper/2412.14234/) (2024)
- [Taming the Titans: A Survey of Efficient LLM Inference Serving](https://mlsanity.com/paper/2504.19720/) (2025)
- [Small Generalizable Prompt Predictive Models Can Steer Efficient RL Post-Training of Large Reasoning Models](https://mlsanity.com/paper/2602.01970/) (2026)
- [Self-Steering Language Models](https://mlsanity.com/paper/2504.07081/) (2025)
- [AdaBoN: Adaptive Best-of-N Alignment](https://mlsanity.com/paper/2505.12050/) (2025)
- [Adaptive Test-Time Compute Allocation for Reasoning LLMs via Constrained Policy Optimization](https://mlsanity.com/paper/2604.14853/) (2026)
- [Strategic Scaling of Test-Time Compute: A Bandit Learning Approach](https://mlsanity.com/paper/2506.12721/) (2025)
- [Dropping Just a Handful of Preferences Can Change Top Large Language Model Rankings](https://mlsanity.com/paper/2508.11847/) (2025)

## 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.