Abstract
Reinforcement Learning with Verifiable Rewards (RLVR) has emerged as a primary method for scaling Large Language Model (LLM) performance on mathematical benchmarks without human-labeled rationales. However, the extent to which RLVR induces genuine algorithmic reasoning versus superficial heuristic exploitation remains a critical open question. This study evaluates RLVR through two combinatorial tasks: Activity Scheduling and Longest Increasing Subsequence (LIS). Our findings reveal that while RLVR significantly improves final answer accuracy, it often fails to enhance sequence fidelity, leading models to adopt "reasoning theater" or shortcut heuristics that satisfy reward functions without executing the underlying logic. We demonstrate that models frequently rely on predictable input features rather than robust algorithms, highlighting fundamental limits to generalization in current RLVR paradigms.
Introduction
The recent surge in LLM mathematical performance is largely attributed to Reinforcement Learning with Verifiable Rewards (RLVR). By fine-tuning models against objective signals—such as a correct final answer or a passing unit test—training can be scaled efficiently. However, this creates a "shortcut exploitation" problem: models may achieve correct results for the wrong reasons. This paper moves beyond "black box" accuracy to measure sequence fidelity, evaluating whether a model's internal reasoning steps actually align with the correct algorithmic path, such as dynamic programming or greedy selection.
Methodology
We fine-tuned Qwen2.5-7B-Instruct and Llama-3.1-8B models using Group Relative Policy Optimization (GRPO). To investigate the impact of reward design, we tested several configurations:
- Answer-only ($r_{ans}$): A binary reward for the correct final numeric answer.
- Answer + Format ($r_{ans+fmt}$): A reward for correct answers plus a bonus for using specific tags (e.g.,
<think>) to prevent reasoning collapse. - Exact-IDs ($r_{ids, exa}$): A strict reward requiring the model to output the exact sequence of indices forming the optimal solution.
- Prefix-IDs ($r_{ids, pre}$): Partial credit for correct initial steps in a sequence.
Datasets
We focused on two classic combinatorial problems with unique, verifiable optima:
- Activity Scheduling: Solvable via a greedy algorithm (earliest finish time).
- Longest Increasing Subsequence (LIS): Typically solved using dynamic programming or patience sorting. Each dataset contained 2,000 instances with disjoint length ranges for training and testing to ensure the evaluation of generalization rather than memorization.
Results and Analysis
Performance Divergence and the "Hard Wall"
Our results indicate a significant gap between final answer accuracy and the model's ability to identify the correct underlying sequence. In the Activity Scheduling task, RLVR was relatively successful, with self-consistency (SC@k) improving from 0.24 to 0.68. However, in the more complex LIS task, a "hard wall" was observed where answer accuracy improved while sequence fidelity stagnated.
As shown in Figure 5, while answer accuracy for LIS improves with RL, the accuracy of the selected IDs (sequence fidelity) remains remarkably low for models trained on answer-only rewards ($r_{ans}$). This suggests the model is learning to predict the length of the subsequence using heuristics rather than identifying the actual elements.
Sequence Fidelity and "Reasoning Theater"
To quantify how well models followed the correct logic, we measured the Mean Longest Common Subsequence (LCS) between the model's output and the ground truth sequence of IDs.
Figure 6 illustrates that training on final answers alone ($r_{ans}$) provides minimal improvement in sequence fidelity (0.290) over the base model (0.248). Only when the reward function explicitly targets the sequence of IDs ($r_{ids, exa}$) does the model align its output with the correct algorithmic steps (0.517).
Furthermore, we observed "reasoning theater" in Activity Scheduling: models often output a "sorted" list that was factually incorrect or unrelated to the final answer, yet arrived at the correct result through unrelated internal heuristics. In LIS, "reasoning collapse" occurred when the model learned that writing out a Chain-of-Thought was a liability, leading it to jump directly to a guess to avoid potential errors in the reasoning chain.
Discussion: The Limits of Generalization
Regression analysis revealed that the model's errors were highly predictable ($R^2$ as high as 0.867) based on simple input features like list length or value range. This confirms that the models are relying on "rules of thumb" rather than executing robust algorithms. Additionally, attempts to "help" the model through sub-step rewards (e.g., rewarding sorting as a prerequisite) led to "curriculum failure," where the model optimized for the sub-step reward at the expense of the primary task.
Conclusion
RLVR is an effective tool for re-weighting a model's existing capabilities to improve benchmark scores, but it does not inherently induce new, complex reasoning strategies like dynamic programming if they are not already present. To move toward genuine logical depth, future research must focus on benchmarks that require verifiable intermediate steps and utilize mechanistic interpretability to detect and discourage shortcut exploitation.
Summary updated