Reinforced Efficient Reasoning via Semantically Diverse Exploration

1. Problem Statement

The paper addresses two critical limitations in current Reinforcement Learning with Verifiable Rewards (RLVR) for Large Language Models (LLMs), particularly in mathematical reasoning:

1. Limited Exploration Diversity: Existing methods, including those using Monte Carlo Tree Search (MCTS), often rely on generation entropy to determine branching points. The authors argue that high generation entropy (uncertainty in token selection) does not necessarily equate to semantic diversity. Models may branch at points where tokens are syntactically different but semantically identical (e.g., "can" vs. "need"), leading to redundant reasoning paths that fail to explore the solution space effectively.
2. Inefficient Reasoning (Overthinking): Current RLVR approaches often suffer from "overthinking," where models generate unnecessarily long reasoning chains to arrive at a correct answer. Existing credit assignment methods (like vanilla GRPO) uniformly propagate rewards across all tokens, failing to penalize redundant steps or reward concise reasoning.

2. Methodology: The ROSE Framework

The authors propose ROSE (Reinforced Efficient Reasoning via Semantically Diverse Exploration), a framework that integrates semantic-aware exploration with length-aware credit assignment.

A. Semantic-Entropy Guided Exploration

To solve the diversity issue, ROSE introduces a new branching strategy:

• Semantic Divergence ($SD_k$): Instead of just measuring token probability uncertainty, ROSE calculates the semantic distance between high-probability candidate tokens. It selects the top-20 tokens, retrieves their embeddings, and computes a weighted sum of pairwise cosine similarities. High divergence indicates that the model is choosing between semantically distinct concepts.
• Semantic Entropy ($SE_k$): The branching metric is defined as the product of Generation Entropy ($H_k$) and Semantic Divergence ($SD_k$):
  $$SE_k = SD_k \cdot H_k$$
  This ensures branching occurs only where there is both high uncertainty and high semantic difference, promoting genuinely diverse reasoning paths.
• $\epsilon$-Exploration Mechanism: To prevent the search from getting stuck in local optima, ROSE incorporates an $\epsilon$-greedy strategy. With probability $\epsilon$, the model regenerates a response from scratch (independent rollout) rather than branching from an existing tree node. This balances depth (tree exploration) and breadth (global exploration).

B. Length-Aware Segment-Level Advantage Estimation

To solve the efficiency issue, ROSE leverages the tree structure for granular credit assignment:

• Node Value Assignment: The tree is partitioned into segments based on branching nodes. The value of a node is the average reward of all responses passing through it.
• Segment Advantage: The advantage of a token is calculated as the difference in value between the current node and the parent node ($\hat{A}_{i,t} = \hat{V}(b_j) - \hat{V}(b_{j-1})$).
• Length-Aware Calibration: To penalize overthinking, the advantage of correct but longer reasoning chains is penalized relative to the shortest correct chain. If a response $o_c$ is longer than the shortest correct response $o_s$, the advantage for tokens after their divergence point is scaled down by a factor dependent on the length ratio:
  $$\hat{A}_{i,t} \leftarrow \hat{A}_{i,t} - |\hat{A}_{i,t}| \cdot \left(1 - \left(\frac{|o_s| - b_c}{|o_c| - b_c}\right)^\alpha\right)$$
  Here, $\alpha$ is a hyperparameter controlling the severity of the penalty.

3. Key Contributions

1. Semantic-Entropy Branching: A novel metric combining probabilistic uncertainty and semantic embedding divergence to guide MCTS branching, ensuring exploration of semantically distinct reasoning paths.
2. $\epsilon$-Exploration Mechanism: A stochastic mechanism to restart rollouts from the root, preventing the search process from becoming overly local.
3. Length-Aware Advantage Estimation: A segment-level credit assignment method that explicitly rewards concise reasoning and penalizes redundant steps, addressing the "overthinking" problem without degrading performance.
4. Comprehensive Validation: Extensive experiments demonstrating that ROSE outperforms state-of-the-art baselines (GRPO, DAPO, Dr.GRPO, TreePO, FR3E) across multiple model families (Qwen, Llama) and benchmarks.

4. Experimental Results

The authors evaluated ROSE on mathematical reasoning benchmarks (AIME2024, AIME2025, AMC2023, MATH500) using Qwen3 (4B/8B) and Llama-3.2 (3B) models.

• Performance Gains: ROSE consistently achieved the highest pass@8 scores.
  • On Qwen3-8B, ROSE achieved an average score of 55.75%, outperforming the best baseline (Dr.GRPO at 51.02%) by 4.73 percentage points.
  • On Llama-3.2-3B, ROSE improved the average score from 28.35% (GRPO) to 31.67%.
• Efficiency: ROSE significantly reduced the average token length of reasoning chains. For example, with $\alpha=1$, the Qwen3-8B model reduced reasoning length by 3.0% while improving accuracy, whereas standard GRPO variants often increased length.
• Ablation Studies:
  • Removing $\epsilon$-exploration caused a drop in performance, confirming the need for global exploration.
  • Replacing semantic entropy with random branching or standard generation entropy resulted in lower scores, validating the importance of semantic-aware branching.
  • Removing length-aware calibration led to longer, less efficient reasoning chains.

5. Significance

• Paradigm Shift in Exploration: ROSE moves beyond simple token-level uncertainty (generation entropy) to semantic-level uncertainty, a crucial step for improving LLM reasoning in complex tasks where surface-level variations do not imply logical diversity.
• Solving Overthinking: By integrating length penalties directly into the advantage estimation within an MCTS framework, ROSE provides a principled way to train models to be both accurate and concise, a common failure mode in current RLHF/RLVR approaches.
• Generalizability: The method is compatible with existing GRPO-based loss functions and does not require training a separate critic model, making it computationally efficient and easy to integrate into current RL pipelines for LLMs.

In summary, ROSE represents a significant advancement in RL for LLMs by simultaneously optimizing for diversity (via semantic entropy) and efficiency (via length-aware calibration), leading to more robust and concise reasoning capabilities.