Skip to content

Evolving Deeper LLM Thinking

ArXiv: 2501.09891

🎯 Pitch

This paper introduces Mind Evolution, a language-based genetic search that leverages an LLM to generate, recombine, and iteratively refine complete natural-language solutions using programmatic fitness evaluators. By combining broad stochastic exploration with deep global refinement, it substantially raises solve rates on challenging planning and steganography-like tasks—achieving 95%+ with Gemini 1.5 Flash and near-perfect rates with a Flash→Pro two-stage setup—without requiring explicit problem formalization, making LLM-driven problem solving far more reliable and practical for real-world, hard-to-formalize tasks.

1. Executive Summary (2-3 sentences)

The paper introduces Mind Evolution, an evolutionary (genetic) search strategy that uses an LLM to generate, recombine, and iteratively refine complete candidate solutions using feedback from a programmatic solution evaluator (Figure 1, Section 3). On natural-language planning benchmarks (TravelPlanner and Natural Plan), it substantially improves solve rates over inference-time baselines like Best-of-N and multi-turn revision under comparable candidate budgets, reaching 95%+ with Gemini 1.5 Flash and ~99–100% with a two-stage Flash → Pro setup (Table 2). The same approach also transfers to a new, hard-to-formalize steganography-style benchmark StegPoet, where programmatic verification exists even though formal solving is difficult (Section 5, Table 6).

2. Context and Motivation

  • Problem / gap addressed.
  • The paper targets the question: How can an LLM be guided to “think deeper” at inference time—i.e., use more test-time compute to improve problem-solving on complex tasks—without requiring a formal task formalization (Introduction, Section 1).

  • Many strong inference-time approaches either:

    • rely on sampling many independent answers (Best-of-N) to increase odds of a correct solution, or
    • rely on sequential refinement / stepwise reasoning that often benefits from step-level evaluation (Introduction, Section 1).

  • Why this matters.

  • The tasks studied are natural-language planning problems where constraints and objectives are described in text (e.g., trip planning, meeting scheduling). These require globally consistent decisions across many constraints (Section 1; Sections 4.1–4.3).

  • The paper emphasizes a key asymmetry: it can be easier to verify whether a proposed solution satisfies constraints than it is to generate a satisfying solution from scratch (Section 1; Section 3.2 “Fitness Evaluation”; the paper references this idea and makes it concrete via implemented evaluators).

  • Prior approaches and shortcomings (as framed by the paper).

  • Best-of-N: explores broadly but does not learn from evaluator feedback, because candidates are independent (Section 1; Section 4.4 hypothesis about TravelPlanner).
  • Sequential revision / self-refinement: can refine but tends to be local and can get stuck; also many approaches assume stepwise rewards, whereas some tasks only provide global solution evaluation (Section 1; Section 3.2).

  • Formal solvers: prior high performance on TravelPlanner is associated (in the paper’s discussion) with LLM-based formalization + formal verification tools, which requires nontrivial domain expertise and a solver pipeline (Section 1; Section 4.1 compares to [16]).

  • Positioning.

  • Mind Evolution is positioned as a general search wrapper: it operates directly in natural language solution space and only assumes: 1) you can generate candidates with an LLM, and
    2) you have some evaluator that can score/validate solutions and ideally return critique text (Section 1; Section 3.2).
  • It differs from earlier LLM+evolution work that focuses on formal program spaces (Section 1; Section 2 “Pairing LLMs with Evolutionary Search”).

3. Technical Approach

3.1 Reader orientation (approachable technical breakdown)

  • The system is an inference-time search procedure that repeatedly asks an LLM to propose and improve complete solutions, while a separate evaluator scores them.
  • It solves constraint-heavy planning problems by running a genetic algorithm in natural language, combining population-based exploration with iterative refinement under a compute budget (Figure 1; Section 3).

