rStar-Coder

Analysis

Why This Paper Matters

Code reasoning remains a critical bottleneck for large language models (LLMs), especially for complex, competition-level problems that require multi-step logic and algorithmic thinking. Existing datasets are often limited in size, quality, or diversity, and generating reliable test cases for synthetic problems is notoriously difficult. rStar-Coder addresses this by constructing a massive, verified dataset of 418K competition-level code problems with 580K long-reasoning solutions and rich test cases. This dataset enables fine-tuning of smaller models (1.5B-14B parameters) to achieve performance comparable to frontier reasoning LLMs like QWQ-32B, significantly lowering the barrier for advanced code reasoning.

How It Works

The rStar-Coder pipeline consists of four main stages:

1. Collection of Competitive Code Problems

A seed dataset is curated from public sources including TACO, APPS, CodeContests, CodeForces, USACO, and IOI (2002-2023). IOI problems are converted from PDF to LaTeX using Mathpix. After deduplication and filtering, 37,754 unique problems with at least one reference solution remain.

2. Synthesis of New Solvable Problems

Structured prompts guide an LLM to analyze a seed problem and its solution, identify core reasoning steps and knowledge points, then generate a new problem testing similar skills. The prompt explicitly instructs: "Analyze and understand the original problem and its solution. Identify the reasoning steps... Design a new problem that is similar to the original one and can be solved using the same knowledge points." This yields 1,565K synthetic problems.

3. Test Case Generation

A three-step pipeline ensures reliable input-output pairs:

• Utility function generation: GPT-4o generates two functions per problem: generate_test_input using the CYaRon library (a reliable input generation toolkit) and validate_test_input to check constraint satisfaction. This reduces hallucinations from direct LLM generation.

• Input scale definition: Scale-controlling parameters from the generation function are assigned value ranges to control test case difficulty.

• Execution and validation: For each parameter instantiation, generate_test_input is called, and only inputs passing validate_test_input are retained.

4. Mutual Verification for Output Labeling

For seed problems, the oracle solution provides ground-truth outputs. For synthetic problems, 16 candidate solutions are sampled from QWQ-32B, executed on at least 50 diverse test inputs. If a majority of candidates produce identical outputs across all inputs, both outputs and those candidates are considered correct. This mutual verification mechanism ensures high-quality labels without oracle solutions.

Augmentation and Post-Processing

Solutions are rewritten with detailed reasoning steps (e.g., self-reflection). For each problem, 16 CoT solutions are generated, retaining only those passing all tests. Unsolvable problems are filtered using agreement thresholds (60% for most, 40% for hard Codeforces problems). Decontamination removes overlaps with evaluation benchmarks. The final dataset contains 418K problems and 580K question-solution pairs.

Results

rStar-Coder significantly improves code reasoning across all model sizes. On HumanEval and MBPP, it achieves state-of-the-art results. On challenging Olympiad problems (USACO 2025), the 7B and 14B models outperform larger models like QWQ-32B, demonstrating the effectiveness of the verified dataset.

Significance

rStar-Coder provides a scalable, reproducible pipeline for generating high-quality synthetic code reasoning data. By combining curated seed problems, LLM-based synthesis, and robust mutual verification, it overcomes the key challenge of reliable test case generation. The resulting dataset enables smaller models to compete with frontier systems, democratizing access to advanced code reasoning capabilities. This work has broad implications for AI education, automated programming assistance, and the development of more capable coding assistants.