Research map / Large language models / Reasoning and chain of thought

RPM-MCTS: Knowledge-Retrieval as Process Reward Model with Monte Carlo Tree Search for Code Generation

AAAI 2026 · Large language models › Reasoning and chain of thought · approach: Test-time compute scaling · 1 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes RPM-MCTS, a tree search for code generation that uses knowledge-base retrieval similarity as a process reward, similarity filtering for diversity, and sandbox feedback to localize and truncate erroneous steps.

Problem

Tree search methods for LLM code generation struggle to evaluate intermediate algorithmic steps and to locate and correct erroneous steps, leading to incorrect code and high token cost.

Approach

Replace trained process reward models with retrieval scores from a knowledge base of correct algorithmic steps (cosine similarity), add LLM-generated step candidates filtered by similarity, and use sandbox execution feedback during simulation to prune erroneous steps and keep verified correct prefixes in the tree.

Key results

• On Qwen3-8B, RPM-MCTS averages 64.0 vs 52.1 base LLM (+11.9) across six benchmarks.
• On Claude Sonnet 3.7, RPM-MCTS averages 78.1 vs 67.3 base (+10.9), and on Qwen3-235B-A22B 72.3 vs 64.6 (+7.7).
• Token consumption is reduced by about 15% relative to the previous MCTS method on Qwen3-235B-A22B and Claude Sonnet 3.7.

Surprising findings

• Results without the knowledge base (w/o KB) slightly outperform the full method on some simple datasets such as APPS-Introductory for Qwen3-235B-A22B.
• SRA-MCTS underperforms the base LLM on several datasets, attributed to premature termination from overestimated LLM self-evaluation.

Limitations

• Single-line solutions may be split into multiple steps, which is unnecessary though not harmful to correctness.
• Gains depend on task difficulty and LLM evaluation confidence; knowledge base rewards can add noise on simple problems.
• Evaluation weights between execution and LLM scores are fixed rather than adaptive.

Experimental setup

Datasets: APPS train CodeContests train APPS test CodeContests test HumanEval+ MBPP+

Benchmarks: APPS-Introductory APPS-Interview APPS-Competition CodeContests HumanEval+ MBPP+ SWE-Bench LiveCodeBench Aider McEval

Metrics: pass@1 token consumption

Baselines: Base LLM LDB ToT SRA-MCTS

Builds on: Monte Carlo Tree Search Upper Confidence Bound SRA-MCTS Tree-of-Thought LDB

Closest papers by meaning

• Let's Revise Step-by-Step: A Unified Local Search Framework for Code Generation with LLMs (NeurIPS 2025 · similarity 0.88)
• Reasoning Through Execution: Unifying Process and Outcome Rewards for Code Generation (ICML 2025 · similarity 0.87)
• From Mathematical Reasoning to Code: Generalization of Process Reward Models in Test-Time Scaling (AAAI 2026 · similarity 0.86)
• CodeChemist: Test-Time Scaling for Low-Resource Code Generation via Functional Knowledge Transfer (ICML 2026 · similarity 0.86)
• Planning in Natural Language Improves LLM Search for Code Generation (ICLR 2025 · similarity 0.85)
• Repoformer: Selective Retrieval for Repository-Level Code Completion (ICML 2024 · similarity 0.85)