3.2 Big-picture architecture (diagram in words)

  • Input: a problem instance (e.g., a trip-planning query + options/constraints).
  • Components and flow:
  • Initializer (LLM prompting): sample an initial population of solutions (Section 3.2 “Population Initialization”).
  • Evaluator (fitness function): parse each candidate, score it, and generate text feedback describing violations (Section 3.2 “Fitness Evaluation”; Appendix A.2).
  • Selector: probabilistically choose parent solutions biased toward higher fitness using Boltzmann tournament selection (Section 3.2 “Selection”).
  • Recombiner/Mutator (LLM-driven): produce improved “children” using a structured critic/author refinement conversation (RCC) over one or more parents (Figure 2; Section 3.2 “Crossover and Mutation”).
  • Island model controller: evolve multiple sub-populations, periodically migrating elites and resetting weak islands (Section 3.1 “Island Model”; Section 3.2 “Migration” and “Island Reset”).
  • Termination: stop early if a valid solution is found, else stop after N_gens and return best candidate (Figure 1; Section 3.2).

3.3 Roadmap for the deep dive

  • I will explain:
  • What the paper means by a language-based genetic algorithm (population, fitness, selection, crossover/mutation) (Section 3.1).
  • The evaluator: what signals it provides and why textual feedback matters (Section 3.2; Table 4; Appendix A.2).
  • The RCC refinement mechanism (Figure 2; Section 3.2; Appendix A.1).
  • The population mechanics: Boltzmann selection, islands, migration, reset (Section 3.1–3.2; Table 1).
  • How compute is controlled and compared to baselines (Table 1; Section 4 “Baselines” and “Metrics”; Table 2).

3.4 Detailed, sentence-based technical breakdown

Framing sentence (type of paper + core idea).
This is an empirical algorithm/system paper that proposes an inference-time evolutionary search procedure—Mind Evolution—where an LLM iteratively refines a population of complete candidate solutions using evaluator feedback, rather than relying on single-pass answers or independent sampling (Section 1; Section 3; Figure 1).

Core objects and terminology (defined in plain language)

  • A candidate solution is one full proposed plan in natural language (often required to be in a structured JSON-like format for parsing), such as a day-by-day travel plan (Figure 1; Appendix A.2).
  • A fitness function is the evaluator that returns:
  • a score (higher is better; in the paper’s evaluators the maximum is 0 and penalties make it negative), and
  • textual feedback listing constraint violations and formatting issues (Section 3.2 “Fitness Evaluation”; Appendix A.2).
  • A generation is one iteration of producing new child solutions from selected parents (Figure 1; Section 3.2).
  • Selection, crossover, and mutation are genetic-algorithm concepts:
  • selection: pick better candidates more often,
  • crossover: combine information from multiple parents,
  • mutation: introduce modifications that may discover new improvements (Section 3.1).
  • Here, these are implemented via LLM prompting rather than explicit symbolic operators (Section 3.1 “Language-based Genetic Representation”; Section 3.2).

