Large language models increasingly rely on test-time compute to solve hard reasoning problems. The dominant strategy remains deceptively simple: draw many independent solutions through repeated sampling and keep those a verifier or judge deems correct. But this approach explores only through local decoding noise, and it tends to produce many near duplicate attempts rather than genuinely different ideas. A paper submitted to arXiv on September 22, 2026, asks whether exploration can be steered at a semantic level instead.
Beyond Repeated Sampling: Learning Search Policies for LLM Reasoning comes from Ismail Labiad, Matthieu Kowalski, Marc Schoenauer, Rémi Munos, and Julia Kempe at Meta FAIR and the Université Paris-Saclay. The paper proposes a two-part answer. First, an inference-time procedure that emits many diverse concepts in a single trajectory rather than generating them one at a time. Second, a trainable concept generator optimized with reinforcement learning so that its concepts maximize the downstream success of a much larger, frozen answer generator. On hard mathematical reasoning problems, the trained concept generator doubles the answer generator's pass@128 from 19.0 percent to 39.2 percent, surpasses concepts drawn from a model ten times larger, and transfers to answer generators it was never trained against.
Why Repeated Sampling Falls Short on Hard Problems
Repeated sampling works by drawing multiple complete answers from the same model and selecting the best. On easy problems, this reliably finds correct solutions. On hard problems, the sampling distribution is concentrated around incorrect or incomplete reasoning, and the model repeatedly explores the same dead ends through small perturbations to token-level decoding.
The paper identifies two practical limitations of prior concept-guided approaches. First, concepts are generated one at a time in an iterative loop, which is wasteful because LLMs are autoregressive and will generate newer concepts conditioned on the older ones. Second, the method generates approximately one concept per problem on average, sharply limiting the diversity the approach was meant to provide. The authors find that when the repeated-sampling baseline is allowed to use exploratory decoding parameters, the advantage of concept-guided sampling largely disappears across all model size pairs.
These observations motivate a rethinking of the approach. Rather than using concepts as an auxiliary loop around repeated sampling, the paper proposes generating all concepts in a single trajectory and evaluating on hard problem subsets where repeated sampling fails outright.
Concept-Guided Sampling: From Iterative to Single-Trajectory
The first contribution is an improved inference-time procedure. Instead of sampling concepts one by one, the method prompts the concept generator to analyze a problem and emit all useful concepts in a single trajectory. Each concept is required to be high-signal, problem-specific, and non-duplicative. Up to ten concepts are parsed from the trajectory, and answer rollouts are conditioned on them.
The evaluation focuses on model-specific hard subsets constructed from the MATH test set. For each answer-generator size, only problems where the repeated-sampling baseline obtains zero percent accuracy with 100 rollouts are retained. This ensures the comparison targets problems where naive sampling genuinely struggles.
On these hard subsets, the single-trajectory procedure produces consistent gains. Almost every concept-generator and answer-generator pair improves over the repeated-sampling baseline, with gains of up to 9.7 pass@50 points. The improvements scale with the strength of the concept generator. Most importantly, a small 7 billion parameter generator raises a 32 billion parameter answer generator by 8.8 points, indicating that useful exploration can be produced with little compute and injected into a larger, possibly frozen or closed-source, answer generator.
The approach also generates far more concepts than the prior method. Whereas the original procedure produced about one concept per problem, single-trajectory generation yields between 4 and roughly 10 concepts on average, with stronger generators saturating the cap of ten. This increase in concept count coincides with the accuracy gains, suggesting that diversity of exploration concepts is central to the improvement.
Training Concept Generators as Search Policies
The inference-time results raise a natural question: can a small model be trained to generate better concepts for a larger answer generator? This is useful because the larger answer generator may be impractical to train directly, or its weights may be unavailable, accessible only through an API.
The paper frames this as an RL problem over concepts rather than answers. The concept generator is trained with reinforcement learning, rewarding each concept trajectory by the downstream success of the answer generator it steers. The answer generator remains frozen throughout, making the concept generator a reusable search policy that can be deployed against any sufficiently capable answer generator.
For each problem, the concept generator samples eight concept trajectories. Each trajectory receives a downstream reward computed from 128 answer-rollout allocations distributed across the parsed concepts. Correctness is graded by an LLM judge, and rewards are aggregated in two ways. Max-of-max assigns a binary reward if any answer rollout from any concept is correct, rewarding the discovery of at least one concept that unlocks a solution. Max-of-mean takes the maximum over concepts of the per-concept accuracy, rewarding concepts that are reliably useful rather than occasionally correct.
The concept generator is trained with a GRPO-style objective, a variant of group relative policy optimization. Training runs for 200 batches using the Qwen2.5-7B-Instruct model as the concept generator and Qwen2.5-32B-Instruct as the frozen answer generator. Training data comes from DeepMath-103k, filtered to problems where the answer generator achieves less than 5 percent success with 128 rollouts. The held-out evaluation set consists of problems where the answer generator achieves zero percent success.
Results: Doubling Pass@k on Hard Problems
The trained concept generator substantially improves pass@k over naive repeated sampling on the held-out hard problems. The max-of-mean variant reaches 39.2 percent pass@128, roughly double the 19.0 percent of naive repeated sampling. The gap holds at smaller allocations: 29.6 percent versus 11.4 percent at pass@64.
A generic, problem-agnostic prompt modification helps only modestly, reaching 22.6 percent pass@128, far below problem-specific concepts. This indicates that most of the improvement comes from problem-specific concepts rather than generic prompt perturbation. A random derangement test confirms this: when concepts are mismatched across problems, performance drops to 23.9 percent, on par with the generic baseline.
The trained 7B concept generator surpasses the untuned 32B concept generator, reaching 39.2 percent pass@128 versus 33.8 percent. This supports the view that the concept generator learns a specialized search policy rather than relying on model scale. Useful exploration can be produced with a small model and injected into a larger frozen answer generator.
Transfer Across Models and Datasets
The trained concept generator transfers without retraining to Llama-3.3-70B-Instruct, a larger model from a different family. The concept generator was trained only against the Qwen2.5-32B answer generator and never sees Llama during training. On the DeepMath held-out set, the transferred CG reaches 34.3 percent pass@128 versus 26.2 percent for naive sampling and 28.9 percent for Llama generating its own concepts.
The small trained CG outperforms the ten-times-larger answer generator's self-generated concepts despite never being trained against it. This indicates the CG learns a transferable exploration policy rather than one tied to a specific answer generator.
The improvement also persists out of distribution. On Omni-MATH 2, a filtered subset of the Omni-MATH benchmark used only for evaluation, the trained CG reaches 18.6 percent pass@128 versus 11.3 percent for naive sampling. The margin is smaller than on DeepMath, but the direction is consistent.
Diversity analysis confirms the mechanism. Embedding the generated chains of thought and measuring their diversity shows that concept guidance, and especially the trained CG, produces more diverse reasoning than naive sampling. The improvement comes from reshaping the answer generator's exploration distribution rather than merely drawing more samples from the same distribution.
Analysis and Practical Considerations
Training is compute-heavy, and the bottleneck is reward estimation, not concept generation. Scoring eight concept trajectories for a problem requires 1,024 generations from the frozen answer generator plus 1,024 judge calls. In a representative training step, the AG rollouts and judging consume roughly 94 percent of the time, while concept generation takes only about 18 seconds and the actor update about 10 seconds. Training is run only once, however, so the compute cost is a one-time investment.
Training saturates after a few hundred steps. Longer training yields no sustained gain, and the max-of-mean objective eventually becomes unstable, justifying the choice of 200 steps. The paper also finds that position effects and answer leakage are not significant confounds, as verified through controlled ablations.
The approach has limitations. It is evaluated primarily on mathematical reasoning tasks where answer correctness can be verified. Extension to open-ended generation or tasks without clear correctness criteria remains open. The use of an LLM judge for correctness grading introduces its own limitations, and a separate high-quality judge would consume additional resources.
What This Means for Practitioners
For teams deploying LLMs on hard reasoning tasks, the paper offers a practical insight: exploration at the semantic level can substantially outperform exploration at the token level. On problems where repeated sampling fails, investing compute in generating diverse reasoning concepts can unlock solutions that the model would never find on its own.
The trained concept generator functions as a reusable search policy. Once trained against a frozen answer generator, it can steer any sufficiently capable model, including closed-source systems accessible only through an API. This decouples the cost of training a strong reasoning model from the cost of deploying it: a small, trained concept generator can improve a large, frozen answer generator without any gradient updates to the answer generator.
The framework also suggests a broader design principle for LLM reasoning systems. Separating the decision of which ideas to explore from the execution of the full solution can be more effective than generating complete answers in parallel. This mirrors how human experts approach hard problems, pausing to consider which ideas or tools might apply before committing to a full derivation. The paper provides both the empirical evidence and the practical infrastructure to implement this approach.