Large Language Monkeys: Scaling Inference Compute with Repeated Sampling

2024/07/31 by Bradley Brown, Brown, Bradley, Jordan Juravsky +11 · 2 voices · 161 citations
Computer Science · #cs.LG #cs.AI

paper · pdf · doi:10.48550/arxiv.2407.21787

Abstract

Scaling the amount of compute used to train language models has dramatically improved their capabilities. However, when it comes to inference, we often limit models to making only one attempt at a problem. Here, we explore inference compute as another axis for scaling, using the simple technique of repeatedly sampling candidate solutions from a model. Across multiple tasks and models, we observe that coverage -- the fraction of problems that are solved by any generated sample -- scales with the number of samples over four orders of magnitude. Interestingly, the relationship between coverage and the number of samples is often log-linear and can be modelled with an exponentiated power law, suggesting the existence of inference-time scaling laws. In domains like coding and formal proofs, where answers can be automatically verified, these increases in coverage directly translate into improved performance. When we apply repeated sampling to SWE-bench Lite, the fraction of issues solved with DeepSeek-Coder-V2-Instruct increases from 15.9% with one sample to 56% with 250 samples, outperforming the single-sample state-of-the-art of 43%. In domains without automatic verifiers, we find that common methods for picking from a sample collection (majority voting and reward models) plateau beyond several hundred samples and fail to fully scale with the sample budget.

Cited by

