File size: 27,934 Bytes
9c0a4e6
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
"""Approximate Speculative Decoding (ASD) as a Transformers custom generation method.

ASD is a training-free, deterministic acceptance policy for *greedy* assisted
decoding. Instead of discarding the whole draft suffix at the first position
where the draft token differs from the target argmax, it accepts a draft prefix
while ALL of the following hold:

1. request-level cumulative regret ``sum(r_j) <= assistant_asd_budget``;
2. local regret ``r_i / (K - i) <= assistant_asd_local_ratio``
   (suffix-value weighting: later draft positions get less slack);
3. relaxed mismatches in the current block ``<= assistant_asd_max_mismatches``.

Here ``r_i = max_v z_i(v) - z_i(x_i)`` is the local regret of draft token
``x_i`` under target logits ``z_i`` (``r_i = 0`` iff ``x_i`` is the target
argmax) and ``K`` is the candidate length. The policy uses *target logits only*
(no draft logits, no RNG) and exactly reduces to strict greedy verification
when the budget, the local ratio, or the mismatch cap is ``0``.

Paper: "ASD: Approximate Speculative Decoding", https://arxiv.org/abs/2608.03447

Implementation notes
--------------------
`generate` below mirrors the signature of `GenerationMixin.generate` (this is
the contract for Hub custom generation methods). It validates the ASD knobs and
then temporarily swaps `type(model)._assisted_decoding` for the ASD loop in
this file, so the standard `generate()` pipeline (logits processors, stopping
criteria, cache preparation, streamer, assistant handling, ...) runs unchanged.
The swap is reverted in a `finally` block.

`_asd_assisted_decoding` is a byte-faithful copy of
`transformers.generation.utils.GenerationMixin._assisted_decoding`
(transformers v5.19.0) with exactly three changes, marked `ASD-CHANGE`:
  1. request-level risk state is initialised before the decode loop;
  2. the strict greedy prefix match (upstream "Case 2") is replaced by the ASD
     acceptance rule (the sampling path is rejected in `generate`, so upstream
     "Case 1" is unreachable here);
  3. the risk account is charged after the EOS/length crop, only for draft
     tokens that were actually committed.
"""

from __future__ import annotations

import copy
import math
from typing import TYPE_CHECKING, Any, NamedTuple

import torch
from transformers import GenerationMixin
from transformers.cache_utils import StaticCache
from transformers.generation.candidate_generator import (
    AssistedCandidateGenerator,
    MTPCandidateGenerator,
    _prepare_attention_mask,
    _prepare_position_ids,
    _prepare_token_type_ids,
)
from transformers.generation.utils import (
    ALL_CACHE_NAMES,
    GenerateDecoderOnlyOutput,
    GenerateEncoderDecoderOutput,
    _split_model_outputs,
)

if TYPE_CHECKING:
    from transformers import (
        GenerationConfig,
        LogitsProcessorList,
        PreTrainedModel,
        PreTrainedTokenizerBase,
        StoppingCriteriaList,
    )
    from transformers.generation import BaseStreamer
    from transformers.generation.utils import GenerateNonBeamOutput


class _ASDVerification(NamedTuple):
    """Resolved ASD acceptance parameters for one request."""

    budget: float  # request-level cumulative regret budget B (inf = uncapped)
    local_ratio: float  # per-token regret / suffix-value cap g (inf = uncapped)
    max_mismatches: int  # per-block relaxed mismatch cap m
    strict_identity: bool  # True => exactly upstream strict argmax verification


_ASD_CONFIG_ATTR = "_asd_verification"


def _resolve_asd_params(
    budget: Any,
    local_ratio: Any,
    max_mismatches: Any,
) -> _ASDVerification:
    """Validate the user-facing knobs and return the resolved acceptance config.

    All three knobs ``None`` means "ASD disabled": the policy is strict argmax
    verification, i.e. token-identical to native assisted decoding. When any
    knob is set, the unset ones default to their permissive limit. A value of
    ``0`` for any knob forces strict verification (the paper's correctness
    baseline).
    """
    all_none = budget is None and local_ratio is None and max_mismatches is None

    if budget is not None:
        budget = float(budget)
        if not math.isfinite(budget) or budget < 0:
            raise ValueError(f"`assistant_asd_budget` must be a finite float >= 0, got {budget}.")
    else:
        budget = math.inf

    if local_ratio is not None:
        local_ratio = float(local_ratio)
        if not math.isfinite(local_ratio) or local_ratio < 0:
            raise ValueError(
                f"`assistant_asd_local_ratio` must be a finite float >= 0, got {local_ratio}."
            )
    else:
        local_ratio = math.inf

    if max_mismatches is not None:
        max_mismatches = int(max_mismatches)
        if max_mismatches < 0:
            raise ValueError(f"`assistant_asd_max_mismatches` must be an int >= 0, got {max_mismatches}.")
    else:
        max_mismatches = 2**31 - 1

    strict_identity = all_none or budget == 0.0 or local_ratio == 0.0 or max_mismatches == 0
    return _ASDVerification(budget, local_ratio, max_mismatches, strict_identity)


