Elamur Research⌕
☰
home / papers / 2024 / Large Language Models As Evolution Strategies

Large Language Models As Evolution Strategies

Paper · 2024 · Robert Tjarko Lange, Yingtao Tian and Yujin Tang

Summary

The paper asks whether LLMs trained only on text, and never on optimization, can work as black-box optimizers. Specifically, it tests whether they can act as the update step of an evolution strategy. The authors introduce EvoLLM, a prompting scheme for isotropic Gaussian ES. Candidate solutions are mapped onto an integer grid so that the tokenizer handles them cleanly. Past generations and their members are listed from worst to best fitness, and the model is then asked for a new mean of the search distribution. Long search vectors can be divided into blocks and processed with batched queries.

EvoLLM was evaluated on synthetic BBOB functions and small neuroevolution control tasks. It consistently outperformed random search and Gaussian Hill Climbing. Ablations show that the integer representation is essential, while results are fairly insensitive to how much context is supplied. Fine-tuning the LLM on optimization trajectories from a teacher algorithm improves performance further.

These results suggest that frozen LLMs can serve as drop-in recombination operators for evolutionary optimization.

Key points

  • Main benchmark: 8 BBOB settings (10 runs each) plus 3 neuroevolution control problems (5 runs each). EvoLLM beat traditional baselines on both.
  • Among the tested LLMs (including PaLM2 variants), smaller models generally performed better than larger ones.
  • A plain-text prompting baseline (Zhang et al.) improved early but then stalled, failing to home in on optima. With a range of −3 to 3, performance rose as resolution increased up to 1000 bins and fell again at 10,000. Since tokenizers such as SentencePiece encode integers below 1000 as single tokens, this grid size fits well.
  • Supplying more past generations tended to help more than supplying more members per generation. Even very limited context was enough to produce improving mean updates.
  • PaLM-XS was fine-tuned on Gaussian Hill Climbing rollouts collected on Sphere and Rosenbrock. It was then evaluated on Sphere and Rastrigin (2 and 5 dimensions) and on the unseen CartPole task, where it gained modestly and usually surpassed the teacher.

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

🎓Technische Universität BerlinBerlin · Germany23 works · 1,022 citations

 Fields, topics and concepts

📚 Shelves 3The field of science this work belongs to (OpenAlex fields).Computer Science · 19,503 worksArtificial Intelligence · 18,805 worksComputational Theory and Mathematics · 496 works

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

Cite

Cite as Robert Tjarko Lange, Yingtao Tian and Yujin Tang. 2024. Large Language Models As Evolution Strategies. arXiv:2402.18381.

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

@misc{lange2024large,
  title = {{Large Language Models As Evolution Strategies}},
  author = {Robert Tjarko Lange, Yingtao Tian and Yujin Tang},
  year = {2024},
  doi = {10.48550/arxiv.2402.18381},
  eprint = {2402.18381},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2402.18381}
}

