RefChess: Training-Free Contextual Search for Zero-Shot Referring Image Segmentation

Recent advances in zero-shot referring image segmentation (RIS), driven by foundation models such as SAM and CLIP, have improved cross-modal alignment between visual regions and natural language expressions. Nevertheless, selecting the correct segmentation proposal remains challenging, as existing methods typically score proposals independently and can be distracted by visually similar candidates that partially satisfy the expression. To address this limitation, we propose RefChess, a training-free contextual search framework for robust proposal selection. Instead of treating proposal selection as a single-step ranking problem, RefChess evaluates candidate masks under sampled distractor contexts and uses Monte-Carlo Tree Search as a budgeted mechanism to explore the combinatorial space of contextual perturbations. The search is guided by a stability-aware reward that integrates language decomposition, vision--language similarity, object-centric cues, and spatial guidance signals. Experiments on standard RIS benchmarks show that RefChess consistently improves robustness and referring segmentation performance without task-specific training. Code is available at https://github.com/Tongshiyan/RefChess.