# microsoft/rstar architecture

> Architecture diagram of the GitHub repository microsoft/rstar, generated by GitDiagram from its file tree, README and a sample of source files (last updated 2025-05-16). It is an AI-made overview: check details against the source.

- Interactive diagram: https://gitdiagram.com/microsoft/rstar
- Repository: https://github.com/microsoft/rstar

## Overview

##### Project Type and Purpose
- This is an open-source, research-oriented Python codebase that implements an ML pipeline for math reasoning with small language models (SLMs) via Monte Carlo Tree Search (MCTS).
- Its core goal is to generate high-quality reasoning trajectories (deep thinking) using a policy model and a reward model, use those trajectories to produce training data (SFT and RM), train the models, and finally evaluate on math benchmarks.

##### High-Level Architecture
A. Configuration & Data
B. Core Inference Pipeline (main.py, eval.py)
C. Data Extraction & Training Pipeline (extra_*.py, train/)
D. Evaluation & Results

##### Main Components
A. Configuration & Data
- config/*.yaml – defines MCTS parameters, beam-search, sampling settings.
- eval_data/*.json – raw math problem datasets.
- few_shots/*.json – prompt templates and few-shot examples for policy initialization.
B. Core Inference
- main.py – orchestrates trajectory generation:
- loads config, model_dir (policy), optionally reward_model_dir.
- instantiates LLM engine (rstar_deepthink/llms/llm_engine.py).
- invokes MCTS or beam search agents (rstar_deepthink/agents/).
- interacts with node abstractions (rstar_deepthink/nodes/).
- writes raw trajectory files.
- run_example.sh – convenience script demonstrating multi-trajectory runs.
- eval.py, eval_output.py – wrappers for Greedy decode and result file evaluation.
C. Data Extraction & Training
- extra_sft_file.py, extra_rm_file.py – parse MCTS trajectory files into SFT and RM datasets.
- train/
- sample_sft_data.py, sample_rm_data.py – subsample data for training.
- train_SFT.py (distributed fine-tuning of the policy model).
- train_RM.py (reward model training via pairwise preference).
- save_rm.py – convert checkpoints to RM format.
D. Utilities & Supporting Code
- utils/ – math answer checking, parsing, generic utilities.
- rstar_deepthink/solver.py – high-level wrapper combining prompts, agents, and node logic.
- rstar_deepthink/tools/python_tool.py – code execution tool for solving subproblems.

##### Relationships and Data Flow
1. Preprocessing
- Input: eval_data and few_shots JSON.
- Output: few-shot prompts ready for the inference pipeline.
2. Inference Pipeline (main.py)
- Config Loader → LLM Engine → Agent (MCTS/Beam Search) → Node Expansion → Reward Model → Trajectory Storage
3. Extraction Pipeline
- Take raw trajectories → extra_sft_file / extra_rm_file → generate .jsonl of SFT and RM examples
- sample_* scripts → create training subsets
4. Model Training
- Distributed SFT and RM training scripts consume sampled data → produce updated policy and reward model checkpoints
5. Iteration
- New policy and reward models feed back into the inference pipeline for further rounds.
6. Evaluation
- eval.py and eval_output.py apply models to test sets → compute accuracy metrics.

##### Architectural Patterns & Design Principles
- Modular CLI: each script has a single responsibility (generate, extract, sample, train, evaluate).
- Config-driven execution: all parameters (e.g., GPU allocation, MCTS depth, beam width) are externalized in YAML.
- Clear separation of concerns:
- rstar_deepthink/ for core algorithmic logic
- train/ for training loops
- utils/ for cross-cutting utilities
- Data lineage tracking: raw trajectories → extracted examples → model checkpoints → new trajectories

## Diagram (Mermaid)

```mermaid
flowchart TD
    %% Config & Data Layer
    subgraph "Configuration & Data"
        direction TB
        cfg["Config Files (.yaml)"]:::config
        evalData["Evaluation Data (.json)"]:::data
        fewShots["Few-Shot Templates (.json)"]:::data
    end

    %% Core Inference Layer
    subgraph "Core Inference Pipeline"
        direction TB
        main["main.py"]:::inference
        run_example["run_example.sh"]:::inference
        llmEngine["LLM Engine"]:::inference
        llmInterfaces["LLM Interfaces & RM Loader"]:::inference
        subgraph "Agents"
            direction TB
            mcts["MCTS Agent"]:::inference
            beam["Beam-Search Agent"]:::inference
            tree["Tree Utilities"]:::inference
            agentUtils["Agent Utils"]:::inference
        end
        subgraph "Search Tree Nodes"
            direction TB
            baseNode["Base Node"]:::inference
            mctsNode["MCTS Node"]:::inference
        end
        solver["Solver API"]:::inference
        prompts["Prompt Definitions"]:::inference
        tool["Python Execution Tool"]:::inference
        traj["Trajectory Files"]:::data
    end

    %% Extraction & Training Layer
    subgraph "Data Extraction & Training"
        direction TB
        extraSFT["extra_sft_file.py"]:::extract
        extraRM["extra_rm_file.py"]:::extract
        sftSample["Sample SFT Data"]:::train
        rmSample["Sample RM Data"]:::train
        trainSFT["train_SFT.py"]:::train
        trainRM["train_RM.py"]:::train
        saveRM["save_rm.py"]:::train
        staticSFT["sft_data_examples.json"]:::data
        staticRM["rm_data_examples.json"]:::data
        newModels["Updated Models"]:::data
    end

    %% Evaluation & Results Layer
    subgraph "Evaluation & Results"
        direction TB
        eval["eval.py"]:::eval
        evalMaj["eval_maj.py"]:::eval
        evalOut["eval_output.py"]:::eval
        results["Accuracy Metrics"]:::data
    end

    %% Data Flow Connections
    cfg -->|"config"| main
    evalData -->|"raw problems"| main
    fewShots -->|"few-shot prompts"| main
    main -->|"invoke LLM"| llmEngine
    llmEngine -->|"interfaces"| llmInterfaces
    llmInterfaces -->|"init agents"| mcts
    llmInterfaces -->|"init agents"| beam
    mcts --> tree
    beam --> tree
    tree --> agentUtils
    agentUtils --> baseNode
    agentUtils --> mctsNode
    baseNode --> solver
    mctsNode --> solver
    prompts --> solver
    tool --> solver
    solver -->|"generate trajectories"| traj
    traj -->|"raw trajectories"| extraSFT
    traj -->|"raw trajectories"| extraRM
    extraSFT -->|"sft_data.jsonl"| sftSample
    extraRM -->|"rm_data.jsonl"| rmSample
    sftSample --> trainSFT
    rmSample --> trainRM
    trainSFT -->|"policy checkpoints"| newModels
    trainRM -->|"reward checkpoints"| newModels
    saveRM -->|"convert ckpt"| newModels
    newModels --> main
    newModels --> eval
    eval --> results
    evalMaj --> results
    evalOut --> results

    %% Click Events
    click cfg "https://github.com/microsoft/rstar/blob/main/config/sample_mcts.yaml"
    click evalData "https://github.com/microsoft/rstar/blob/main/eval_data/GSM8K_test.json"
    click fewShots "https://github.com/microsoft/rstar/blob/main/rstar_deepthink/few_shots/few_shots.json"
    click main "https://github.com/microsoft/rstar/blob/main/main.py"
    click run_example "https://github.com/microsoft/rstar/blob/main/run_example.sh"
    click llmEngine "https://github.com/microsoft/rstar/blob/main/rstar_deepthink/llms/llm_engine.py"
    click llmInterfaces "https://github.com/microsoft/rstar/blob/main/rstar_deepthink/llms/llms.py"
    click mcts "https://github.com/microsoft/rstar/blob/main/rstar_deepthink/agents/mcts.py"
    click beam "https://github.com/microsoft/rstar/blob/main/rstar_deepthink/agents/beam_search.py"
    click tree "https://github.com/microsoft/rstar/blob/main/rstar_deepthink/agents/tree.py"
    click agentUtils "https://github.com/microsoft/rstar/blob/main/rstar_deepthink/agents/utils.py"
    click baseNode "https://github.com/microsoft/rstar/blob/main/rstar_deepthink/nodes/base_node.py"
    click mctsNode "https://github.com/microsoft/rstar/blob/main/rstar_deepthink/nodes/mcts_node.py"
    click solver "https://github.com/microsoft/rstar/blob/main/rstar_deepthink/solver.py"
    click prompts "https://github.com/microsoft/rstar/blob/main/rstar_deepthink/prompts/prompt_rstar.py"
    click tool "https://github.com/microsoft/rstar/blob/main/rstar_deepthink/tools/python_tool.py"
    click extraSFT "https://github.com/microsoft/rstar/blob/main/extra_sft_file.py"
    click extraRM "https://github.com/microsoft/rstar/blob/main/extra_rm_file.py"
    click sftSample "https://github.com/microsoft/rstar/blob/main/train/sample_sft_data.py"
    click rmSample "https://github.com/microsoft/rstar/blob/main/train/sample_rm_data.py"
    click trainSFT "https://github.com/microsoft/rstar/blob/main/train/train_SFT.py"
    click trainRM "https://github.com/microsoft/rstar/blob/main/train/train_RM.py"
    click saveRM "https://github.com/microsoft/rstar/blob/main/train/save_rm.py"
    click staticSFT "https://github.com/microsoft/rstar/blob/main/train/sft_data_examples.json"
    click staticRM "https://github.com/microsoft/rstar/blob/main/train/rm_data_examples.json"
    click eval "https://github.com/microsoft/rstar/blob/main/eval.py"
    click evalMaj "https://github.com/microsoft/rstar/blob/main/eval_maj.py"
    click evalOut "https://github.com/microsoft/rstar/blob/main/eval_output.py"

    %% Styling
    classDef config fill:#ffeeba,stroke:#333,stroke-width:1px
    classDef data fill:#d4edda,stroke:#333,stroke-width:1px
    classDef inference fill:#bee5eb,stroke:#333,stroke-width:1px
    classDef extract fill:#f5c6cb,stroke:#333,stroke-width:1px
    classDef train fill:#c3e6cb,stroke:#333,stroke-width:1px
    classDef eval fill:#ffeeba,stroke:#333,stroke-width:1px
```
