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

Motivation

• Prior feedback-based code generation studies indicate that feedback can help open-source code models refine candidates across attempts.The cited approaches include compiler, execution, unit-test, static-analysis, and interactive feedback.Source: §1 · p. 1

Contributions

• ReMCTS formalizes execution-grounded program search with candidate programs as tree states and reusable path-level and cross-branch failure diagnoses.This design reduces dependence on a single repair trajectory.Source: §1 · p. 2
• Its evidence-driven reward and acceptance mechanism integrates execution, proxy, semantic, and risk evidence while distinguishing missing evidence from negative evidence.The design supports settings both with and without explicit tests.Source: §1 · p. 2
• The evaluation uses controlled comparisons across multiple non-GPT models, including paired tests, budget-up baselines, component ablations, and a limited C++ pilot.These comparisons are intended to characterize when the method helps and where it does not.Source: §1 · p. 2

2.1 One-Shot Code Generation and Candidate Selection

• Candidate-selection methods such as CodeT (Chen et al., 2023), LEVER (Ni et al., 2023), and Coder-Reviewer (Zhang et al., 2023) mainly rerank or select candidates after generation rather than use failures to guide shared search.The paper contrasts post-generation selection with a shared state in which execution feedback and reflections guide later branches.Source: §2.1 · p. 2

2.2 Feedback-Based Code Repair

• Feedback-based methods including Self-Refine (Madaan et al., 2023), Reflexion (Shinn et al., 2023), and Self-Debugging (Chen et al., 2024) use feedback to repair programs, but many remain single-trajectory or use feedback for training, filtering, or reranking.Olausson et al. (2024) report that self-repair depends strongly on feedback quality and the model’s ability to use it.Source: §2.2 · p. 2

2.3 Search-Based and Tree-Based Code Generation

• Among search-based methods, ReMCTS uses generated programs as primary search states and retrieves task-local failure diagnoses across branches, unlike approaches centered on plans, agents, or erroneous thoughts.It also marks missing tests as unavailable rather than negative evidence, making this integration—not tree search alone—the stated distinction.Source: §2.3 · pp. 2–3

3.1 Overview

• ReMCTS treats the task as test-time tree search: model-generated candidates become child program states, and selection, expansion, execution, reflection, and backpropagation form a closed loop.The search can use visible tests when available or proxy evidence when explicit tests are absent.Source: §3.1 · p. 3

3.2 Memory-Guided Monte Carlo Tree Design

• Each node stores a candidate program and its recent path reflections, which record errors and repair hints; the memory window is limited to the most recent k reflections.The path memory is intended to keep context manageable and the repair direction coherent.Source: §3.2 · pp. 3–4
• The memory heuristic augments UCB with path-reflection confidence and a penalty for similarity to high-severity global errors.The confidence term rewards lower severity, positive reward changes, and repair hints; the main-run settings use fixed α and β values.Source: §3.2 · p. 4
• A task-local global repository stores failure experience across branches, and retrieved records enter expansion prompts and the semantic heuristic without deleting branches.Memory can therefore influence later search while subsequent execution evidence can override misleading retrieval; its benefit is not uniform across settings.Source: §3.2 · pp. 4–5

3.3 Evidence-Driven Reward and Acceptance Mechanism

• Candidate evaluation aggregates executable, interface, behavioral, semantic, and risk evidence; unavailable items are excluded rather than counted as failed tests.When no explicit tests are available, weak assertions derived from the task text serve as probes, alongside contract, static, semantic, and risk checks.Source: §3.3 · pp. 5–6, Figure 2 · p. 6
• In no_tests, reward combines proxy correctness, execution reachability, semantic review, and signed risk, while acceptance further penalizes low-confidence evidence, risk, and code-length deviation.Acceptance also requires proxy, execution, and semantic thresholds and a risk level below its threshold.Source: §3.3 · p. 5

4.1 Experimental Setup

• The main study used HumanEval and MBPP-Sanitized with five open-weight models, separating visible search feedback from hidden final evaluation.Controlled baselines preserve the base model and evaluator; known-feedback results are mechanism validation, not standard pass@1.Source: §4.1 · pp. 6–7, Table 1 · p. 8

4.2 Main Results

• Weaker models often benefit from execution evidence, while stronger models mainly recover residual errors; proxy-only checks can miss hidden semantics.Plausible candidates can pass weak checks yet fail hidden tests, including in some MBPP no_tests cases.Source: §4.2 · p. 7

4.3 Cross-Language Pilot