References

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

  1. Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. 2016. Openai gym. arXiv preprint arXiv:1606.01540 (2016). find
  2. Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020. Language models are few-shot learners. Advances in neural information processing systems 33 (2020), 1877–1901.
  3. Angelica Chen, David M Dohan, and David R So. 2023. EvoPrompting: Language Models for Code-Level Neural Architecture Search. (2023). find
  4. Lili Chen, Kevin Lu, Aravind Rajeswaran, Kimin Lee, Aditya Grover, Misha Laskin, Pieter Abbeel, Aravind Srinivas, and Igor Mordatch. 2021. Decision transformer: Reinforcement learning via sequence modeling. Advances in neural information processing systems 34 (2021), 15084–15097. find
  5. Yutian Chen, Matthew W Hoffman, Sergio Gómez Colmenarejo, Misha Denil, Timothy P Lillicrap, Matt Botvinick, and Nando Freitas. 2017. Learning to learn without gradient descent by gradient descent. In International Conference on Machine Learning. PMLR, 748–756. find
  6. Yutian Chen, Xingyou Song, Chansoo Lee, Zi Wang, Richard Zhang, David Dohan, Kazuya Kawakami, Greg Kochanski, Arnaud Doucet, Marc’aurelio Ranzato, et al. 2022. Towards learning universal hyperparameter optimizers with transformers. Advances in Neural Information Processing Systems 35 (2022), 32053–3… find
  7. Lucio M Dery, Abram L Friesen, Nando De Freitas, Marc’Aurelio Ranzato, and Yutian Chen. 2022. Multi-step Planning for Automated Hyperparameter Optimization with OptFormer. arXiv preprint arXiv:2210.04971 (2022). — [arXiv:2210.04971](https://arxiv.org/abs/2210.04971) find
  8. Chrisantha Fernando, Dylan Banarse, Henryk Michalewski, Simon Osindero, and Tim Rocktäschel. 2023. Promptbreeder: Self-referential self-improvement via prompt evolution. arXiv preprint arXiv:2309.16797 (2023).
  9. Rohan Anil Google and, Andrew M. Dai, Orhan Firat, Melvin Johnson, Dmitry Lepikhin, Alexandre Passos, Siamak Shakeri, Emanuel Taropa, Paige Bailey, Zhifeng Chen, Eric Chu, Jonathan H. Clark, Laurent El Shafey, Yanping Huang, Kathy Meier-Hellstern, Gaurav Mishra, Erica Moreira, Mark Omernick, Kevin R… — PaLM 2 Technical Report
  10. Qingyan Guo, Rui Wang, Junliang Guo, Bei Li, Kaitao Song, Xu Tan, Guoqing Liu, Jiang Bian, and Yujiu Yang. 2023. Connecting large language models with evolutionary algorithms yields powerful prompt optimizers. arXiv preprint arXiv:2309.08532 (2023).
  11. Nikolaus Hansen. 2006. The CMA evolution strategy: a comparing review. Towards a new evolutionary computation: Advances in the estimation of distribution algorithms (2006), 75–102. find
  12. Nikolaus Hansen, Anne Auger, Steffen Finck, and Raymond Ros. 2010. Real-parameter black-box optimization benchmarking 2010: Experimental setup. Ph.D. Dissertation. INRIA. find
  13. Louis Kirsch, James Harrison, Jascha Sohl-Dickstein, and Luke Metz. 2022. General-purpose in-context learning by meta-learning transformers. arXiv preprint arXiv:2212.04458 (2022). — [arXiv:2212.04458](https://arxiv.org/abs/2212.04458) find
  14. Jannik Kossen, Neil Band, Clare Lyle, Aidan N Gomez, Thomas Rainforth, and Yarin Gal. 2021. Self-attention between datapoints: Going beyond individual input-output pairs in deep learning. Advances in Neural Information Processing Systems 34 (2021), 28742–28756. find
  15. Siddarth Krishnamoorthy, Satvik Mehul Mashkaria, and Aditya Grover. 2022. Generative pretraining for black-box optimization. arXiv preprint arXiv:2206.10786 (2022). — [arXiv:2206.10786](https://arxiv.org/abs/2206.10786) find
  16. Robert Lange, Tom Schaul, Yutian Chen, Chris Lu, Tom Zahavy, Valentin Dalibard, and Sebastian Flennerhag. 2023. Discovering Attention-Based Genetic Algorithms via Meta-Black-Box Optimization. In Proceedings of the Genetic and Evolutionary Computation Conference. 929–937. find
  17. Robert Lange, Tom Schaul, Yutian Chen, Tom Zahavy, Valentin Dalibard, Chris Lu, Satinder Singh, and Sebastian Flennerhag. 2023. Discovering evolution strategies via meta-black-box optimization. In Proceedings of the Companion Conference on Genetic and Evolutionary Computation. 29–30. find
  18. Robert Tjarko Lange. 2022. evosax: JAX-based Evolution Strategies. arXiv preprint arXiv:2212.04180 (2022). find
  19. Robert Tjarko Lange. 2022. gymnax: A JAX-based Reinforcement Learning Environment Library. (2022). http://github.com/RobertTLange/gymnax ↗
  20. Robert Tjarko Lange, Yujin Tang, and Yingtao Tian. 2023. NeuroEvoBench: Benchmarking Evolutionary Optimizers for Deep Learning Applications. arXiv preprint arXiv:2311.02394 (2023). — [arXiv:2311.02394](https://arxiv.org/abs/2311.02394) find
  21. Michael Laskin, Luyu Wang, Junhyuk Oh, Emilio Parisotto, Stephen Spencer, Richie Steigerwald, DJ Strouse, Steven Hansen, Angelos Filos, Ethan Brooks, et al. 2022. In-context reinforcement learning with algorithm distillation. arXiv preprint arXiv:2210.14215 (2022). — [arXiv:2210.14215](https://arxiv.org/abs/2210.14215) find
  22. Juho Lee, Yoonho Lee, Jungtaek Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh. 2019. Set transformer: A framework for attention-based permutation-invariant neural networks. In International conference on machine learning. PMLR, 3744–3753. find
  23. Joel Lehman, Jonathan Gordon, Shawn Jain, Kamal Ndousse, Cathy Yeh, and Kenneth O Stanley. 2023. Evolution through large models. In Handbook of Evolutionary Machine Learning. Springer, 331–366. find
  24. Brian Lester, Rami Al-Rfou, and Noah Constant. 2021. The power of scale for parameter-efficient prompt tuning. arXiv preprint arXiv:2104.08691 (2021).
  25. Yujian Betterest Li and Kai Wu. 2023. SPELL: Semantic Prompt Evolution based on a LLM. arXiv preprint arXiv:2310.01260 (2023). — [arXiv:2310.01260](https://arxiv.org/abs/2310.01260) find
  26. Fei Liu, Xi Lin, Zhenkun Wang, Shunyu Yao, Xialiang Tong, Mingxuan Yuan, and Qingfu Zhang. 2023. Large language model for multi-objective evolutionary optimization. arXiv preprint arXiv:2310.12541 (2023). — [arXiv:2310.12541](https://arxiv.org/abs/2310.12541) find
  27. Fei Liu, Xialiang Tong, Mingxuan Yuan, and Qingfu Zhang. 2023. Algorithm Evolution Using Large Language Model. arXiv preprint arXiv:2311.15249 (2023). — [arXiv:2311.15249](https://arxiv.org/abs/2311.15249) find
  28. Shengcai Liu, Caishun Chen, Xinghua Qu, Ke Tang, and Yew-Soon Ong. 2023. Large Language Models as Evolutionary Optimizers. arXiv preprint arXiv:2310.19046 (2023). — [arXiv:2310.19046](https://arxiv.org/abs/2310.19046) find
  29. Chris Lu, Yannick Schroecker, Albert Gu, Emilio Parisotto, Jakob Foerster, Satinder Singh, and Feryal Behbahani. 2023. Structured state space models for in-context reinforcement learning. arXiv preprint arXiv:2303.03982 (2023). — [arXiv:2303.03982](https://arxiv.org/abs/2303.03982) find
  30. Yao Lu, Jiayi Wang, Sebastian Riedel, and Pontus Stenetorp. 2023. Prompt Optimisation with Random Sampling. arXiv preprint arXiv:2311.09569 (2023). — [arXiv:2311.09569](https://arxiv.org/abs/2311.09569) find
  31. Elliot Meyerson, Mark J Nelson, Herbie Bradley, Arash Moradi, Amy K Hoover, and Joel Lehman. 2023. Language Model Crossover: Variation through Few-Shot Prompting. (2023). find
  32. Suvir Mirchandani, Fei Xia, Pete Florence, Brian Ichter, Danny Driess, Montserrat Gonzalez Arenas, Kanishka Rao, Dorsa Sadigh, and Andy Zeng. 2023. Large Language Models as General Pattern Machines. arXiv preprint arXiv:2307.04721 (2023).
  33. Allen Nie, Ching-An Cheng, Andrey Kolobov, and Adith Swaminathan. 2023. Importance of Directional Feedback for LLM-based Optimizers. In NeurIPS 2023 Foundation Models for Decision Making Workshop. find
  34. OpenAI. 2023. GPT-4 Technical Report. ArXiv abs/2303.08774 (2023). https://arxiv.org/abs/2303.08774 ↗
  35. Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. 2020. Exploring the limits of transfer learning with a unified text-to-text transformer. The Journal of Machine Learning Research 21, 1 (2020), 5485–5551.
  36. Ingo Rechenberg. 1978. Evolutionsstrategien. In Simulationsmethoden in der Medizin und Biologie. Springer, 83–114. find
  37. Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Ilya Sutskever. 2017. Evolution strategies as a scalable alternative to reinforcement learning. arXiv preprint arXiv:1703.03864 (2017). find
  38. Tom Schaul, Tobias Glasmachers, and Jürgen Schmidhuber. 2011. High dimensions and heavy tails for natural evolution strategies. In Proceedings of the 13th annual conference on Genetic and evolutionary computation. 845–852. find
  39. Yujin Tang and David Ha. 2021. The sensory neuron as a transformer: Permutation-invariant neural networks for reinforcement learning. Advances in Neural Information Processing Systems 34 (2021), 22574–22587. find
  40. Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. 2023. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.09288 (2023).
  41. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. Advances in neural information processing systems 30 (2017).
  42. Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. 2022. Self-consistency improves chain of thought reasoning in language models. arXiv preprint arXiv:2203.11171 (2022).
  43. Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. 2022. Chain-of-thought prompting elicits reasoning in large language models. Advances in Neural Information Processing Systems 35 (2022), 24824–24837.
  44. Daan Wierstra, Tom Schaul, Tobias Glasmachers, Yi Sun, Jan Peters, and Jürgen Schmidhuber. 2014. Natural evolution strategies. The Journal of Machine Learning Research 15, 1 (2014). find
  45. Chengrun Yang, Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoc V Le, Denny Zhou, and Xinyun Chen. 2023. Large language models as optimizers. (2023).
  46. Michael Zhang, Nishkrit Desai, Juhan Bae, Jonathan Lorraine, and Jimmy Ba. 2023. Using Large Language Models for Hyperparameter Optimization. In NeurIPS 2023 Foundation Models for Decision Making Workshop. find
  47. Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoc Le, et al. 2022. Least-to-most prompting enables complex reasoning in large language models. arXiv preprint arXiv:2205.10625 (2022). ================ Generation 0 =======…

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/lange-2024-large-language-models-evolution-strategies/