IP Library › Granted Patent US 12,287,795
Granted Patent B2
US 12,287,795 · App. 18/401,120 · Granted Apr 29, 2025

Beam search decoding with forward-looking scores

Inventors: Domenic Joseph Donato (Oviedo, FL); Christopher James Dyer (London, GB); Rémi Leblond (Cachan, FR)
Assignee: DeepMind Technologies Limited
G06F16/24573G06F40/284
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,287,795
App. No.
18/401,120
Granted
Apr 29, 2025
Kind
B2
Abstract

Methods and systems for beam search decoding. One of the methods includes initializing beam data specifying a set of k candidate output sequences and a respective total score for each of the candidate output sequences; updating the beam data at each of a plurality of decoding steps, comprising, at each decoding step: generating a score distribution that comprises a respective score for each token in the vocabulary; identifying a plurality of expanded sequences; generating, for each expanded sequence, a respective backwards-looking score; generating, for each expanded sequence, a respective forward-looking score; computing, for each expanded sequence, a respective total score from the respective forward-looking score for the expanded sequence and the respective backwards-looking score for the expanded sequence; and updating the set of k candidate output sequences using the respective total scores for the expanded sequences.

Claims (78)

1. A method performed by one or more computers and for generating an output sequence that comprises a plurality of vocabulary of tokens that are each selected from a vocabulary of tokens that comprises a set of vocabulary tokens and an end of sequence token, the method comprising:

obtaining a network input;

initializing beam data specifying a set of k candidate output sequences and a respective total score for each of the candidate output sequences, wherein k is an integer greater than or equal to one;

updating the beam data at each of a plurality of decoding steps, the updating comprising, at each decoding step:

processing each candidate output sequence in the beam data as of the decoding step using an auto-regressive neural network that is conditioned on the network input to generate a score distribution that comprises a respective score for each token in the vocabulary;

identifying a plurality of expanded sequences, wherein each expanded sequence corresponds to a respective candidate output sequence and includes the tokens from the corresponding candidate output sequence followed by a respective additional token from the vocabulary;

generating, for each expanded sequence, a respective backwards-looking score based on the respective score for the respective additional token in the score distribution generated for the corresponding candidate output sequence by the auto-regressive neural network;

generating, for each expanded sequence and using the auto-regressive neural network, a respective forward-looking score that estimates a score for a highest-scoring partial output sequence that has the expanded sequence as a prefix;

computing, for each expanded sequence, the respective total score from the respective forward-looking score for the expanded sequence and the respective backwards-looking score for the expanded sequence; and

updating the set of k candidate output sequences using the respective total scores for the expanded sequences.

2. The method of claim 1 , further comprising:

after updating the beam at each of the plurality of decoding steps:

selecting one of the candidate output sequences in the beam, and

generating the output sequence for the network input using the selected candidate output sequence.

3. The method of claim 1 , the updating comprising, at each decoding step:

determining whether one or more termination criteria are satisfied based on the candidate output sequences in the beam after updating the beam at the decoding step; and

determining to perform another decoding step only in response to determining that the one or more termination criteria are not satisfied.

4. The method of claim 1 , wherein updating the set of k candidate output sequences using the respective total scores for the expanded sequences comprises:

selecting, as the k candidate output sequences in the updated set of k candidate output sequences, the k sequences having highest respective total scores from among (i) the expanded sequences and (ii) any finalized candidate output sequences in the set of k candidate output sequences as of the update iteration.

5. The method of claim 4 , wherein a finalized candidate output sequence is a candidate output sequence that ends with the end of sequence token.

6. The method of claim 1 , wherein generating, for each expanded sequence and using the auto-regressive neural network, a respective forward-looking score that estimates a score for a highest-scoring partial output sequence that has the expanded sequence as a prefix comprises:

for each given candidate output sequence:

identifying a most likely expanded sequence corresponding to the given candidate output sequence;

performing a greedy rollout using the auto-regressive neural network to generate a forward-looking score for the most likely expanded sequence; and

computing respective forward-looking scores for other expanded sequences that correspond to the given candidate output sequence from the forward-looking score for the most likely expanded sequence.