System/data pipeline diagram in words (explicit step order)

  1. Start with a problem instance (e.g., TravelPlanner query + lists of options; or Natural Plan constraints; Sections 4.1–4.3).
  2. Population initialization:
  3. The procedure independently samples N_convs initial solutions by prompting the LLM with the task description and instructions (Section 3.2 “Population Initialization”).
  4. If N_seq > 1, each initial solution is then refined for N_seq − 1 turns via the RCC process (Section 3.2).
  5. This yields N_convs × N_seq candidate solutions in the initial population (Section 3.2).
  6. Fitness evaluation of candidates:
  7. Each candidate is parsed and scored by the domain evaluator.
  8. The evaluator also produces text feedback describing what is wrong (e.g., violated constraints, format violations) (Section 3.2; Appendix A.2).
  9. Selection of parents:
  10. For each “conversation” used to generate children, the method samples 0 to N_parent parents using Boltzmann tournament selection, i.e., sampling proportional to a softmax over fitness scores so higher-fitness candidates are more likely but weaker ones can be chosen sometimes to preserve diversity (Section 3.2 “Selection”).
  11. There is also an explicit probability P_r(no parents) that a conversation uses no parents (Table 1), encouraging exploration (implicit from the mechanism described in Section 3.2).
  12. Recombination + mutation via LLM (RCC):
  13. Given one or multiple parents and their evaluation feedback, the LLM runs a structured two-role conversation:
    • a critic analyzes the candidate(s) and feedback and proposes corrections,
    • an author outputs a single refined solution (Figure 2; Section 3.2 “Refinement through Critical Conversation (RCC)”).
  14. For recombination, the method feeds multiple parents into this same RCC-driven improvement step, effectively implementing crossover/mutation in one LLM call sequence (Section 3.2 “Crossover and Mutation”).
  15. If N_seq > 1, the child is further refined sequentially for additional turns, producing N_seq children per conversation (Section 3.2).
  16. Population update:
  17. For each generation and each island, N_convs × N_seq child solutions are added to that island’s population, and duplicates are removed (Section 3.2 “Crossover and Mutation”).
  18. Island evolution, migration, and reset (diversity maintenance):
  19. The population is partitioned into N_island independent sub-populations (“islands”) (Section 3.1; Table 1).
  20. Migration: after updating island i, the top N_emigrate solutions are cloned into island i+1 in a cyclic manner (Section 3.2 “Migration between Islands”; Table 1).
  21. Island reset: every N_reset_interval generations, the N_reset islands with lowest mean score are “retired” and repopulated using top global performers (Section 3.2 “Island Reset”; Table 1).
    • The paper evaluates two reset strategies: 1) directly select top N_top by fitness, or 2) pick top N_candidate by fitness, then ask the LLM to select N_top among them that are high quality and diverse (Section 3.2).
  22. Termination:
  23. The search stops when a fully valid solution is found or after N_gens generations, returning the best-scoring candidate (Figure 1; Section 3.2).

Hyperparameters / configurations (as provided)

Because this is an inference-time method applied to off-the-shelf LLMs (no training described), typical training hyperparameters (optimizer, LR schedule, batch size, etc.) are not applicable and not provided. The paper instead specifies search hyperparameters:

  • Default Mind Evolution hyperparameters (Table 1):
  • N_gens = 10 (max generations)
  • N_island = 4 (islands)
  • N_convs = 5 (conversations per island)
  • N_seq = 4 (turns per conversation)
  • N_reset_interval = 3
  • N_reset = 2 (islands reset each event)
  • N_top = 5
  • N_candidate = 15
  • N_parent = 5 (max parents used)
  • P_r(no parents) = 1/6
  • N_emigrate = 5
  • N_retries = 5 (retries to generate a plan before giving up at each turn)
  • The paper notes: the product of the first four hyperparameters yields the maximum number of candidate solutions generated, which is 800 under the default setting (10 × 4 × 5 × 4 = 800) (Table 1 caption).
  • Two-stage setup with Gemini 1.5 Pro uses altered hyperparameters (Section 4 “Models”):
  • N_convs = 8, N_seq = 3, N_parent = 10, P_r(no parents) = 1/5.

Design choices and their rationale (grounded in the paper)

  • Global solution refinement vs stepwise process rewards.
  • The paper emphasizes that Mind Evolution refines complete solutions and thus only requires a global evaluator, unlike methods that require evaluation of intermediate reasoning steps (Section 1; Section 3.2).
  • Textual feedback is treated as a critical learning signal.
  • The evaluator provides not just a pass/fail but explanations of issues (Section 3.2), and the ablation shows removing textual feedback hurts performance substantially on TravelPlanner (Table 4).
  • Critic/author role separation (RCC) as a prompting technique.
  • The critic produces explicit analysis that the author uses to revise; disabling the critic step reduces performance in the ablation (Section 3.2; Table 4).
  • Island model for diversity and avoiding premature convergence.
  • Multiple islands evolve independently with migration and periodic resets (Section 3.1; Section 3.2), and a hyperparameter study shows better results with islands than without, controlling for ~800 candidates on Trip Planning with 10 cities (Table 5).
  • LLM-assisted island reset to promote diversity among elites.
  • Instead of copying the top-scoring solutions that may be near-duplicates, the method can ask the LLM to select diverse high performers during resets; this improves TravelPlanner results in the ablation (Section 3.2 “Island Reset”; Table 4).

Worked micro-example (single input → output walk-through)

