Elamur Research⌕
☰
home / papers / 2025 / Evolving Deeper LLM Thinking

Evolving Deeper LLM Thinking

Paper · 2025 · Kuang-Huei Lee, Ian Fischer, Yueh-Hua Wu et al.

Summary

The paper asks how extra inference-time compute can make an LLM solve hard planning problems stated purely in natural language, without first converting them into a formal representation. The authors propose Mind Evolution, a genetic-style search. The LLM writes an initial population of complete candidate answers. A programmatic evaluator scores each candidate and returns textual critiques. Prompts then drive the LLM to perform crossover, mutation and refinement. An island model with migration and resets keeps the population diverse. Because only whole solutions are scored, no step-level reward model is needed, and the process parallelizes easily.

Experiments use off-the-shelf Gemini 1.5 Flash and Pro, with no finetuning, on TravelPlanner and Natural Plan. At matched compute, Mind Evolution clearly beats Best-of-N and sequential revision. It approaches perfect accuracy without a formal solver. The authors also release a new steganography benchmark, StegPoet.

The work matters because it extends search-based scaling to problems that are hard to formalize. The only requirement is that answers can be checked automatically.

Key points

  • Baselines are weak on these tasks. On TravelPlanner, Gemini 1.5 Flash solves 5.6% of problems and o1-preview solves 11.7%. Best-of-N with 800 samples lifts Flash to only 55.6% on TravelPlanner and 69.4% on Meeting Planning (Natural Plan).
  • Mind Evolution with Flash alone reaches 95.6% on TravelPlanner and 85.0% on Meeting Planning.
  • A two-stage setup adds Gemini 1.5 Pro for the instances Flash leaves unsolved. This yields 100% on TravelPlanner and 98.4% on Meeting Planning.
  • StegPoet asks the model to hide a number sequence in a poem, story or essay via a number-to-word cipher. It has 101 validation and 245 test instances. The two-stage method scores 87.1% on validation and 79.2% on test, while Best-of-N solves 1% of validation.
  • Ablations: the island model gives a significant gain, and deeper search helps as long as each generation still explores broadly. The main limitation is that a programmatic evaluator is required; LLM-based evaluators are left for future work.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓University of California San DiegoSan Diego · United States101 works · 54,571 citations🎓University of AlbertaEdmonton · Canada54 works · 5,242 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 19,503 worksArtificial Intelligence · 18,805 worksArts and Humanities · 17,959 worksLanguage and Linguistics · 17,789 works

🧭 Topics 1Research subjects and languages the work is about.Language models & pretraining · 4,145 works

Cite

Cite as Kuang-Huei Lee, Ian Fischer, Yueh-Hua Wu, Dave Marwood, Shumeet Baluja, Dale Schuurmans and Xinyun Chen. 2025. Evolving Deeper LLM Thinking. arXiv:2501.09891.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.2501.09891 · arXiv 2501.09891

@misc{lee2025evolving,
  title = {{Evolving Deeper LLM Thinking}},
  author = {Kuang-Huei Lee, Ian Fischer, Yueh-Hua Wu, Dave Marwood, Shumeet Baluja, Dale Schuurmans and Xinyun Chen},
  year = {2025},
  doi = {10.48550/arxiv.2501.09891},
  eprint = {2501.09891},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2501.09891}
}

References