• Lessons from Neuroscience for AI: How integrating Actions, Compositional Structure and Episodic Memory could enable Safe, Interpretable and Human-Like AI
• ACM: Agentic Context Management for Long Horizon Tasks
• DeepLook: Deeper Thinking with Lookahead
• Demystifying LLM-as-a-Judge: Analytically Tractable Model for Inference-Time Scaling
• GroundingME: Exposing the Visual Grounding Gap in MLLMs through Multi-Dimensional Evaluation
• Multimodal RewardBench 2: Evaluating Omni Reward Models for Interleaved Text and Image
• FutureWeaver: Planning Test-Time Compute for Multi-Agent Systems with Modularized Collaboration
• AutoRefiner: Improving Autoregressive Video Diffusion Models via Reflective Refinement Over the Stochastic Sampling Path
• MARINE: Theoretical Optimization and Design for Multi-Agent Recursive IN-context Enhancement
• RoBoN: Routed Online Best-of-n for Test-Time Scaling with Multiple LLMs
• On the Limits of Test-Time Compute: Sequential Reward Filtering for Better Inference
• SPARK: Stepwise Process-Aware Rewards for Reference-Free Reinforcement Learning
• When Does Verification Pay Off? A Closer Look at LLMs as Solution Verifiers
• Think in Parallel, Answer as One: Logit Averaging for Open-Ended Reasoning
• Auxiliary-Hyperparameter-Free Sampling: Entropy Equilibrium for Text Generation
• Rethinking Test Time Scaling for Flow-Matching Generative Models
• Boosting Reasoning in Large Multimodal Models via Activation Replay
• Differential Smoothing Mitigates Sharpening and Improves LLM Reasoning
• Majority of the Bests: Improving Best-of-N via Bootstrapping
• Budget-Aware Tool-Use Enables Effective Agent Scaling
• TRIM: Scalable 3D Gaussian Diffusion Inference with Temporal and Spatial Trimming
• AccelOpt: A Self-Improving LLM Agentic System for AI Accelerator Kernel Optimization
• On the Entropy Calibration of Language Models
• Efficient Thought Space Exploration Through Strategic Intervention
• Seer Self-Consistency: Advance Budget Estimation for Adaptive Test-Time Scaling
• Place Matters: Comparing LLM Hallucination Rates for Place-Based Legal Queries
• Klear-AgentForge: Forging Agentic Intelligence through Posttraining Scaling
• Reusing Pre-Training Data at Test Time is a Compute Multiplier
• Test-time Scaling of LLMs: A Survey from A Subproblem Structure Perspective
• DTS: Enhancing Large Reasoning Models via Decoding Tree Sketching
• UME-R1: Exploring Reasoning-Driven Generative Multimodal Embeddings
• SELF-REDRAFT: Eliciting Intrinsic Exploration-Exploitation Balance in Test-Time Scaling for Code Generation
• The Era of Agentic Organization: Learning to Organize with Language Models
• Test-Time Alignment of LLMs via Sampling-Based Optimal Control in pre-logit space
• Reasoning Path Divergence: A New Metric and Curation Strategy to Unlock LLM Diverse Thinking
• e1: Learning Adaptive Control of Reasoning Effort
• Generalizing Test-time Compute-optimal Scaling as an Optimizable Graph
• Supervised Reinforcement Learning: From Expert Trajectories to Step-wise Reasoning
• Evaluating the Role of Verifiers in Test-Time Scaling for Legal Reasoning Tasks
• MODUS: Decoder-Only Any-to-Any Modeling of Diverse Modalities
• LLM-as-a-Verifier: A General-Purpose Verification Framework
• Rethinking the Evaluation of Harness Evolution for Agents
• Borrowed Strength: Best-of-N Search over a Code EncodingBreaks Self-Check Jailbreak Defenses
• MAS-ProVe: Understanding the Process Verification of Multi-Agent Systems
• What Limits Agentic Systems Efficiency?
• The Best of N Worlds: Aligning Reinforcement Learning with Best-of-N Sampling via max@k Optimisation
• Boosting Accuracy and Efficiency of Budget Forcing in LLMs via Reinforcement Learning for Mathematical Reasoning
• String Seed of Thought: Prompting LLMs for Distribution-Faithful and Diverse Generation
• Language Ranker: A Lightweight Ranking framework for LLM Decoding
• Enhancing Reasoning Skills in Small Persian Medical Language Models Can Outperform Large-Scale Data Training
• PlanU: Large Language Model Reasoning through Planning under Uncertainty
• EdgeReasoning: Characterizing Reasoning LLM Deployment on Edge GPUs
• Scaling Laws Meet Model Architecture: Toward Inference-Efficient LLMs
• 3D Optimization for AI Inference Scaling: Balancing Accuracy, Cost, and Latency
• Test-time Verification via Optimal Transport: Coverage, ROC, & Sub-optimality
• Online In-Context Distillation for Low-Resource Vision Language Models
• Inference-Time Compute Scaling For Flow Matching
• AI for Distributed Systems Design: Scalable Cloud Optimization Through Repeated LLMs Sampling And Simulators
• Integrating Performance Tools in Model Reasoning for GPU Kernel Optimization
• SolverLLM: Leveraging Test-Time Scaling for Optimization Problem via LLM-Guided Search
• The Road Less Traveled: Enhancing Exploration in LLMs via Sequential Sampling
• Rewiring Experts on the Fly:Continuous Rerouting for Better Online Adaptation in Mixture-of-Expert models
• CarBoN: Calibrated Best-of-N Sampling Improves Test-time Reasoning
• GroundedPRM: Tree-Guided and Fidelity-Aware Process Reward Modeling for Step-Level Reasoning
• AutoRubric-R1V: Rubric-Based Generative Rewards for Faithful Multimodal Reasoning
• ToolPRM: Fine-Grained Inference Scaling of Structured Outputs for Function Calling
• Scaling Test-Time Compute to Achieve IOI Gold Medal with Open-Weight Models
• Budget-aware Test-time Scaling via Discriminative Verification
• A Survey on Parallel Reasoning
• xLSTM Scaling Laws: Competitive Performance with Linear Time-Complexity
• MatryoshkaThinking: Recursive Test-Time Scaling Enables Efficient Reasoning
• Enhancing Large Language Model Reasoning with Reward Models: An Analytical Survey
• Quagmires in SFT-RL Post-Training: When High SFT Scores Mislead and What to Use Instead
• LiveOIBench: Can Large Language Models Outperform Human Contestants in Informatics Olympiads?
• Logit Arithmetic Elicits Long Reasoning Capabilities Without Training
• DeepPrune: Parallel Scaling without Inter-trace Redundancy
• First Try Matters: Revisiting the Role of Reflection in Reasoning Models
• Parallel Test-Time Scaling for Latent Reasoning Models
• h1: Bootstrapping LLMs to Reason over Longer Horizons via Reinforcement Learning
• TaTToo: Tool-Grounded Thinking PRM for Test-Time Scaling in Tabular Reasoning
• ARISE: An Adaptive Resolution-Aware Metric for Test-Time Scaling Evaluation in Large Reasoning Models
• Verifier-free Test-Time Sampling for Vision-Language-Action Models
• Efficient Prediction of Pass@k Scaling in Large Language Models
• Bridging Reasoning to Learning: Unmasking Illusions using Complexity Out of Distribution Generalization
• Increasing LLM response trustworthiness using voting ensembles
• Don't Pass@k: A Bayesian Framework for Large Language Model Evaluation
• MetaMuse: Algorithm Generation via Creative Ideation
• OptAgent: Optimizing Query Rewriting for E-commerce via Multi-Agent Simulation
• MITS: Enhanced Tree Search Reasoning for LLMs via Pointwise Mutual Information
• GuidedSampling: Steering LLMs Towards Diverse Candidate Solutions at Inference-Time
• Sample, Align, Synthesize: Graph-Based Response Synthesis with ConGrs
• Lateral Tree-of-Thoughts Surpasses ToT by Incorporating Logically-Consistent, Low-Utility Candidates
• Best-of-Majority: Minimax-Optimal Strategy for Pass@k Inference Scaling
• Generalized Parallel Scaling with Interdependent Generations
• Making, not Taking, the Best of N
• CodeChemist: Functional Knowledge Transfer for Low-Resource Code Generation via Test-Time Scaling
• Training Large Language Models To Reason In Parallel With Global Forking Tokens
• Knapsack RL: Unlocking Exploration of LLMs via Optimizing Budget Allocation
• TUMIX: Multi-Agent Test-Time Scaling with Tool-Use Mixture
• RFG: Test-Time Scaling for Diffusion Large Language Model Reasoning with Reward-Free Guidance
• LatentEvolve: Self-Evolving Test-Time Scaling in Latent Space
• SpecExit: Accelerating Large Reasoning Model via Speculative Exit
• Evaluating the Robustness of Chinchilla Compute-Optimal Scaling
• Emergent Slow Thinking in LLMs as Inverse Tree Freezing
• Pretraining Scaling Laws for Generative Evaluations of Language Models
• From Harm to Help: Turning Reasoning In-Context Demos into Assets for Reasoning LMs
• Critique to Verify: Accurate and Honest Test-Time Scaling with RL-Trained Verifiers
• When Does Reasoning Matter? A Controlled Study of Reasoning's Contribution to Model Performance
• A2R: An Asymmetric Two-Stage Reasoning Framework for Parallel Reasoning
• Position: The Hidden Costs and Measurement Gaps of Reinforcement Learning with Verifiable Rewards
• Quantifying the Impact of Structured Output Format on Large Language Models through Causal Inference
• Best-of-∞ -- Asymptotic Performance of Test-Time Compute
• SCORE: Scaling audio generation using Standardized COmposite REwards
• Thinking While Listening: Simple Test Time Scaling For Audio Classification
• SKIMIX: Multi-Agent Harness-Time Scaling with Skill Mixture for Dynamic Harness Engineering
• Bridging Inference-Time Scaling and Episodic Memory with Action-Centric Graphs
• Lessons from complex systems science for AI governance
• Reinforcement Learning on Pre-Training Data
• Pathways of Thoughts: Multi-Directional Thinking for Long-form Personalized Question Answering
• Introducing LongCat-Flash-Thinking: A Technical Report
• Variation in Verification: Understanding Verification Dynamics in Large Language Models
• MoEs Are Stronger than You Think: Hyper-Parallel Inference Scaling with RoE
• VerilogMonkey: Exploring Parallel Scaling for Automated Verilog Code Generation with LLMs
• Slim-SC: Thought Pruning for Efficient Scaling with Self-Consistency
• LATTS: Locally Adaptive Test-Time Scaling
• The LLM Already Knows: Estimating LLM-Perceived Question Difficulty via Hidden Representations
• LTA-thinker: Latent Thought-Augmented Training Framework for Large Language Models on Complex Reasoning
• Routing Distilled Knowledge via Mixture of LoRA Experts for Large Language Model based Bundle Generation
• RecoWorld: Building Simulated Environments for Agentic Recommender Systems
• GrACE: A Generative Approach to Better Confidence Elicitation in Large Language Models
• Latency and Token-Aware Test-Time Compute
• Uncovering Scaling Laws for Large Language Models via Inverse Problems
• Parallel-R1: Towards Parallel Thinking via Reinforcement Learning
• CancerGUIDE: Cancer Guideline Understanding via Internal Disagreement Estimation
• Test-Time Scaling in Reasoning Models Is Not Effective for Knowledge-Intensive Tasks Yet
• The Majority is not always right: RL training for solution aggregation
• Rethinking LLM Parametric Knowledge as Post-retrieval Confidence for Dynamic Retrieval and Reranking
• Connections between reinforcement learning with feedback,test-time scaling, and diffusion guidance: An anthology
• A Probabilistic Inference Scaling Theory for LLM Self-Correction
• Instance-Wise Adaptive Sampling for Dataset Construction in Approximating Inverse Problem Solutions
• GradeSQL: Test-Time Inference with Outcome Reward Models for Text-to-SQL Generation from Large Language Models
• LLaVA-Critic-R1: Your Critic Model is Secretly a Strong Policy Model
• Logical Reasoning with Outcome Reward Models for Test-Time Scaling
• Learning to Refine: Self-Refinement of Parallel Reasoning in LLMs
• SLIM: Subtrajectory-Level Elimination for More Effective Reasoning
• Optimal Sparsity of Mixture-of-Experts Language Models for Reasoning Tasks
• Deep Think with Confidence
• Trust but Verify! A Survey on Verification Design for Test-time Scaling
• Your Reward Function for RL is Your Best PRM for Search: Unifying RL and Search-Based TTS
• Controlling Multimodal LLMs via Reward-guided Decoding
• Retrieval-augmented reasoning with lean language models
• SSRL: Self-Search Reinforcement Learning
• Pass@k Training for Adaptively Balancing Exploration and Exploitation of Large Reasoning Models
• KDPE: A Kernel Density Estimation Strategy for Diffusion Policy Trajectory Selection
• ASPD: Unlocking Adaptive Serial-Parallel Decoding by Exploring Intrinsic Parallelism in LLMs
• RTTC: Reward-Guided Collaborative Test-Time Compute
• Causal Reward Adjustment: Mitigating Reward Hacking in External Reasoning via Backdoor Correction
• LLMs are Single-threaded Reasoners: Demystifying the Working Mechanism of Soft Thinking
• CTTS: Collective Test-Time Scaling
• Inference-time Scaling for Diffusion-based Audio Super-resolution
• Teaching Language Models To Gather Information Proactively

Discussions

• Beating GPT-4o and Claude 3.5 on SWE-bench Lite through repeated sampling [hn, 5 points, 0 comments]
• Large Language Monkeys: Scaling Inference Compute with Repeated Sampling [hn, 2 points, 0 comments]

Related

• Keep Guessing? When Considering Inference Scaling, Mind the Baselines
• Inference Scaling Laws: An Empirical Analysis of Compute-Optimal Inference for Problem-Solving with Language Models
• When Life Gives You Samples: The Benefits of Scaling up Inference Compute for Multilingual LLMs
• From Decoding to Meta-Generation: Inference-time Algorithms for Large Language Models
• A Simple Model of Inference Scaling Laws