ReMCTS: Reflection-Enhanced Monte Carlo Tree Search for Code Generation

Huifei Wang; Xinying Huang; Yiheng Sun; Yifan Yuan

cs.CLSep 28, 2026

ReMCTS: Reflection-Enhanced Monte Carlo Tree Search for Code Generation

Authors: Huifei Wang, Xinying Huang, Yiheng Sun, Yifan Yuan

Organizations: College of Computer Science and Software Engineering, Shenzhen University · School of Artificial Intelligence, Shenzhen University

Abstract

Open-weight large language models (LLMs) can generate function-level programs from natural-language prompts, but plausible candidates still fail on hidden semantics and repeat mistakes across repair attempts. We present ReMCTS, an execution-grounded, memory-augmented, LLM-guided MCTS-style search framework. It organizes program candidates as tree states, retains branch-local debugging context, retrieves failure experience across branches, and distinguishes failed checks from unavailable evidence. On HumanEval and MBPP-Sanitized, visible-test ReMCTS improves over direct generation in 8 of 10 model-dataset pairs under held-out evaluation, whereas proxy-only search is less stable. Controlled tree-search, sampling, repair, and memory ablations characterize the source and limits of these gains. A 30-task HumanEval-X C++ pilot further demonstrates compatibility with compiler-backed execution, but does not constitute a broad multilingual evaluation.

Figures & tables

Figure 1: Overview of ReMCTS. The search proceeds through selection, expansion, execution, reflection, and backpropagation. Execution evidence determines rewards and acceptance, while path and global reflection memories guide later selection and expansion.

Figure 2: Evidence-driven reward and acceptance mechanism. A candidate program is first evaluated in the sandbox and converted into availability-aware evidence. When explicit tests are absent, unit-test evidence is marked unavailable ( $A_{unit}=0$ ) rather than failed. The reward aggregator combines proxy correctness, execution reachability, semantic review, and risk. The acceptance gate further penalizes uncertainty, risk, and code-length deviation; rejected candidates return to search.

Model	Dataset	Direct no_tests	ReMCTS no_tests	ReMCTS known	TG– no_tests (pp)
Qwen3-1.7B	HumanEval	60.37%	69.51% (+9.14)	83.54% (+23.17)	+14.03
Qwen3-1.7B	MBPP	53.40%	51.29% (-2.11)	63.47% (+10.07)	+12.18
Qwen3-8B	HumanEval	79.88%	86.59% (+6.71)	93.90% (+14.02)	+7.31
Qwen3-8B	MBPP	64.17%	66.74% (+2.57)	74.24% (+10.07)	+7.50
Qwen3-14B	HumanEval	82.93%	78.66% (-4.27)	82.93% (+0.00)	+4.27
Qwen3-14B	MBPP	66.98%	60.42% (-6.56)	65.57% (-1.41)	+5.15

Table 1: Hidden solve rates on HumanEval and MBPP-Sanitized. Parentheses in the two ReMCTS columns report percentage-point differences from Direct no_tests . TG– no_tests is the difference between ReMCTS known and ReMCTS no_tests . known results are used for mechanism validation and are not equivalent to standard pass@1.

Model	Method	Hidden solve	Tok/task	Calls/task	Wall (s)	Cost (CNY)
Qwen3-8B	ReMCTS	66.74	10,295	19.7	1,980	3.72
Qwen3-8B	Best-of-32	59.95	8,290	44.7	1,502	3.18
Qwen3-8B	Reflexion-16	62.30	15,777	17.1	903	4.54
Qwen3-32B	ReMCTS	70.49	9,735	19.7	3,053	13.15
Qwen3-32B	Best-of-32	64.17	8,600	33.0	2,232	13.79
Qwen3-32B	Reflexion-16	69.09	11,072	12.4	1,147	12.94

Table 2: Budget-up baselines on MBPP no_tests . Wall-clock is total elapsed time over 427 tasks; tokens and calls are per task. Hidden tests are used only for final evaluation.

Model	Dataset	Setting	Full	W/O global	W/O path
DeepSeek-V4-Flash	HumanEval	known	98.78	99.39	99.39
DeepSeek-V4-Flash	HumanEval	no_tests	95.12	94.51	94.51
DeepSeek-V4-Flash	MBPP	known	81.03	80.56	80.09
DeepSeek-V4-Flash	MBPP	no_tests	72.83	73.07	72.83
Qwen3-8B	HumanEval	known	93.90	92.07	95.12
Qwen3-8B	HumanEval	no_tests	86.59	85.37	86.59

