# US 2025/0209355 A1 · Fast Speculative Decoding Using Multiple Parallel Drafts

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

- Number: US 2025/0209355 A1
- Document ID: US20250209355A1
- Status: Published application
- Kind: A1
- Application number: 18/990,227
- Filed: 2024-12-20
- Published: 2025-06-26
- Earliest claimed: 2023-12-21
- Assignees: Google Inc.
- Applicants: Google LLC
- Inventors: Ziteng Sun; Ananda Theertha Suresh; Jae Hun Ro; Ahmad Beirami; Himanshu Jain; Xinnan Yu; Michael Dennis Riley; Sanjiv Kumar
- Web page: https://patentgrep.com/patent/US20250209355A1

## CPC

- G06N 7/01: Probabilistic graphical models, e.g. probabilistic networks
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

Systems and methods are provided for low-latency autoregressive generation of sequence output based on a plurality of parallel draft sequences. A lower-latency machine-learned model (e.g., having a smaller number of parameters than a model of interest) can generate a plurality of draft sequences comprising a plurality of draft tokens per sequence. A machine-learned model of interest (e.g., having a high latency per token) can evaluate a plurality of respective conditional probabilities for the respective draft tokens in parallel. An output sequence comprising one or more accepted draft tokens, corrected tokens, and/or additional tokens can be generated based on the draft tokens and conditional probabilities.

## Claims

### Claim 1

A computer-implemented method, comprising:
obtaining, by a computing system comprising one or more computing devices, an input context;
generating, by the computing system using one or more first machine-learned sequence processing models and based on the input context, a plurality of draft sequences, wherein each draft sequence of the plurality of draft sequences is configured to immediately follow the input context;
evaluating, using a second, different machine-learned sequence processing model and based on the input context by the computing system, a respective conditional probability for each of one or more tokens of each of the plurality of draft sequences;
selecting, by the computing system, one or more of the tokens from one of the plurality of draft sequences for inclusion in an output sequence based on the respective conditional probabilities; and
providing, by the computing system, the output sequence as output.

### Claim 2 (depends on 1)

The method of claim 1, wherein:
a first draft sequence of the plurality of draft sequences comprises a first draft token associated with a first respective conditional probability;
a second draft sequence of the plurality of draft sequences comprises a second draft token associated with a second respective conditional probability; and
evaluating comprises evaluating the first respective conditional probability and second respective conditional probability in parallel.

### Claim 3 (depends on 1)

The method of claim 1, wherein:
the respective conditional probability is a respective second-model conditional probability;
generating a draft sequence comprises evaluating, using the one or more first machine-learned sequence processing models and based on the input context by the computing system, a respective first-model conditional probability for each of the one or more tokens of each of the plurality of draft sequences; and
selecting one or more tokens for inclusion in an output sequence comprises determining, based on a comparison between at least one respective first-model conditional probability and at least one respective second-model conditional probability, whether to include a draft token associated with the at least one respective first-model conditional probability and the at least one respective second-model conditional probability.

### Claim 4 (depends on 3)

The method of claim 3, wherein determining whether to include the draft token comprises:
generating a random value;
determining, based at least in part on the respective first-model conditional probability and the respective second-model conditional probability, a sampling threshold; and
determining, based on a comparison between the random value and the sampling threshold, whether to include the draft token in the output sequence.

### Claim 5 (depends on 4)

The method of claim 4, wherein a ratio ρ of a quotient q(x)/p(x) to the sampling threshold is between 1 and k inclusive, wherein q(x) is the respective second-model conditional probability, p(x) is the respective first-model conditional probability, and k is a number of draft sequences of the plurality of draft sequences.

### Claim 6 (depends on 5)

The method of claim 5, wherein the ratio ρ of the quotient to the sampling threshold is greater than or equal to ρ*, where
ρ
*
=
1
-
(
1
-
∑
x
∈
Ω
min
⁡
(
p
⁡
(
x
)
,
q
⁢
(
x
)
ρ
*
)
)
k
∑
x
∈
Ω
min
⁡
(
p
⁡
(
x
)
,
q
⁢
(
x
)
ρ
*
)
.

### Claim 7 (depends on 1)

The method of claim 1, wherein a probability distribution of the output sequence is equivalent to a probability distribution of the second machine-learned sequence processing model.

### Claim 8 (depends on 1)

The method of claim 1, wherein selecting one or more tokens for inclusion comprises:
obtaining a valid transport plan between a probability distribution of the one or more first machine-learned sequence processing models and a probability distribution of the second machine-learned sequence processing model; and
determining, based on the valid transport plan, whether to accept a draft token of the plurality of draft sequences.

### Claim 9 (depends on 8)

The method of claim 8, wherein obtaining the valid transport plan comprises linear programming.

### Claim 10 (depends on 3)

