REVIEW 4 major objections 4 minor 39 references
Learning Fitness Functions for Machine Programming
T0 review · 4 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read NetSyn learns the fitness function for genetic program synthesis from data, and finds more correct programs with fewer candidate generations than prior learned synthesizers.
desk verdict NetSyn has a genuinely interesting way to learn a GA fitness function for program synthesis, but its long-program results rest on an unaddressed and likely load-bearing representational gap. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central mechanism is the neural-network fitness function (NN-FF). The network receives an input-output example, a candidate program encoded as a sequence of DSL function identifiers, and the execution trace of that candidate on the input; LSTM encoders combine these into a hidden vector, and fully connected layers output a predicted fitness score. The paper trains it to match one of three oracle metrics: common functions (CF), longest common subsequence (LCS), or the DeepCoder-style function-probability map (FP). The trained network is then used in a genetic algorithm to rank candidate programs, and a sliding-window stagnation detector triggers a local neighborhood search that enumerates all single-function replacements of the top-scoring genes, providing a fast convergence path from approximately correct programs.
What would settle it
Train the same CF and LCS fitness networks on length-5 programs, then run NetSyn on a fresh set of length-7 and length-10 target programs while logging, for each generation, the correlation between the network's predicted fitness rank and the true oracle fitness rank of the candidate programs. If the rank correlation does not exceed random for candidates with true oracle score between 1 and 4, the claimed generalization of the fitness function is contradicted.
Extended reading notes
Core claim
The paper claims that one can train a neural network on a large corpus of randomly generated programs, their input-output examples, and their execution traces to predict an oracle fitness value (such as the number of common functions or the longest common subsequence between a candidate and the target), and then use that network as the fitness function of a genetic algorithm for inductive program synthesis. Under a search-space budget, NetSyn synthesizes more target programs than the compared learned synthesis systems and uses fewer candidate program generations to do so, with the gap largest for length-5 programs and still present at length 10, where NetSyn synthesizes about 65-66% of programs while the baselines synthesize below 60%.
Load-bearing premise
A neural network trained only on programs of length 5, with fitness classes from 0 to 5, assigns meaningful fitness rankings to candidate programs of length 7 and 10, so that evolution toward a longer target program makes forward progress. If that generalization fails, the reported synthesis rates for longer programs would not be explained.
Editorial extensions
If this is right
- If NetSyn's fitness-network approach is correct, then the hardest part of applying genetic algorithms to program synthesis, the hand-crafted fitness heuristic, can be replaced by a data-driven learned model that does not require knowledge of the target program.
- The reported results suggest that genetic algorithms with learned fitness functions can outperform popular neural program-synthesis systems on list-processing DSL benchmarks when measured by candidate search space, motivating a re-examination of the role of evolutionary search in machine programming.
- Because the fitness network is trained on programs of length 5 but used to synthesize programs of length 7 and 10, the results imply that the learned fitness signal generalizes beyond its training length, at least within this DSL.
- The introduction of a search-space metric (number of candidate programs generated), alongside wall-clock time, gives the community a way to compare synthesis algorithms on algorithmic efficiency rather than implementation efficiency.
- The success of the neighborhood-search heuristic suggests that a small, local search around top-ranked genes can rescue genetic-algorithm convergence when the learned fitness function is good but not perfect.
Reading between the lines
- The same learned-fitness idea could likely be transferred to other genetic-algorithm domains where an oracle distance is computable during training, such as symbolic regression or program repair, by generating training pairs and measuring a structural similarity metric.
- The CF and LCS fitness networks, trained as multiclass classifiers with output classes 0..5, would be expected to saturate for programs much longer than length 10, since those classes cannot express the full range of similarity to a longer target; a scale of the approach would need ordinal or regression targets with a bounded rank.
- A reader who wants to test the generality could check whether the fitness network transfers to DSLs with different function sets or to programs with constants and control flow, where the trace information that carries much of the signal would be richer but also harder to embed.
- The paper's stagnation-triggered neighborhood search suggests a generic recipe: use a learned ranker to identify a small set of promising candidates, then exhaustively search a one-edit neighborhood, which may be cheaper and more targeted than relying on mutation alone.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces NetSyn, a genetic-algorithm-based framework for inductive program synthesis over a list-processing DSL adapted from DeepCoder's. The central contribution is replacing a hand-crafted fitness function with a neural network fitness function (NN-FF) trained on 4.2 million length-5 programs to predict three oracle closeness metrics: common functions (CF), longest common subsequence (LCS), and function probability (FP). The framework augments the genetic search with a local neighborhood search that exhaustively replaces single functions in top-scoring genes. NetSyn is evaluated on target programs of lengths 5, 7, and 10 against DeepCoder, PCCoder, RobustFill, PushGP, an edit-distance fitness, and an oracle fitness, using a proposed search-space metric. The paper's headline claim is that NetSyn 'finds more correct programs with fewer candidate program generations' than the compared program synthesis methods.
Significance. If the empirical claims hold, the paper makes a useful contribution by demonstrating that a neural network can serve as a learned fitness function in a genetic program synthesizer, and by proposing a search-space metric that separates algorithmic efficiency from implementation speed. The ablation study and the reported negative results (regression, pairwise ordering, bigram, and two-tier models) are informative for future work. However, the central claim is currently under-supported for program lengths 7 and 10: the NN-FF for CF and LCS is trained only as a 6-class classifier on length-5 programs, and the validation evidence (confusion matrices, ablations) is entirely length-5. Because the headline result explicitly includes longer programs, this missing generalization evidence is load-bearing.
major comments (4)
- [Section 4.2.1, Section 5] The CF and LCS neural network fitness functions are trained as multiclass classifiers with classes 0-5 on 4.2 million length-5 programs (Section 5), but Figures 4(b)-(c) and Tables 3-4 report synthesis for target programs of length 7 and 10. For these targets the true f_CF and f_LCS values range up to 7 or 10, yet the networks' output layers cannot represent values above 5, and the paper does not describe any retraining, output-head adaptation, or monotonic transform. The confusion matrices in Figure 7 and all ablations in Table 2 are for length-5 programs only, so no evidence is provided that the models rank longer candidates sensibly. Because the central claim explicitly includes lengths 7 and 10, this missing length-generalization support is load-bearing.
- [Section 5.2] The characterization of NetSyn is restricted to length-5 programs: Table 2 gives ablations for length 5, Figure 5 shows synthesis rates for length 5, and Figure 7 shows validation confusion matrices on length-5 data. The statement in Section 5.2 that 'our general observations to be true for longer length programs also' is not accompanied by any data or model analysis. The authors should provide either per-length ablations, NN-FF accuracy metrics for lengths 7 and 10, or a clear argument why length-5 behavior suffices to support the longer-length claims.
- [Section 4.2.2, Section 5.1] The neighborhood search (NS) can find correct programs by exhaustive single-function replacement over the top-N population without any help from the learned fitness, and the paper does not decompose the reported success rates for lengths 7 and 10 into successes due to the NN-FF versus those due to NS. Table 2 shows that on length-5 programs NS alone adds only 2 of 94 successes, but for longer programs, where the NN-FF's output is capped at 5, NS may dominate. The authors should report, for each program length, the fraction of targets found directly by the GA, by NS, or jointly, so that the contribution of the learned fitness is identifiable.
- [Section 5.1, Tables 3-4] The search-space metric is central to the claim of 'fewer candidate program generations,' but the paper does not specify how candidate programs are counted for each baseline. DeepCoder, PCCoder, and RobustFill are not population-based GA methods, so it is unclear what a 'candidate program generation' means for them and whether the comparison is apples-to-apples. The authors should define the counting procedure for each system, including whether NetSyn's neighborhood-search evaluations are included in its search-space count, and justify that the metric treats all methods equivalently.
minor comments (4)
- [Figure 4] The figure is dense and the text does not describe how to distinguish the plotted curves for the different methods; a legend or a tabular version of the same data would improve readability.
- [Section 4.2.1] The notation for fitness functions alternates between fCF/fLCS/fFP and f_CF/f_LCS/f_FP; please unify the notation throughout for consistency.
- [Tables 3-4] The column labeled 'PERCENTAGE' appears to denote each method's overall synthesis rate, but this is not explained in the caption or the text; please add a clarifying note.
- [Section 5.1] The sentence 'up to 30% of the programs can be synthesized by searching less than 2% of the maximum search space' is approximate and would be more precise if tied to a specific figure or table entry.
Circularity Check
No circularity: the learned NN-FF is a standard supervised approximation of an independently defined oracle fitness, and the central synthesis claim is tested against external baselines.
full rationale
The paper's derivation chain is not circular. The NN-FF is trained on a large corpus of randomly generated target/candidate program pairs whose labels are independently defined oracle fitness values (CF, LCS, or FP) computed directly from the two programs in Section 4.2.1. At test time the same network scores candidate programs for held-out targets, which is a standard supervised learning setup; no test-target output or final evaluation quantity is used to fit the network. The fitness metrics are defined externally: set intersection for CF, longest common subsequence for LCS, and DeepCoder's function-probability map for FP, and they do not depend on NetSyn's parameters. The central comparison against DeepCoder, PCCoder, RobustFill, and PushGP in Section 5.1 uses counts of candidate programs searched and synthesis rates, not quantities constructed from the model outputs, so the reported superiority claim is an empirical comparison against independent systems rather than a restatement of the training objective. The self-citations (Gottschlich et al. 2018; Becker and Gottschlich 2017) appear only in related-work context and are not load-bearing for the derivation. The concern that the CF/LCS classifiers have output classes 0..5 while evaluation includes length-7 and length-10 programs is a legitimate generalization or correctness risk, but it is not circularity: the model's restricted output space is not defined in terms of the test results, and no equation or fitted value is reused to force the reported synthesis outcome.
Assumptions & free parameters
free parameters (2)
- GA hyperparameters =
pool 100, reserve 5, max generations 30000, crossover 40%, mutation 30%
- NS sliding window w =
not specified
assumptions (4)
- domain assumption All programs in the DSL are valid by construction and the search space is the set of all function sequences.
- domain assumption The oracle fitness functions CF, LCS, and FP are meaningful proxies for program correctness.
- domain assumption Randomly generated training programs from the DSL represent the distribution of target programs at test time.
- domain assumption The baseline systems (DeepCoder, PCCoder, RobustFill) are evaluated under conditions that allow fair comparison.
Cite this review
Pith. "Pith review of Learning Fitness Functions for Machine Programming." pith.science (2026). https://pith.science/paper/Q3W4XWEC
@misc{pith2026190808783,
author = {Pith},
title = {Pith review of: Learning Fitness Functions for Machine Programming},
year = {2026},
howpublished = {\url{https://pith.science/paper/Q3W4XWEC}},
note = {Machine review of arXiv:1908.08783}
}
read the original abstract
The problem of automatic software generation is known as Machine Programming. In this work, we propose a framework based on genetic algorithms to solve this problem. Although genetic algorithms have been used successfully for many problems, one criticism is that hand-crafting its fitness function, the test that aims to effectively guide its evolution, can be notably challenging. Our framework presents a novel approach to learn the fitness function using neural networks to predict values of ideal fitness functions. We also augment the evolutionary process with a minimally intrusive search heuristic. This heuristic improves the framework's ability to discover correct programs from ones that are approximately correct and does so with negligible computational overhead. We compare our approach with several state-of-the-art program synthesis methods and demonstrate that it finds more correct programs with fewer candidate program generations.
Figures
Figures from the paper (4 more)
Reference graph
Works this paper leans on
-
[1]
write newline
" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...
-
[2]
URL https://images.nvidia.com/content/pdf/tesla/whitepaper/pascal-architecture-whitepaper.pdf
NVIDIA Tesla P100 White Paper . URL https://images.nvidia.com/content/pdf/tesla/whitepaper/pascal-architecture-whitepaper.pdf
-
[3]
TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems , 2015
Abadi, M., Agarwal, A., Barham, P., Brevdo, E., Chen, Z., Citro, C., Corrado, G., Davis, A., Dean, J., Devin, M., Ghemawat, S., Goodfellow, I., Harp, A., Irving, G., Isard, M., Jia, Y., Jozefowicz, R., Kaiser, L., Kudlur, M., Levenberg, J., Mané, D., Monga, R., Moore, S., Murray, D., Olah, C., Schuster, M., Shlens, J., Steiner, B., Sutskever, I., Talwar, ...
work page 2015
-
[4]
Alur, R., Bod \' k, R., Dallal, E., Fisman, D., Garg, P., Juniwal, G., Kress - Gazit, H., Madhusudan, P., Martin, M. M. K., Raghothaman, M., Saha, S., Seshia, S. A., Singh, R., Solar - Lezama, A., Torlak, E., and Udupa, A. Syntax-Guided Synthesis . In Irlbeck, M., Peled, D. A., and Pretschner, A. (eds.), Dependable Software Systems Engineering, volume 40 ...
2015
-
[5]
L., Brockschmidt, M., Nowozin, S., and Tarlow, D
Balog, M., Gaunt, A. L., Brockschmidt, M., Nowozin, S., and Tarlow, D. DeepCoder: Learning to Write Programs . In International Conference on Learning Representations, April 2017
work page 2017
-
[6]
AI Programmer: Autonomously Creating Software Programs Using Genetic Algorithms
Becker, K. and Gottschlich, J. AI Programmer: Autonomously Creating Software Programs Using Genetic Algorithms . CoRR, abs/1709.05703, 2017. URL http://arxiv.org/abs/1709.05703
work page Pith review arXiv 2017
-
[7]
Bod \'i k, R. and Jobstmann, B. Algorithmic Program Synthesis: Introduction . International Journal on Software Tools for Technology Transfer, 15: 0 397--411, 2013
work page 2013
-
[8]
J., Devlin, J., Singh, R., and Kohli, P
Bunel, R., Hausknecht, M. J., Devlin, J., Singh, R., and Kohli, P. Leveraging Grammar and Reinforcement Learning for Neural Program Synthesis . In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings . OpenReview.net, 2018. URL https://openreview.net/forum?id=H1Xw62kRZ
work page 2018
Show all 39 references
-
[9]
Making Neural Programming Architectures Generalize via Recursion
Cai, J., Shin, R., and Song, D. Making Neural Programming Architectures Generalize via Recursion . In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings . OpenReview.net, 2017. URL https://openre...
2017
-
[10]
Using Program Synthesis for Social Recommendations
Cheung, A., Solar-Lezama, A., and Madden, S. Using Program Synthesis for Social Recommendations . ArXiv, abs/1208.2925, 2012
2012 arXiv
-
[11]
K., Evans, W., Muth, R., and De Sutter, B
Debray, S. K., Evans, W., Muth, R., and De Sutter, B. Compiler Techniques for Code Compaction . ACM Trans. Program. Lang. Syst., 22 0 (2): 0 378--415, March 2000. ISSN 0164-0925. doi:10.1145/349214.349233. URL http://doi.acm.org/10.1145/349214.349233
-
[12]
ImageNet: A Large-Scale Hierarchical Image Database
Deng, J., Dong, W., Socher, R., Li, L.-J., Li, K., and Fei-Fei, L. ImageNet: A Large-Scale Hierarchical Image Database . In CVPR09, 2009
2009
-
[13]
LINQ to SQL: .NET Language-Integrated Query for Relational Data , 2007
Dinesh, K., Luca, B., Matt, W., Anders, H., and Kit, G. LINQ to SQL: .NET Language-Integrated Query for Relational Data , 2007. URL https://docs.microsoft.com/en-us/previous-versions/dotnet/articles/bb425822(v=msdn.10)
2007
-
[14]
Goldberg, D. E. Genetic Algorithms in Search, Optimization and Machine Learning . Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1st edition, 1989. ISBN 0201157675
1989
-
[15]
B., and Mattson, T
Gottschlich, J., Solar-Lezama, A., Tatbul, N., Carbin, M., Rinard, M., Barzilay, R., Amarasinghe, S., Tenenbaum, J. B., and Mattson, T. The Three Pillars of Machine Programming . In Proceedings of the 2nd ACM SIGPLAN International Workshop on Machine Learning and Programming L...
2018
-
[16]
R., and Singh, R
Gulwani, S., Harris, W. R., and Singh, R. Spreadsheet Data Manipulation Using Examples . Commun. ACM, 55 0 (8): 0 97--105, August 2012. ISSN 0001-0782. doi:10.1145/2240236.2240260. URL http://doi.acm.org/10.1145/2240236.2240260
2012
-
[17]
Stratified Synthesis: Automatically Learning the x86-64 Instruction Set
Heule, S., Schkufza, E., Sharma, R., and Aiken, A. Stratified Synthesis: Automatically Learning the x86-64 Instruction Set . SIGPLAN Not., 51 0 (6): 0 237--250, June 2016. ISSN 0362-1340. doi:10.1145/2980983.2908121. URL http://doi.acm.org/10.1145/2980983.2908121
2016
-
[18]
Genetic algorithm with artificial neural networks as its fitness function to design rectangular microstrip antenna on thick substrate
Khuntia, B., Pattnaik, S., Panda, D., Neog, D., Devi, S., and Dutta, M. Genetic algorithm with artificial neural networks as its fitness function to design rectangular microstrip antenna on thick substrate . Microwave and Optical Technology Letters, 44: 0 144 -- 146, 01 2005. ...
2005 doi
-
[19]
Korns, M. F. Accuracy in Symbolic Regression , pp.\ 129--151. Springer New York, New York, NY, 2011. ISBN 978-1-4614-1770-5. doi:10.1007/978-1-4614-1770-5_8. URL https://doi.org/10.1007/978-1-4614-1770-5_8
2011 doi
-
[20]
Learning Multiple Layers of Features from Tiny Images
Krizhevsky, A. Learning Multiple Layers of Features from Tiny Images . Technical report, 2009
2009
-
[21]
Evolv Delivers Autonomous Optimization Across Web & Mobile
Labs, S. Evolv Delivers Autonomous Optimization Across Web & Mobile . https://www.evolv.ai/
-
[22]
and Wang, B
Li, C. and Wang, B. Principal Components Analysis , 2014. URL http://www.ccs.neu.edu/home/vip/teach/MLcourse/5_features_dimensions/lecture_notes/PCA/PCA.pdf
2014
-
[23]
Hierarchical Representations for Efficient Architecture Search
Liu, H., Simonyan, K., Vinyals, O., Fernando, C., and Kavukcuoglu, K. Hierarchical Representations for Efficient Architecture Search . CoRR, abs/1711.00436, 2017. URL http://arxiv.org/abs/1711.00436
2017 arXiv
-
[24]
D., and Torlak, E
Loncaric, C., Ernst, M. D., and Torlak, E. Generalized Data Structure Synthesis . In Proceedings of the 40th International Conference on Software Engineering, ICSE 2018, pp.\ 958--968, New York, NY, USA, 2018. ACM. ISBN 978-1-4503-5638-1. doi:10.1145/3180155.3180211. URL http:...
2018
-
[25]
and Waldinger, R
Manna, Z. and Waldinger, R. Knowledge and Reasoning in Program Synthesis . Artificial Intelligence, 6 0 (2): 0 175 -- 208, 1975. ISSN 0004-3702
1975
-
[26]
Matos Dias, J., Rocha, H., Ferreira, B., and Lopes, M. d. C. A genetic algorithm with neural network fitness function evaluation for IMRT beam angle optimization . Central European Journal of Operations Research, 22, 09 2014. doi:10.1007/s10100-013-0289-4
2014 doi
-
[27]
Murphy, K. P. Machine Learning: A Probabilistic Perspective . The MIT Press, 2012. ISBN 0262018020, 9780262018029
2012
-
[28]
G., Bailis, P., Bird, S., Carlini, N., Catanzaro, B., Chung, E., Dally, B., Dean, J., Dhillon, I
Ratner, A., Alistarh, D., Alonso, G., Andersen, D. G., Bailis, P., Bird, S., Carlini, N., Catanzaro, B., Chung, E., Dally, B., Dean, J., Dhillon, I. S., Dimakis, A. G., Dubey, P., Elkan, C., Fursin, G., Ganger, G. R., Getoor, L., Gibbons, P. B., Gibson, G. A., Gonzalez, J. E.,...
1904 arXiv
-
[29]
Code Completion with Statistical Language Models
Raychev, V., Vechev, M., and Yahav, E. Code Completion with Statistical Language Models . In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '14, pp.\ 419--428, New York, NY, USA, 2014. ACM. ISBN 978-1-4503-2784-8. doi:10....
2014
-
[30]
Real, E., Aggarwal, A., Huang, Y., and Le, Q. V. Regularized Evolution for Image Classifier Architecture Search . CoRR, abs/1802.01548, 2018. URL http://arxiv.org/abs/1802.01548
2018 arXiv
-
[31]
Real, E., Aggarwal, A., Huang, Y., and Le, Q. V. Regularized Evolution for Image Classifier Architecture Search . In Thirty-Third AAAI Conference on Artificial Intelligence, February 2019
2019
-
[32]
Reed, S. E. and de Freitas, N. Neural Programmer-Interpreters . In Bengio, Y. and LeCun, Y. (eds.), 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings , 2016. URL http://arxiv.org/abs/1511.06279
2016 arXiv
-
[33]
Evolution Strategies as a Scalable Alternative to Reinforcement Learning
Salimans, T., Ho, J., Chen, X., Sidor, S., and Sutskever, I. Evolution Strategies as a Scalable Alternative to Reinforcement Learning . CoRR, abs/1703.03864, 2017. URL https://arxiv.org/abs/1703.03864
2017 arXiv
-
[34]
M., and El-Maleh, A
Shawahna, A., Sait, S. M., and El-Maleh, A. FPGA-Based Accelerators of Deep Learning Networks for Learning and Classification: A Review . IEEE Access, 7: 0 7823--7859, 2019. ISSN 2169-3536. doi:10.1109/ACCESS.2018.2890150
2019
-
[35]
Combinatorial Sketching for Finite Programs
Solar-Lezama, A., Tancau, L., Bodik, R., Seshia, S., and Saraswat, V. Combinatorial Sketching for Finite Programs . SIGOPS Oper. Syst. Rev., 40 0 (5): 0 404--415, October 2006. ISSN 0163-5980. doi:10.1145/1168917.1168907. URL http://doi.acm.org/10.1145/1168917.1168907
2006
-
[36]
P., Madhavan, V., Conti, E., Lehman, J., Stanley, K
Such, F. P., Madhavan, V., Conti, E., Lehman, J., Stanley, K. O., and Clune, J. Deep Neuroevolution: Genetic Algorithms Are a Competitive Alternative for Training Deep Neural Networks for Reinforcement Learning . CoRR, abs/1712.06567, 2017. URL http://arxiv.org/abs/1712.06567
2017 arXiv
-
[37]
Global Optimization Algorithms-Theory and Application
Thomas. Global Optimization Algorithms-Theory and Application . 2009. http://www.it-weise.de/projects/book.pdf
2009
-
[38]
and Wolf, L
Zohar, A. and Wolf, L. PCCoder . https://github.com/amitz25/PCCoder, 2018 a
2018
-
[39]
and Wolf, L
Zohar, A. and Wolf, L. Automatic Program Synthesis of Long Programs with a Learned Garbage Collector . CoRR, abs/1809.04682, 2018 b . URL http://arxiv.org/abs/1809.04682
2018 arXiv
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.