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

תקציר מקורי באנגליתarXiv:2604.23989v3 Announce Type: replace Abstract: 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