IP Library › Granted Patent US 12,282,411
Granted Patent B2
US 12,282,411 · App. 18/159,712 · Granted Apr 22, 2025

Program improvement using large language models

Inventors: Jialu Zhang (New Haven, CT); José Pablo Cambronero Sánchez (New Haven, CT); Gustavo Araujo Soares (Seattle, WA); Vu Minh Le (Redmond, WA); Sumit Gulwani (Sammamish, WA); Gust Ben Anneloes Verbruggen (Keerbergen, BE)
Assignee: Microsoft Technology Licensing, LLC
G06F11/3608G06F8/42G06F8/71
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,282,411
App. No.
18/159,712
Filed
Jan 26, 2023
Granted
Apr 22, 2025
Kind
B2
Art Unit
2191
USPC
717/122
Abstract

Some embodiments generate prompts and submit them in queries to a language model trained on code to perform automated program repair. Some embodiments fix syntactic mistakes and semantic mistakes by combining multimodal prompts, iterative querying, test-case-based selection of few-shots, and program chunking. In some cases, edit distance is minimized between an initial flawed program and the automatically created improved version of that program. The initial flawed program is obtained from a programming student, or from a source code generator.

Claims (48)

1. A source code improvement process performed by a computing system to improve a first version of a source code, the process comprising:

a phased iterative process performed in the computing system, the phased iterative process comprising:

repairing any syntax errors in the first version of the source code or confirming that the first version of the source code is free of syntax errors, or both, thereby yielding a syntactically correct version of the source code;

generating a multimodal prompt which includes at least two of the following: a portion of the syntactically correct version of the source code, a natural language description of a task to be accomplished by any improved version of the source code, or a test case to be satisfied by the improved version of the source code;

submitting the multimodal prompt to a machine learning model trained on source codes;

obtaining candidate versions of the improved version of the source code from the machine learning model trained on source codes;

selecting a valid candidate version of the improved version of the source code from among the candidate versions; and

outputting the selected valid candidate version;

whereby the phased iterative process results in an overall higher fix rate than an approach which attempts to fix syntax and semantics in a single combined stage.

2. The process of claim 1 , wherein the multimodal prompt includes: the portion of the syntactically correct version of the source code, and the natural language description of the task to be accomplished by any improved version of the source code.

3. The process of claim 1 , wherein the multimodal prompt includes: the portion of the syntactically correct version of the source code, and the test case to be satisfied by the improved version of the source code.

4. The process of claim 1 , wherein the multimodal prompt includes: the portion of the syntactically correct version of the source code, the natural language description of the task to be accomplished by any improved version of the source code, and the test case to be satisfied by the improved version of the source code.

5. The process of claim 1 , wherein selecting the valid candidate version of the improved version of the source code from among the candidate versions comprises minimizing a distance between the candidate versions and the first version of the source code.

6. The process of claim 1 , wherein the process comprises repairing a syntax error in the first version of the source code, and the repairing comprises: generating a syntactic prompt which includes the syntax error, submitting the syntactic prompt to the machine learning model trained on source codes, and getting a syntax error correction from the machine learning model trained on source codes.

7. The process of claim 6 , wherein generating the syntactic prompt comprises extracting a code chunk of the first version of the source code, and the extracting is based on a location of the syntax error and also based on at least one of the following: a programming language reserved word location in the first version of the source code, or a formatting indentation in the first version of the source code.

8. The process of claim 1 , further comprising utilizing alternate versions of the source code in few-shot learning by the machine learning model trained on source codes.

9. The process of claim 1 , wherein the process is suitable for improving programs written by students in at least one of the following ways:

the first version of the source code and the selected valid candidate version are each no longer than fifty lines;

an instructor-provided alternative to the selected valid candidate version is included in a prompt to the machine learning model trained on source codes;

an instructor-provided natural language description of the task to be accomplished by any improved version of the source code is included in a prompt to the machine learning model trained on source codes; or

an instructor-provided edge test case is included in a prompt to the machine learning model trained on source codes.

10. A computing system which is configured to receive as input a first version of a source code which is a portion of a program, and configured to produce as output an improved second version of the source code, the computing system comprising:

