Beyond Repeated Sampling: When AI Learns to Plan Approaches Before Solving, Exploration Efficiency Transforms
A Frustrating Reality
Ask a mathematically strong student to solve a competition problem. They fail. Ask them to try again. They fail again. Try again. Fail.
After 100 attempts, each starting from scratch, they guessed correctly 3 times out of 100.
This is the current state of large language models doing mathematical reasoning—repeated sampling. Draw 100 independent answers and hope at least one is correct. That's how pass@k curves are plotted.
The problem: there is no "learning" across those 100 attempts. Each starts from zero, each circles in the same thinking pattern. Like a person repeatedly running into the same wall at slightly different angles.
The team at Meta FAIR and Université Paris-Saclay asked a more fundamental question: can AI think through several different approaches before actually solving the problem?
The Fundamental Flaw of Repeated Sampling
Suppose you ask a model to solve: "Find all positive integer pairs satisfying x² + y² = 25 and x + y = 7."
Repeated sampling generates 100 complete solutions independently. But the variation comes mainly from token-level randomness in decoding—not from differences in approach.
The result: all 100 solutions may use the same method—algebraic elimination—with slightly different ordering or minor computational differences. If the key to the problem is "changing the approach"—say, a geometric interpretation of the circle—then 100 repeated samples might never find it.
Analogy: ask 100 people with similar backgrounds and training to solve a puzzle independently, and they will most likely use the same method. Diversity doesn't come from "sampling more people"; it comes from "having each person use a different strategy."
Concept-Guided Sampling: Think of Approaches First, Then Solve
The paper's core innovation is Concept-Guided Sampling.
The process has two steps:
Step 1: Generate Concepts
Given a math problem, the model first generates multiple "concepts"—solution approaches, strategy hints, key observations. For example:
- "This can be solved with algebraic elimination"
- "Consider a geometric interpretation: x² + y² = 25 is a circle"
- "Try parametrization: let x = 5cosθ, y = 5sinθ"
- "Boundary cases: x and y are positive integers; enumerate possible combinations"
Step 2: Conditioned Generation
Then the model generates a complete solution conditioned on each concept. Same model, but told "use the geometric method" or "use parametrization," producing genuinely different solutions.
It's like giving 100 solvers each a different "hint card" before they solve. Diversity is injected at the source, not left to luck.
Making Concept Generation Trainable
But a new question arises: who generates good concepts?
You could use a bigger model (like GPT-5) to generate concepts. But the paper goes further—making concept generation itself trainable.
The approach: 1. Use a small model as the "concept generator" 2. It generates concepts; a large model generates answers based on them 3. Use answer correctness as the reward signal 4. Use reinforcement learning to optimize the small model so it generates concepts that "help the large model solve problems"
It's an elegant architecture: the small model doesn't solve problems directly—it learns "how to help the large model solve problems." It is trained as a search policy, not an answer generator.
Analogy: a junior analyst doesn't make decisions directly, but learns to provide good analytical frameworks to a senior analyst. The junior's value lies not in their own conclusions, but in whether they help the senior see more angles.
Experimental Results: A Small Model Teaching a Large Model to Solve Problems
Performance on Mathematical Reasoning
The paper tests on mathematical reasoning benchmarks with impressive results:
1. A trained small-model concept generator is more effective than an untrained large-model generator. A small model trained with RL can generate more useful solution concepts than GPT-5.
2. Significant pass@k improvement: at the same answer-generation budget (e.g., k=64), concept-guided sampling achieves far higher pass@k than repeated sampling. The gap is even larger on hard problems.
3. Cross-model transfer: a concept generator trained for model A also helps model B solve problems—even if B comes from a different model family. This shows the generator learns a "general search policy," not an overfit to a specific model.
Key Ablations
The paper runs important ablations to answer "why does it work":
Do question-specific concepts matter? Yes. Replacing question-specific concepts with random or generic ones significantly degrades performance. Concepts must be "approaches tailored to this problem," not generic "think carefully" prompts.
Is there an optimal number of concepts? Yes. Too few (1-2) lacks diversity; too many (>16) degrades quality. Middle values (4-8) work best.
Why This Matters
1. Exploration, Not Generation, Is the Reasoning Bottleneck
The current bottleneck for LLM reasoning isn't "can it generate a correct answer" but "can it think of the right approach." Repeated sampling explores only at the token level; concept-guided sampling explores at the semantic level. That's a qualitative leap.
2. Small Models Can Serve as Search Policies for Large Models
This is the most exciting finding. Conventional wisdom is "large models teach small models" (distillation). This paper reverses it: small models can teach large models how to think.
The small model doesn't produce answers—it produces "directions of thought." This opens a new collaboration paradigm: models of different scales divide labor at different levels, with small models handling "divergence" and large models handling "convergence."
3. Concepts Are Transferable Search Policies
A concept generator trained for model A helps model B. This suggests "good solution approaches" have some cross-model universality—just as good problem-solving strategies work for any mathematically strong student, regardless of their specific techniques.
An Honest Assessment
The paper has limitations.
First, experiments are mainly on mathematical reasoning, where correct answers exist and rule-based verification is possible. Open-ended tasks (writing, design, creativity) lack clear right/wrong answers; concept guidance remains unverified there.
Second, the concept generator needs to be trained on specific datasets. Though it transfers across models, cross-domain transfer (math to code, code to logic puzzles) is unverified.
Third, the extra concept-generation step adds inference cost. Though the paper compares "at the same answer-generation budget," the cost of generating concepts isn't counted. If the generator needs 100 runs to produce good concepts, that cost isn't negligible.
But the core contribution is clear: elevating exploration from token level to semantic level, and training the search policy itself with RL. That's a paradigm shift.
Implications for the Future
This paper evokes a deeper analogy: human problem-solving is also "dual-track."
Psychologists have long identified two modes: System 1 (fast intuition) and System 2 (slow reasoning). Concept-guided sampling is like adding a "System 1.5"—an intermediate "idea divergence" layer between System 1 (fast generation) and System 2 (full reasoning).
A more radical thought: reasoning itself may not be a linear "think-do-verify" but a "diverge-converge-verify" loop. Concept generation diverges, answer generation converges, reward signals verify. This three-step loop may be closer to real reasoning than simple "repeated sampling + verification."
If so, the "search policy" isn't just an engineering optimization—it's the essence of reasoning: intelligence lies not in "being able to think of the correct answer," but in "being able to think of enough different approaches, then selecting the right one."
---
Paper: Beyond Repeated Sampling: Learning Search Policies for LLM Reasoning
Authors: Ismail Labiad, Matthieu Kowalski, Marc Schoenauer, Rémi Munos, Julia Kempe (Meta FAIR / Université Paris-Saclay)