A minimal walk-through is illustrated directly in Figure 2:

  1. Input task (Trip Planning-style): e.g., “visit 7 Asian cities; spend 5 days in Tokyo…” (Figure 2a).
  2. Initial solution: a JSON-like list allocates "Tokyo": 3 days (Figure 2b).
  3. Evaluator feedback: flags the violation: “planned 3 days for Tokyo, required 5” (Figure 2c).
  4. Critic analysis: explicitly identifies the needed correction (“Tokyo should be 5 instead of 3”) (Figure 2d).
  5. Author revision: outputs an updated plan with "Tokyo": 5 days (Figure 2e).

The key point is that this same mechanism is reused both for: - single-parent refinement (mutation-like), and - multi-parent recombination (crossover-like) where the critic considers multiple parents and their feedback before proposing a revised child (Section 3.2 “Crossover and Mutation”).

4. Key Insights and Innovations

  1. Evolutionary search directly in natural-language solution space (not formalized programs).
  2. Prior LLM+evolution work discussed by the paper often searches formal program spaces or uses execution feedback (Section 1; Section 2).

  3. Here the “genome” is natural language, enabling application to tasks that are difficult to formalize but still evaluable (Section 1; Section 3.1 “Language-based Genetic Representation”; Section 5 on StegPoet).

  4. Combining broad exploration and deep refinement under one search budget.

  5. The method is explicitly designed to do both:
    • “broad” exploration via population sampling, stochastic parent selection, and no-parent conversations, and
    • “deep” exploitation via multi-turn refinement (N_seq turns) and repeated generations (N_gens) (Section 1; Table 1; Figures 6–9 show scaling trends).

  6. This is positioned as an advantage over Best-of-N (breadth without feedback) and purely sequential revision (depth but less population diversity) (Section 1; Section 4.1 discussion).

  7. RCC prompting (critic/author) as the operative mutation/recombination operator.

  8. Instead of hand-designed crossover/mutation operators, Mind Evolution uses a structured prompting protocol to implement both (Figure 2; Section 3.2 “Refinement through Critical Conversation”; Section 3.2 “Crossover and Mutation”).

  9. The critic role is not cosmetic: disabling it causes a large drop in TravelPlanner success in the ablation (Table 4).

  10. Diversity maintenance via island model + LLM-based reset selection.

  11. The method imports the island model concept (Section 3.1) and shows empirically that it helps (Table 5).

  12. The reset step optionally uses the LLM to select diverse elites, and this improves results versus choosing elites solely by score (Section 3.2; Table 4).

  13. Demonstrating evaluator-guided search on a new task (StegPoet) where verification is feasible but formal solving is hard.

  14. StegPoet is designed to be hard to formalize; the paper provides a concrete verification method (Appendix F) and shows large gains for Mind Evolution over baselines (Section 5; Table 6; Figure 10).

5. Experimental Analysis

Evaluation methodology

  • Tasks / datasets (Section 4 “Tasks”).
  • TravelPlanner in “sole-planning mode” (Section 4.1).
  • Natural Plan:
    • Trip Planning (Section 4.2),
    • Meeting Planning (Section 4.3).
  • New benchmark: StegPoet (Section 5).
  • Splits (Appendix B; Section 5).
  • TravelPlanner: 180 validation, 1,000 test (Appendix B).
  • Trip Planning: 320 validation, 1,280 test (Appendix B).
  • Meeting Planning: 500 validation, 500 test (Appendix B).
  • StegPoet: 101 validation, 245 test (Section 5).
  • Metric.
  • Success Rate = fraction of instances solved within a domain (Section 4 “Metrics”).
  • Compute / cost reporting.
  • Average LLM calls, input tokens, output tokens, and API cost (USD) using October 2024 pricing (Section 4 “Metrics”; Table 2; Table 6; Table 8).

Baselines (Section 4 “Baselines”)

All baselines use the same evaluator and task-specific prompts (Section 4):

  1. 1-Pass: single forward pass.
  2. Best-of-N: generate up to 800 independent candidates until success (same upper bound as default Mind Evolution).
  3. Sequential-Revision+: 10 independent candidates, each revised up to 80 turns using RCC (10 × 80 = 800 refinement steps).
  4. Additional reference: o1-preview 1-Pass (Section 4; Table 2).