7. The method of claim 6 , wherein identifying a most likely expanded sequence corresponding to the given candidate output sequence comprises identifying the token having the highest score in the score distribution for the given candidate output sequence and identifying, as the most likely expanded sequence, the expanded sequence that has the highest scoring token following the given candidate output sequence.

8. The method of claim 6 , wherein computing respective forward-looking scores for other expanded sequences that correspond to the given candidate output sequence from the forward-looking score for the most likely expanded sequence, comprises, for each other expanded sequence:

computing the respective forward-looking score for the other expanded sequence based on the forward-looking score for the most likely expanded output sequence, the score for the highest-scoring token, and the score for the token that follows the candidate output sequence in the other expanded output sequence.

9. The method of claim 6 , wherein performing a greedy rollout using the auto-regressive neural network to generate a forward-looking score for the most likely expanded sequence comprises:

appending tokens to the most likely expanded sequence using the auto-regressive neural network at respective steps of the greedy roll-out until a termination criterion is reached; and

generating the forward-looking score for the most likely expanded sequence using the scores for the highest scoring tokens at each respective step of the greedy roll-out.

10. A system comprising:

one or more computers; and

one or more storage devices storing instructions that, when executed by the one or more computers, cause the one or more computers to perform operations for generating an output sequence that comprises a plurality of vocabulary of tokens that are each selected from a vocabulary of tokens that comprises a set of vocabulary tokens and an end of sequence token, the operations comprising:

obtaining a network input;

initializing beam data specifying a set of k candidate output sequences and a respective total score for each of the candidate output sequences, wherein k is an integer greater than or equal to one;

updating the beam data at each of a plurality of decoding steps, the updating comprising, at each decoding step:

processing each candidate output sequence in the beam data as of the decoding step using an auto-regressive neural network that is conditioned on the network input to generate a score distribution that comprises a respective score for each token in the vocabulary;

identifying a plurality of expanded sequences, wherein each expanded sequence corresponds to a respective candidate output sequence and includes the tokens from the corresponding candidate output sequence followed by a respective additional token from the vocabulary;

generating, for each expanded sequence, a respective backwards-looking score based on the respective score for the respective additional token in the score distribution generated for the corresponding candidate output sequence by the auto-regressive neural network;

generating, for each expanded sequence and using the auto-regressive neural network, a respective forward-looking score that estimates a score for a highest-scoring partial output sequence that has the expanded sequence as a prefix;

computing, for each expanded sequence, the respective total score from the respective forward-looking score for the expanded sequence and the respective backwards-looking score for the expanded sequence; and

updating the set of k candidate output sequences using the respective total scores for the expanded sequences.

11. The system of claim 10 , the operations further comprising:

after updating the beam at each of the plurality of decoding steps:

selecting one of the candidate output sequences in the beam, and

generating the output sequence for the network input using the selected candidate output sequence.

12. The system of claim 10 , the updating comprising, at each decoding step:

determining whether one or more termination criteria are satisfied based on the candidate output sequences in the beam after updating the beam at the decoding step; and

determining to perform another decoding step only in response to determining that the one or more termination criteria are not satisfied.

13. The system of claim 10 , wherein updating the set of k candidate output sequences using the respective total scores for the expanded sequences comprises:

selecting, as the k candidate output sequences in the updated set of k candidate output sequences, the k sequences having highest respective total scores from among (i) the expanded sequences and (ii) any finalized candidate output sequences in the set of k candidate output sequences as of the update iteration.

14. The system of claim 13 , wherein a finalized candidate output sequence is a candidate output sequence that ends with the end of sequence token.

15. The system of claim 10 , wherein generating, for each expanded sequence and using the auto-regressive neural network, a respective forward-looking score that estimates a score for a highest-scoring partial output sequence that has the expanded sequence as a prefix comprises:

for each given candidate output sequence:

identifying a most likely expanded sequence corresponding to the given candidate output sequence;

performing a greedy rollout using the auto-regressive neural network to generate a forward-looking score for the most likely expanded sequence; and

computing respective forward-looking scores for other expanded sequences that correspond to the given candidate output sequence from the forward-looking score for the most likely expanded sequence.

