Beyond Repeated Sampling: Learning Search Policies for LLM Reasoning

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.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Computation & Language / NLP

• arXiv preprint · 22 September 2026

  Matryoshka attribution: Learning to attribute language model outputs to representations and weights

  Aryaman Arora, Kirill Acharya, Nathan Hu and 4 others
• arXiv preprint · 23 September 2026

  Realize What Matters: Principled Context Representation for Large-Scale Reasoning

  Michael Theologitis, Dean Light, Shuyue Stella Li and 3 others
• arXiv preprint · 22 September 2026

  Compressing Long Context into Answer-Aligned Memory Embeddings for LLM Inference

  Md Mostafizer Rahman, Md Faizul Ibne Amin, Md Shahajada Mia and 2 others
• arXiv preprint · 23 September 2026

  Beyond Overlap: Estimating the Causal Effect of Benchmark Exposure

  Divyansh Singh
• arXiv preprint · 22 September 2026

  Rewired or Gated? How Instruction Tuning Shapes Knowledge-Conflict Circuits in LLMs

  Shubham Santosh Pandere, Gautam Ranka, Ritika Varshney and 3 others

All new papers in Computation & Language / NLP