AdverMCTS: Combating Pseudo-Correctness in Code Generation via Adversarial Monte Carlo Tree Search

Recent advancements in Large Language Models (LLMs) have successfully employed search-based strategies to enhance code generation. However, existing methods typically rely on static, sparse public test cases for verification, leading to pseudo-correctness—where solutions overfit the visible public tests but fail to generalize to hidden test cases. We argue that optimizing against a fixed, weak environment inherently limits robustness. To address this, we propose AdverMCTS, a novel adversarial Monte Carlo Tree Search framework that combats pseudo-correctness by coupling code search with active vulnerability discovery. AdverMCTS formulates generation as a minimax-style game between a Solver agent, which synthesizes code candidates, and an Attacker agent, which evolves to generate targeted test cases that exploit logical divergences in the current solution pool. These discovered tests form a dynamic, progressively hostile filter that penalizes fragile reasoning. Extensive experiments demonstrate that AdverMCTS significantly outperforms state-of-the-art baselines, effectively reducing false positive rates and forcing the model to generalize beyond the initial constraints. The resources of this work are available at https://github.com/SIMONLQY/AdverMCTS.

When AI assistants write code, the result often looks correct on a handful of example tests but breaks on hidden edge cases, a phenomenon we call pseudo-correctness. The root cause is that today's AI coding systems verify their own work using a small, fixed set of public tests, so they learn to barely pass those rather than to truly solve the problem. We introduce AdverMCTS, which fixes this by pairing a code-writing agent, the Solver, with an adversarial agent, the Attacker, that actively searches for tricky inputs designed to expose flaws in the Solver's candidates. Every newly discovered failing input becomes a permanent, stricter test, so the bar keeps rising as the game proceeds. On competition-style programming benchmarks, AdverMCTS produces substantially more reliable code than prior search-based methods. The broader takeaway: rather than trusting a fixed, weak checker, let the checker grow adversarially alongside the coder.