We study how to scale reasoning token budgets for competitive programming through two complementary approaches: training-time reinforcement learning (RL) and test-time parallel thinking. During RL training, we observe an approximately log-linear relationship between validation accuracy and the average number of generated reasoning tokens over successive checkpoints, and show two ways to shift this training trajectory: verification RL warmup raises the starting point, while randomized clipping produces a steeper trend in the observed regime. As scaling single-generation reasoning during RL quickly becomes expensive under full attention, we introduce a multi-round parallel thinking pipeline that distributes the token budget across threads and rounds of generation, verification, and refinement. We train the model end-to-end on this pipeline to match the training objective to the test-time structure. Starting from Seed-OSS-36B, the full system with 16 threads and 16 rounds per thread matches the underlying RL model's oracle pass@16 at pass@1 using 7.6 million tokens per problem on average, and surpasses GPT-5-high on 456 hard competitive programming problems from AetherCode.
Figures & tables
Figure 1: Log-linear trend: validation accuracy scales linearly with the logarithm of the average number of reasoning tokens during RL training. Each point corresponds to a successive RL training checkpoint.
Figure 2: Randomized clipping replaces the hard reward cliff (left) with a smooth ramp (middle), producing a steeper log-linear scaling curve (right).
Figure 3: Training pipeline: SFT cold start with generation and verification trajectories, followed by verification RL and generation RL.
Figure 4: Verification RL warmup. Left : recall remains high while precision and accuracy improve during verification RL. Right : initializing generation RL from the verification checkpoint shifts the log-linear scaling curve upward.
Figure 5: The parallel thinking inference pipeline. The system spawns N independent threads. Each thread generates a candidate solution, then verifies it via V independent sampling calls, each producing a correctness judgment and reasoning. If all V verdicts unanimously deem the solution correct, the thread terminates early; otherwise, one negative verdict is randomly selected and the model refines the solution conditioned on the previous attempt and the selected reasoning. This verify-refine loop repeats for up to M rounds. After all threads complete, all solutions across threads and rounds are ranked by verification vote count, and the highest-scoring one is returned.
Figure 6: Left : Unified token budget axis spanning training-time RL scaling from 20K to 60K tokens and test-time parallel thinking with the end-to-end RL model from 60K to 7.6M tokens. Sequential refinement outperforms parallel generation at every token budget; combining both extends scaling beyond the sequential plateau and surpasses GPT-5-high by a wide margin. Right : Effect of end-to-end RL on sequential-plus-parallel scaling. Separate training initially outperforms end-to-end RL with turn-grouped GRPO due to stronger single-round generation, but the latter catches up by ∼2 M tokens and overtakes it at higher budgets. End-to-end RL with REINFORCE scales substantially worse. 3 3 3 Due to limited computational resources, we evaluate the REINFORCE checkpoint only up to N=8 threads and M=8 rounds. Even within this truncated range, it remains substantially below the other methods at comparable token budgets.
Figure 7: Parallel scaling accuracy versus number of threads N for varying verdicts V∈{1,2,4,8} ( colored ), with M=1 , i.e., no refinement. More verdicts improve ranking quality, but the gap to the oracle pass@ N ( dashed ) remains substantial, suggesting that verifier capability is the primary bottleneck.
Figure 8: Oracle pass@ k versus token budget for three training stages: SFT cold start , verification RL , and generation RL after verification RL . Generation RL dominates at every token budget. The gap persists even at pass@ 256 , indicating that RL can expand solution coverage beyond the SFT frontier rather than merely concentrating probability on existing solutions.
While large language models (LLMs) have demonstrated strong performance on complex reasoning tasks such as competitive programming (CP), existing methods predominantly focus on single-attempt settings, overlooking their capacity for iterative refinement. In this paper, we present RefineRL, a novel approach designed to unleash the self-refinement capabilities of LLMs for CP problem solving. RefineRL introduces two key innovations: (1) Skeptical-Agent, an iterative self-refinement agent equipped with local execution tools to validate generated solutions against public test cases of CP problems. This agent always remains skeptical of its own outputs and thereby enforces rigorous self-refinement even when validation suggests correctness. (2) A reinforcement learning (RL) solution to incentivize LLMs to self-refine with only standard RLVR data (i.e., problems paired with their verifiable answers). Extensive experiments on Qwen3-4B and Qwen3-4B-2507 demonstrate that our method yields substantial gains: after our RL training, these compact 4B models integrated with the Skeptical-Agent not only outperform much larger 32B models but also approach the single-attempt performance of 235B models. Notably, although our models are trained solely on CP coding data, RefineRL also substantially improves their performance on mathematical reasoning benchmarks, suggesting that the learned self-refinement behavior can transfer beyond coding-specific tasks. These findings highlight self-refinement as a promising direction for scaling LLMs' general reasoning ability.
Shaopeng Fu, Xingxing Zhang, Li Dong +1
Work done during an internship at Microsoft Research · KAUST · Microsoft Research
Reasoning LLMs often spend substantial tokens on long intermediate reasoning traces (e.g., chain-of-thought) when solving new problems. We propose to summarize and store reusable reasoning skills distilled from extensive deliberation and trial-and-error exploration, and to retrieve these skills at inference time to guide future reasoning. Unlike the prevailing reasoning from scratch paradigm, our approach first recalls relevant skills for each query, helping the model avoid redundant detours and focus on effective solution paths. We evaluate our method on coding and mathematical reasoning tasks, and find that it significantly reduces reasoning tokens while improving overall performance. The resulting lower per-request cost indicates strong practical and economic potential for real-world deployment.
Guangxiang Zhao, Qilong Shi, Xusen Xiao +3
Qiyuan Tech · Tsinghua University · The University of Hong Kong +1
Scaling test-time compute via extended reasoning has become a key paradigm for improving the capabilities of large language models (LLMs). However, existing approaches optimize reasoning under fixed or uniformly sampled token budgets, ignoring the fundamental mismatch between problem difficulty and allocated compute. This leads to overthinking on easy problems and underthinking on hard ones, resulting in suboptimal token efficiency across diverse reasoning scenarios. In this paper, we propose Budget-Adaptive Curriculum Reasoning (BCAE), a unified framework that jointly optimizes reasoning quality and token efficiency through three synergistic components: (1) a budget-conditioned unified policy that embeds the token budget as a continuous conditioning signal, eliminating the need for decoupled thinking and summarization strategies; (2) a curriculum-aware budget scheduler that adaptively shifts the training budget distribution from easy to hard problems based on real-time learning progress; and (3) a truncation-aware dense reward mechanism that provides fine-grained credit assignment at intermediate reasoning steps via process-level verification. We further introduce Budget-Conditioned Advantage Estimation (BCAE), a novel variance reduction technique that conditions the advantage baseline on the sampled budget, yielding more stable policy gradients. Experiments on mathematical reasoning benchmarks (MATH, GSM8K, AIME, and Minerva Math) demonstrate that BACR consistently outperforms other strong baselines across all token budgets, achieving up to 8.3% accuracy improvement under tight budgets while reducing average token consumption by 34% compared to unconstrained reasoning.