def _effective_generation_value(name: str, kwargs: dict, generation_config, model):
    """Resolve a generation flag the way `generate()` would: kwargs > config arg > model config."""
    if name in kwargs:
        return kwargs[name]
    if generation_config is not None and getattr(generation_config, name, None) is not None:
        return getattr(generation_config, name)
    return getattr(model.generation_config, name, None)


def _choose_asd_prefix(
    candidate_new_tokens: torch.LongTensor,
    new_logits: torch.FloatTensor,
    target_argmax: torch.LongTensor,
    config: _ASDVerification,
) -> tuple[int, list[float], list[bool]]:
    """Return ``(accepted, regrets, mismatches)`` for one draft block.

    ``candidate_new_tokens`` is ``(1, K)``, ``new_logits`` is ``(1, K, V)`` (the
    processed target logits at each drafted position) and ``target_argmax`` is
    ``(1, K)``: the target argmax token per position, computed with the exact
    same ``argmax`` op upstream strict verification uses, so the strict path is
    token-identical by construction. ``accepted`` is the longest prefix
    satisfying all ASD constraints; ``regrets``/``mismatches`` are the
    per-position values so the caller can charge the budget after the
    EOS/length crop, only for tokens that were actually committed.
    """
    candidate_length = candidate_new_tokens.shape[1]
    if candidate_length == 0:
        return 0, [], []

    # r_i = max_v z_i(v) - z_i(x_i); mismatch_i = (x_i != argmax_v z_i(v))
    top_logits = new_logits[0].max(dim=-1).values
    draft_logits = new_logits[0].gather(-1, candidate_new_tokens[0].unsqueeze(-1)).squeeze(-1)
    regrets = (top_logits - draft_logits).clamp_min(0.0).tolist()
    mismatches = (candidate_new_tokens[0] != target_argmax[0]).tolist()

    # `config.budget` is the *remaining* request budget for this block: the caller
    # (`_asd_assisted_decoding`) subtracts the running spend before calling.
    remaining = max(0.0, config.budget)
    cumulative_risk = 0.0
    cumulative_relaxed = 0
    accepted = 0
    for index in range(candidate_length):
        mismatch = mismatches[index]
        regret = regrets[index]
        value = float(candidate_length - index)  # suffix-value weighting

        if mismatch:
            if config.strict_identity:
                break
            cumulative_risk += regret
            cumulative_relaxed += 1

        worthwhile = (not mismatch) or (regret / value <= config.local_ratio)
        affordable = cumulative_risk <= remaining + 1e-9
        within_cap = cumulative_relaxed <= config.max_mismatches

        if not (worthwhile and affordable and within_cap):
            break
        accepted = index + 1

    return accepted, regrets, mismatches