Table 3: Memory ablations under final hidden evaluation (%). Full denotes complete ReMCTS; the other columns disable one memory component.

Appendix figures & tables17 assets

Supplementary material from the paper’s appendix.

Appendix

Symbol	Type	Definition
$C,k,t,\alpha,\beta$	Search and semantic-heuristic hyperparameters	$C=1.4$ , $k=3$ , $t=2$ ; ReMCTS uses $\alpha=0.4,\beta=0.6$ , while pure-MCTS/MCTS-style ablations set the memory heuristic to zero.
$\omega_{g},\gamma_{j},\tau_{*}$	Reward and acceptance hyperparameters	known uses unit/exec/semantic weights $(0.6,0.2,0.2)$ ; no_tests uses proxy/exec/semantic/risk weights $(0.4,0.2,0.3,0.1)$ . The no_tests acceptance penalties are $\gamma=(0.10,0.35,0.10)$ , and its thresholds are $\tau_{proxy}=0.50$ , $\tau_{exec}=0.60$ , $\tau_{sem}=0.45$ , $\tau_{risk}=0.25$ , and $\tau_{accept}=0.62$ .
$\eta_{k}$	Proxy-evidence weights	Contract/probe/meta/static weights are $(0.35,0.25,0.15,0.25)$ ; fixed before evaluation.
$A_{k},C_{k},R_{k},I_{\cdot},R_{\cdot},U_{i}$	Runtime evidence quantities	Produced by visible tests, sandbox execution, contract checks, probes, property checks, static checks, risk scans, and LLM reviews; $U_{i}$ is computed from the confidence of available evidence groups.
$H_{i},D_{i},R_{sem}$	Rule- or LLM-assisted scores	$H_{i}$ combines path-reflection confidence and high-severity global-memory similarity; $D_{i}$ depends on nonblank code length; $R_{sem}$ is a confidence- and risk-weighted LLM review.
$\epsilon$	Numerical stability term	Used only to avoid division by zero; not a tunable experimental parameter.

Appendix

Table 4: Symbol categories and hyperparameter settings.

Evidence	Meaning	Role
Unit	Visible unit tests or assertions	Provides the highest-confidence functional feedback in known
Exec	Compilation, loading, entry call, timeout, and crash status	Checks whether the candidate is runnable and callable
Contract	Function name, argument count, return form, or schema	Prevents interface mismatches and entry-point errors
Probe	Four LLM-generated weak assertions from task text; fixed confidence 0.45	Provides low-cost behavioral signals without explicit tests after sanitizer checks
Meta	Properties or metamorphic relations extracted from the requirement; fixed confidence 0.35	Checks task properties such as sorting, length, idempotence, and reversal
Static	Compilation/execution status; fixed confidence 0.80	Filters obviously non-runnable code

Appendix

Table 5: Evidence items used in reward computation.

File	Tasks	Use	Source or Description
HumanEval_feedback.jsonl	164	known input	Visible feedback parsed from doctest examples in HumanEval prompts; some tasks have no visible examples
HumanEval_no_tests.jsonl	164	no_tests input	Explicit tests removed; only the prompt and entry point are retained
HumanEval_eval.jsonl	164	hidden eval	Original HumanEval test fields retained only for final offline evaluation
mbpp_sanitized_feedback_split.json	427	known input	Converted from Google Research sanitized-mbpp.json ; only the first assertion per task is used as search feedback
mbpp_sanitized_no_tests.json	427	no_tests input	Explicit assertions removed; only task description and entry point are retained
mbpp_sanitized_eval_split.json	427	hidden eval	Setup/imports and remaining assertions retained for final evaluation

Appendix

Table 6: Experimental data files and usage.

Model	Method	Tasks	Visible pass	Hidden solve	Tok/task	Cost (CNY)
Qwen3-8B	Direct	30	73.33	73.33	335	0.0094
Qwen3-8B	ReMCTS	30	93.33	90.00	3,217	0.0818
Qwen3-32B	Direct	30	83.33	83.33	337	0.0381
Qwen3-32B	ReMCTS	30	96.67	96.67	3,245	0.3260
DeepSeek-V4-Flash	Direct	30	60.00	60.00	330	0.0123
DeepSeek-V4-Flash	ReMCTS	30	96.67	96.67	2,996	0.1063

