STRIDE: Strategic Trajectory Reasoning via Discriminative Estimation for Verifiable Reinforcement Learning

Qinjian Zhao, Zhihao Dou, Dinggen Zhang, Xiangyu Li, Chaoda Song, Zhongwei Wan, Xinpeng Li, Yanyan Zhang, Kaijie Chen, Qingtao Pan, Chengcheng Feng, Zhiqiang Gao, Xiaoyu XiaarXiv 2026 · arXiv

TL;DR

STRIDE is a fine-grained Reinforcement Learning with Verifiable Rewards (RLVR) framework that moves beyond uniform, trajectory-level rewards for Large Language Models. By contrasting successful and failed reasoning paths within the same response group, STRIDE isolates specific phrase-level ($n$-gram) strategic patterns that drive correct answers. This approach delivers precise credit assignment while preserving automated verifiability, yielding consistent performance boosts across complex math, multimodal, and agent-based tasks.

What Problem Does This Paper Address?

Reinforcement Learning with Verifiable Rewards (RLVR) has become a powerful tool for scaling up the reasoning capabilities of LLMs. By using automated, rule-based feedback (like checking if a math answer is correct or if code compiles), models can learn through trial and error.

However, standard RLVR suffers from a glaring sparse supervision problem. It typically evaluates only the final answer, applying a uniform reward or penalty to every single token in the reasoning trajectory. This means a correct response filled with redundant or sloppy logic gets fully rewarded, while an incorrect response containing brilliant intermediate steps gets entirely penalized.

While recent methods try to fix this by tracking intermediate signals like token generation entropy (uncertainty peaks), the authors show that these signals are not inherently verifiable. As illustrated in Figure 1, correct and incorrect trajectories exhibit nearly identical entropy distributions; uncertainty tells you where a critical decision is being made, but not whether it was the right move.

Figure 1: (a) Token-level entropy trajectories of correct and incorrect responses to the same questions show highly similar patterns, with nearly indistinguishable high-entropy peaks and frequencies. (b) The entropy density distributions of correct and incorrect responses also largely overlap, indicating that entropy alone cannot reliably determine whether a reasoning region contributes positively or negatively to the final outcome.

Methods

To bridge this gap, the authors introduce STRIDE (Strategic Trajectory Reasoning with Discriminative Estimation), which extracts fine-grained strategic supervision directly from verifiable outcomes via a four-step process:

  1. Group Sampling & Partitioning: For any given prompt, the policy model generates a group of responses (similar to Group Relative Policy Optimization, or GRPO). These responses are automatically partitioned into a successful subset ($D^+$) and a failed subset ($D^-$) based on final answer correctness.
  2. Frequency-Based Discriminability ($S_{freq}$): STRIDE analyzes short phrases ($n$-grams ranging from 2 to 5 tokens) across the trajectories. It computes a log-ratio score for each $n$-gram based on how much more frequently it appears in successful rollouts versus failed ones.
  3. Strategic Saliency Filtering ($H_{sal}$): To prevent the model from over-reinforcing routine filler text or common transitions that happen to skew toward correct answers, STRIDE applies an entropy filter. Only $n$-grams with an average token entropy above a threshold ($\tau = 2.5$) are flagged as true "decision-relevant" strategic patterns.
  4. Advantage Reweighting: Finally, a significance score combining both metrics is added directly to the base GRPO advantage. This selectively amplifies rewards for helpful strategic phrases (e.g., "convert minutes into hour") and penalizes harmful ones (e.g., "guess many small repeated numbers").

Datasets

The framework was trained and evaluated across several diverse domains:

  • Mathematical Reasoning: Trained on 30K problems from DeepMath. Evaluated on AIME24, AIME25, MATH500, AMC23, Minerva, and Olympiad.
  • Multimodal Reasoning: Evaluated using Qwen2.5-VL-7B on MMMU-Pro, MMMU, EMMA, and MMK-12 (covering Physics, Chemistry, and Biology).
  • Agentic Decision-Making: Trained on 7,160 trajectories from AgentGym and evaluated on WebShop, ALFWorld, and BabyAI.

