When and How to Reflect: State-Aware Multi-Scale Reflection for LLM-Based Automatic Heuristic Design

LLMs can search directly over executable heuristics, but effective program generation still depends on providing the right evidence about what should be improved. Island-based search maintains multiple independently evolving subpopulations of candidate programs, called islands, enabling parallel exploration of different regions of the search space. Existing frameworks such as FunSearch and OpenEvolve maintain multiple independently evolving islands and promote diversity through mechanisms such as MAP-Elites, migration, and the selection of both parent and inspiration programs. We instead ask a complementary question in this paper: how should the evidence presented to each island change as its search progresses, stagnates, or requires a restart? We propose SAMR (State-Aware Multi-Scale Reflection), a framework that personalizes reflective evidence across islands and throughout the search process. Each island tracks its momentum, stagnation, and age, and dynamically transitions among three states: exploit, explore, and reset. These states determine access to different forms of evidence, including case contrasts, empirical edit-pattern statistics, and cross-island knowledge. On 36 CO-bench problem types, SAMR with Claude Sonnet 4.5 achieves a mean normalized score of 0.853, outperforming FunSearch (0.818), OpenEvolve (0.811), ReEvo (0.779), and MCTS-AHD (0.747). Although CORAL scores marginally higher (0.863), it adopts a fundamentally different agent-based framework and requires 26.6× more tokens on average. Using DeepSeek V3, SAMR also ranks first in mean score among all evaluated methods. Overall, our results demonstrate that state-dependent routing of diagnostic evidence, including long-term and cross-island reflections, improves the quality–cost tradeoff in LLM-guided program search.