Rewarding the Rare: Uniqueness-Aware RL for Creative Problem Solving in LLMs

Zhiyuan Hu, Yucheng Wang, Yufei He, Jiaying Wu, Yilun Zhao, See-Kiong Ng, Cynthia Breazeal, Anh Tuan Luu, Hae Won Park, Bryan Hooi

TL;DR

Large language models (LLMs) trained with reinforcement learning (RL) often get stuck in a rut, finding only a few "good enough" solutions and failing to explore more creative or rare strategies. This paper introduces "Uniqueness-Aware RL," a method that explicitly rewards LLMs for discovering novel, high-level reasoning strategies, leading to better performance on complex tasks without sacrificing accuracy.

What Problem Does This Paper Address?

Reinforcement learning (RL) is a powerful technique for fine-tuning large language models (LLMs) for complex reasoning tasks. However, a common issue is "exploration collapse," where the LLM's policy quickly converges to a small set of dominant reasoning patterns. While this might improve performance on a single solution (pass@1), it severely limits the diversity of solutions found, hindering performance when multiple diverse solutions are needed (pass@k). The authors argue that existing methods focus too much on local token-level variations rather than the diversity of high-level strategies used to solve a problem. This leads to LLMs that might rephrase the same core idea in slightly different ways, rather than discovering genuinely different approaches.

Methods

The core innovation is Uniqueness-Aware Reinforcement Learning (URL). Instead of just rewarding correct answers, URL rewards correct solutions that employ rare high-level strategies. Here's how it works:

  1. Rollout Generation: For a given problem, the LLM generates multiple reasoning traces (rollouts).
  2. LLM-based Strategy Clustering: An LLM judge is used to group these rollouts based on their high-level solution strategies, ignoring superficial differences in wording or minor algebraic steps. This creates clusters of similar strategies.
  3. Uniqueness Weighting: The size of each strategy cluster is used to calculate a "uniqueness weight." Rollouts belonging to smaller clusters (rarer strategies) receive higher weights.
  4. Advantage Reweighting: The standard RL advantage signal (which reflects correctness and difficulty) is multiplied by this uniqueness weight. This means correct solutions using rare strategies get a boosted reward, while correct solutions using common strategies are downweighted.
  5. Policy Optimization: The LLM's policy is updated using this reweighted advantage, encouraging it to explore and discover these rarer, more creative strategies.

This approach builds upon the Group-based Reinforcement Learning framework, specifically GRPO (Group Relative Policy Optimization).

Datasets

The authors evaluate their method on several challenging reasoning benchmarks across different domains:

  • Mathematics: MATH (Levels 3-5), AIME 2024/2025, HLE (Humanity's Last Exam).
  • Physics: Textbook reasoning split from the Mega-Science corpus, OlympiadBench.
  • Medicine: MedCaseReasoning.

They use LLMs like Qwen2.5-7B, OLMo-3-7B, and Qwen3-8B for training and evaluation.

Key Insights and Ideas

  • Strategy-level diversity is crucial: The paper strongly argues that focusing on superficial token-level diversity is insufficient for true exploration. The real goal is to discover genuinely different approaches to solving a problem.
  • "Rewarding the rare" works: By explicitly incentivizing novel strategies, the LLM is pushed beyond common solutions, leading to richer exploration and better performance on tasks requiring diverse approaches.
  • LLM judges are effective for strategy identification: Using an LLM to cluster rollouts by strategy is a practical and effective way to quantify strategy uniqueness, even for complex reasoning tasks.
  • URL complements existing RL: The method is presented as a drop-in replacement for the advantage calculation in existing RL frameworks like GRPO, making it easy to integrate.

Key Results

  • Improved Pass@k: URL consistently improves pass@k performance across mathematics, physics, and medicine benchmarks, especially at larger sampling budgets (k=64, 128, 256).
  • Higher AUC@K: The Area Under the Curve (AUC@K) for pass@k performance is significantly increased, indicating a better trade-off between accuracy and coverage of diverse solutions. For example, on AIME, AUC@64 increased by +0.044 with URL compared to a strong RL baseline.
  • Sustained Exploration: Policy entropy dynamics show that URL maintains a higher and more stable entropy during training compared to standard GRPO, which exhibits a downward trend indicating exploration collapse.
  • Increased Human Solution Coverage (cover@n): Human evaluations show that URL models recover a greater percentage of canonical human solution strategies, demonstrating a deeper understanding of diverse problem-solving approaches. For instance, on a geometry problem, URL achieved 100% coverage of five human-referenced ideas, while the baseline only covered two.
  • No Sacrifice in Pass@1: The method improves pass@k without degrading pass@1 performance.

Limitations and Future Work

  • LLM Judge Overhead: The reliance on an LLM judge for strategy clustering introduces computational overhead.
  • Task-Dependent Strategy Definition: The definition of a "high-level strategy" can be task-dependent, and misclusterings by the judge could impact performance.
  • Limited to Single Problem: The current method measures rarity only within the rollout set of a single problem, not across different problems or in a long-term novelty sense.

Future work could explore more efficient, globally consistent, or judge-free formulations of uniqueness-aware objectives, and extend the concept to cross-problem diversity.

Summary updated

Abstract

Reinforcement learning (RL) has become a central paradigm for post-training large language models (LLMs), particularly for complex reasoning tasks, yet it often suffers from exploration collapse: policies prematurely concentrate on a small set of dominant reasoning patterns, improving pass@1 while limiting rollout-level diversity and gains in pass@k. We argue that this failure stems from regularizing local token behavior rather than diversity over sets of solutions. To address this, we propose Uniqueness-Aware Reinforcement Learning, a rollout-level objective that explicitly rewards correct solutions that exhibit rare high-level strategies. Our method uses an LLM-based judge to cluster rollouts for the same problem according to their high-level solution strategies, ignoring superficial variations, and reweights policy advantages inversely with cluster size. As a result, correct but novel strategies receive higher rewards than redundant ones. Across mathematics, physics, and medical reasoning benchmarks, our approach consistently improves pass@$k$ across large sampling budgets and increases the area under the pass@$k$ curve (AUC@$K$) without sacrificing pass@1, while sustaining exploration and uncovering more diverse solution strategies at scale.
BibTeX
@inproceedings{hu2026rewarding,
  author = {Zhiyuan Hu and Yucheng Wang and Yufei He and Jiaying Wu and Yilun Zhao and See-Kiong Ng and Cynthia Breazeal and Anh Tuan Luu and Hae Won Park and Bryan Hooi},
  title = {{Rewarding the Rare: Uniqueness-Aware RL for Creative Problem Solving in LLMs}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2026},
  doi = {10.18653/v1/2026.findings-acl.1982},
}

Loading related content...

Figure