16. The system of claim 15 , wherein identifying a most likely expanded sequence corresponding to the given candidate output sequence comprises identifying the token having the highest score in the score distribution for the given candidate output sequence and identifying, as the most likely expanded sequence, the expanded sequence that has the highest scoring token following the given candidate output sequence.

17. The system of claim 15 , wherein computing respective forward-looking scores for other expanded sequences that correspond to the given candidate output sequence from the forward-looking score for the most likely expanded sequence, comprises, for each other expanded sequence:

computing the respective forward-looking score for the other expanded sequence based on the forward-looking score for the most likely expanded output sequence, the score for the highest-scoring token, and the score for the token that follows the candidate output sequence in the other expanded output sequence.

18. The system of claim 15 , wherein performing a greedy rollout using the auto-regressive neural network to generate a forward-looking score for the most likely expanded sequence comprises:

appending tokens to the most likely expanded sequence using the auto-regressive neural network at respective steps of the greedy roll-out until a termination criterion is reached; and

generating the forward-looking score for the most likely expanded sequence using the scores for the highest scoring tokens at each respective step of the greedy roll-out.

19. One or more non-transitory computer-readable storage media storing instructions that when executed by one or more computers cause the one or more computers to perform operations for generating an output sequence that comprises a plurality of vocabulary of tokens that are each selected from a vocabulary of tokens that comprises a set of vocabulary tokens and an end of sequence token, the operations comprising:

obtaining a network input;

initializing beam data specifying a set of k candidate output sequences and a respective total score for each of the candidate output sequences, wherein k is an integer greater than or equal to one;

updating the beam data at each of a plurality of decoding steps, the updating comprising, at each decoding step:

processing each candidate output sequence in the beam data as of the decoding step using an auto-regressive neural network that is conditioned on the network input to generate a score distribution that comprises a respective score for each token in the vocabulary;

identifying a plurality of expanded sequences, wherein each expanded sequence corresponds to a respective candidate output sequence and includes the tokens from the corresponding candidate output sequence followed by a respective additional token from the vocabulary;

generating, for each expanded sequence, a respective backwards-looking score based on the respective score for the respective additional token in the score distribution generated for the corresponding candidate output sequence by the auto-regressive neural network;

generating, for each expanded sequence and using the auto-regressive neural network, a respective forward-looking score that estimates a score for a highest-scoring partial output sequence that has the expanded sequence as a prefix;

computing, for each expanded sequence, the respective total score from the respective forward-looking score for the expanded sequence and the respective backwards-looking score for the expanded sequence; and

updating the set of k candidate output sequences using the respective total scores for the expanded sequences.

20. The media of claim 19 , the operations further comprising:

after updating the beam at each of the plurality of decoding steps:

selecting one of the candidate output sequences in the beam, and

generating the output sequence for the network input using the selected candidate output sequence.