a digital memory;

a processor set including at least one processor, the processor set in operable communication with the digital memory;

a model interface to a machine learning model; and

at least one of: (i) a syntactic phase code transformer comprising a syntax checker, a program chunker, and a syntactic prompt generator, or (ii) a semantic phase code transformer comprising a semantic prompt generator and a candidate validity tester;

wherein upon execution of the syntactic phase code transformer by the processor set, the syntax checker identifies a syntax error in the first version of the source code, the program chunker extracts a code chunk from the first version of the source code, the code chunk including the syntax error, the syntactic prompt generator receives the code chunk and produces a syntactic prompt which contains the syntax error, and the model interface receives the syntactic prompt and produces at least a portion of the second version of the source code in which the syntax error has been repaired, thereby providing improved performance of the source code of the program; or

wherein upon execution of the semantic phase code transformer by the processor set, the semantic prompt generator receives a semantic prompt dataset which includes a syntactically correct version of the source code which contains a semantic error, the semantic prompt dataset also including a test suite, the semantic prompt generator produces multiple semantic prompts which permute the semantic prompt dataset, the model interface receives the semantic prompts and produces candidate versions of the source code, the candidate validity tester selects a candidate version which is syntactically correct and which also passes the test suite, and the semantic phase code transformer produces the selected candidate version which the system includes in the second version of the source code in which the semantic error has been mitigated, thereby providing improved performance of the program.

11. The computing system of claim 10 , comprising both the syntactic phase code transformer and the semantic phase code transformer.

12. The computing system of claim 10 , comprising the semantic phase code transformer, wherein the second version of the source code in which the semantic error has been mitigated has improved performance over the syntactically correct version of the source code which contains a semantic error, the improved performance measured with respect to at least one of the following performance metrics: execution time, volatile memory usage, nonvolatile memory usage, bandwidth usage, or electric power consumption.

13. The computing system of claim 10 , comprising the semantic phase code transformer, wherein the semantic prompt dataset includes a task description in a natural language.

14. The computing system of claim 10 , further comprising a source code generator, and wherein at least one of the following is an output of the source code generator: the first version of the source code which is input to the syntactic phase code transformer, or the syntactically correct version of the source code which contains the semantic error and which is input to the semantic phase code transformer.

15. A computer-readable storage device configured with data and instructions which upon execution by a processor cause a computing system to perform a source code improvement process to improve a first version of a source code which is a portion of a program, the process comprising:

a phased iterative process performed in the computing system, the phased iterative process comprising:

repairing any syntax errors in the first version of the source code or confirming that the first version of the source code is free of syntax errors, or both, thereby yielding a syntactically correct version of the source code;

submitting a multimodal prompt to a machine learning model;

receiving candidate versions of the improved version of the source code from the machine learning model;

selecting a valid candidate version of the improved version of the source code from among the candidate versions; and

outputting the selected valid candidate version;

whereby the phased iterative process results in at least one of: an improved performance of the source code of the program as a result of a repair of a source code syntax error, or an improved performance of the program as a result of a mitigation of a source code semantic error.

16. The storage device of claim 15 , wherein the process comprises repairing any syntax errors in the first version of the source code, the repairing comprises submitting to the machine learning model a first syntactic prompt which contains the syntax error and submitting to the machine learning model a second syntactic prompt which does not contain the syntax error, and getting a syntax error correction from the machine learning model in response to at least the first syntactic prompt and the second syntactic prompt.

17. The storage device of claim 15 , wherein the process comprises repairing any syntax errors in the first version of the source code, the repairing comprises submitting to the machine learning model a code chunk, and the code chunk includes a control-flow statement which encompasses the syntax error.

18. The storage device of claim 15 , wherein the process is suitable for improving programs written by students in at least one of the following ways:

an instructor-provided alternative to the selected valid candidate version is included in a prompt to the machine learning model;

an instructor-provided natural language description of the task to be accomplished by any improved version of the source code is included in a prompt to the machine learning model; or

an instructor-provided edge test case is included in a prompt to the machine learning model.

