US 2023/0418567 A1Published application

Constrained prefix matching for generating next token predictions

AssigneeAmazon Technologies, Inc.

InventorsPraphruetpong Athiwaratkun, Yuchen Tian, Mingyue Shang, Zijian Wang, Ramesh M. Nallapati, Parminder Bhatia, Andrew Oliver Arnold, Bing Xiang, Sudipta Sengupta, Yanitsa Donchev, Srinivas Iragavarapu, Matthew Lee, Vamshidhar Krishnamurthy Dantu, Atul Deo, Ankur Deepak Desai

Life of this patent

Estimating the term…

patentgrep

Loading patent…

Abstract

Pre-fix matching may constrain the generation of next token predictions. Input text to perform a next token prediction may be received. Multiple tokens may be determined from the input text, including a partial token. From possible tokens, one or more matching possible tokens with the partial token may be identified. Next token predictions may then be filtered using the identified possible tokens in order to ensure that the partial token is matched.

Claims20

Dependent claims

A system, comprising:

at least one processor;
and
A memory, storing program instructions that when executed by the at least one processor, cause the at least one processor to implement a code generation system, the code generation system configured to:
receive input programming code to perform a next token prediction for the input programming code;
determine word boundaries with respect to a tokenizer for the input text where the rightmost boundary contains a partial token, the partial token being used as a prompt suffix;
identify, from a plurality of possible tokens, one or more possible tokens that are a match with the prompt suffix by starting with the prompt suffix or ending with the prompt suffix;
filter next token predictions according to the identified one or more possible tokens, wherein the next token predictions are generated by applying a machine learning model trained to predict next tokens for programming code to a remaining portion of the input programming code that does not include a number of backtrack tokens corresponding to a pre-token, wherein the filtering is performed for one or more iterations that remove after each iteration one or more characters from the left of the partial token that match one of the next token predictions until there are no remaining characters in the partial token;
and
provide a last one of the next token predictions as the next token prediction for the input programming code.

6 more elements

One or more non-transitory, computer-readable storage media, storing program instructions that when executed on or across one or more computing devices cause the one or more computing devices to implement:

receiving input text to perform a next token prediction for the input text;
determining word boundaries with respect to a tokenizer for the input text where the rightmost boundary contains a partial token, the partial token being used as a prompt suffix;
identifying from a plurality of possible tokens one or more possible tokens that are a match with the prompt suffix by starting with the prompt suffix or ending with the prompt suffix;
filtering next token predictions according to the identified one or more possible tokens, wherein the next token predictions are generated by applying a machine learning model to a remaining portion of the input text that does not include a number of backtrack tokens corresponding to a pre-token, wherein the filtering is performed for one or more iterations that remove after each iteration one or more characters from the left of the partial token that match one of the next token predictions until there are no remaining characters in the partial token;
and
providing a last one of the next token predictions as the next token prediction for the input text.

3 more elements

Dependencies are inferred from the claim text.