Appendix

Table 7: HumanEval-X C++ pilot on the first 30 tasks. Official tests are used only for final hidden evaluation. Costs use the logged-token pricing assumptions of the Python experiments.

Item	Setting
Model alias	Qwen3-1.7B , Qwen3-8B , Qwen3-14B , Qwen3-32B , DeepSeek-V4-Flash
Invocation	OpenAI-compatible API; main experiments were run in May 2026 and the budget-up/C++ pilots in July 2026
Direct, ReMCTS, and tree-search baselines	Code-generation temperature 0.2, maximum output length 1024 tokens, and API request timeout 90 seconds
Best-of-8	8 independent candidates per task, generation temperature 0.7, and 5 self-generated assertion tests for selection
Best-of-32	32 independent candidates per task with the same generation and proxy-selection protocol as Best-of-8
Reflexion-style	Up to 8 Actor–Evaluator–Self-Reflection rounds; Actor, Evaluator, and reflection temperatures are all 0.2

Appendix

Table 8: Model invocation and decoding settings.

Parameter	Value
max_iterations	8
branch_factor	5
max_depth	8
no_improve_patience	8
min_accept_iterations	3
complete_branch_before_accept	true

Appendix

Table 9: Search parameters for the main ReMCTS experiments.

Metric	Definition	Applicable Settings
Hidden Solve Rate	Fraction of tasks whose final candidate passes hidden tests	All experiments
Accepted Rate	Fraction of tasks whose candidate is automatically accepted	Methods/settings with an internal acceptor
Acceptance Precision	Fraction of automatically accepted candidates that pass hidden tests	Methods/settings with an internal acceptor
False Acceptance Rate	Fraction of automatically accepted candidates that fail hidden tests	Methods/settings with an internal acceptor
Avg. Iterations	Average search iterations per task	Search efficiency analysis
Avg. Tree Size	Average search-tree nodes per task	Search efficiency analysis

Appendix

Table 10: Definitions of evaluation metrics.

Model	Dataset	Method	Hidden Solve	Accepted	Acc. Prec.	False Acc.	Oracle Pool
Qwen3-8B	HumanEval	Best-of-8	82.93%	95/164	98.95%	1.05%	82.93%
Qwen3-8B	HumanEval	Reflexion	81.10%	99/164	96.97%	3.03%	84.15%
Qwen3-8B	HumanEval	pure-MCTS	84.76%	163/164	84.66%	15.34%	87.20%
Qwen3-8B	HumanEval	MCTS-style	85.98%	90/164	90.00%	10.00%	86.59%
Qwen3-8B	MBPP	Best-of-8	60.42%	190/427	80.53%	19.47%	61.83%
Qwen3-8B	MBPP	Reflexion	61.59%	234/427	74.36%	25.64%	64.17%

Appendix

Table 11: Supplementary baselines for Best-of-8, Reflexion-style, pure-MCTS, and MCTS-style. Accepted is the number of tasks accepted by the method’s internal acceptor. It is not the number of final returned tasks. Hidden Solve is always computed with the final returned candidate for each task. Oracle Pool is the offline upper bound indicating whether at least one candidate in the pool passes hidden tests. Best-of-8 uses 8 independent candidates. Reflexion-style uses all attempts. pure-MCTS and MCTS-style use non-root nodes generated in the search tree. DeepSeek abbreviates DeepSeek-V4-Flash.

Model	Dataset	Method	Hidden Solve	Accepted	Acc. Prec.	Avg. Iter.
DeepSeek-V4-Flash	HumanEval	Reflexion-style	96.34	96.34	100.00	1.360
DeepSeek-V4-Flash	HumanEval	MCTS-style	96.34	96.34	100.00	3.183
DeepSeek-V4-Flash	MBPP	Reflexion-style	94.15	93.21	100.00	1.684
DeepSeek-V4-Flash	MBPP	MCTS-style	75.88	74.24	100.00	4.288
Qwen3-8B	HumanEval	Reflexion-style	86.59	86.59	100.00	2.098
Qwen3-8B	HumanEval	MCTS-style	86.59	86.59	100.00	3.445