19. The storage device of claim 15 , wherein the process comprises prompting the machine learning model with a syntactic prompt, utilizing a machine learning model response to the syntactic prompt to repair a syntax error in the first version of the source code, then prompting the machine learning model with a semantic prompt, and including a machine learning model response to the semantic prompt in the selected valid candidate version.

20. The storage device of claim 15 , further comprising training the machine learning model by few-shot learning.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jan 26, 2023
From: ZHANG, JIALU; CAMBRONERO SANCHEZ, JOSE PABLO; ARAUJO SOARES, GUSTAVO; LE, VU MINH; GULWANI, SUMIT; VERBRUGGEN, GUST BEN ANNELOES
To: MICROSOFT TECHNOLOGY LICENSING, LLC
Reel/Frame 062494/0220 →
Continuity (1)
Related Publication 20240256423A1 · Aug 1, 2024
References Cited (77)
US 20030131337A1 · Perumainar · 2003 [cited by applicant]
US 20150135166A1 · Tarlow et al. · 2015 [cited by applicant]
US 20180150742A1 · Woulfe · 2018 [cited by examiner]
US 20190227902A1 · Cheng · 2019 [cited by examiner]
US 20190287029A1 · Sobran · 2019 [cited by examiner]
US 20190324886A1 · Champlin-Scharff et al. · 2019 [cited by applicant]
US 20200097389A1 · Smith et al. · 2020 [cited by applicant]
US 20210182039A1 · Cappello · 2021 [cited by examiner]
US 20210192321A1 · Zhang · 2021 [cited by examiner]
US 20210240453A1 · Badlani · 2021 [cited by examiner]
US 20210271587A1 · Miller · 2021 [cited by examiner]
US 20220121554A1 · Das et al. · 2022 [cited by applicant]
US 20220405091A1 · Mahanta · 2022 [cited by examiner]
Santos et al., “Syntax and Sensibility: Using Language Models to Detect and Correct Syntax Errors” (Year: 2018). [cited by examiner]
Y. Ke, K. T. Stolee, C. Le Goues, and Y. Brun, “Repairing programs with semantic code search (t),” in 2015 30th IEEE/ACM International Conference on Automated Software Engineering (ASE). IEEE, no later than Dec. 31, 201… [cited by applicant]
Jiajun Jiang, et al., “Shaping Program Repair Space with Existing Patches and Similar Code”, https://doi.org/10.1145/3213846.3213871, Jul. 16-21, 2018, 12 pages. [cited by applicant]
Kaizhong Zhang, et al., “Approximate Tree Matching in the Presence of Variable Length Don't Cares”, Jan. 18, 1993, 30 pages. [cited by applicant]
U. Z. Ahmed, p. Kumar, A. Karkare, p. Kar, and S. Gulwani, “Compilation error repair: for the student programs, from the student programs,” in Proceedings of the 40th International Conference on Software Engineering: So… [cited by applicant]
C. Wong, P. Santiesteban, C. K [cited by applicant]
Claire Le Goues, et al., “Current challenges in automatic software repair”, DOI 10.1007/s11219-013-9208-0, Jun. 7, 2013, 23 pages. [cited by applicant]
C. Le Goues, T. Nguyen, S. Forrest, and W. Weimer, “Genprog: A generic method for automatic software repair,” IEEE Transactions on Software Engineering, vol. 38, No. 1, pp. 54-72, Mar. 16, 2010. [cited by applicant]
Jialu Zhang, et al., “Repairing Bugs in Python Assignments Using Large Language Models”, arXiv:2209.14876v1 [cs. SE] Sep. 29, 2022, 12 pages. [cited by applicant]
“Your AI pair programmer”, https://github.com/features/copilot/, no later than Jan. 18, 2023. [cited by applicant]
Berger, Emery. “Coping with Copilot.” Aug. 10, 2022, https://www.sigarch.org/coping-with-copilot/, 14 pages. [cited by applicant]
“New GPT-3 Capabilities: Edit & Insert.” Mar. 15, 2022. OpenAI. https://openai.com/blog/gpt-3-edit-insert/, 6 pages. [cited by applicant]
Singer, Natash. Jan. 24, 2019. “The Hard Part of Computer Science? Getting Into Class.” The New York Times, January. https://www.nytimes.com/2019/01/24/technology/computer-science-courses-college.html, 3 pages. [cited by applicant]
“Tabnine.” Dec. 12, 2022. https://github.com/codota/TabNine, 2 pages. [cited by applicant]
H. Laurenc, on, L. Saulnier, T. Wang, C. Akiki, A. V. del Moral, T. Le Scao, L. Von Werra, C. Mou, E. G. Ponferrada, H. Nguyen et al., “The bigscience corpus a 1.6 tb composite multilingual dataset.”, no later than Dec.… [cited by applicant]
K. Wang, R. Singh, and Z. Su, “Search, align, and repair: Data-driven feedback generation for introductory programming exercises,” ser. PLDI 2018. New York, NY, USA: Association for Computing Machinery, Nov. 20, 2017, p… [cited by applicant]
K. Wang, Z. Su, and R. Singh, “Dynamic neural program embeddings for program repair,” in International Conference on Learning Representations, Jun. 30, 2018, 12 pages. [cited by applicant]
Chhatbar, U. Z. Ahmed, and P. Kar, “Macer: A modular framework for accelerated compilation error repair,” in Artificial Intelligence in Education: 21st International Conference, AIED 2020, Ifrane, Morocco Proceedings, M… [cited by applicant]
T. B. Brown et al., “Language models are few-shot learners,” in NeurIPS 2020, Jul. 22, 2020, 75 pages. [cited by applicant]
Dan Hendrycks, et al., “Measuring Coding Challenge Competence With APPS”, arXiv:2105.09938v3 [cs.SE] Nov. 8, 2021, 22 pages. [cited by applicant]
M. Yasunaga and P. Liang, “Break-it-fix-it: Unsupervised learning for program repair,” in ICML, ser. Proceedings of Machine Learning Research, vol. 139. PMLR, Jun. 22, 2021, pp. 11 941-11 952. [cited by applicant]
M. Chen et al., “Evaluating large language models trained on code,” arXiv:2107.03374v2 [cs.LG] Jul. 14, 2021, 35 pages. [cited by applicant]
Y. Lu, N. Meng, and W. Li, “FAPR: fast and accurate program repair for introductory programming courses,” CoRR, vol. abs/2107.06550, Jul. 14, 2021. [Online]. Available: https://arxiv:org/abs/2107:06550, 15 pages. [cited by applicant]
P. Liu, W. Yuan, J. Fu, Z. Jiang, H. Hayashi, and G. Neubig, “Pre-train, prompt, and predict: A systematic survey of prompting methods in natural language processing,” arXiv preprint arXiv:2107.13586, Jul. 28, 2021, 46 … [cited by applicant]
G. Poesia, O. Polozov, V. Le, A. Tiwari, G. Soares, C. Meek, and S. Gulwani, “Synchromesh: Reliable code generation from pre-trained language models,” arXiv preprint arXiv:2201.11227, Jan. 26, 2022, 19 pages. [cited by applicant]
Y. Li et al., “Competition-level code generation with AlphaCode,” arXiv:2203.07814v1 [cs.PL] Feb. 8, 2022, 74 pages. [cited by applicant]
Erik Nijkamp, et al., “Codegen: an Open Large Language Model for Code With Multi-Turn Program Synthesis”, arXiv:2203.13474v4 [cs.LG] Sep. 29, 2022, 22 pages. [cited by applicant]
J. Zhang, D. Li, J. C. Kolesar, H. Shi, and R. Piskac, “Automated feedback generation for competition-level code,” CORR, vol. abs/2206.01848, Jun. 3, 2022. [Online]. Available: https://doi:org/10:48550/arXiv:2206:01848,… [cited by applicant]
C. S. Xia and L. Zhang, “Less training, more repairing please: Revisiting automated program repair via zero-shot earning,” arXiv preprint arXiv:2207.08281, Jul. 26, 2022, 13 pages. [cited by applicant]
H. Joshi, J. Cambronero, S. Gulwani, V. Le, I. Radicek, and G. Verbruggen, “Repair is nearly generation: Multilingual program repair with IIms,” arXiv preprint arXiv:2208.11640, Dec. 5, 2022, 13 pages. [cited by applicant]
Sven Apel, et al., “Semistructured Merge: Rethinking Merge in Revision Control Systems”, ESEC/FSE'11, Sep. 5-9, 2011, Szeged, Hungary, 11 pages. [cited by applicant]
R. Singh, S. Gulwani, and A. Solar-Lezama, “Automated feedback generation for introductory programming assignments,” in Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation, s… [cited by applicant]
Y. Qi, X. Mao, Y. Lei, Z. Dai, and C. Wang, “The strength of random search on automated program repair,” in Proceedings of the 36th International Conference on Software Engineering, ser. ICSE 2014, New York, NY, USA, Ma… [cited by applicant]
A. Altadmri and N. C. Brown, “37 million compilations: Investigating novice programming mistakes in large-scale student data,” in Proceedings of the 46th ACM Technical Symposium on Computer Science Education, ser. SIGCS… [cited by applicant]
F. Long and M. Rinard, “Automatic patch generation by learning correct code,” in Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, ser. POPL '16. New York, NY, USA: Asso… [cited by applicant]
S. Mechtaev, J. Yi, and A. Roychoudhury, “Angelix: Scalable multiline program patch synthesis via symbolic analysis,” In 2016 IEEE/ACM 38th International Conference on Software Engineering (ICSE), May 14-22, 2016, pp. 6… [cited by applicant]
Shalini Kaleeswaran, et al., “Semi-supervised Verified Feedback Generation”, http://dx.doi.org/10.1145/2950290.2950363, Nov. 13-18, 2016, 12 pages. [cited by applicant]
Y. Pu, K. Narasimhan, A. Solar-Lezama, and R. Barzilay, “Sk p: A neural program corrector for moocs,” in Companion Proceedings of the 2016 ACM SIGPLAN International Conference on Systems, Programming, Languages and Appl… [cited by applicant]
F. Long, P. Amidon, and M. Rinard, “Automatic inference of code transforms for patch generation,” in Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering, ser. ESEC/FSE 2017. New York, NY, U… [cited by applicant]
J. Yi, U. Z. Ahmed, A. Karkare, S. H. Tan, and A. Roychoudhury, “A feasibility study of using automated program repair for introductory programming assignments,” in Proceedings of the 2017 11th Joint Meeting on Foundati… [cited by applicant]
Guilherme Cavalcanti, et al., “Evaluating and Improving Semistructured Merge”, https://doi.brg/10.1145/3133883, no later than Oct. 31, 2017, 27 pages. [cited by applicant]
Q. Xin and S. P. Reiss, “Leveraging syntax-related code for automated program repair,” in Proceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering, ser. ASE 2017. IEEE Press, no later … [cited by applicant]
Junho Lee, et al., “Automatic Diagnosis and Correction of Logical Errors for Functional Programming Assignments”, https://doi.org/10.1145/3276528, no later than Nov. 30, 2018, 30 pages. [cited by applicant]
S. Gulwani, I. Radicek, and F. Zuleger, “Automated clustering and program repair for introductory programming assignments,” SIGPLAN Not., vol. 53, No. 4, p. 465-480, Jun. 18-22, 2018. [cited by applicant]
David M. Perry, et al., “SemCluster: Clustering of Imperative Programming Assignments Based on Quantitative Semantic Features”, https://doi.org/10.1145/3314221.3314629, Jun. 22-26, 2019, 14 pages. [cited by applicant]
R. Shariffdeen, Y. Noller, L. Grunske, and A. Roychoudhury, “Concolic program repair,” in Proceedings of the 42nd Acm Sigplan International Conference on Programming Language Design and Implementation, ser. PLDI 2021. N… [cited by applicant]
D. Song, W. Lee, and H. Oh, Context-Aware and Data-Driven Feedback Generation for Programming Assignments. New York, NY, USA: Association for Computing Machinery, Aug. 23-28, 2021, p. 328-340. [cited by applicant]
U. Z. Ahmed, Z. Fan, J. Yi, O. I. Al-Bataineh, and A. Roychoudhury, “Verifix: Verified repair of programming assignments,” ACM Trans. Softw. Eng. Methodol., vol. 31, No. 4, no later than Jul. 31, 2022, 31 pages. [cited by applicant]
J. Finnie-Ansley, P. Denny, B. A. Becker, A. Luxton-Reilly, and J. Prather, “The robots are coming: Exploring the implications of openai codex on introductory programming,” in Australasian Computing Education Conference… [cited by applicant]
J. Zhang, T. Mytkowicz, M. Kaufman, R. Piskac, and S. K. Lahiri, “Using pre-trained language models to resolve textual and semantic merge conflicts (experience paper),” in ISSTA. ACM, Jul. 18-22, 2022, pp. 77-88. [cited by applicant]
Y. Hu, U. Z. Ahmed, S. Mechtaev, B. Leong, and A. Roychoudhury, “Refactoring based program repair applied to programming assignments,” in 2019 34th IEEE/ACM International Conference on Automated Software Engineering (AS… [cited by applicant]
C. Le Goues, M. Pradel, and A. Roychoudhury, “Automated program repair,” Commun. ACM, vol. 62, No. 12, p. 56-65, no later than Dec. 31, 2019. [cited by applicant]
Luca Gazzola, et al., “Automatic Software Repair: A Survey”, Digital Object Identifier No. 10.1109/TSE.2017.2755013, Aug. 6, 2016, 34 pages. [cited by applicant]
Loris D'Antoni, et al., “Qlose: Program Repair with Quantitative Objectives”, Jul. 1, 2016, 19 pages. [cited by applicant]
L. Li, H. Liu, K. Li, Y. Jiang, and R. Sun, “Generating concise patches for newly released programming assignments,” IEEE Transactions on Software Engineering, no later than Dec. 31, 2021, 18 pages. [cited by applicant]
R. W. Hamming, “Error detecting and error correcting codes,” The Bell System Technical Journal, vol. 29, No. 2, pp. 147-160, no later than Dec. 31, 1950. [cited by applicant]
I. Drosos, P. J. Guo, and C. Parnin, “Happyface: Identifying and predicting frustrating obstacles for learning programming at scale,” in 2017 IEEE Symposium on Visual Languages and Human-Centric Computing (VL/HCC), no l… [cited by applicant]
E. Dinella, H. Dai, Z. Li, M. Naik, L. Song, and K. Wang, “Hoppity: Learning graph transformations to detect and fix bugs in programs,” in 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa… [cited by applicant]
S. Mechtaev, M. Nguyen, Y. Noller, L. Grunske, and A. Roychoudhury, “Semantic program repair using a reference implementation,” in Proceedings of the 40th International Conference on Software Engineering, ICSE 2018, Got… [cited by applicant]
R. Rolim, G. Soares, L. D'Antoni, O. Polozov, S. Gulwani, R. Gheyi, R. Suzuki, and B. Hartmann, “Learning syntactic program transformations from examples,” in ICSE 2017, no later than Apr. 30, 2017, 12 pages. [cited by applicant]
E. Dinella, G. Ryan, T. Mytkowicz, and S. K. Lahiri, “TOGA: A neural method for test oracle generation,” in 44th IEEE/ACM 44th International Conference on Software Engineering, ICSE 2022, Pittsburgh, PA, USA, May 25-27,… [cited by applicant]
D. Kim, J. Nam, J. Song, and S. Kim, “Automatic patch generation learned from human-written patches,” in Proceedings of the 2013 International Conference on Software Engineering, ser. ICSE '13. IEEE Press, no later than… [cited by applicant]
K. Rahmani, M. Raza, S. Gulwani, V. Le, D. Morris, A. Radhakrishna, G. Soares, and A. Tiwari, “Multi-modal program Inference: a marriage of pre-trained language models and component-based synthesis,” Proc. ACM Program. … [cited by applicant]
G. Verbruggen, V. Le, and S. Gulwani, “Semantic programming by example with pre-trained models,” Proc. ACM Program. Lang., vol. 5, No. OOPSLA, pp. 1-25, no later than Oct. 31, 2021. [cited by applicant]
Cited By (2)
US 12,487,912 US 12,724,699