• 73.33 to 90.00 (Qwen3-8B), 83.33 to 96.67 (Qwen3-32B), and 60.00 to 96.67 (DeepSeek-V4-Flash) were the pilot hidden solve-rate changes.The C++17 pilot used the first 30 HumanEval-X tasks and a smaller search budget; it demonstrates compiler-backed compatibility, not broad multilingual capability.Source: §4.3 · p. 7

4.4 Budget-Up and Cost Analysis

• Best-of-32 remained 6.79 and 6.32 percentage points below ReMCTS for Qwen3-8B and Qwen3-32B, respectively, on representative MBPP no_tests runs.These were not strict wall-clock matches; ReMCTS adds sequential search overhead and is not necessarily the cheapest or fastest method.Source: §4.4 · p. 7

4.2 Main Results

• 8 of 10 model–dataset pairs improved with ReMCTS known over Direct no_tests, and ReMCTS known beat ReMCTS no_tests in all pairs.Across 2,955 paired outputs, Direct no_tests solved 69.37% and ReMCTS known solved 77.56% (two-sided exact McNemar p = 5.3 × 10−29).Source: §4.2 · p. 7, Table 1 · p. 8

4.4 Budget-Up and Cost Analysis

• In known feedback, full ReMCTS beat MCTS-style in all six pairs by 5.07 points on average, while Reflexion-style was stronger on MBPP.Visible assertions can make single-path repair competitive; ReMCTS is more robust when feedback is incomplete or hard to exploit in one trajectory.Source: §4.4 · p. 8

4.5 Ablation Results

• Removing global retrieval lowered hidden solve rate by 0.97 points on average across twelve settings, while path-memory effects were mixed.The clearest paired effects were on Qwen3-8B and Qwen3-32B MBPP-known; the DeepSeek MBPP-known effect was noisy.Source: §4.5 · p. 8, Table 3 · p. 9
• Increasing min_accept_iterations from 1 to 3 improved hidden solve rate in 7 of 10 no_tests combinations, by 1.55 points on average.Trees were usually shallow, averaging 1.23–1.61 maximum depth; qualitative trajectories illustrate sibling exploration and residual edge-case repair, while proxy-only acceptance could still return candidates later rejected by hidden tests.Source: §4.5 · p. 9

• Visible feedback gives ReMCTS the strongest hidden-test gains on HumanEval and MBPP-Sanitized; no_tests is positive on average but unstable.Source: §5 · p. 9
• Paired tests and budget-up controls indicate that the gains are not explained by more samples alone.Source: §5 · p. 9
• Global memory contributes more consistently than path memory.Source: §5 · p. 9
• A 30-task C++ pilot suggests compiler-backed transfer, not broad multilingual or repository-level capability.Source: §5 · p. 9

Limitations

• Evaluation is limited to function-level benchmarks; known is test-guided mechanism validation, not standard pass@1, and the 30-task C++ pilot does not establish broad multilingual or repository-level capability.Workspace patches, cross-file dependencies, environment configuration, test selection, and long-horizon debugging are not evaluated; not every heuristic is isolated. Cost comparisons are within-study diagnostics, not deployment-wide efficiency claims.Source: Limitations · p. 10

A ReMCTS Pseudocode

• The search evaluates each generated branch, then returns the highest-reward accepted sibling after the minimum iteration; otherwise it returns the highest-reward candidate.In known, acceptance requires all visible tests to pass; in no_tests, the gate uses proxy, execution, semantic, risk, and acceptance-score thresholds.Source: A ReMCTS Pseudocode · p. 13

B Reward and Evidence Details

• Method symbols cover fixed hyperparameters, runtime evidence quantities, and rule- or LLM-assisted scores; hyperparameters are fixed before evaluation and are not learned from tasks.Unavailable evidence is excluded from the reward denominator rather than counted as a failed check.Source: B Reward and Evidence Details · p. 13

• The experiments use existing public function-level benchmarks, including HumanEval, MBPP-Sanitized, and HumanEval-X, and collect no human or user-generated data.Source: C Datasets and Input Settings · p. 13
• The task files were checked for obvious direct identifiers and offensive-content concerns; no personal identifiers were used, and materials remain subject to their source terms.No additional anonymization was required.Source: C Datasets and Input Settings · p. 13
• The C++ pilot covers the first 30 HumanEval-X tasks in published order, searches with example_test, and reserves official tests for final evaluation.Runs use C++17, three iterations, branch factor three, maximum depth four, minimum acceptance iteration two, and an eight-second execution timeout.Source: C Datasets and Input Settings · p. 13