Assignments (2)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jun 6, 2025
From: DEEPMIND TECHNOLOGIES LIMITED
To: GDM HOLDING LLC
Reel/Frame 071498/0210 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Mar 11, 2024
From: DONATO, DOMENIC JOSEPH; DYER, CHRISTOPHER JAMES; LEBLOND, RÉMI
To: DEEPMIND TECHNOLOGIES LIMITED
Reel/Frame 066713/0906 →
Continuity (2)
Provisional Application 63436468 · Dec 30, 2022
Related Publication 20240220506A1 · Jul 4, 2024
References Cited (28)
US 20230029590A1 · De Freitas Adiwardana · 2023 [cited by examiner]
US 20230244934A1 · Lazaridou · 2023 [cited by examiner]
US 20240267529A1 · Chen · 2024 [cited by examiner]
Barrault et al., “Proceedings of the Fifth Conference on Machine Translation.” Proceedings of the Fifth Conference on Machine Translation, Nov. 2020, 36 pages. [cited by applicant]
Bhattacharyya et al., “Energy-based reranking: Improving neural machine translation using energy based models” CoRR, Submitted on Sep. 2021, arXiv:2009.13267v4, 10 pages. [cited by applicant]
Cettolo et al., “Report on the 11th IWSLT evaluation campaign.” Proceedings of the 11th International Workshop on Spoken Language Translation: Evaluation Campaign, Feb. 17, 2014. [cited by applicant]
Cohen et al., “Empirical analysis of beam search performance degradation in neural sequence models” In Proceedings of the 36th International Conference onMachine Learning, May 2019, 10 pages. [cited by applicant]
Dusek et al., “Sequence-to-Sequence Generation for Spoken Dialogue via Deep Syntax Trees and String” CoRR, Submitted on Jun. 2016, arXiv:1606.05491v1, 7 pages. [cited by applicant]
Github.com [online], “JAX: composable transformations of Python+NumPy programs” Nov. 2019, retrieved on Dec. 24, 2024, retrieved from URL <https://github.com/jax-ml/jax>, 8 pages. [cited by applicant]
Hargreaves et al., “Incremental beam manipulation for natural language generation” CoRR, Submitted on Mar. 2021, arXiv:2102.02574v3, 14 pages. [cited by applicant]
Hart et al., “A formal basis for the heuristic determination of minimum cost paths.” IEEE transactions on Systems Science and Cybernetics 4.2, Jul. 1968, 100-107. [cited by applicant]
He et al., “Decoding with value networks for neural machine translation.” Advances in Neural information processing systems 30, 2017, 10 pages. [cited by applicant]
Holtzman et al., “The curious case of neural text degeneration” CoRR, Submitted on Apr. 2019, arXiv:1904.09751v1, 11 pages. [cited by applicant]
Jouppi et al., “In-datacenter performance analysis of a tensor processing unit” CoRR, Submitted on Apr. 2017, arXiv:1704.04760v1, 17 pages. [cited by applicant]
Klein et al., “Opennmt: Open-source toolkit for neural machine translation” CoRR, Submitted on Mar. 2017, arXiv:1701.02810v2, 6 pages. [cited by applicant]
Kumar et al., “Minimum bayes-risk decoding for statistical machine translation.” Proceedings of the Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics: HL… [cited by applicant]
Leblond et al., “Machine translation decoding beyond beam search” CoRR, Submitted on Apr. 2021, arXiv:2104.05336v1, 23 pages. [cited by applicant]
Murray et al., “Correcting Length Bias in Neural Machine Translation” CoRR, Submitted on Aug. 2018, arXiv:1808.10006v2, 12 pages. [cited by applicant]
Post, “A Call for Clarity in Reporting BLEU Scores” CoRR, Submitted on Sep. 2018, arXiv:1804.08771v2, 6 pages. [cited by applicant]
Ren et al., “Deep reinforcement learning-based image captioning with embedding reward” In 2017 IEEE Conference on Computer Vision and Pattern Recognition, 2017, 290-298. [cited by applicant]
Sennrich et al., “Neural machine translation of rare words with subword units” CoRR, Submitted on Jun. 2016, arXiv:1508.07909v5, 11 pages. [cited by applicant]
Shazeer, “Fast transformer decoding: One write-head is all you need” CoRR, Submitted on Nov. 2019, arXiv:1911.02150v1, 9 pages. [cited by applicant]
Shen et al., “Minimum risk training for neural machine translation” In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (vol. 1: Long Papers), Aug. 2016, 1683-1692. [cited by applicant]
Stahlberg et al., “On NMT search errors and model errors: Cat got your tongue?” CoRR, Submitted on Aug. 2019, arXiv:1908.10090v1, 7 pages. [cited by applicant]
Vaswani et al., “Attention is all you need” CoRR, Submitted on Jun. 2017, arXiv:1706.03762v4, 15 pages. [cited by applicant]
Wang et al., “Investigating the Decoders of Maximum Likelihood Sequence Models: A Look-ahead Approach” CoRR, Submitted on Mar. 2020, arXiv:2003.03716v1, 7 pages. [cited by applicant]
Wu et al., “Google's neural machine translation system: Bridging the gap between human and machine translation” CoRR, Submitted on Oct. 2016, arXiv:1609.08144v2, 23 pages. [cited by applicant]
Yang et al., “Breaking the beam search curse: A study of (re-) scoring methods and stopping criteria for neural machine translation” CoRR, Submitted on Oct. 2018, arXiv:1808.09582v3, 6 pages. [cited by applicant]