Unearthing Gems from Stones: Policy Optimization with Negative Sample Augmentation for LLM Reasoning (2025)

Abstract: Recent advances in reasoning language models have witnessed a paradigm shift from short to long CoT pattern. Given the substantial computational cost of rollouts in long CoT models, maximizing the utility of fixed training datasets becomes crucial. Our analysis reveals that negative responses contain valuable components such as self-reflection and error-correction steps, yet primary existing methods either completely discard negative samples (RFT) or apply equal penalization across all tokens (RL), failing to leverage these potential learning signals. In light of this, we propose Behavior Constrained Policy Gradient with Negative Sample Augmentation (BCPG-NSA), a fine-grained offline RL framework that encompasses three stages: 1) sample segmentation, 2) consensus-based step correctness assessment combining LLM and PRM judgers, and 3) policy optimization with NSA designed to effectively mine positive steps within negative samples. Experimental results show that BCPG-NSA outperforms baselines on several challenging math/coding reasoning benchmarks using the same training dataset, achieving improved sample efficiency and demonstrating robustness and scalability when extended to multiple iterations.

## introduction reasoning capabilities are a critical aspect of evaluating the intelligence of large language models (llms). recent advances have witnessed a paradigm shift from short to long chain-of-thought (cot) reasoning, particularly after the release of openai's o1 series @xcite and deepseek r1 @xcite . however, generating lengthy cot responses incurs substantial computational costs. in the online learning paradigm, the periodic rollout process has become the bottleneck of * equal contribution. the post-training system @xcite , significantly reducing training efficiency. consequently, maximizing the utility of fixed training datasets under offline learning paradigm becomes increasingly crucial. motivated by this, a natural question arises: how can we better utilize negative samples, particularly those from long cot model? currently, selfimprovement algorithms for enhancing llms' reasoning capabilities fall into two categories: rejection sampling fine-tuning (rft @xcite ) and reinforcement learning (rl @xcite @xcite ), yet neither fully exploits the potential of negative samples. for rft methods, negative samples are entirely discarded. while rl methods like dpo @xcite , grpo @xcite , and gpg @xcite attempt to leverage negative samples, they simply apply equal penalization to all tokens without fine-grained discrimination. we argue that while treating all steps in negative samples as flawed is reasonable for short cot responses due to their brevity and directness, the situation differs significantly in long reasoning trajectories. even when the final answer is incorrect, many intermediate steps can be valuable @xcite . as illustrated in figure 1(a) , we observe that model responses often exhibit intrinsic behaviors such as verification, errorcorrection, and self-reflection @xcite , with these patterns occurring more frequently than in positive samples, partly due to the typically longer response length of negative samples @xcite . therefore, in the long cot pattern, simply rejecting all steps of negative samples is not sound, potentially undermining beneficial reasoning steps. ppo @xcite attempts token-level credit assignment through value model. nevertheless, its effectiveness is limited by the exponentially growing action space under the long cot paradigm, requiring substantial data for accurate token-level value estimation. to better utilize negative samples, we propose a fine-grained offline rl framework named behavior constrained policy gradient with negative sample augmentation (bcpg-nsa). our framework first employs a semantic segmentation model to divide negative samples into multiple steps. these steps are then evaluated for correctness using an llm judger and/or a process reward model (prm) @xcite . finally, we introduce a novel token-level policy optimization objective that enables fine-grained leveraging of negative samples, where the penalization for valuable steps is reduced or even reversed to encourage their generation, with this adjustment strength controlled by the mining coefficient. experimental results demonstrate that bcpg-nsa achieves the best performance and improved sample efficiency compared to baselines on challenging math reasoning benchmarks aime24 and aime25, and o.o.d coding benchmark live-codebench. in addition, our ablation studies show that the consensus-based llm-prm annotation approach yields the best results compared to llmonly and prm-only approaches, indicating the importance of precise step correctness assessment in negative samples. we also demonstrate that bcpg-nsa is robust across different mining coefficient values, maintains stability over extended training epochs, and scales effectively to multiple iterations. our contributions are summarized as follows: long chain-of-thought reasoning language models llms have demonstrated remarkable reasoning capabilities in complex tasks. cot @xcite @xcite )is one of the significant methods to encourage and enhance the reasoning ability of llms, which guides llms to break down problems and solve them step by step. openai o1 (openai, 2024) is the first to introduce inference time scaling law, which employs large-scale rl to enable autonomous optimization of cot during training and overcome challenging tasks by generating more reasoning tokens. several efforts @xcite @xcite @xcite have successfully replicated the inference time scaling law, demonstrating the powerful capabilities of this new inference paradigm. process reward models in mathematical reasoning mathematical reasoning in llms has made significant strides with the introduction of reward models. reward models are primarily divided into two categories: outcome reward model (orm) and process reward model (prm). orms only score the final answer of the llms' responses, while prms assign scores to each reasoning step, providing granular feedback. consequently, prms can not only guide search @xcite but also offer dense rewards in rl training @xcite . benefits from negative data many rl methods for llms, such as grpo @xcite and gpg @xcite , consider every step in a negative sample incorrect, and use the same strength to push down the likelihood of all tokens in incorrect responses. prior research on learning from negative samples primarily focuses on training data construction. recent works on dpo @xcite propose constructing training pairs with shared prefixes between positive and negative samples, aiming to improve the model's decision-making at critical intermediate steps. another research targeting sft data construction @xcite additionally adds a prefix to indicate whether the current generation is a successful trajectory, helping the model better distinguish between correct and incorrect responses. the most closely related work @xcite ) leverages valuable signals from negative samples in short cot reasoning, through a specialized dual-lora framework for model distillation. under the long cot paradigm, incorrect and correct steps more frequently alternate throughout the reasoning process. therefore, fine-grained mining of the value of negative samples is a promising direction. ## preliminary analysis: the value of negative samples in this section, we investigate two fundamental questions: 1) can supervised fine-tuning on negative samples bring performance benefits? and if so, 2) to what extent can these benefits be realized? specifically, we construct two distinct training datasets from the open-source r1 dataset @xcite : sft-pos and sft-neg, to compare their respective performance gains when training the base model qwen2.5-14b-base @xcite . both datasets share identical prompts and contain an equal number of samples (19,000 each). the key difference lies in their composition: sft-pos consists exclusively of responses with correct final answers, while sft-neg contains only responses with incorrect answers. ## method our method bcpg-nsa encompasses three stages: thinking process segmentation, consensus-based step correctness annotation, and policy optimization with negative sample augmentation. the overall framework of bcpg-nsa is shown in figure 1(b) . ## conclusion in this paper, we present bcpg-nsa, a novel offline rl framework designed to effectively leverage valuable components within negative samples for llms' long cot reasoning. unlike existing methods that either discard negative samples or apply equal penalization, our approach enables fine-grained treatment of negative samples through three key components: semantic step segmentation, consensus-based step correctness assessment, and policy optimization with negative sample augmentation. experimental results on challenging reasoning benchmarks demonstrate that bcpg-nsa achieves superior performance and exhibits great robustness and scalability when extended to multiple iterations.