Parallel decoding using autoregressive machine learning models

Patent metadata

Field	Value
Publication number	US-10521701-B2
Application number	US-201916417190-A
Country	US
Kind code	B2
Filing date	May 20, 2019
Priority date	May 18, 2018
Publication date	Dec 31, 2019
Grant date	Dec 31, 2019

Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for performing parallel generation of output from an autoregressive sequence to sequence model. In one aspect, a blockwise parallel decoding method takes advantage of the fact that some architectures can score sequences in sublinear time. By generating predictions for multiple time steps at once then backing off to a longest prefix validated by the scoring model, the methods can substantially improve the speed of greedy decoding without compromising performance.

First claim

What is claimed is:

1. A method for generating output from an autoregressive model p 1 , comprising:
obtaining k−1 auxiliary models p i for i=2, . . . , k, the auxiliary models p i each configured to predict a single i-th output from the model p 1 for a given prefix input; and
performing the following operations for a current input until a termination condition is met:
generating a respective independent prediction from each of the models p 1 through p k for the current input, each independent prediction being a prediction of a single token;
finding a largest n such that (i) a prediction from model p 1 of a next token for an input of the current input concatenated with the first through the (n−1)st tokens independently predicted by models p 1 through p (n−1) matches (ii) the independent prediction of the n-th token by model p n ; and
extending a generated output by appending the independent predictions from models p 1 through p n , to the generated output.

2. The method of claim 1 , wherein a respective prediction matches an output of p 1 only if the two are identical.

3. The method of claim 1 , wherein a respective prediction matches an output of p 1 only if it is one of a predetermined number of closest predictions to that output of p 1 .

4. The method of claim 1 , wherein a respective prediction matches an output of p 1 only if the two are within a predetermined distance from each other.

5. The method of claim 1 , wherein k is an integer in a range of 2-20, or 2-10, or 4-6.

6. The method of claim 1 , wherein the autoregressive model is a deep neural autoregressive model.

7. The method of claim 1 , wherein the one-token predictions from each of the models p 1 through p k are generated in parallel.

8. A system implemented by one or more computers, the system comprising:
an autoregressive model p 1 ; and
k−1 auxiliary models p i for i=2, . . . , k, the auxiliary model p i each configured to predict a single i-th output from the model p 1 for a given prefix input;
wherein the system is configured to perform the following operations for a current input until a termination condition is met:
generating independent predictions from each of the models p 1 through p k for the current input, each independent prediction being a prediction of a single token;
finding a largest n such that (i) a prediction from model p 1 of a next token for an input of the current input concatenated with the first through the (n−1)st tokens independently predicted by models p 1 through p (n−1) matches (ii) the independent prediction of the n-th token by model p n ; and
extending a generated output by appending the independent predictions from models p 1 through p n , to the generated output.

9. The system of claim 8 , wherein a respective prediction matches an output of p1 only if the two are identical.

10. The system of claim 8 , wherein a respective prediction matches an output of p1 only if it is one of a predetermined number of closest predictions to that output of p1.

11. The system of claim 8 , wherein a respective prediction matches an output of p1 only if the two are within a predetermined distance from each other.

12. The system of claim 8 , wherein k is an integer in a range of 2-20, or 2-10, or 4-6.

13. The system of claim 8 , wherein the autoregressive model is a deep neural autoregressive model.

14. The system of claim 8 , wherein the one-token predictions from each of the models p 1 through p k are generated in parallel.

15. One or more computer-readable storage media encoded with instructions that, when executed by one or more computers, cause the one or more computers to perform operations comprising:
obtaining an autoregressive model p 1 and k−1 auxiliary models p i for i=2, . . . , k, the auxiliary models p i each configured to predict a single i-th output from the model p 1 for a given prefix input; and
performing the following operations for a current input until a termination condition is met:
generating a respective independent prediction from each of the models p 1 through p k for the current input, each independent prediction being a prediction of a single token;
finding a largest n such that (i) a prediction from model p 1 of a next token for an input of the current input concatenated with the first through the (n−1)st tokens independently predicted by models p 1 through p (n−1) matches (ii) the independent prediction of the n-th token by model p n ; and
extending a generated output by appending the independent predictions from models p 1 through p n , to the generated output.

16. The one or more computer-readable storage media of claim 15 , wherein a respective prediction matches an output of p 1 only if the two are identical.

17. The one or more computer-readable storage media of claim 15 , wherein a respective prediction matches an output of p 1 only if it is one of a predetermined number of closest predictions to that output of p 1 .

18. The one or more computer-readable storage media of claim 15 , wherein a respective prediction matches an output of p 1 only if the two are within a predetermined distance from each other.

19. The one or more computer-readable storage media of claim 15 , wherein k is an integer in a range of 2-20, or 2-10, or 4-6.

20. The one or more computer-readable storage media of claim 15 , wherein the autoregressive model is a deep neural autoregressive model.

21. The one or more computer-readable storage media of claim 15 , wherein the one-token predictions from each of the models p 1 through p k are generated in parallel.

Assignees

• Google Llc

Inventors

• Shazeer Noam M
• Uszkoreit Jakob D
• Stern Mitchell Thomas

Classifications

• G06N20/20 Primary

  Ensemble learning · CPC title

• G06V10/82

  using neural networks · CPC title

• G06V10/764

  using classification, e.g. of video objects · CPC title

• G06F18/2185

  the supervisor being an automated module, e.g. intelligent oracle · CPC title

• G06N20/00

  Machine learning · CPC title