Appendix

Table 12: Known-feedback baseline completion results. Hidden Solve, Accepted, Acc. Prec., and False Acc. are percentages.

Model	Dataset	Setting	ReMCTS Tok. (M)	MCTS-style Tok. (M)	Ratio
Qwen3-8B	HumanEval	no_tests	2.52	2.26	1.12
Qwen3-8B	HumanEval	known	1.07	1.74	0.61
Qwen3-8B	MBPP	no_tests	4.40	3.96	1.11
Qwen3-8B	MBPP	known	3.93	3.77	1.04
Qwen3-32B	HumanEval	no_tests	2.32	2.23	1.04
Qwen3-32B	HumanEval	known	0.80	1.72	0.46

Appendix

Table 13: Logged token comparison between full ReMCTS and MCTS-style. Token counts are prompt-plus-completion totals in millions (M). Ratio is ReMCTS tokens divided by MCTS-style tokens.

Model	Dataset	Direct	ReMCTS	ReMCTS-only	Direct-only	Exact $p$	ReMCTS 95% CI
Qwen3-1.7B	HumanEval	99/164	137/164	40	2	$4.11\times 10^{-10}$	77.11–88.43
Qwen3-1.7B	MBPP	228/427	271/427	62	19	$1.77\times 10^{-6}$	58.80–67.89
Qwen3-8B	HumanEval	131/164	154/164	25	2	$5.65\times 10^{-6}$	89.14–96.65
Qwen3-8B	MBPP	274/427	317/427	57	14	$2.67\times 10^{-7}$	69.89–78.16
Qwen3-14B	HumanEval	136/164	136/164	15	15	1.00	76.43–87.92
Qwen3-14B	MBPP	286/427	280/427	40	46	0.59	60.95–69.92

Appendix

Table 14: Paired hidden-test comparisons between Direct no_tests and ReMCTS known . “Only” columns count tasks solved by exactly one method.

Model	Dataset	MCTS-style	ReMCTS	ReMCTS-only	MCTS-only	Exact $p$	ReMCTS 95% CI
Qwen3-8B	HumanEval	142/164	154/164	13	1	0.00183	89.14–96.65
Qwen3-8B	MBPP	285/427	317/427	33	1	$4.07\times 10^{-9}$	69.89–78.16
Qwen3-32B	HumanEval	154/164	156/164	5	3	0.727	90.67–97.51
Qwen3-32B	MBPP	304/427	333/427	30	1	$2.98\times 10^{-8}$	73.82–81.66
DeepSeek-V4-Flash	HumanEval	158/164	162/164	5	1	0.219	95.66–99.66
DeepSeek-V4-Flash	MBPP	324/427	346/427	27	5	$1.13\times 10^{-4}$	77.04–84.47

Appendix

Table 15: Paired comparison of ReMCTS known with the same-search-budget MCTS-style baseline. MCTS-style disables path/global memory, semantic UCB, and LLM probes.

Model	Dataset	Method	Hidden Solve	Accepted	False Acc.	Avg. Iter.	Avg. Tree
DeepSeek-V4-Flash	HumanEval known	No global	99.39	99.39	0.00	3.043	7.165
DeepSeek-V4-Flash	HumanEval known	No path	99.39	99.39	0.00	3.030	7.238
DeepSeek-V4-Flash	HumanEval no_tests	No global	94.51	99.39	5.52	3.030	6.835
DeepSeek-V4-Flash	HumanEval no_tests	No path	94.51	100.00	5.49	3.000	6.695
DeepSeek-V4-Flash	MBPP known	No global	80.56	79.39	0.00	4.082	10.761
DeepSeek-V4-Flash	MBPP known	No path	80.09	78.45	0.00	4.082	11.354

Appendix

Table 16: Memory ablation results. Hidden Solve, Accepted, and False Acc. are percentages.

Model	Dataset	Setting	Avg. Iter.	Avg. Tree	Median	Range	Avg. Depth	Eff. Branch
Qwen3-1.7B	HumanEval	no_tests	3.098	5.165	5	2–17	1.396	2.858
Qwen3-1.7B	HumanEval	known	3.835	5.762	5	2–21	1.384	2.861
Qwen3-1.7B	MBPP	no_tests	3.068	5.433	5	2–15	1.412	2.967
Qwen3-1.7B	MBPP	known	4.974	7.651	7	2–29	1.609	2.820
Qwen3-8B	HumanEval	no_tests	3.500	3.671	3	2–12	1.341	1.904
Qwen3-8B	HumanEval	known	3.354	3.537	3	2–21	1.366	1.741

