A Neuro-Evolutionary Program Synthesis for Compositional Reasoning = 구성적 추론을 위한 신경-진화적 프로그램 합성

다국어 초록 (Multilingual Abstract)

This thesis pursues the insight that evolutionary learning algorithms, while inter- pretable and powerful, often become trapped in local optima when synthesizing pro- grams. A natural question follows: Can this limitation be mitigated by leveraging the code-editing capabilities of large language models （LLMs）? Because LLMs are trained on sequential modifications and human-like refinements of code, they may provide a novel mechanism for helping evolutionary search escape local optima and they can approximate likely changes that humans would make. To investigate, Genetic Pro- gramming （GP） is first evaluated on the Abstraction and Reasoning Corpus （ARC） and ConceptARC benchmarks, where it synthesizes correct programs for 65 tasks, competitive with symbolic baselines yet prone to premature convergence. In the main experiment, a frozen LLM is introduced as a repair operator: rather than generating entire solutions, it modifies promising GP candidates using fitness feedback and train- ing task input–output examples. This hybrid process improves results, with an average fitness gain of ≈ 6.5% and broader coverage of reasoning concepts such as counting, movement, and shape recognition. This thesis points to two promising directions for future research. First, although dataset expansion was not investigated here, the pro- grams evolved throughout the search process naturally yield paired artifacts （program, input, and output）. Such artifacts could be used to construct extended training sets, which may in turn support fine-tuning of future code editing models. Second, future work could explore seeding LLM-edited programs back into the evolutionary process, thus relaxing the dependence on human-defined primitives and moving toward more open-ended forms of neuro-evolution. Together, these directions highlight how the in- terplay between GP and LLMs can extend beyond mitigating local optima to enabling advances in program synthesis and open-ended discovery. ©2026 Woletemaryam Liyew Abitew ALL RIGHTS RESERVED

목차 (Table of Contents)

• Abstract （English） i
• List of Contents ii
• List of Tables iv
• List of Figures v
• 1 Introduction 1
• 1.1 Introduction 1
• 1.2 Research Questions 2
• 2 Background 3
• 2.1 Genetic Programming 3
• 2.2 Large Language Model Code repair 4
• 2.3 Open-Endedness 5
• 2.4 The ARC benchmark and approaches 5
• 3 Method 8
• 3.1 Motivation 8
• 3.2 Program Synthesis using Evolutionary Learning 8
• 3.3 Evolve and Refine Programs 15
• 3.4 Case Studies and Analysis 17
• 4 Experiments 25
• 4.1 Task Setup and Evaluation Metrics 25
• 4.2 Experiment 1: Program Synthesis With Evolutionary Learning 27
• 4.3 Analysis of Evolutionary Stagnation 29
• 4.4 Experiment 2: Evolve and Refine 31
• 4.5 Computational Time and Resource Usage 34
• 4.6 Comprehensive Fitness Evaluation 37
• – ii –
• 5 Conclusion 40
• 5.1 Discussion 40
• 5.2 Conclusion 41
• References 43
• Acknowledgements 48
• – iii –