def _asd_assisted_decoding(
    self: "PreTrainedModel",
    input_ids: torch.LongTensor,
    logits_processor: "LogitsProcessorList",
    stopping_criteria: "StoppingCriteriaList",
    generation_config: "GenerationConfig",
    synced_gpus: bool = False,
    streamer: "BaseStreamer | None" = None,
    inputs_tensor: torch.FloatTensor | None = None,
    assistant_model: "PreTrainedModel | None" = None,
    assistant_tokenizer: "PreTrainedTokenizerBase | None" = None,
    tokenizer: "PreTrainedTokenizerBase | None" = None,
    **model_kwargs,
) -> "GenerateNonBeamOutput | torch.LongTensor":
    """Drop-in replacement for `GenerationMixin._assisted_decoding` (greedy only).

    Identical to upstream except for the ASD changes marked `ASD-CHANGE`.
    """
    asd: _ASDVerification | None = getattr(self, _ASD_CONFIG_ATTR, None)
    if asd is None:  # defensive: behave exactly like upstream strict verification
        asd = _ASDVerification(math.inf, math.inf, 2**31 - 1, True)

    # The cache must be dynamic for assisted generation, and the check must happen AFTER preparing cache
    if not model_kwargs["use_cache"]:
        raise ValueError("assisted generate requires `use_cache=True`")
    if (
        generation_config.cache_implementation in ["static", "hybrid", "sliding_window"]
        or type(model_kwargs.get("past_key_values")) is StaticCache
    ):
        raise ValueError("assisted generate is not supported with Static cache classes`")

    # Same tensor the stopping criteria are built from
    eos_token_id = getattr(generation_config, "_eos_token_tensor", None)

    # Make sure we can record past on the cache
    cache = model_kwargs.get("past_key_values")
    if cache is None:
        raise RuntimeError("assisted decoding requires a cache")
    cache.activate_past_recording()

    # Get the candidate generator, given the parameterization
    candidate_generator = self._get_candidate_generator(
        generation_config=generation_config,
        input_ids=input_ids,
        inputs_tensor=inputs_tensor,
        assistant_model=assistant_model,
        logits_processor=logits_processor,
        target_tokenizer=tokenizer,
        assistant_tokenizer=assistant_tokenizer,
        model_kwargs=model_kwargs,
    )
    # init values
    output_attentions = generation_config.output_attentions
    output_hidden_states = generation_config.output_hidden_states
    output_scores = generation_config.output_scores
    output_logits = generation_config.output_logits
    return_dict_in_generate = generation_config.return_dict_in_generate

    # init attention / hidden states / scores tuples
    scores = () if (return_dict_in_generate and output_scores) else None
    raw_logits = () if (return_dict_in_generate and output_logits) else None
    decoder_attentions = () if (return_dict_in_generate and output_attentions) else None
    cross_attentions = () if (return_dict_in_generate and output_attentions) else None
    decoder_hidden_states = () if (return_dict_in_generate and output_hidden_states) else None

    # if model is an encoder-decoder, retrieve encoder attention weights and hidden states
    if return_dict_in_generate and self.config.is_encoder_decoder:
        encoder_attentions = model_kwargs["encoder_outputs"].get("attentions") if output_attentions else None
        encoder_hidden_states = (
            model_kwargs["encoder_outputs"].get("hidden_states") if output_hidden_states else None
        )

    # keep track of which sequences are already finished
    batch_size, cur_len = input_ids.shape[:2]
    if batch_size > 1:
        raise ValueError("assisted generate is only supported for batch_size = 1")
    unfinished_sequences = torch.ones(batch_size, dtype=torch.long, device=input_ids.device)

    this_peer_finished = False
    is_first_iteration = True  # to preserve the same API in the output as other generation methods
    outputs = None
    n_matches = 0
    total_risk_spent = 0.0  # ASD-CHANGE (1): request-level cumulative regret account
    while self._has_unfinished_sequences(this_peer_finished, synced_gpus, device=input_ids.device):
        cur_len = input_ids.shape[1]

        #  1. Fetch candidate sequences from a `CandidateGenerator` and move to the correct device
        if candidate_generator.requires_model_outputs:
            candidate_input_ids, candidate_logits = candidate_generator.get_candidates(
                input_ids,
                model_kwargs=model_kwargs,
                model_outputs=outputs,
                is_first_iteration=is_first_iteration,
                n_last_matches=n_matches,
            )
        else:
            candidate_input_ids, candidate_logits = candidate_generator.get_candidates(input_ids)
        candidate_input_ids = candidate_input_ids.to(self.device)
        if candidate_logits is not None:
            candidate_logits = candidate_logits.to(self.device)

        candidate_length = candidate_input_ids.shape[1] - input_ids.shape[1]

        # 2. Use the original model to obtain the next token logits given the candidate sequence. We obtain
        # `candidate_length + 1` relevant logits from this process: in the event that all candidates are correct,
        # we use this forward pass to also pick the subsequent logits in the original model.

        # 2.1. Prepare the model inputs
        candidate_kwargs = copy.copy(model_kwargs)
        candidate_kwargs = _prepare_attention_mask(
            candidate_kwargs, candidate_input_ids.shape[1], self.config.is_encoder_decoder
        )
        candidate_kwargs = _prepare_token_type_ids(candidate_kwargs, candidate_input_ids.shape[1])
        if (position_ids := candidate_kwargs.get("position_ids")) is not None and candidate_length > 0:
            new_length = candidate_length + position_ids.shape[-1]
            candidate_kwargs = _prepare_position_ids(candidate_kwargs, new_length, self.config.is_encoder_decoder)

        next_sequence_length = candidate_length + 1 if not is_first_iteration else None
        model_inputs = self.prepare_inputs_for_generation(
            candidate_input_ids,
            next_sequence_length=next_sequence_length,
            is_first_iteration=is_first_iteration,
            **candidate_kwargs,
        )

        if "logits_to_keep" in model_inputs:
            model_inputs["logits_to_keep"] = candidate_length + 1

        # We usually need to force returning hidden_states and some others if the candidate_generator requires the model's outputs
        if candidate_generator.requires_model_outputs:
            model_inputs |= candidate_generator.model_kwargs_overrides

        # 2.2. Run a forward pass on the candidate sequence
        outputs = self(**model_inputs)

        # 2.3. Process the new logits
        # .float() is needed to retain precision for later logits manipulations
        new_logits = outputs.logits[:, -candidate_length - 1 :].to(
            dtype=torch.float32, device=input_ids.device
        )  # excludes the input prompt if present
        next_token_logits = new_logits.clone()
        if len(logits_processor) > 0:
            for i in range(candidate_length + 1):
                new_logits[:, i, :] = logits_processor(candidate_input_ids[:, : cur_len + i], new_logits[:, i, :])

        # 3. Select the accepted tokens.
        # ASD-CHANGE (2): the greedy verification below replaces upstream's strict argmax
        # prefix match with the ASD acceptance rule. The sampling path ("Case 1") and the
        # `assistant_ensemble_weight` variant are unreachable: `generate()` rejects
        # `do_sample=True` and `assistant_ensemble_weight` before installing this method.
        candidate_new_tokens = candidate_input_ids[:, cur_len:]
        # Same op as upstream strict verification, so strict mode matches by construction.
        target_argmax = new_logits.argmax(dim=-1)  # (1, candidate_length + 1)
        block_config = _ASDVerification(
            budget=asd.budget - total_risk_spent,  # remaining request budget for this block
            local_ratio=asd.local_ratio,
            max_mismatches=asd.max_mismatches,
            strict_identity=asd.strict_identity,
        )
        accepted, regrets, mismatches = _choose_asd_prefix(
            candidate_new_tokens, new_logits[:, :-1, :], target_argmax[:, :-1], block_config
        )

        # Commit the accepted draft prefix, then the target argmax at the first position
        # after it as the bonus token (deterministic, exactly as upstream: upstream's
        # `selected_tokens[:, :n_matches + 1]` is the argmax at position `n_matches`).
        bonus_token = target_argmax[:, accepted : accepted + 1]
        if accepted > 0:
            valid_tokens = torch.cat([candidate_new_tokens[:, :accepted], bonus_token], dim=-1)
        else:
            valid_tokens = bonus_token
        n_matches = accepted

        # Whenever we are drafting several tokens at once with the candidate without capping its draft (e.g. MTP), we need to
        # make sure that we did not just validate tokens outside the max length, or outside an eos token
        # Note that we should technically crop based on other stopping criteria as well in all generality, not only EOS and Length
        tokens_budget = generation_config.max_length - input_ids.shape[1]
        # This is for the max length
        if valid_tokens.shape[1] > tokens_budget:
            valid_tokens = valid_tokens[:, :tokens_budget]
        # This is for eos tokens
        if eos_token_id is not None:
            # We are restricted to batch_size == 1, so we can squeeze the batch dim to simplify
            eos_positions = torch.isin(valid_tokens.squeeze(0), eos_token_id.to(valid_tokens.device)).nonzero()
            if eos_positions.numel() > 0:
                num_drafted = eos_positions[0].item() + 1
                valid_tokens = valid_tokens[:, :num_drafted]
        # Recompute how many matches we accepted if we just cropped above due to length/eos
        n_matches = valid_tokens.shape[1] - 1

        # ASD-CHANGE (3): charge the request-level regret account after the crop, only
        # for relaxed (mismatched) draft tokens that were actually committed.
        for index in range(max(0, min(n_matches, accepted))):
            if mismatches[index]:
                total_risk_spent += regrets[index]

        # 4. Update variables according to the number of matching assistant tokens. Remember: the token generated
        # by the model after the last candidate match is also valid, as it is generated from a correct sequence.
        # Because of this last token, assisted generation search reduces to a normal greedy search/sample if there
        # is no match.

        # 4.1. Get the valid continuation, after the matching tokens
        input_ids = torch.cat((input_ids, valid_tokens), dim=-1)
        if streamer is not None:
            streamer.put(valid_tokens.cpu())
        new_cur_len = input_ids.shape[1]

        # 4.2. Discard past key values relative to unused assistant tokens if any - if `number_of_tokens_to_crop == 0`, `crop` will
        # still take care of shrinking back sliding window or linear attention cache layers back to their max size, so it's important
        # to call it still
        number_of_tokens_to_crop = candidate_length - n_matches
        outputs.past_key_values.crop(-number_of_tokens_to_crop)

        # 5. Update the candidate generation strategy if needed
        candidate_generator.update_candidate_strategy(input_ids, new_logits, n_matches)

        # synced_gpus: don't waste resources running the code we don't need; kwargs must be updated before skipping
        model_kwargs = self._update_model_kwargs_for_generation(
            outputs,
            model_kwargs,
            is_encoder_decoder=self.config.is_encoder_decoder,
            num_new_tokens=n_matches + 1,
        )
        if synced_gpus and this_peer_finished:
            continue

        # Store scores, attentions and hidden_states when required
        # Assistant: modified to append one tuple element per token, as in the other generation methods.
        if return_dict_in_generate:
            newly_added_length = n_matches + 1
            if output_scores:
                scores += tuple(new_logits[:, i, :] for i in range(newly_added_length))
            if output_logits:
                raw_logits += tuple(next_token_logits[:, i, :] for i in range(newly_added_length))

            newly_added_length = new_cur_len if is_first_iteration else newly_added_length
            if output_attentions:
                if self.config.is_encoder_decoder:
                    cross_attentions = _split_model_outputs(
                        cross_attentions, outputs.cross_attentions, cur_len, newly_added_length
                    )
                    decoder_attentions = _split_model_outputs(
                        decoder_attentions,
                        outputs.decoder_attentions,
                        cur_len,
                        newly_added_length,
                        is_decoder_attention=True,
                    )
                # some (V)LLMs have hard requirement on SDPA and thus never return attn
                elif outputs.attentions[0] is not None:
                    decoder_attentions = _split_model_outputs(
                        decoder_attentions,
                        outputs.attentions,
                        cur_len,
                        newly_added_length,
                        is_decoder_attention=True,
                    )
            if output_hidden_states:
                if self.config.is_encoder_decoder:
                    decoder_hidden_states = _split_model_outputs(
                        decoder_hidden_states, outputs.decoder_hidden_states, cur_len, newly_added_length
                    )
                else:
                    decoder_hidden_states = _split_model_outputs(
                        decoder_hidden_states, outputs.hidden_states, cur_len, newly_added_length
                    )

        unfinished_sequences = unfinished_sequences & ~stopping_criteria(input_ids, scores)
        this_peer_finished = unfinished_sequences.max() == 0
        is_first_iteration = False

    if streamer is not None:
        streamer.end()

    if (
        isinstance(candidate_generator, AssistedCandidateGenerator)
        and not isinstance(candidate_generator, MTPCandidateGenerator)
        and candidate_generator.assistant_model.generation_config.num_assistant_tokens_schedule == "heuristic"
    ):
        candidate_generator.assistant_model.generation_config.num_assistant_tokens = (
            candidate_generator.num_assistant_tokens
        )
    if return_dict_in_generate:
        cache = None
        if any(cache_key in model_kwargs for cache_key in ALL_CACHE_NAMES):
            cache_key = next(cache_key for cache_key in ALL_CACHE_NAMES if cache_key in model_kwargs)
            cache = model_kwargs[cache_key]
        if self.config.is_encoder_decoder:
            return GenerateEncoderDecoderOutput(
                sequences=input_ids,
                scores=scores,
                logits=raw_logits,
                encoder_attentions=encoder_attentions,
                encoder_hidden_states=encoder_hidden_states,
                decoder_attentions=decoder_attentions,
                cross_attentions=cross_attentions,
                decoder_hidden_states=decoder_hidden_states,
                past_key_values=cache,
            )
        else:
            return GenerateDecoderOnlyOutput(
                sequences=input_ids,
                scores=scores,
                logits=raw_logits,
                attentions=decoder_attentions,
                hidden_states=decoder_hidden_states,
                past_key_values=cache,
            )
    else:
        return input_ids