48 references, 18 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. [1] Y. Bai, S. Kadavath, S. Kundu, A. Askell, J. Kernion, A. Jones, A. Chen, A. Goldie, A. Mirhoseini, C. McKinnon, et al. Constitutional AI: Harmlessness from AI feedback. arXiv preprint arXiv:2212.08073, 2022.
  2. [2] B. Berger, M. S. Waterman, and Y. W. Yu. Levenshtein distance, sequence comparison and biological database search. IEEE Transactions on Information Theory, 67(6):3287–3294, 2021. doi: 10.1109/TIT.2020.2996543. — [doi:10.1109/tit.2020.2996543](https://doi.org/10.1109/tit.2020.2996543) find
  3. [3] S. Brahmachary, S. M. Joshi, A. Panda, K. Koner-ipalli, A. K. Sagotra, H. Patel, A. Sharma, A. D. Jagtap, and K. Kalyanaraman. Large language model-based evolutionary optimizer: Reasoning with elitism. arXiv preprint arXiv:2403.02054, 2024. — [arXiv:2403.02054](https://arxiv.org/abs/2403.02054) find
  4. [4] B. Brown, J. Juravsky, R. Ehrlich, R. Clark, Q. V. Le, C. Ré, and A. Mirhoseini. Large language monkeys: Scaling inference compute with repeated sampling. arXiv preprint arXiv:2407.21787, 2024.
  5. [5] E. Cantú-Paz et al. A survey of parallel genetic algorithms. Calculateurs paralleles, reseaux et systems repartis, 10(2):141–171, 1998. find
  6. [6] A. Chen, D. M. Dohan, and D. R. So. EvoPrompting: Language models for code-level neural architecture search. In Proceedings of the 37th International Conference on Neural Information Processing Systems, pages 7787–7817, 2023. find
  7. [7] B. Chen, F. Zhang, A. Nguyen, D. Zan, Z. Lin, J.-G. Lou, and W. Chen. CodeT: Code generation with generated tests. In The Eleventh International Conference on Learning Representations, 2023. URL https://openreview.net/forum?id=ktrw68Cmu9c. ↗
  8. [8] X. Chen, M. Lin, N. Schärli, and D. Zhou. Teaching large language models to self-debug. In The Twelfth International Conference on Learning Representations, 2024. URL https://openreview.net/forum?id= KuPixIqPiq. ↗
  9. [9] K. Cobbe, V. Kosaraju, M. Bavarian, M. Chen, H. Jun, L. Kaiser, M. Plappert, J. Tworek, J. Hilton, R. Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168, 2021.
  10. [10] C. Fernando, D. Banarse, H. Michalewski, S. Osindero, and T. Rocktäschel. Promptbreeder: Self-referential self-improvement via prompt evolution. arXiv preprint arXiv:2309.16797, 2023.
  11. [11] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP Completeness. W. H. Freeman & Co., 1979. find
  12. [12] D. E. Golberg. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison Wesley, 1989. find
  13. [13] D. E. Goldberg. A note on Boltzmann tournament selection for genetic algorithms and population-oriented simulated annealing. Complex Systems, 4:445–460, 1990. find
  14. [25] H. Lightman, V. Kosaraju, Y. Burda, H. Edwards, B. Baker, T. Lee, J. Leike, J. Schulman, I. Sutskever, and K. Cobbe. Let’s verify step by step. arXiv preprint arXiv:2305.20050, 2023.
  15. [14] J. P. Guilford. The Nature of Human Intelligence. 1967. find
  16. [26] F. Liu, X. Lin, Z. Wang, S. Yao, X. Tong, M. Yuan, and Q. Zhang. Large language model for multi-objective evolutionary optimization. arXiv preprint arXiv:2310.12541, 2023. — [arXiv:2310.12541](https://arxiv.org/abs/2310.12541) find
  17. [15] Q. Guo, R. Wang, J. Guo, B. Li, K. Song, X. Tan, G. Liu, J. Bian, and Y. Yang. Connecting large language models with evolutionary algorithms yields powerful prompt optimizers. arXiv preprint arXiv:2309.08532, 2023.
  18. [16] Y. Hao, Y. Chen, Y. Zhang, and C. Fan. Large language models can plan your travels rigorously with formal verification tools. arXiv preprint arXiv:2404.11891, 2024. — [arXiv:2404.11891](https://arxiv.org/abs/2404.11891) find
  19. [17] E. Hemberg, S. Moskal, and U.-M. O’Reilly. Evolving code with a large language model. Genetic Programming and Evolvable Machines, 25(2):21, 2024. find
  20. [18] J. H. Holland. Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, MI, 1975. second edition, 1992. find
  21. [19] G. Kim, P. Baldi, and S. McAleer. Language models can solve computer tasks. arXiv preprint arxiv:2303.17491, 2023.
  22. [20] J. H. Kirchner, Y. Chen, H. Edwards, J. Leike, N. McAleese, and Y. Burda. Prover-verifier games improve legibility of LLM outputs. arXiv preprint arXiv:2407.13692, 2024. — [arXiv:2407.13692](https://arxiv.org/abs/2407.13692) find
  23. [21] T. Kojima, S. S. Gu, M. Reid, Y. Matsuo, and Y. Iwasawa. Large language models are zero-shot reasoners. Advances in Neural Information Processing Systems, 35:22199–22213, 2022.
  24. [22] H. Le, Y. Wang, A. D. Gotmare, S. Savarese, and S. C. H. Hoi. CodeRL: Mastering code generation through pretrained models and deep reinforcement learning. Advances in Neural Information Processing Systems, 35:21314–21328, 2022.
  25. [27] J. Liu, Y. Zhu, K. Xiao, Q. FU, X. Han, Y. Wei, and D. Ye. RLTF: Reinforcement learning from unit test feedback. Transactions on Machine Learning Research, 2023. ISSN 2835-8856. URL https://openreview.net/ forum?id=hjYmsV6nXZ. ↗
  26. [28] S. Liu, C. Chen, X. Qu, K. Tang, and Y.-S. Ong. Large language models as evolutionary optimizers. In 2024 IEEE Congress on Evolutionary Computation (CEC), pages 1–8. find
  27. [29] V. Liventsev, A. Grishina, A. Härmä, and L. Moonen. Fully autonomous programming with large language models. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 1146–1155, 2023. find
  28. [30] A. Madaan, N. Tandon, P. Gupta, S. Hallinan, L. Gao, S. Wiegreffe, U. Alon, N. Dziri, S. Prabhumoye, Y. Yang, et al. Self-refine: Iterative refinement with self-feedback. Advances in Neural Information Processing Systems, 36, 2024. find
  29. [31] M. Mitchell. An Introduction to Genetic Algorithms. MIT press, 1998. find
  30. [32] J. S. Park, J. O’Brien, C. J. Cai, M. R. Morris, P. Liang, and M. S. Bernstein. Generative agents: Interactive simulacra of human behavior. In Proceedings of the 36th Annual ACM Symposium on User Interface Software and Technology, pages 1–22, 2023. find
  31. [33] N. Provos and P. Honeyman. Hide and seek: An introduction to steganography. IEEE security & privacy, 1(3):32–44, 2003. find
  32. [23] J. Lehman, J. Gordon, S. Jain, K. Ndousse, C. Yeh, and K. O. Stanley. Evolution through large models. In Handbook of Evolutionary Machine Learning, pages 331–366. Springer, 2023. find
  33. [34] B. Romera-Paredes, M. Barekatain, A. Novikov, M. Balog, M. P. Kumar, E. Dupont, F. J. Ruiz, J. S. Ellenberg, P. Wang, O. Fawzi, et al. Mathematical discoveries from program search with large language models. Nature, 625(7995):468–475, 2024.
  34. [24] Z. Liang, Y. Liu, T. Niu, X. Zhang, Y. Zhou, and S. Yavuz. Improving LLM reasoning through scaling inference computation with collaborative verification. arXiv preprint arXiv:2410.05318, 2024. — [arXiv:2410.05318](https://arxiv.org/abs/2410.05318) find
  35. [35] A. Setlur, C. Nagpal, A. Fisch, X. Geng, J. Eisenstein, R. Agarwal, A. Agarwal, J. Berant, and A. Kumar. Rewarding progress: Scaling automated process verifiers for LLM reasoning. arXiv preprint arXiv:2410.08146, 2024.
  36. [36] N. Shinn, F. Cassano, A. Gopinath, K. Narasimhan, and S. Yao. Reflexion: Language agents with verbal reinforcement learning. Advances in Neural Information Processing Systems, 36, 2024.
  37. [37] C. Snell, J. Lee, K. Xu, and A. Kumar. Scaling LLM test-time compute optimally can be more effective than scaling model parameters. arXiv preprint arXiv:2408.03314, 2024.
  38. Information Processing Systems, pages 54769– 54784, 2023. find
  39. [47] H. S. Zheng, S. Mishra, H. Zhang, X. Chen, M. Chen, A. Nova, L. Hou, H.-T. Cheng, Q. V. Le, E. H. Chi, et al. NATURAL PLAN: Benchmarking LLMs on natural language planning. arXiv preprint arXiv:2406.04520, 2024. find
  40. [38] R. Tanese. Distributed genetic algorithms for function optimization. University of Michigan, 1989. find
  41. [39] X. Wang, J. Wei, D. Schuurmans, Q. V. Le, E. H. Chi, S. Narang, A. Chowdhery, and D. Zhou. Self-consistency improves chain of thought reasoning in language models. In The Eleventh International Conference on Learning Representations, 2023. URL https://openreview.net/forum?id=1PL1NIMMrw. ↗
  42. [40] Z. Wang, Y. Li, Y. Wu, L. Luo, L. Hou, H. Yu, and J. Shang. Multi-step problem solving through a verifier: An empirical analysis on model-induced process supervision. arXiv preprint arXiv:2402.02658, 2024.
  43. [41] J. Wei, X. Wang, D. Schuurmans, M. Bosma, F. Xia, E. Chi, Q. V. Le, D. Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in Neural Information Processing Systems, 35:24824–24837, 2022.
  44. [42] J. Xie, K. Zhang, J. Chen, T. Zhu, R. Lou, Y. Tian, Y. Xiao, and Y. Su. Travelplanner: A benchmark for real-world planning with language agents. arXiv preprint arXiv:2402.01622, 2024.
  45. [43] S. Yao, D. Yu, J. Zhao, I. Shafran, T. L. Griffiths, Y. Cao, and K. Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. In Proceedings of the 37th International Conference on Neural Information Processing Systems, pages 11809–11822, 2023. find
  46. [44] H. Ye, J. Wang, Z. Cao, F. Berto, C. Hua, H. Kim, J. Park, and G. Song. ReEvo: Large language models as hyper-heuristics with reflective evolution. arXiv preprint arXiv:2402.01145, 2024. find
  47. [45] S. Yuan, K. Song, J. Chen, X. Tan, D. Li, and D. Yang. EvoAgent: Towards automatic multi-agent generation via evolutionary algorithms. arXiv preprint arXiv:2406.14228, 2024. find
  48. [46] K. Zhang, D. Wang, J. Xia, W. Y. Wang, and L. Li. ALGO: Synthesizing algorithmic programs with LLM-generated oracle verifiers. In Proceedings of the 37th International Conference on Neural

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/lee-2025-evolving-deeper-llm-thinking/