# US 2021/0279042 A1 · Neural code completion via re-ranking

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2021/0279042 A1
- Document ID: US20210279042A1
- Status: Published application
- Kind: A1
- Application number: 16/900,993
- Filed: 2020-06-15
- Published: 2021-09-09
- Earliest claimed: 2020-03-05
- Assignees: Microsoft Technology Licensing, LLC
- Applicants: Microsoft Technology Licensing, LLC.
- Inventors: MILTIADIS ALLAMANIS; SHENGYU FU; XIAOYU LIU; NEELAKANTAN SUNDARESAN; ALEXEY SVYATKOVSKIY
- Web page: https://patentgrep.com/patent/US20210279042A1

## CPC

- G06F 8/33: Intelligent editors
- G06F 8/35: model driven
- G06F 8/37: {Compiler construction; Parser generation}
- G06N 3/044: Recurrent networks, e.g. Hopfield networks
- G06N 3/0442: characterised by memory or gating, e.g. long short-term memory [LSTM] or gated recurrent units [GRU]
- G06N 3/045: Combinations of networks
- G06N 3/0464: Convolutional networks [CNN, ConvNet]
- G06N 3/049: Temporal neural networks, e.g. delay elements, oscillating neurons or pulsed inputs
- G06N 3/084: Backpropagation, e.g. using gradient descent
- G06N 3/09: Supervised learning
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

A code completion system uses neural components to rank the unordered list of code completion candidates generated from an existing static analyzer. The candidates represent the next sequence of tokens likely to complete a partially-formed program element as a developer is typing in a software development tool. A re-ranking component generates a ranked order of the candidates based on a context embedding of the code context and candidate embeddings of the candidates, where both embeddings are based a common token encoding.

## Claims

### Claim 1

A system comprising:
one or more processors; and
a memory that stores one or more programs that are configured to be executed by the one or more processors, the one or more programs including instructions that:
obtain a plurality of unranked candidates likely to follow a code snippet in a source code development tool from a non-machine-learning-based static analyzer;
compute a probability distribution for the unranked candidates, the probability distribution based on a context embedding of a context of the code snippet and a candidate embedding for each unranked candidates;
rank each candidate of the plurality of candidates based on the probability distribution; and
return k candidates having a highest probability.

### Claim 2 (depends on 1)

The system of claim 1, wherein the one or more programs include instructions that:
generate a context embedding having a token embedding for each token of a context of the code snippet.

### Claim 3 (depends on 2)

The system of claim 2, wherein the one or more programs include instructions that:
generate a token embedding from a token encoder, a subtoken encoder, a character encoder, or a byte-pair encoder.

### Claim 4 (depends on 2)

The system of claim 2, wherein the one or more programs include instructions that:
generate a context embedding from a Gated Recurrent Neural Network (GRU) encoder, a Long Short-Term Memory (LSTM) encoder, a one-dimensional Convolutional Neural Network (1D CNN) or a neural transformer with attention.

### Claim 5 (depends on 1)

The system of claim 1, wherein the candidate embedding includes a token embedding for each token of a candidate.

### Claim 6 (depends on 1)

The system of claim 1, wherein the probability for each candidate is based on the context embedding and a dot product of the token embedding of a candidate with a linearly transformed context embedding.

### Claim 7 (depends on 1)

The system of claim 1, wherein the one or more programs are part of an integrated development environment.

### Claim 8

A computer-implemented method, comprising:
analyzing, through a non-machine learning static analysis, a context of a source code program to generate a plurality of unranked candidates to complete a program element of the source code program under development;
generating a context embedding representing the context and a candidate embedding representing the plurality of candidates;
computing a probability distribution for the candidates based on the context embedding and a candidate embedding for a respective candidate; and
ranking the plurality of candidates based on a respective probability from the computed probability distribution.

### Claim 9 (depends on 8)

The computer-implemented method of claim 8, further comprising:
providing k candidates having a highest probability for completion of the program element.

### Claim 10 (depends on 8)

The computer-implemented method of claim 8, further comprising:
extracting tokens from each candidate; and
computing a candidate embedding for a candidate as a combination of token embeddings for each token of a candidate.

### Claim 11 (depends on 8)

The computer-implemented method of claim 8, wherein a token embedding is derived from a subtoken encoder, a token-unit encoder, a character encoder, or a byte-pair encoder.

### Claim 12 (depends on 8)

The computer-implemented method of claim 8, further comprising:
generating the context embedding from a token encoding of the context applied to a neural context encoder.

### Claim 13 (depends on 12)

The computer-implemented method of claim 12, wherein the neural context encoder is a Gated Recurrent Unit (GRU), a Long Short Term Memory (LSTM), a one-dimensional Convolutional Neural Network (1D CNN), or a transformer.

### Claim 14 (depends on 8)

The computer-implemented method of claim 8, wherein the computer-implemented method is implemented in a source code editor or integrated development environment.

### Claim 15 (depends on 8)

The method of claim 8, wherein the computer-implemented method is implemented in a cloud service.

### Claim 16

A device, comprising:
at least one processor and a memory;
wherein the at least one processor is configured to:
obtain an unordered list of candidates to complete a code snippet in a source code program using a non-neural static analysis based on a context of the code snippet; and
rank the unordered list of candidates based on a probability distribution computed from a neural network model, the neural network model configured to generate the probability distribution based on a context embedding of the context and candidate embeddings of the unordered list of candidates, wherein the context embedding and the candidate embeddings are based on a common token embedding.

### Claim 17 (depends on 16)

The device of claim 16, wherein the at least one processor is further configured to:
provide a list of the candidates in descending probability order to the source code program for completion of the code snippet.

### Claim 18 (depends on 16)

The device of claim 16, wherein the common token embedding is produced from a subtoken encoder.

### Claim 19 (depends on 16)

The device of claim 16, wherein the probability distribution is based on a softmax function of the dot product of a linearly transformed context embedding and candidate embedding of each candidate.

### Claim 20 (depends on 16)

The device of claim 16, wherein the neural network model is a Gated Recurrent Unit (GRU) or a Long Short-Term Memory (LSTM) model.
