Beyond Repeated Sampling: Learning Search Policies for LLM Reasoning
An RL-trained concept generator lifts a frozen LLM's pass@k on hard math versus repeated sampling.
The paper argues that repeated independent sampling wastes test-time compute on near-duplicate solutions. It instead samples problem-specific concepts, hints, or strategies and conditions answer generation on them. A small concept generator trained with reinforcement learning raises a larger frozen model's pass@k on hard math at the same answer budget, beats concepts from much larger untuned models, and transfers to generators it was not trained with, including another model family.
- Concept sampling explores semantically instead of local decoding noise.
- Reinforcement learning tunes a small generator for a frozen answer model.
- Pass@k improves versus repeated sampling at the same generation budget.
- The search policy transfers to a different model family.
Full article210 words · extracted from arxiv.org · click to collapse
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.
Text extracted automatically; images, tables and formatting may be missing. Original: https://arxiv.org/abs/2609.26704