Classic curiosity — "go where you haven't been" — ported into the messy space of chain-of-thought, as a bolt-on exploration bonus for GRPO.
Reasoning RL (GRPO and friends) uses a sparse, right/wrong outcome reward. That collapses the model onto a few habitual chains of thought and kills exploration. MERCI adds a second, intrinsic reward: a count-based novelty bonus that pays the model to visit reasoning states it hasn't seen much. The counts come from a Coin Flipping Network (a neat trick for estimating visitation without literally counting strings), and the bonus is folded into the GRPO advantage. Result: consistent, small-but-real gains — GRPO 65.8 → 67.4 and DAPO 66.9 → 69.0 (pass@k avg on six math benchmarks), with the biggest jumps on the hardest problems (AIME25 50.0 → 60.0) and on out-of-domain SQL. Not a revolution, but a clean demonstration that a genuine curiosity drive helps LLM reasoning escape local ruts.
The idea
Curiosity is one of the oldest ideas in reinforcement learning: to explore well, give the agent an intrinsic reward for reaching novel states — states it has visited few times. In grid-worlds and Atari this is "count-based exploration": keep a visit count $N(s)$ for each state and add a bonus like $1/\sqrt{N(s)}$ so rarely-seen states become attractive. It works beautifully when states are discrete and countable.
The problem: an LLM's "state" is the entire token sequence generated so far. You will essentially never see the exact same reasoning prefix twice, so literal counts are always 1 and the classic bonus is useless. MERCI's bet is that you can still recover a meaningful notion of "how novel is this reasoning step" using a pseudo-count — an estimate of visitation learned by a small neural network — and that paying the reasoning policy for novelty, on top of the usual correctness reward, makes it explore richer chains of thought instead of grinding the same groove. In short: bring animal curiosity to chain-of-thought, and do it with a principled uncertainty estimator rather than a hack.
Reinforcement Learning with Verifiable Rewards (RLVR) — the DeepSeek-R1 recipe, usually via GRPO — trains a model to reason by sampling a group of answers per question and rewarding the ones that reach the correct final answer. The only signal is outcome correctness: sparse (one bit at the end of a long trajectory) and outcome-based (it says nothing about which reasoning steps were good).
Two well-documented pathologies follow. First, entropy collapse: as training proceeds the policy becomes confident and stops sampling diverse trajectories, so it can no longer discover a better solution than the ones it already favors. Second, repetitive, suboptimal reasoning: the model converges to a narrow set of templates that happen to work on the training distribution, and gets stuck in local optima. You can see this empirically — the authors note that plain GRPO's pass@k degrades late in training (from 65.8 down to 61.6 by step 260), a signature of an over-exploited policy. Prior fixes mostly tweak the correctness reward or the KL/entropy regularizer. MERCI instead imports the RL exploration toolbox — but adapts it to the fact that language "states" are uncountable.
MERCI (Motivating Exploration with count-based intrinsic Rewards for Chain-of-thought Inference) has three moving parts: a pseudo-count estimator, a way to turn per-step novelty into a trajectory-level bonus, and a careful scheme to inject that bonus into GRPO's advantage without destabilizing training.
Instead of a density model or hashing, MERCI uses the Coin Flipping Network — a slick way to estimate a visit count by solving a regression problem. Each time a state $s$ (the token sequence so far) is visited, you draw a fresh random label vector $c \in \{-1,+1\}^d$ (independent coin flips, $d=20$) and train a small head $f_\phi$ to regress toward it with MSE. The intuition: if a state has been visited many times, the network has seen many different random labels for it and averages toward zero; if visited rarely, it fits the few labels it saw and its output has large magnitude. The magnitude of the prediction therefore tracks the inverse count:
$$\frac{1}{d}\,\lVert f_\phi(s)\rVert^2 \;\approx\; \frac{1}{N(s)}$$This says the squared output length of the coin-flip network, averaged over its $d$ dimensions, approximates one-over-the-visit-count of that reasoning state — a differentiable stand-in for a counter you could never actually keep. That quantity also equals the estimated reward variance $\mathbb{V}[\hat r(s)]$, which is what plugs into the theory below.
MERCI leans on a simplified Uncertainty Bellman Equation. Because the reasoning MDP has deterministic, known transitions (the next state is just the current tokens plus the new token, $s' = (s,a)$), the usual propagation of uncertainty collapses into a clean sum of local reward variances along the trajectory. The paper is careful about one subtlety: you should sum the variances and then take a square root, not sum the standard deviations (the latter overestimates). The trajectory bonus is:
$$\mathcal{B} \;=\; \sqrt{\frac{1}{l}\sum_{i\in\mathbb{I}} \left(\frac{1}{d}\,\lVert f_\phi(s^i_{\text{hidden}})\rVert^2\right)}$$In words: take the CFN's inverse-count estimate at each selected reasoning position, average them over the trajectory, and square-root — giving a single normalized "how novel was this whole chain of thought" score. Normalizing at the trajectory level (rather than per token) turns out to be one of the choices that matters most.
Within each GRPO group of $G$ sampled answers, the raw bonuses are standardized and negatives are truncated, so the exploration advantage only ever adds pressure toward novelty:
$$\hat{A}^i_{\text{exp}} \;=\; \max\!\left(0,\; \frac{\mathcal{B}_i - \mu}{\sigma}\right)$$Then it is combined with the ordinary correctness advantage under a coefficient $\gamma$ and a clipping factor $\alpha$, so the exploration term can nudge but never dominate the correctness signal:
$$\hat{A}^i_{\text{new}} = \begin{cases}\min\!\big(\hat{A}^i_{\text{old}} + \gamma\hat{A}^i_{\text{exp}},\;(1+\alpha)\hat{A}^i_{\text{old}}\big), & \hat{A}^i_{\text{old}} \ge 0\\[4pt] \min\!\big(\hat{A}^i_{\text{old}} + \gamma\hat{A}^i_{\text{exp}},\;(1-\alpha)\hat{A}^i_{\text{old}}\big), & \hat{A}^i_{\text{old}} < 0\end{cases}$$This bounds the novelty bonus to a fraction of the existing advantage: a good-and-novel trajectory gets boosted, but novelty alone can't override being wrong. Finally, three filters keep the bonus honest before it is applied: percentile filtering (keep only the top 30% of positions for math, 20% for SQL), spatial coherence filtering (reward contiguous elevated regions, not isolated spikes), and noise-suppression filtering (strip out bonuses coming from code blocks and repetition). The ablations show the noise filter is the single most important one.
The gains are consistent across benchmarks and across two RL algorithms, and they are largest exactly where exploration should matter most — the hardest problems and out-of-domain transfer.
| Math (pass@k avg over 6 benchmarks) | Avg | AIME25 | AIME24 | MATH500 | Olympiad |
|---|---|---|---|---|---|
| GRPO | 65.8 | 50.0 | 76.7 | 91.8 | 59.7 |
| GRPO + MERCI | 67.4 | 60.0 | 80.0 | 91.4 | 60.9 |
| DAPO | 66.9 | 56.7 | 76.7 | 92.0 | 60.9 |
| DAPO + MERCI | 69.0 | 60.0 | 83.3 | 91.8 | 62.1 |
The headline single number: on AIME25 (a hard, contamination-resistant competition set) pass@k jumps from 50.0 to 60.0 when MERCI is added to GRPO — a +10-point absolute gain on precisely the problems where a stuck policy fails. On easy, saturated sets like MATH500 the effect is flat, as you'd expect (there's nothing left to explore). The mean@k numbers move too (GRPO 40.5 → 42.2; DAPO 42.2 → 44.9), so this isn't only a pass@k artifact.
| SQL | Bird (in-domain) P@16 | Spider (OOD) greedy | Spider P@16 |
|---|---|---|---|
| GRPO | 74.6 | 74.7 | 82.9 |
| GRPO + MERCI | 74.9 | 78.0 | 85.6 |
The SQL story is the more interesting one for the exploration thesis: in-domain (Bird) gains are tiny, but out-of-domain (Spider) gains are much larger (+3.3 greedy, +2.7 P@16). More exploration during training buys generalization, not just fit — consistent with the idea that the extra novelty pressure keeps the policy from over-specializing.
| Variant (GRPO, math pass@k avg) | Avg |
|---|---|
| GRPO baseline | 65.8 |
| MERCI w/o noise filtering | 63.8 |
| MERCI w/ token-level integration | 63.2 |
| MERCI w/ cumulative std (instead of variance) | 66.2 |
| Full MERCI | 67.4 |
Two findings stand out. Removing noise filtering or switching to token-level (rather than trajectory-level) integration actually drops performance below the GRPO baseline — an unfiltered or badly-normalized novelty bonus is worse than none. And the "sum variances then √" vs "sum std" choice is worth ~1.2 points. In other words, the theory (√ of accumulated variance) isn't decoration; the naïve version of the same idea underperforms.
Yes, but for a narrower reason than the framing implies. This is the most intellectually honest of the curiosity-for-LLMs papers I looked at: it doesn't claim to have discovered that LLMs "want" to explore, it just takes a 30-year-old, theoretically-grounded exploration mechanism (count-based bonuses, uncertainty Bellman equation) and does the real engineering to make it work when the "state" is a token sequence. The Coin Flipping Network is a genuinely elegant answer to "how do you count something you'll never see twice," and the ablations are the tell that the authors understand their own method — the naïve variants lose to the baseline, which is exactly what you'd expect if the details are load-bearing.
What keeps it at "interesting" rather than "hot": the gains are real but modest (~1.5–2 points on average), and the whole thing rides on GRPO — it's an add-on, not a new paradigm. The crux I'd scrutinize: is the CFN pseudo-count over hidden states actually measuring "reasoning novelty," or is it measuring surface-form novelty (new phrasings, new numbers) that happens to correlate with useful exploration on these benchmarks? The noise filter — which explicitly strips code and repetition — hints the raw signal is partly surface junk. The AIME25 +10 and the out-of-domain SQL transfer are the strongest evidence it's tracking something real, because those are the cases where memorized surface patterns shouldn't help. If you care about the reader's deeper question — can you give an LLM a genuine drive to seek novelty — this is a solid "yes, a little, and here's the honest amount," which is more useful than a paper overselling it.
Your feedback trains which papers I pick next and how I explain them. Anonymous — no login.