Appendix

Table 17: Search-tree structure statistics for all main ReMCTS experiments. Range gives the minimum and maximum number of tree nodes per task. Eff. Branch is the micro-average effective branch factor over non-leaf nodes.

Model	Dataset	Setting	Score@1	Score@3	$\Delta$ Score
Qwen3-1.7B	HumanEval	no_tests	64.02	69.51	+5.49
Qwen3-1.7B	HumanEval	known	82.32	83.54	+1.22
Qwen3-1.7B	MBPP	no_tests	51.99	51.29	-0.70
Qwen3-1.7B	MBPP	known	63.70	63.47	-0.23
Qwen3-8B	HumanEval	no_tests	87.20	86.59	-0.61
Qwen3-8B	HumanEval	known	93.29	93.90	+0.61

Appendix

Table 18: Effect of changing the minimum search iterations from 1 to 3 on hidden solve rate. Score@1 and Score@3 are percentages.

\Delta

Score is the percentage-point difference.

Model	Dataset	Setting	Iter@1	Iter@3	Tree@1	Tree@3	$\Delta$ Tree
Qwen3-1.7B	HumanEval	no_tests	1.293	3.098	2.591	5.165	+2.573
Qwen3-1.7B	HumanEval	known	2.317	3.835	3.927	5.762	+1.835
Qwen3-1.7B	MBPP	no_tests	1.237	3.068	2.506	5.433	+2.927
Qwen3-1.7B	MBPP	known	3.864	4.974	6.129	7.651	+1.522
Qwen3-8B	HumanEval	no_tests	3.677	3.500	4.073	3.671	-0.402
Qwen3-8B	HumanEval	known	1.585	3.354	2.677	3.537	+0.860

Appendix

Table 19: Effect of changing the minimum search iterations from 1 to 3 on search scale. Iter@1/Tree@1 come from early experiments without the current lower bound. Iter@3/Tree@3 come from the current main experiments.

\Delta

Tree is the change in average search-tree size.

Case	Observation
Qwen3-1.7B, HumanEval/5, known	Direct fails hidden evaluation on intersperse . In the ReMCTS run, the search tree has 10 nodes. Three root candidates fail all visible tests. Several sibling candidates pass all 3 visible tests. The selected candidate inserts the delimiter only between adjacent elements. It passes hidden evaluation. This supports the view that weaker models often benefit from sandbox filtering and evidence-based selection.
Qwen3-8B, HumanEval/26, known	Direct fails hidden evaluation on remove_duplicates . The ReMCTS run needs 7 iterations and reaches depth 3. Early nodes repeatedly fail visible tests. The reflection memory records two issues. The model confuses “keep first occurrence” with “keep elements that occur once”. It also misses a List import. The final node counts element frequencies. It keeps only elements with count one. It passes all 3 visible tests and hidden evaluation. This shows how path reflections can prevent repeated repair mistakes.
Qwen3-32B, HumanEval/83, known	Direct fails hidden evaluation on starts_one_ends . It overcounts numbers ending in 1. Qwen3-32B Direct is already strong overall. Thus, this is a residual error rather than a broad failure mode. ReMCTS explores 10 nodes over 8 iterations. The reflection memory points to an inclusion–exclusion error and the special case $n=1$ . The selected candidate passes all 7 visible tests and hidden evaluation. This supports the claim that stronger models mainly benefit by recovering a smaller set of missed implementations.
Qwen3-14B, MBPP task 9, no_tests	The task asks for the minimum positive rotation needed to obtain the same string. In no_tests , ReMCTS accepts a candidate that returns -1 for strings with no smaller period. Hidden evaluation expects full-length rotations, e.g., find_Rotations("ab")==2 and find_Rotations("abc")==3 . Probe evidence partially fails. Contract and static checks pass. The LLM semantic review remains optimistic. This produces a false acceptance. This case shows why proxy evidence can be insufficient on MBPP. It also shows why no_tests improvements are less stable.