• The release includes the search and evaluation framework, prompts, configurations, preprocessing and split scripts, Python and C++ executors, hidden-evaluation scripts, anonymized outputs, logs, and run metadata.API-dependent runs save outputs and exact model alias, date, decoding parameters, and data hashes to support recomputing hidden scores without re-querying a mutable service; credentials are excluded.Source: D Implementation and Reproducibility · pp. 13–14
• No_tests probes use four weak assertions derived from task text, sanitized against risky operations and executed in a subprocess sandbox.Global memory retrieves the top two memories using deterministic hashed-token embeddings and cosine similarity.Source: D Implementation and Reproducibility · p. 14
• Cost and wall-time comparisons are operational accounting rather than strict compute-matched comparisons; parallel workers can make elapsed times non-additive.Source: D Implementation and Reproducibility · pp. 14–15
• Table 6 summarizes experimental data files and usage, while Table 7 reports the 30-task HumanEval-X C++ pilot with official tests held out for final evaluation.Source: Table 6 · p. 15, Table 7 · p. 15

E Search Parameters and Evaluation Metrics

• Hidden Solve Rate evaluates the final returned candidate across all tasks, while acceptance metrics depend on whether the method’s internal acceptor accepts a task.When a task is not accepted, the current best candidate is still returned for hidden evaluation.Source: E Search Parameters and Evaluation… · p. 15

F Supplementary Baseline Results

• Supplementary baselines use hidden tests only for final offline evaluation; known-feedback runs use visible tests during search.MCTS-style retains tree search but disables path memory, global memory retrieval, semantic UCB, and LLM probes.Source: G Known-Feedback Baseline Results · p. 16, F Supplementary Baseline Results · p. 16, Table 11 · p. 17

H Logged Token Comparison

• Across all twelve comparable settings, ReMCTS uses 1.09× the total tokens of MCTS-style.The ratio is 1.14× in no_tests and 1.04× in known.Source: H Logged Token Comparison · p. 16

E Search Parameters and Evaluation Metrics

• Main experiments use a fixed budget of 8 iterations, branch factor 5, maximum depth 8, and minimum acceptance iteration 3.Best-of-8 generates exactly eight candidates; Reflexion-style runs up to eight feedback rounds.Source: E Search Parameters and Evaluation… · p. 15, Table 9 · p. 16, H Logged Token Comparison · p. 17

I Paired Significance Tests

• Paired comparisons use two-sided exact McNemar tests descriptively, with a Wilson interval for the second method’s solve rate.The authors make no claim of theoretical optimality from these tests.Source: I Paired Significance Tests · p. 17

J Memory Ablation Results

• The memory ablations compare variants without global memory and without path memory under the same final hidden-evaluation protocol.The no-global-memory variant sets global_memory_top_t=0; the no-path-memory variant sets path_memory_k=0.Source: J Memory Ablation Results · p. 17, Table 15 · p. 18

K Search-Tree Structure Statistics

• Search-tree statistics report effective branch as total edges divided by total non-leaf nodes.Table 17 covers the main ReMCTS experiments; known uses latest hidden-evaluation reruns and no_tests uses the adopted v2 results.Source: K Search-Tree Structure Statistics · p. 18

L Minimum Search Iteration Ablation

• With minimum acceptance iterations set to 3, no_tests generally has more stable hidden solve rates, while known scores remain nearly unchanged.The comparison is against early experiments with the minimum set to 1.Source: L Minimum Search Iteration Ablation · p. 18
• In known, changing the minimum iteration setting mainly changes search scale while leaving scores nearly unchanged.Table 19 compares search scale between minimum-iteration settings of 1 and 3.Source: L Minimum Search Iteration Ablation · p. 18

M Qualitative Case Analysis

• Representative trajectories illustrate how mechanisms behind aggregate trends appear in concrete tasks, but are not a full manual audit.The examples come from latest main-result runs and use hidden tests only for offline analysis.Source: M Qualitative Case Analysis · p. 19

N Evaluation Protocol Notes

• Known results are test-guided mechanism validation, not standard pass@1, because visible tests guide search before hidden-test scoring.The no_tests setting uses no explicit tests and is closer to production-style generation without test cases.Source: N Evaluation Protocol Notes · p. 19
• HumanEval and MBPP-Sanitized are function-level benchmarks and do not cover cross-file context, dependency installation, permission control, or security risks.This boundary limits how broadly benchmark outcomes represent real software projects.Source: N Evaluation Protocol Notes · p. 19
• Hidden tests are reserved for final offline evaluation, not candidate selection; representative trajectories are illustrative rather than a full audit.The baseline comparisons include diverse sampling, single-path reflection, reflection-free tree search, and tree search with LLM semantic review.Source: N Evaluation Protocol Notes · pp. 19–20, Table 20 · p. 21