def generate(
    model: "PreTrainedModel",
    inputs: torch.Tensor | None = None,
    generation_config: "GenerationConfig | None" = None,
    logits_processor: "LogitsProcessorList | None" = None,
    stopping_criteria: "StoppingCriteriaList | None" = None,
    prefix_allowed_tokens_fn=None,
    synced_gpus: bool | None = None,
    assistant_model: "PreTrainedModel | None" = None,
    streamer: "BaseStreamer | None" = None,
    negative_prompt_ids: torch.Tensor | None = None,
    negative_prompt_attention_mask: torch.Tensor | None = None,
    assistant_asd_budget: float | None = None,
    assistant_asd_local_ratio: float | None = None,
    assistant_asd_max_mismatches: int | None = None,
    **kwargs,
):
    """Custom generation entry point loaded from the Hub.

    Accepts every argument of `GenerationMixin.generate` plus the three ASD
    knobs below, then runs the standard `generate()` pipeline with the ASD
    assisted-decoding loop installed. With no ASD knob set (or any knob equal
    to ``0``), the result is token-identical to native greedy assisted decoding.

    Parameters
    ----------
    assistant_asd_budget:
        Request-level cumulative regret budget ``B >= 0``. ``None`` (default)
        leaves the budget uncapped; ``0.0`` forces strict verification.
    assistant_asd_local_ratio:
        Per-token cap ``g >= 0`` on ``r_i / (K - i)``. ``None`` leaves it
        uncapped; ``0.0`` forces strict verification.
    assistant_asd_max_mismatches:
        Per-block cap ``m >= 0`` on relaxed mismatches. ``None`` leaves it
        uncapped; ``0`` forces strict verification.
    """
    asd = _resolve_asd_params(assistant_asd_budget, assistant_asd_local_ratio, assistant_asd_max_mismatches)
    any_asd_knob = any(
        knob is not None
        for knob in (assistant_asd_budget, assistant_asd_local_ratio, assistant_asd_max_mismatches)
    )

    if _effective_generation_value("do_sample", kwargs, generation_config, model) is True:
        raise ValueError(
            "ASD is a deterministic verifier for greedy decoding (`do_sample=False`). "
            "For the sampling path, use native assisted decoding with `assistant_ensemble_weight` instead."
        )
    if _effective_generation_value("assistant_ensemble_weight", kwargs, generation_config, model) is not None:
        raise ValueError(
            "`assistant_ensemble_weight` and ASD are mutually exclusive verification relaxations. "
            "Please use only one of them."
        )
    if (
        any_asd_knob
        and assistant_model is None
        and _effective_generation_value("prompt_lookup_num_tokens", kwargs, generation_config, model) is None
    ):
        raise ValueError(
            "ASD knobs require a draft source: pass `assistant_model` "
            "(or set `prompt_lookup_num_tokens` for prompt-lookup drafting)."
        )

    # Install the ASD loop as the model class's assisted-decoding method for the
    # duration of this call. `generate()` dispatches assisted generation through
    # `getattr(type(self), "_assisted_decoding")`, so a class-level swap is the
    # supported seam; it is reverted in `finally` below.
    cls = type(model)
    was_inherited = "_assisted_decoding" not in cls.__dict__
    original = cls._assisted_decoding
    cls._assisted_decoding = _asd_assisted_decoding
    setattr(model, _ASD_CONFIG_ATTR, asd)
    try:
        return GenerationMixin.generate(
            model,
            inputs=inputs,
            generation_config=generation_config,
            logits_processor=logits_processor,
            stopping_criteria=stopping_criteria,
            prefix_allowed_tokens_fn=prefix_allowed_tokens_fn,
            synced_gpus=synced_gpus,
            assistant_model=assistant_model,
            streamer=streamer,
            negative_prompt_ids=negative_prompt_ids,
            negative_prompt_attention_mask=negative_prompt_attention_mask,
            **kwargs,
        )
    finally:
        if was_inherited:
            del cls._assisted_decoding
        else:
            cls._assisted_decoding = original
        try:
            delattr(model, _ASD_CONFIG_ATTR)
        except AttributeError:
            pass