Appendix

Table 20: Representative trajectories used to interpret the aggregate trends. The examples are selected from the latest main-result runs. They use hidden tests only for offline analysis.

Explore similar work

Apr 19, 2026cs.CL

Probabilistic Programs of Thought

LLMs are widely used for code generation and mathematical reasoning tasks where they are required to generate structured output. They either need to reason about code, generate code for a given specification, or reason using programs of thought. The typical approach to code generation is to prompt the model and generate samples until an appropriate program is obtained. Within this process, sampling

n

programs from the language model requires

n

GPU compute-intensive generations which becomes prohibitively expensive for larger values of

n

. In this work, we address this limitation by exposing the LLM's distribution within the generated programs themselves. We propose a novel test-time framework we dub probabilistic programs of thought to obtain more samples from the model with fewer LLM generations. Given a program generated by a model and the associated next-token probabilities, we build a probabilistic program that compactly represents exponentially many deterministic programs. Since performing probabilistic reasoning in this probabilistic program is much cheaper, our approach allows sampling new programs without any additional GPU compute and little CPU overhead. We instantiate our approach on benchmarks for code generation, code understanding and mathematical reasoning and report improvements in performance with fewer generations from the LLM.

Poorva Garg, Renato Lui Geh, Daniel Israel +3

University of California Los Angeles · Allen Institute for AI

Code Generation LLM Reasoning Strategies Large Language Model Generation Thoughts

Ask PDF

Apr 27, 2026cs.LG

Understanding Scattered Forest Search: A Version-Space Perspective on Multi-Turn Program Correction

In multi-turn program correction, the state-of-the-art method Scattered Forest Search (SFS) has been proposed, employing Monte Carlo Tree Search (MCTS) with carefully crafted initial seeds and text-based optimization. However, since SFS integrates multiple components, the effects of each component on performance and the overall behavior of SFS have not been sufficiently analyzed. In this work, we theoretically analyze the refinement process of SFS from the perspective of version spaces in learning theory and clarify its behavior. First, as a basis for the theoretical analysis, we introduce a sequential self-refinement method (Line), which starts from an initial program and repeatedly refines the resulting program. Furthermore, while Line progresses the refinement process in the depth direction, we introduce Iterative Refinement of Repair Instructions (IRRI) to capture the refinement process in the width direction, which fixes initial programs and iteratively refines repair instructions. We then analyze Line and IRRI and conduct a theoretical analysis of SFS by positioning it as an intermediate method between the two. Our theoretical analysis reveals that SFS exhibits behavior closer to IRRI than to Line, and this theoretical characteristic is also confirmed experimentally. Considering computational resources and methodological simplicity, these results suggest that a simpler method, IRRI, may achieve a similar refinement process without relying on the complex correction mechanism of SFS.

Yuto Tanaka, Issei Sato

Department of Computer Science The University of Tokyo Tokyo, Japan

Efficient Inference Iterative Refinement Iterative Repair Tree Search

Ask PDF

Apr 18, 2026cs.AI

Playing Psychic: Using Thought Trees to Predict Reasoning Models Accuracy on Coding Tasks

Recent advances in large language models (LLMs) have shown that test-time scaling can substantially improve model performance on complex tasks, particularly in the coding domain. Under this paradigm, models use a larger token budget during inference to generate intermediate reasoning traces before producing a final answer. However, current evaluations primarily rely on competitive programming benchmarks, which may not capture the full range of reasoning abilities. In this work, we perform a systematic study of frontier reasoning models to understand their performance on real-world coding benchmarks. To gain more insights into the performance of such models, we devise a programmatic way to {\em automatically generate} coding tasks of arbitrary difficulty and structure from existing benchmarks. Using this framework, our analysis reveals that the structure of a reasoning trace, not just its contents, is a strong predictor of correctness. Motivated by this, we propose structured thought-trees as means to represent reasoning traces. To illustrate their use, we train a lightweight classifier on features extracted from thought-trees to predict trace correctness, and demonstrate that flagging and retrying structurally anomalous traces based on the extracted features yields consistent gains at lower complexity levels.

Jiaxin Fang, Runyuan He, Sahil Bhatia +2

University of California, Berkeley

Reasoning Traces Large Reasoning Models Tree-Of-Thoughts Frontier Models

Ask PDF