Beyond Repeated Sampling: Learning Search Policies for LLM Reasoning
cs.CL, cs.AI
Submitted: 2026-09-22
Updated: 2026-09-22
License: http://creativecommons.org/licenses/by/4.0/
The gist: Large language models increasingly tackle hard reasoning problems by spending more test-time compute, yet the dominant strategy remains naive repeated sampling: draw many independent solutions and
Terminology
Abstract
Large language models increasingly tackle hard reasoning problems by spending more test-time compute, yet the dominant strategy remains naive repeated sampling: draw many independent solutions and hope one is correct. Because such sampling explores only through local decoding noise, it tends to produce many near duplicate attempts rather than genuinely different ideas. We ask whether exploration can instead be steered at a semantic level, by first sampling problem specific concepts, hints, or strategies and then conditioning answer generation on them. We refine this into a simple, more exploratory procedure that emits many diverse concepts in a single trajectory, and evaluate it on hard problems where repeated sampling struggles. We then go a step further and make concept generation trainable: a small concept generator is optimized with reinforcement learning so that its concepts maximize the downstream success of a larger, frozen answer generator. On hard mathematical reasoning problems, the trained concept generator substantially improves the answer generator's pass@k over naive repeated sampling at the same answer generation allocation, surpasses concepts drawn from much larger untuned models, and transfers to answer generators it was never trained against, including a model from a different family. A small model can thus be trained into an effective, reusable search policy for a much larger one.
Sources
- Benchmarks Saturate When The Model Gets Smarter Than The Judge
- Large Language Monkeys: Scaling Inference Compute with Repeated Sampling
- Evaluating Large Language Models Trained on Code
- The Llama 3 Herd of Models
- Not the Example, but the Process: How Self-Generated Examples Enhance LLM Reasoning
- Measuring Mathematical Problem Solving With the MATH Dataset
- Scaling Laws for Neural Language Models
- Olmo 3
- RLAD: Training LLMs to Discover Abstractions for Solving Reasoning Problems
- DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models
- HybridFlow: A Flexible and Efficient RLHF Framework
- Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters
- ToolOrchestra: Elevating Intelligence via Efficient Model and Tool Orchestration
- Self-Consistency Improves Chain of Thought Reasoning in Language Models
- Qwen2.5 Technical Report
- Qwen3 Embedding: Advancing Text Embedding and Reranking Through Foundation Models
- Automatic Chain of Thought Prompting in Large Language Models
Related papers
- Exploring Solution Divergence and Its Effect on Large Language Model Problem Solving
- Ishigaki-IDS-Bench: A Benchmark for Generating Information Delivery Specification from BIM Information Requirements
- Subliminal Steering: Stronger Encoding of Hidden Signals
- MedStruct-S: A Benchmark for Key Discovery, Key-Conditioned QA and Semi-Structured Extraction from OCR Clinical Reports
- The End of Transformers? On Challenging Attention and the Rise of Sub-Quadratic Architectures
- Untangling the Mechanisms of Misleading Context in Medical Question Answering