2022

Toward Trustworthy Neural Program Synthesis

Key, Darren, Li, Wen-Ding, Ellis, Kevin

Understand

We develop an approach to estimate the probability that a program sampled from a large language model is correct.

Given a natural language description of a programming problem, our method samples both candidate programs as well as candidate predicates specifying how the program should behave.
This allows learning a model that forms a well-calibrated probabilistic prediction of program correctness.
Our system also infers which predicates are useful to explain the behavior of the generated code, and humans preferred these in a human study over raw language model outputs.

Built on

Synthesis: Dreams → Programs
Manna, Z.; and Waldinger, R. 1979 · 1979
Earlier work this paper cites.
Property-based testing: a new approach to testing for assurance
Fink, G.; and Bishop, M. 1997 · 1997
Earlier work this paper cites.
Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods
Platt, J.; et al. 1999 · 1999
Earlier work this paper cites.
Language Models are Few-Shot Learners
Original
Brown, T. B.; Mann, B.; Ryder, N.; Subbiah, M.; Kaplan, J.; Dhariwal, P.; Neelakantan, A.; Shyam, P.; Sastry, G.; Askell, A.; Agarwal, S.; Herbert-Voss, A.; Krueger, G.; Henighan, T.; Child, R.; Ramesh, A.; Ziegler, D. M.; Wu, J.; Winter, C.; Hesse, C.; Chen, M.; Sigler, E.; Litwin, M.; Gray, S.; Chess, B.; Clark, J.; Berner, C.; McCandlish, S.; Radford, A.; Sutskever, I.; and Amodei, D. 2020 · 2005
Earlier work this paper cites.
A survey of automated techniques for formal software verification
D’silva, V.; Kroening, D.; and Weissenbacher, G. 2008 · 2008
Earlier work this paper cites.
Syntax-guided synthesis
Alur, R.; Bodik, R.; Juniwal, G.; Martin, M. M.; Raghothaman, M.; Seshia, S. A.; Singh, R.; Solar-Lezama, A.; Torlak, E.; and Udupa, A. 2013 · 2013
Earlier work this paper cites.
TRANSIT: Specifying Protocols with Concolic Snippets
Udupa, A.; Raghavan, A.; Deshmukh, J. V.; Mador-Haim, S.; Martin, M. M.; and Alur, R. 2013 · 2013
Earlier work this paper cites.
Program synthesis
Gulwani, S.; Polozov, O.; Singh, R.; et al. 2017 · 2017
Earlier work this paper cites.
Attention is All you Need
Vaswani, A.; Shazeer, N.; Parmar, N.; Uszkoreit, J.; Jones, L.; Gomez, A. N.; Kaiser, L. u.; and Polosukhin, I. 2017 · 2017
Earlier work this paper cites.
A survey of symbolic execution techniques
Baldoni, R.; Coppa, E.; D’elia, D. C.; Demetrescu, C.; and Finocchi, I. 2018 · 2018
Earlier work this paper cites.
Programming with a Read-Eval-Synth Loop
Peleg, H.; Gabay, R.; Itzhaky, S.; and Yahav, E. 2020 · 2020
Earlier work this paper cites.

Similar

Program synthesis with pragmatic communication
Pu, Y.; Ellis, K.; Kryven, M.; Tenenbaum, J.; and Solar-Lezama, A. 2020 · 2020
Cited alongside, same era.
Communicating Natural Programs to Humans and Machines
Original
Acquaviva, S.; Pu, Y.; Kryven, M.; Wong, C.; Ecanow, G. E.; Nye, M. I.; Sechopoulos, T.; Tessler, M. H.; and Tenenbaum, J. B. 2021 · 2021
Cited alongside, same era.
Program synthesis with large language models
Original
Austin, J.; Odena, A.; Nye, M.; Bosma, M.; Michalewski, H.; Dohan, D.; Jiang, E.; Cai, C.; Terry, M.; Le, Q.; et al. 2021 · 2021
Cited alongside, same era.
Evaluating Large Language Models Trained on Code
Chen, M.; Tworek, J.; Jun, H.; Yuan, Q.; Pinto, H. P. d. O.; Kaplan, J.; Edwards, H.; Burda, Y.; Joseph, N.; Brockman, G.; Ray, A.; Puri, R.; Krueger, G.; Petrov, M.; Khlaaf, H.; Sastry, G.; Mishkin, P.; Chan, B.; Gray, S.; Ryder, N.; Pavlov, M.; Power, A.; Kaiser, L.; Bavarian, M.; Winter, C.; Tillet, P.; Such, F. P.; Cummings, D.; Plappert, M.; Chantzis, F.; Barnes, E.; Herbert-Voss, A.; Guss, W. H.; Nichol, A.; Paino, A.; Tezak, N.; Tang, J.; Babuschkin, I.; Balaji, S.; Jain, S.; Saunders, W.; Hesse, C.; Carr, A. N.; Leike, J.; Achiam, J.; Misra, V.; Morikawa, E.; Radford, A.; Knight, M.; Brundage, M.; Murati, M.; Mayer, K.; Welinder, P.; McGrew, B.; Amodei, D.; McCandlish, S.; Sutskever, I.; and Zaremba, W. 2021 · 2021
Cited alongside, same era.
Show Your Work: Scratchpads for Intermediate Computation with Language Models
Original
Nye, M. I.; Andreassen, A. J.; Gur-Ari, G.; Michalewski, H.; Austin, J.; Bieber, D.; Dohan, D.; Lewkowycz, A.; Bosma, M.; Luan, D.; Sutton, C.; and Odena, A. 2021 · 2021
Cited alongside, same era.
Program of Thoughts Prompting: Disentangling Computation from Reasoning for Numerical Reasoning Tasks
Original
Chen, W.; Ma, X.; Wang, X.; and Cohen, W. W. 2022 · 2022
Cited alongside, same era.
Fault-Aware Neural Code Rankers
Original
Inala, J. P.; Wang, C.; Yang, M.; Codas, A.; Encarnación, M.; Lahiri, S. K.; Musuvathi, M.; and Gao, J. 2022 · 2022
Cited alongside, same era.
Language Models (Mostly) Know What They Know
Original
Kadavath, S.; Conerly, T.; Askell, A.; Henighan, T.; Drain, D.; Perez, E.; Schiefer, N.; Dodds, Z. H.; DasSarma, N.; Tran-Johnson, E.; et al. 2022 · 2022
Cited alongside, same era.
Solving quantitative reasoning problems with language models
Original
Lewkowycz, A.; Andreassen, A.; Dohan, D.; Dyer, E.; Michalewski, H.; Ramasesh, V.; Slone, A.; Anil, C.; Schlag, I.; Gutman-Solo, T.; et al. 2022 · 2022
Cited alongside, same era.
Competition-level code generation with alphacode
Original
Li, Y.; Choi, D.; Chung, J.; Kushman, N.; Schrittwieser, J.; Leblond, R.; Eccles, T.; Keeling, J.; Gimeno, F.; Lago, A. D.; et al. 2022 · 2022
Cited alongside, same era.