Main quantitative results (with specific numbers)

TravelPlanner (Section 4.1; Table 2; Figure 3).

Table 2 (validation):
- 1-Pass (Gemini 1.5 Flash): 5.6% (10/180)
- Best-of-N: 55.6% (100/180)
- Sequential-Revision+: 82.8% (149/180)
- Mind Evolution: 95.6% (172/180) with 174 calls and US(0.29** avg cost
- Mind Evolution (+pro): **100%** (180/180) (two-stage) with **US\)0.54 avg cost on remaining problems

Table 2 (test):
- Mind Evolution: 95.2% (952/1000) with US(0.28** avg cost
- Mind Evolution (+pro): **99.9%** (999/1000) with **US\)0.33 avg cost on remaining problems

  • Figure 3 breaks down performance by difficulty and trip length, showing 1-Pass and Best-of-N decline for longer trips, while Mind Evolution and Sequential-Revision+ are more stable (Figure 3; Section 4.1 discussion).

Natural Plan – Trip Planning (Section 4.2; Table 2; Figure 4).

Table 2:
- Validation: Mind Evolution 96.2% (308/320) vs Best-of-N 77.2%, Sequential-Revision+ 74.4%
- Test: Mind Evolution 94.1% (1204/1280)
- Two-stage: 100% val, 99.6% test

  • Figure 4 shows success rate by number of cities (3–10), with the gap favoring Mind Evolution growing as the number of cities increases (Figure 4; Section 4.2).

Natural Plan – Meeting Planning (Section 4.3; Table 2; Figure 5).

Table 2:
- Validation: Mind Evolution 85.0% (425/500) vs Best-of-N 69.4%, Sequential-Revision+ 62.0%
- Test: Mind Evolution 83.8% (419/500)
- Two-stage: 98.4% val, 98.2% test

  • The task is different: not every instance has a clearly known optimum, so searches run to the iteration cap rather than stopping at first success (Section 4.3).

StegPoet (Section 5; Table 6; Figure 11).

Table 6 (validation):
- 1-Pass: 0.0% (0/101)
- Best-of-N: 1.0% (1/101)
- Sequential-Revision+: 19.8% (20/101)
- Mind Evolution (Flash): 46.5% (47/101)
- Mind Evolution (+pro): 87.1% (88/101)

Table 6 (test):
- Mind Evolution (Flash): 43.3% (106/245)
- Mind Evolution (+pro): 79.2% (194/245)

  • Figure 11 shows success stratified by the minimum required word spacing B (difficulty increases as B grows) (Section 5; Figure 11).

Do the experiments support the claims?

  • Claim: outperform other inference strategies controlling for inference cost.
  • The paper explicitly reports costs (calls/tokens/USD) and shows Mind Evolution can be both more accurate and cheaper than some baselines at similar candidate budgets.
  • Example: TravelPlanner validation:
    • Mind Evolution costs US(0.29** vs Best-of-N **US\)0.47 and Sequential-Revision+ US$2.75, while also having higher success (Table 2).

  • The cost-benefit trend is also visualized as success vs number of candidates (Figures 7–9) and success vs API cost (Figure 25).

  • Scaling evidence.

  • Figure 6 shows success improves with more generations across tasks.
  • Figures 7–9 show monotonic improvement with more candidate solutions, and Mind Evolution achieves higher success for a given candidate count than baselines.

Ablations / robustness / failure cases

  • Ablation study on TravelPlanner (Section 4.4; Table 4).
  • Table 4 shows large drops when removing:
    • the critic step in RCC, and
    • textual feedback from the evaluator.
  • It also shows benefits from Reset with LLM and task-specific S/Q prompts.
  • Hyperparameter sensitivity (Trip Planning, 10 cities) (Table 5).
  • With the same ~800 candidates, using an island model improves success:
    • w/ island model: 87.5%
    • w/o island model: 77.4% (Table 5).

  • There is also a depth vs breadth trade-off: more generations with fewer candidates per generation vs fewer generations with more candidates per generation show different outcomes (Table 5).

  • Qualitative examples of failure modes in baselines.

  • Table 3 shows different baseline errors: wrong day counts, missing event constraints, invalid flights; Mind Evolution satisfies all constraints in the example.
  • Table 10 shows a Meeting Planning example where the “best possible” plan cannot meet everyone; Mind Evolution omits Michelle but is judged best possible by the evaluator framing (Table 10).

