# US 11,307,831 B2 · 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 11,307,831 B2
- Document ID: US11307831B2
- Status: Granted
- Kind: B2
- Application number: 16/900,993
- Filed: 2020-06-15
- Published: 2021-09-09
- Granted: 2022-04-19
- 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/US11307831B2

## 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:
generate a plurality of unranked candidates likely to complete a partially-formed code snippet in a source code development tool from a non-machine-learning-based static analyzer;
obtain a context embedding of a context of the partially-formed code snippet and a candidate embedding for each of the plurality of unranked candidates;
compute a probability distribution for the unranked candidates, the probability distribution based on the context embedding of the context of the partially-formed code snippet and the candidate embedding for each of the plurality of unranked candidates;
rank each unranked candidate of the plurality of unranked candidates based on the probability distribution; and
return k ranked 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 the context embedding having a token embedding for each token of the context of the partially-formed code snippet.

### Claim 3 (depends on 2)

The system of claim 2, wherein the one or more programs include instructions that:
generate the 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 the 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 an unranked candidate.

### Claim 6 (depends on 1)

The system of claim 1, wherein the probability for each unranked candidate is based on the context embedding and a dot product of the token embedding of the unranked 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 unranked candidates;
computing a probability distribution for the unranked candidates based on the context embedding and a candidate embedding for a respective unranked candidate;
ranking the plurality of unranked candidates based on a respective probability from the computed probability distribution; and
return k ranked candidates having a highest probability.

### Claim 9 (depends on 8)

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

### Claim 10 (depends on 9)

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

### Claim 11 (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 12 (depends on 11)

The computer-implemented method of claim 11, 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 13 (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 14 (depends on 8)

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

### Claim 15

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;
obtain a context embedding of the context and candidate embeddings of the unordered list of candidates;
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 the context embedding of the context and the candidate embeddings of the unordered list of candidates, wherein the context embedding and the candidate embeddings are based on a common token embedding; and
return k ranked candidates having a highest probability.

### Claim 16 (depends on 15)

The device of claim 15, wherein the at least one processor is further configured to:
return the k ranked candidates in descending probability order to the source code program for completion of the code snippet.

### Claim 17 (depends on 15)

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

### Claim 18 (depends on 15)

The device of claim 15, 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 19 (depends on 15)

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