acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
optimization
Keywords:
Automated Heuristic Design

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_NkZjOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes SAMR, a state-aware reflection framework for LLM-based automatic heuristic design. It tracks the momentum, stagnation, and age of individual islands to determine their search states. Based on these states, it dynamically selects short-term, long-term, and cross-island reflection to guide program generation. The method is evaluated on 36 CO-Bench tasks using Claude Sonnet 4.5 and DeepSeek V3. Results show improvements over several existing baselines, while CORAL achieves slightly better performance at a substantially higher token cost.

Critical strengths
  1. The idea of adapting reflection based on the search state of individual islands is reasonable and intuitive.
  2. The paper includes comparisons across two LLM backbones and ablation studies to examine the contributions of different components.
Critical weaknesses
  1. Stagnation may reflect task difficulty rather than ineffective search. Score improvements may naturally become smaller or less frequent as solution quality increases. Thus, SAMR's state controller may misinterpret normal optimization plateaus as stagnation, leading to premature exploration or resets.

  2. Unfair budget comparison with CORAL. The authors match methods by the number of heuristic evaluations, but CORAL consumes 26.6× more tokens than SAMR. Without reporting CORAL's performance under the same token budget, the claimed quality–cost advantage is not sufficiently supported.

  3. Limited benchmark coverage in the CORAL comparison. CORAL was originally evaluated on diverse mathematical and systems optimization tasks, yet none of its original benchmarks appear to be included in SAMR's evaluation. This makes the comparison less convincing, as it remains unclear whether SAMR can achieve comparable performance on tasks where CORAL has demonstrated strong results.

Questions for authors

See my weakness

Reviewer_5nchOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

Paper introduces SAMR, an island-based framework for LLM-driven automatic heuristic design. Each island uses recent improvement and stagnation signals to select an EXPLOIT, EXPLORE, or RESET state. These states determine which diagnostic evidence enters the generation prompt: case-level comparisons, statistics over historical edit patterns, cross-island evidence, or retained negative knowledge following a reset. Evaluation covers 36 CO-Bench tasks with development-based program selection and held-out test evaluation. SAMR almost outperformed CORAL's while using fewer tokens.

Critical strengths
  • SAMR specifies how different stages of search receive different evidence, rather than relying on an undifferentiated reflection prompt. Combining empirical edit statistics with case comparisons and cross-island transfer is a useful design contribution.
  • The improvements over well-known baseline appear with two evaluated models. Development-based selection followed by held-out testing strengthens the evaluation. Reporting token consumption alongside quality also makes the substantial cost difference from CORAL visible.
Critical weaknesses
  • Section 4.1 states that evaluation counts are matched but does not give the numerical budget. The number of independent runs, aggregation across runs, and standard deviation are also unspecified. Detailed settings and complete per-task results are unprovided. That make the limit confidence in baseline comparisons and does not convince about the claim SAMR equivalent performance with CORAL
  • The “all evidence” variant changes the evidence supplied at each step and potentially increases prompt length. Its lower score could therefore reflect excessive or conflicting context, rather than demonstrate that matching particular evidence bundles to particular island states is responsible for the improvement. The contribution of preserving negative memory during resets is also not isolated.
Questions for authors
  1. Were controller thresholds, evidence policies, and other hyperparameters selected exclusively using development data? Were settings shared across tasks or tuned separately?
  2. Given the adaptive prompting and persistent knowledge mechanisms discussed in Section 2.2, what distinguishes SAMR operationally from HiFo-Prompt and AdaEvolve?
  3. Table 2 and Figure 2 compare quality and token consumption. What are the corresponding wall-clock search times, including reflection and clustering?
  4. What exact evaluator-query budget does each method receive? How are initialization, invalid programs, retries, and CORAL’s internal evaluations counted? Does reported token consumption include all reflection, clustering, and auxiliary calls?
Reviewer_a3XjOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes SAMR, a method for LLM-based heuristic design built on island-based evolutionary search. The main idea is that each island should get different evidence in its prompt depending on how its search is going. A simple controller puts each island into one of three states. Experiments show effectiveness of the proposed method.

Critical strengths

A clear and useful idea. The paper separates two questions that are often mixed together: how to search (which operator, which island) and what evidence to put in the prompt. Two islands that use the same operator may still need different information. Making the prompt content depend on the island's state gives reflection a clear job.

Memory based on real outcomes. The method records actual parent-to-child code changes and their measured score changes, rather than relying only on free-form verbal advice. Keeping a list of failed edit patterns after a reset is a reasonable way to avoid repeating the same mistakes.

Broad evaluation. The experiments cover 36 tasks and two LLM backbones, and test instances stay hidden during search. The paper is also open about trade-offs.

Critical weaknesses

The main claim is not directly tested. The paper claims that matching the type of evidence to the island's state is what helps. The key support is the "all evidence" ablation in Table 3 (0.779 vs. 0.853). However, this ablation changes several things at once: prompt length, the total amount of information, and the chance of conflicting signals. So it shows that a smaller, focused prompt beats giving everything. It does not show that the specific state-to-evidence mapping matters; a fixed, smaller set of evidence used in every state might work just as well.

Negative memory may become outdated, and it is not tested on its own. A pattern is marked "deprecated" based on edits to the island's old population. After a reset, the population is re-initialized, so the programs can look very different. An edit that failed on the old programs may work on the new ones. The paper does not say whether, or when, a deprecated pattern can be tried again. If the prompt tells the LLM to avoid it, the island may never collect the new data needed to clear it. In addition, knowledge-preserving reset is listed as a main contribution, but Table 3 has no ablation that removes negative memory (and none that removes short-term reflection). Table 7 shows that extra reflection can sometimes hurt, but it cannot tell us whether negative memory is part of the cause.

The novelty is incremental, and the closest baselines are missing. SAMR combines known parts: island-based search, reflection, memory of past edits, and rule-based state switching. Its value therefore depends on showing that evidence routing itself is what helps. The closest related methods are discussed but not compared: HiFo-Prompt and AdaEvolve (which also use progress or stagnation signals and stored insights), EoH-MR, HSEvo, and EoH. The paper acknowledges this gap in Sec. 5. Without these comparisons, it is hard to tell whether the gains come from evidence routing or from adaptive search control in general.

Run-to-run variance and key settings are not reported. The paper does not say how many runs were done per task, and it gives no standard deviations or confidence intervals. LLM-driven search is noisy, and some gaps are small (e.g., 0.035 over FunSearch). The main paper does not give the momentum window W, the induction interval N, the worst-case count K, the stagnation and reset thresholds, or the rules for labeling a pattern "confirmed" or "deprecated", and the code is only promised for later. This makes the method hard to reproduce from the paper alone.

Minor: Sec. 4.5 says removing long-term reflection causes "a decrease of 7.5 percentage points", but 0.853 → 0.789 is 6.4 points (a 7.5% relative drop). The 8.1 figure has the same issue (6.9 points).

Questions for authors

Does state-based routing beat (a) random routing with a matched token budget, (b) fixed evidence subsets, and (c) shuffled state assignments?

Can a deprecated pattern ever be tried again, for example after a reset? How does performance change if you remove negative memory, or remove short-term reflection?

How many runs per task did you use, and how much do the results vary across runs? Do the main conclusions hold across seeds?

How do you handle a code diff that contains several changes? How stable are the induced pattern categories across re-clusterings and across runs?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.