6. Limitations and Trade-offs

  • Requires an evaluator that can be implemented programmatically (major constraint).
  • The approach depends on being able to parse and score candidate solutions, and ideally produce text critique (Section 3.2; Conclusion “Limitations”).

  • The paper explicitly frames this as the main limitation and suggests future work on LLM-based evaluators (Conclusion).

  • Evaluator engineering and formatting constraints are nontrivial.

  • For planning tasks, the evaluators expect structured formats (often JSON), and the paper modifies/extends benchmark evaluators to provide cumulative scoring + textual feedback (Appendix A.2).
  • On TravelPlanner test, constraints are only in text; the paper extracts constraints into JSON using Gemini 1.5 Flash with repeated prompting and majority vote, validating agreement on the validation set and agreement with the official server (Appendix A.2 “TravelPlanner”).

  • This introduces an additional dependency: an information extraction step that must be reliable.

  • Compute/cost trade-off vs single-pass inference.

  • Search is substantially more expensive than one call (Section 4 “Metrics”).

  • Even if cheaper than some baselines, Mind Evolution still uses many calls per instance on average (e.g., TravelPlanner validation average 174 calls; Table 2).

  • Task fit: better when “verification is easier than generation.”

  • The method is naturally suited to domains where checking is easier than solving (Section 3.2).

  • If evaluation is ambiguous, subjective, or hard to formalize/implement, the method’s advantage may shrink unless a reliable learned evaluator exists (the paper notes learned/self-evaluators can be noisy; Section 2 “Pairing LLMs with Evaluators”).

  • Meeting Planning objective ambiguity / stopping criteria.

  • For Meeting Planning, the paper notes you cannot know optimality for every instance; searches are run to the iteration cap (Section 4.3). This highlights that “success” may depend on the evaluator’s definition and thresholds.

7. Implications and Future Directions

  • How this changes the landscape (within the paper’s scope).
  • The results suggest that test-time compute scaling via structured population search + evaluator feedback can dramatically close the gap on complex constraint-satisfaction planning tasks without requiring formal solvers (Section 4.1; Conclusion).

  • The paper demonstrates that evolutionary mechanisms—islands, migration, reset, and Boltzmann selection—are practical and beneficial when the “genome” is natural language and mutation/crossover are implemented via prompting (Section 3; Tables 4–5).

  • Follow-up research directions suggested by the paper.

  • Develop LLM-based evaluators to extend beyond domains with implementable oracles (Conclusion “Limitations”; Section 2 notes learned feedback can be noisy and is left for future work).
  • Improve robustness and generality of evaluator feedback, since textual feedback is empirically critical (Table 4).

  • Explore broader tasks beyond planning, as motivated by StegPoet (Section 5).

  • Practical applications / downstream use cases (as implied by tasks).

  • Any domain with: 1) complex constraints described in text, 2) a way to parse candidate outputs, 3) a verifier/scorer that can produce actionable critique, can potentially benefit—e.g., itinerary planning and schedule construction are the paper’s concrete demonstrations (Sections 4.1–4.3).

  • Repro/Integration Guidance (when to prefer this over alternatives).

  • Prefer Mind Evolution over Best-of-N when evaluator feedback contains important implicit constraints that need to be learned through iteration; the paper hypothesizes this explains why Best-of-N underperforms on TravelPlanner (Section 4.4).
  • Prefer Mind Evolution over pure sequential refinement when you need diversity and want to avoid getting stuck in a single refinement trajectory; islands + migration + reset are designed for this (Sections 3.1–3.2; Table 5).
  • Use the two-stage (Flash → Pro) approach when cost matters: solve most instances cheaply with a smaller model, then escalate hard cases to a stronger model with adjusted search hyperparameters (Section 4 “Models”; Table 2; Table 6).