The method of claim 3, wherein the draft token associated with the at least one respective first-model conditional probability and the at least one respective second-model conditional probability is not included in the output sequence, and further comprising:
determining, by the computing system and using a conditional probability distribution of the one or more first machine-learned sequence processing models and a conditional probability distribution of the second machine-learned sequence processing model, a residual probability distribution; and
determining, based on the residual probability distribution, an output token to include in the output sequence.

### Claim 11 (depends on 10)

The method of claim 10, wherein determining the output token comprises random sampling based on the residual probability distribution.

### Claim 12 (depends on 3)

The method of claim 3, wherein the draft token associated with the at least one respective first-model conditional probability and the at least one respective second-model conditional probability is included in the output sequence, and further comprising:
determining, using the second machine-learned sequence processing model and based at least in part on the input context and the draft token associated with the at least one respective first-model conditional probability and the at least one respective second-model conditional probability, a conditional probability distribution of the second machine-learned sequence processing model;
randomly sampling an additional output token based on the conditional probability distribution; and
including the additional output token in the output sequence.

### Claim 13

A computing system comprising:
one or more processors; and
one or more non-transitory computer-readable media storing instructions that are executable by the one or more processors to cause the computing system to perform one or more operations, the operations comprising:
obtaining an input context;
generating, using one or more first machine-learned sequence processing models and based on the input context, a plurality of draft sequences, wherein each draft sequence of the plurality of draft sequences is configured to immediately follow the input context;
evaluating, using a second, different machine-learned sequence processing model and based on the input context, a respective conditional probability for each of one or more tokens of each of the plurality of draft sequences;
selecting one or more of the tokens from one of the plurality of draft sequences for inclusion in an output sequence based on the respective conditional probabilities; and
providing the output sequence as output.

### Claim 14 (depends on 13)

The computing system of claim 13, wherein:
a first draft sequence of the plurality of draft sequences comprises a first draft token associated with a first respective conditional probability;
a second draft sequence of the plurality of draft sequences comprises a second draft token associated with a second respective conditional probability; and
evaluating comprises evaluating the first respective conditional probability and second respective conditional probability in parallel.

### Claim 15 (depends on 13)

The computing system of claim 13, wherein:
the respective conditional probability is a respective second-model conditional probability;
generating a draft sequence comprises evaluating, using the one or more first machine-learned sequence processing models and based on the input context, a respective first-model conditional probability for each of one or more tokens of each of the plurality of draft sequences; and
selecting one or more tokens for inclusion in an output sequence comprises determining, based on a comparison between at least one respective first-model conditional probability and at least one respective second-model conditional probability, whether to include a draft token associated with the at least one respective first-model conditional probability and the at least one respective second-model conditional probability.

### Claim 16 (depends on 15)

The computing system of claim 15, wherein determining whether to include the draft token comprises:
generating a random value;
determining, based at least in part on the respective first-model conditional probability and the respective second-model conditional probability, a sampling threshold; and
determining, based on a comparison between the random value and the sampling threshold, whether to include the draft token in the output sequence.

### Claim 17 (depends on 13)

The computing system of claim 13, wherein a probability distribution of the output sequence is equivalent to a probability distribution of the second machine-learned sequence processing model.

### Claim 18 (depends on 15)

The computing system of claim 15, wherein the draft token associated with the at least one respective first-model conditional probability and the at least one respective second-model conditional probability is not included in the output sequence, and further comprising:
determining, using a conditional probability distribution of the one or more first machine-learned sequence processing models and a conditional probability distribution of the second machine-learned sequence processing model, a residual probability distribution; and
determining, based on the residual probability distribution, an output token to include in the output sequence.

### Claim 19 (depends on 15)

The computing system of claim 15, wherein the draft token associated with the at least one respective first-model conditional probability and the at least one respective second-model conditional probability is included in the output sequence, and further comprising:
determining, using the second machine-learned sequence processing model and based at least in part on the input context and the draft token associated with the at least one respective first-model conditional probability and the at least one respective second-model conditional probability, a conditional probability distribution of the second machine-learned sequence processing model;
randomly sampling an additional output token based on the conditional probability distribution; and
including the additional output token in the output sequence.

### Claim 20

One or more non-transitory computer-readable media storing instructions that are executable by a computing system to perform one or more operations, the operations comprising:
obtaining an input context;
generating, using one or more first machine-learned sequence processing models and based on the input context, a plurality of draft sequences, wherein each draft sequence of the plurality of draft sequences is configured to immediately follow the input context;
evaluating, using a second, different machine-learned sequence processing model and based on the input context, a respective conditional probability for each of one or more tokens of each of the plurality of draft sequences;
selecting one or more of the tokens from one of the plurality of draft sequences for inclusion in an output sequence based on the respective conditional probabilities; and
providing the output sequence as output.