Key Insights and Ideas

  • Entropy is Blind to Correctness: One of the paper's core realizations is that high-entropy "forking points" look identical regardless of the final outcome (see Figure 2). Token uncertainty marks the location of strategic choices, but outcome-based contrastive analysis is required to judge their quality.
  • The Power of the Phrase ($n$-gram): Standard token-level adjustments often fail to capture semantic meaning. By optimizing at the phrase level (2-5 tokens), STRIDE reinforces coherent strategic actions rather than isolated words.
  • Preserving Verifiability: Unlike Process Reward Models (PRMs) which require expensive human annotations or fallible GPT-4 critiques, STRIDE derives its fine-grained advantages purely from rule-based final correctness, keeping the training loop fully automated and scalable.

Key Results

STRIDE consistently outperformed standard GRPO and other competitive token-level RL baselines across all tested models and benchmarks:

  • Math Benchmarks: On Qwen2.5-7B-Instruct, STRIDE achieved a benchmark average of 44.71%, outperforming standard GRPO (41.61%) and the previous best token-level baseline, HET-DAPO (42.18%).
  • Ablation Impact: Removing the $n$-gram phrase modeling caused the largest performance drop (falling to an average of 40.39%), proving that optimizing multi-token strategic blocks is critical.
  • Multimodal & Agent Generalization: When extended to vision-language models (Qwen2.5-VL-7B), STRIDE pushed MMMU-Pro scores from a base of 30.5% up to 44.2%. On interactive agent tasks, it achieved the highest average score of 84.3%, beating strong offline RL baselines like AgentSTaR (82.6%).

Limitations and Future Work

  • Strict Verifiability Requirement: STRIDE relies entirely on splitting rollouts into binary success/failure groups. This limits its current application to fields with objective ground truths (math, code, games) and makes it harder to deploy on open-ended generation or creative writing.
  • Rollout Scale Dependency: The contrastive estimation requires a meaningful mix of both correct and incorrect answers within the sampled group. If a problem is too easy (all correct) or too hard (all incorrect), the discriminative signal degrades.
  • Rigid N-gram Windows: The use of fixed-length $n$-grams is a simplified proxy for strategy. The authors note that future work should explore more flexible semantic units, such as full syntactic clauses or logical propositions, to improve interpretability.

Summary updated

Abstract

Reinforcement Learning with Verifiable Rewards (RLVR) has become an effective post-training paradigm for improving the reasoning abilities of large language models. However, existing RLVR methods typically rely on final-answer correctness to assign trajectory-level rewards, providing sparse supervision and treating all tokens uniformly regardless of their actual contribution to reasoning. Although recent studies introduce intermediate signals such as process rewards, high-entropy tokens, and semantic uncertainty, these signals are often not inherently verifiable and may fail to distinguish beneficial strategic patterns from harmful ones. To address this limitation, we propose STRIDE (Strategic Trajectory Reasoning with Discriminative Estimation), a fine-grained RLVR framework that derives strategic reasoning supervision from verifiable outcomes. STRIDE contrasts successful and failed trajectories within each response group to estimate the outcome-discriminative preference of each $n$-gram strategic pattern, and further combines this signal with reasoning saliency entropy to identify decision-relevant strategic patterns. These patterns are assigned differentiated advantage values during RL optimization, enabling more precise credit assignment while preserving the verifiability of RLVR. Extensive experiments demonstrate that STRIDE consistently improves reasoning performance across diverse models, tasks, and extended settings, including VLMs and agent-based systems.
BibTeX
@misc{zhao2026stride,
  author = {Qinjian Zhao and Zhihao Dou and Dinggen Zhang and Xiangyu Li and Chaoda Song and Zhongwei Wan and Xinpeng Li and Yanyan Zhang and Kaijie Chen and Qingtao Pan and Chengcheng Feng and Zhiqiang Gao and Xiaoyu Xia},
  title = {{STRIDE: Strategic Trajectory Reasoning via Discriminative Estimation for Verifiable Reinforcement Learning}},
  year = {2026},
  eprint = {2606.15866},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2606.15866},
}

Loading related content...

Figure