Then

Teaching Models to Express Their Uncertainty in Words
Original
Lin, S.; Hilton, J.; and Evans, O. 2022 · 2022
Closest in time.
Natural Language to Code Translation with Execution
Original
Shi, F.; Fried, D.; Ghazvininejad, M.; Zettlemoyer, L.; and Wang, S. I. 2022 · 2022
Closest in time.
Prompting gpt-3 to be reliable
Original
Si, C.; Gan, Z.; Yang, Z.; Wang, S.; Wang, J.; Boyd-Graber, J.; and Wang, L. 2022 · 2022
Closest in time.
LaMDA: Language Models for Dialog Applications
Original
Thoppilan, R.; Freitas, D. D.; Hall, J.; Shazeer, N.; Kulshreshtha, A.; Cheng, H.; Jin, A.; Bos, T.; Baker, L.; Du, Y.; Li, Y.; Lee, H.; Zheng, H. S.; Ghafouri, A.; Menegali, M.; Huang, Y.; Krikun, M.; Lepikhin, D.; Qin, J.; Chen, D.; Xu, Y.; Chen, Z.; Roberts, A.; Bosma, M.; Zhou, Y.; Chang, C.; Krivokon, I.; Rusch, W.; Pickett, M.; Meier-Hellstern, K. S.; Morris, M. R.; Doshi, T.; Santos, R. D.; Duke, T.; Soraker, J.; Zevenbergen, B.; Prabhakaran, V.; Diaz, M.; Hutchinson, B.; Olson, K.; Molina, A.; Hoffman-John, E.; Lee, J.; Aroyo, L.; Rajakumar, R.; Butryna, A.; Lamm, M.; Kuzmina, V.; Fenton, J.; Cohen, A.; Bernstein, R.; Kurzweil, R.; Aguera-Arcas, B.; Cui, C.; Croak, M.; Chi, E. H.; and Le, Q. 2022 · 2022
Closest in time.
Coder Reviewer Reranking for Code Generation
Original
Zhang, T.; Yu, T.; Hashimoto, T. B.; Lewis, M.; tau Yih, W.; Fried, D.; and Wang, S. I. 2022 · 2022
Closest in time.
CodeT: Code Generation with Generated Tests
Chen, B.; Zhang, F.; Nguyen, A.; Zan, D.; Lin, Z.; Lou, J.-G.; and Chen, W. 2023 · 2023
Closest in time.
FrugalGPT: How to Use Large Language Models While Reducing Cost and Improving Performance
Original
Chen, L.; Zaharia, M.; and Zou, J. 2023 · 2023
Closest in time.
PAL: Program-aided Language Models
Original
Gao, L.; Madaan, A.; Zhou, S.; Alon, U.; Liu, P.; Yang, Y.; Callan, J.; and Neubig, G. 2023 · 2023
Closest in time.
Semantic Uncertainty: Linguistic Invariances for Uncertainty Estimation in Natural Language Generation
Kuhn, L.; Gal, Y.; and Farquhar, S. 2023 · 2023
Closest in time.
LEVER: Learning to Verify Language-to-Code Generation with Execution
Original
Ni, A.; Iyer, S.; Radev, D.; Stoyanov, V.; Yih, W.-t.; Wang, S. I.; and Lin, X. V. 2023 · 2023
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…