schedule_batch.py 30.5 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
"""
Copyright 2023-2024 SGLang Team
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

    http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
"""

16
"""Meta data for requests and batches"""
Lianmin Zheng's avatar
Lianmin Zheng committed
17

Ying Sheng's avatar
Ying Sheng committed
18
import logging
19
import warnings
20
from dataclasses import dataclass
21
from typing import List, Optional, Union
Lianmin Zheng's avatar
Lianmin Zheng committed
22
23

import torch
24
import torch.distributed as dist
25
from flashinfer.sampling import top_k_top_p_sampling_from_probs
26
from vllm.distributed import get_tensor_model_parallel_group
Liangsheng Yin's avatar
Liangsheng Yin committed
27

28
import sglang.srt.sampling.penaltylib as penaltylib
Liangsheng Yin's avatar
Liangsheng Yin committed
29
from sglang.global_config import global_config
30
31
from sglang.srt.constrained import RegexGuide
from sglang.srt.constrained.jump_forward import JumpForwardMap
32
from sglang.srt.mem_cache.base_prefix_cache import BasePrefixCache
33
from sglang.srt.mem_cache.chunk_cache import ChunkCache
34
from sglang.srt.mem_cache.memory_pool import BaseTokenToKVPool, ReqToTokenPool
Liangsheng Yin's avatar
Liangsheng Yin committed
35
36

INIT_INCREMENTAL_DETOKENIZATION_OFFSET = 5
Lianmin Zheng's avatar
Lianmin Zheng committed
37

38
39
40
41
42
# Put some global args for easy access
global_server_args_dict = {
    "disable_flashinfer": False,
    "disable_flashinfer_sampling": False,
    "attention_reduce_in_fp32": False,
43
    "enable_mla": False,
44
45
}

Lianmin Zheng's avatar
Lianmin Zheng committed
46

Ying Sheng's avatar
Ying Sheng committed
47
48
49
logger = logging.getLogger(__name__)


50
51
52
class BaseFinishReason:
    def __init__(self, is_error: bool = False):
        self.is_error = is_error
Lianmin Zheng's avatar
Lianmin Zheng committed
53

54
55
56
57
58
    def __str__(self):
        raise NotImplementedError("Subclasses must implement this method")


class FINISH_MATCHED_TOKEN(BaseFinishReason):
Mingyi's avatar
Mingyi committed
59
    def __init__(self, matched: Union[int, List[int]]):
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
        super().__init__()
        self.matched = matched

    def __str__(self) -> str:
        return f"FINISH_MATCHED_TOKEN: {self.matched}"


class FINISH_LENGTH(BaseFinishReason):
    def __init__(self, length: int):
        super().__init__()
        self.length = length

    def __str__(self) -> str:
        return f"FINISH_LENGTH: {self.length}"


class FINISH_MATCHED_STR(BaseFinishReason):
    def __init__(self, matched: str):
        super().__init__()
        self.matched = matched

    def __str__(self) -> str:
        return f"FINISH_MATCHED_STR: {self.matched}"


class FINISH_ABORT(BaseFinishReason):
    def __init__(self):
        super().__init__(is_error=True)

    def __str__(self) -> str:
        return "FINISH_ABORT"
91

Lianmin Zheng's avatar
Lianmin Zheng committed
92
93

class Req:
94
95
    """Store all inforamtion of a request."""

Liangsheng Yin's avatar
Liangsheng Yin committed
96
    def __init__(self, rid, origin_input_text, origin_input_ids):
97
        # Input and output info
Lianmin Zheng's avatar
Lianmin Zheng committed
98
        self.rid = rid
Liangsheng Yin's avatar
Liangsheng Yin committed
99
        self.origin_input_text = origin_input_text
Liangsheng Yin's avatar
Liangsheng Yin committed
100
        self.origin_input_ids_unpadded = origin_input_ids  # Before image padding
Liangsheng Yin's avatar
Liangsheng Yin committed
101
        self.origin_input_ids = origin_input_ids
Liangsheng Yin's avatar
Liangsheng Yin committed
102
        self.output_ids = []  # Each decode stage's output ids
103
        self.fill_ids = None  # fill_ids = origin_input_ids + output_ids
Liangsheng Yin's avatar
Liangsheng Yin committed
104

105
106
107
        # Memory info
        self.req_pool_idx = None

108
        # For incremental decoding
109
110
111
112
113
114
115
116
        # ----- | --------- read_ids -------|
        # ----- |   surr_ids  |
        # xxxxx | xxxxxxxxxxx | xxxxxxxxxxx |
        # ----- ^ ----------- ^ ----------- ^
        # ----- 1 ----------- 2 ----------- 3
        # 1: surr_offset
        # 2: read_offset
        # 3: last token
117
        self.vid = 0  # version id to sync decode status with in detokenizer_manager
Liangsheng Yin's avatar
Liangsheng Yin committed
118
119
120
        self.decoded_text = ""
        self.surr_offset = None  # Surrounding offset to defeat the cleanup algorithm
        self.read_offset = None
121

122
123
124
        # The number of decoded tokens for token usage report. Note that
        # this does not include the jump forward tokens.
        self.completion_tokens_wo_jump_forward = 0
125

126
        # For vision input
Lianmin Zheng's avatar
Lianmin Zheng committed
127
        self.pixel_values = None
shiyi.c_98's avatar
shiyi.c_98 committed
128
        self.image_size = None
129
        self.image_offset = None
130
        self.pad_value = None
131

132
133
134
135
136
        # Prefix info
        self.extend_input_len = 0
        self.prefix_indices = []
        self.last_node = None

137
        # Sampling parameters
Lianmin Zheng's avatar
Lianmin Zheng committed
138
139
140
        self.sampling_params = None
        self.stream = False

141
        # Check finish
142
        self.tokenizer = None
143
        self.finished_reason = None
Lianmin Zheng's avatar
Lianmin Zheng committed
144

145
146
        # Logprobs
        self.return_logprob = False
147
        self.embedding = None
148
149
150
        self.logprob_start_len = 0
        self.top_logprobs_num = 0
        self.normalized_prompt_logprob = None
151
152
153
154
        self.input_token_logprobs = None
        self.input_top_logprobs = None
        self.output_token_logprobs = []
        self.output_top_logprobs = []
Liangsheng Yin's avatar
Liangsheng Yin committed
155
156
157
        # The tokens is prefilled but need to be considered as decode tokens
        # and should be updated for the decode logprobs
        self.last_update_decode_tokens = 0
Lianmin Zheng's avatar
Lianmin Zheng committed
158

159
        # Constrained decoding
Liangsheng Yin's avatar
Liangsheng Yin committed
160
161
162
        self.regex_fsm: RegexGuide = None
        self.regex_fsm_state: int = 0
        self.jump_forward_map: JumpForwardMap = None
Liangsheng Yin's avatar
Liangsheng Yin committed
163

164
165
166
167
    # whether request reached finished condition
    def finished(self) -> bool:
        return self.finished_reason is not None

168
    def init_next_round_input(self, tree_cache: Optional[BasePrefixCache] = None):
169
        self.fill_ids = self.origin_input_ids + self.output_ids
170
171
172
173
        if tree_cache is not None:
            self.prefix_indices, self.last_node = tree_cache.match_prefix(
                rid=self.rid, key=self.adjust_max_prefix_ids()
            )
174
        self.extend_input_len = len(self.fill_ids) - len(self.prefix_indices)
175

176
    def adjust_max_prefix_ids(self):
177
178
        self.fill_ids = self.origin_input_ids + self.output_ids
        input_len = len(self.fill_ids)
Liangsheng Yin's avatar
Liangsheng Yin committed
179
180
181
182
183
184
        max_prefix_len = input_len

        if self.sampling_params.max_new_tokens > 0:
            # Need at least one token to compute logits
            max_prefix_len = min(max_prefix_len, input_len - 1)

185
        if self.return_logprob:
Liangsheng Yin's avatar
Liangsheng Yin committed
186
187
188
189
190
            max_prefix_len = min(max_prefix_len, self.logprob_start_len)

            if self.normalized_prompt_logprob is None:
                # Need at least two tokens to compute normalized logprob
                max_prefix_len = min(max_prefix_len, input_len - 2)
191

192
        return self.fill_ids[:max_prefix_len]
193

Liangsheng Yin's avatar
Liangsheng Yin committed
194
    # Based on https://github.com/vllm-project/vllm/blob/7a64d24aad69e4d2548aa0bf528d9fe63428ab01/vllm/transformers_utils/detokenizer.py#L194-L313
195
    def init_incremental_detokenize(self):
Liangsheng Yin's avatar
Liangsheng Yin committed
196
197
198
199
200
201
202
203
204
        first_iter = self.surr_offset is None or self.read_offset is None

        if first_iter:
            self.read_offset = len(self.origin_input_ids_unpadded)
            self.surr_offset = max(
                self.read_offset - INIT_INCREMENTAL_DETOKENIZATION_OFFSET, 0
            )

        all_ids = self.origin_input_ids_unpadded + self.output_ids
205
        return all_ids[self.surr_offset :], self.read_offset - self.surr_offset
Liangsheng Yin's avatar
Liangsheng Yin committed
206

207
    def get_next_inc_detokenization(self):
208
209
        if self.tokenizer is None:
            return False, ""
210
211
        read_ids, read_offset = self.init_incremental_detokenize()
        surr_ids = read_ids[:read_offset]
Liangsheng Yin's avatar
Liangsheng Yin committed
212
213
214
215
216

        surr_text = self.tokenizer.decode(
            surr_ids,
            skip_special_tokens=self.sampling_params.skip_special_tokens,
            spaces_between_special_tokens=self.sampling_params.spaces_between_special_tokens,
Liangsheng Yin's avatar
Liangsheng Yin committed
217
        )
Liangsheng Yin's avatar
Liangsheng Yin committed
218
219
220
221
222
223
224
        new_text = self.tokenizer.decode(
            read_ids,
            skip_special_tokens=self.sampling_params.skip_special_tokens,
            spaces_between_special_tokens=self.sampling_params.spaces_between_special_tokens,
        )

        if len(new_text) > len(surr_text) and not new_text.endswith("�"):
225
            return True, new_text[len(surr_text) :]
Liangsheng Yin's avatar
Liangsheng Yin committed
226
227

        return False, ""
Lianmin Zheng's avatar
Lianmin Zheng committed
228

229
    def check_finished(self):
230
        if self.finished():
231
232
            return

Liangsheng Yin's avatar
Liangsheng Yin committed
233
        if len(self.output_ids) >= self.sampling_params.max_new_tokens:
234
235
236
            self.finished_reason = FINISH_LENGTH(
                length=self.sampling_params.max_new_tokens
            )
237
238
            return

239
        last_token_id = self.output_ids[-1]
240
241
242
243
244
245

        matched_eos = last_token_id in self.sampling_params.stop_token_ids

        if self.tokenizer is not None:
            matched_eos |= last_token_id == self.tokenizer.eos_token_id

246
        if matched_eos and not self.sampling_params.ignore_eos:
247
248
249
            self.finished_reason = FINISH_MATCHED_TOKEN(matched=last_token_id)
            return

250
251
252
253
254
255
        if len(self.sampling_params.stop_strs) > 0:
            tail_str = self.tokenizer.decode(
                self.output_ids[-(self.sampling_params.stop_str_max_len + 1) :]
            )

            for stop_str in self.sampling_params.stop_strs:
Liangsheng Yin's avatar
Liangsheng Yin committed
256
                if stop_str in tail_str or stop_str in self.decoded_text:
257
                    self.finished_reason = FINISH_MATCHED_STR(matched=stop_str)
258
259
                    return

Liangsheng Yin's avatar
Liangsheng Yin committed
260
    def jump_forward_and_retokenize(self, jump_forward_str, next_state):
Liangsheng Yin's avatar
Liangsheng Yin committed
261
262
263
264
265
266
        if self.origin_input_text is None:
            # Recovering text can only use unpadded ids
            self.origin_input_text = self.tokenizer.decode(
                self.origin_input_ids_unpadded
            )

Liangsheng Yin's avatar
Liangsheng Yin committed
267
        all_text = self.origin_input_text + self.decoded_text + jump_forward_str
Liangsheng Yin's avatar
Liangsheng Yin committed
268
269
        all_ids = self.tokenizer.encode(all_text)
        prompt_tokens = len(self.origin_input_ids_unpadded)
Liangsheng Yin's avatar
Liangsheng Yin committed
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291

        if all_ids[prompt_tokens - 1] != self.origin_input_ids_unpadded[-1]:
            # TODO(lsyin): fix token fusion
            warnings.warn(
                "Token fusion between input and output, try to avoid this by removing the space at the end of the input."
            )
            return False

        old_output_ids = self.output_ids
        self.output_ids = all_ids[prompt_tokens:]
        self.decoded_text = self.decoded_text + jump_forward_str
        self.surr_offset = prompt_tokens
        self.read_offset = len(all_ids)

        # NOTE: A trick to reduce the surrouding tokens decoding overhead
        for i in range(0, INIT_INCREMENTAL_DETOKENIZATION_OFFSET):
            surr_text_ = self.tokenizer.decode(
                all_ids[self.read_offset - i : self.read_offset]
            )
            if not surr_text_.endswith("�"):
                self.surr_offset = self.read_offset - i
                break
Liangsheng Yin's avatar
Liangsheng Yin committed
292
293
294
295
296
297

        self.regex_fsm_state = next_state

        if self.return_logprob:
            # For fast-forward part's logprobs
            k = 0
Liangsheng Yin's avatar
Liangsheng Yin committed
298
299
            for i, old_id in enumerate(old_output_ids):
                if old_id == self.output_ids[i]:
Liangsheng Yin's avatar
Liangsheng Yin committed
300
301
302
                    k = k + 1
                else:
                    break
303
304
            self.output_token_logprobs = self.output_token_logprobs[:k]
            self.output_top_logprobs = self.output_top_logprobs[:k]
Liangsheng Yin's avatar
Liangsheng Yin committed
305
            self.logprob_start_len = prompt_tokens + k
Liangsheng Yin's avatar
Liangsheng Yin committed
306
            self.last_update_decode_tokens = len(self.output_ids) - k
307

Liangsheng Yin's avatar
Liangsheng Yin committed
308
        return True
Liangsheng Yin's avatar
Liangsheng Yin committed
309

Lianmin Zheng's avatar
Lianmin Zheng committed
310
    def __repr__(self):
Liangsheng Yin's avatar
Liangsheng Yin committed
311
        return f"rid(n={self.rid}, " f"input_ids={self.origin_input_ids}, "
Lianmin Zheng's avatar
Lianmin Zheng committed
312
313


314
@dataclass
315
class ScheduleBatch:
316
317
    """Store all inforamtion of a batch."""

318
    # Request, memory pool, and cache
319
320
    reqs: List[Req]
    req_to_token_pool: ReqToTokenPool
321
    token_to_kv_pool: BaseTokenToKVPool
322
    tree_cache: BasePrefixCache
323

324
    # Batched arguments to model runner
325
326
327
328
329
    input_ids: torch.Tensor = None
    req_pool_indices: torch.Tensor = None
    seq_lens: torch.Tensor = None
    position_ids_offsets: torch.Tensor = None
    out_cache_loc: torch.Tensor = None
330
    extend_num_tokens: int = None
Liangsheng Yin's avatar
Liangsheng Yin committed
331

332
    # For processing logprobs
333
    return_logprob: bool = False
334
    top_logprobs_nums: List[int] = None
335

336
    # Batched sampling params
337
338
339
    temperatures: torch.Tensor = None
    top_ps: torch.Tensor = None
    top_ks: torch.Tensor = None
340
    penalizer_orchestrator: penaltylib.BatchedPenalizerOrchestrator = None
341
342
343
344
    logit_bias: torch.Tensor = None

    @classmethod
    def init_new(cls, reqs, req_to_token_pool, token_to_kv_pool, tree_cache):
345
        return_logprob = any(req.return_logprob for req in reqs)
346
347
348
349
350
351

        return cls(
            reqs=reqs,
            req_to_token_pool=req_to_token_pool,
            token_to_kv_pool=token_to_kv_pool,
            tree_cache=tree_cache,
352
            return_logprob=return_logprob,
Lianmin Zheng's avatar
Lianmin Zheng committed
353
354
        )

355
356
357
    def batch_size(self):
        return len(self.reqs) if self.reqs is not None else 0

Lianmin Zheng's avatar
Lianmin Zheng committed
358
359
360
    def is_empty(self):
        return len(self.reqs) == 0

361
    def has_stream(self) -> bool:
362
        # Return whether batch has at least 1 streaming request
363
364
        return any(r.stream for r in self.reqs)

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
    def alloc_req_slots(self, num_reqs):
        req_pool_indices = self.req_to_token_pool.alloc(num_reqs)
        if req_pool_indices is None:
            raise RuntimeError(
                "Out of memory. "
                "Please set a smaller number for `--max-running-requests`."
            )
        return req_pool_indices

    def alloc_token_slots(self, num_tokens: int):
        out_cache_loc = self.token_to_kv_pool.alloc(num_tokens)

        if out_cache_loc is None:
            if self.tree_cache is not None:
                self.tree_cache.evict(num_tokens, self.token_to_kv_pool.free)
                out_cache_loc = self.token_to_kv_pool.alloc(num_tokens)

            if out_cache_loc is None:
                logger.error("Prefill out of memory. Try to lower your batch size.")
                if self.tree_cache is not None:
                    self.tree_cache.pretty_print()
                exit(1)

        return out_cache_loc

390
    def batch_sampling_params(self, vocab_size):
391
392
393
394
395
396
397
398
399
400
401
402
403
        device = "cuda"
        bs, reqs = self.batch_size(), self.reqs
        self.temperatures = torch.tensor(
            [r.sampling_params.temperature for r in reqs],
            dtype=torch.float,
            device=device,
        ).view(-1, 1)
        self.top_ps = torch.tensor(
            [r.sampling_params.top_p for r in reqs], dtype=torch.float, device=device
        )
        self.top_ks = torch.tensor(
            [r.sampling_params.top_k for r in reqs], dtype=torch.int, device=device
        )
404
405
406
407
408
409
410
411
412
413
414

        # Each penalizers will do nothing if they evaluate themselves as not required by looking at
        # the sampling_params of the requests (See {_is_required()} of each penalizers). So this
        # should not add hefty computation overhead other than simple checks.
        #
        # While we choose not to even create the class instances if they are not required, this
        # could add additional complexity to the {ScheduleBatch} class, especially we need to
        # handle {filter_batch()} and {merge()} cases as well.
        self.penalizer_orchestrator = penaltylib.BatchedPenalizerOrchestrator(
            vocab_size=vocab_size,
            batch=self,
415
            device=device,
416
417
418
419
420
421
            Penalizers={
                penaltylib.BatchedFrequencyPenalizer,
                penaltylib.BatchedMinNewTokensPenalizer,
                penaltylib.BatchedPresencePenalizer,
                penaltylib.BatchedRepetitionPenalizer,
            },
422
423
424
425
        )

        # Handle logit bias but only allocate when needed
        self.logit_bias = None
426
427

    def prepare_for_extend(self, vocab_size: int):
428
        bs = self.batch_size()
Lianmin Zheng's avatar
Lianmin Zheng committed
429
        reqs = self.reqs
430
        input_ids = [r.fill_ids[len(r.prefix_indices) :] for r in reqs]
431
        extend_num_tokens = sum(len(ids) for ids in input_ids)
Lianmin Zheng's avatar
Lianmin Zheng committed
432
433
        seq_lens = []

434
        # Allocate memory
435
        req_pool_indices_cpu = self.alloc_req_slots(bs)
436
        out_cache_loc = self.alloc_token_slots(extend_num_tokens)
437

438
        pt = 0
439
440
        for i, req in enumerate(reqs):
            req.req_pool_idx = req_pool_indices_cpu[i]
441
            pre_len, seq_len = len(req.prefix_indices), len(req.fill_ids)
442
443
            ext_len = seq_len - pre_len
            seq_lens.append(seq_len)
Lianmin Zheng's avatar
Lianmin Zheng committed
444

445
            if pre_len > 0:
446
                self.req_to_token_pool.req_to_token[req.req_pool_idx][
447
448
                    :pre_len
                ] = req.prefix_indices
Lianmin Zheng's avatar
Lianmin Zheng committed
449

450
451
452
453
            self.req_to_token_pool.req_to_token[req.req_pool_idx][pre_len:seq_len] = (
                out_cache_loc[pt : pt + ext_len]
            )
            pt += ext_len
Lianmin Zheng's avatar
Lianmin Zheng committed
454
455

        # Set fields
456
457
458
459
        with torch.device("cuda"):
            self.input_ids = torch.tensor(sum(input_ids, []), dtype=torch.int32)
            self.req_pool_indices = torch.tensor(req_pool_indices_cpu)
            self.seq_lens = torch.tensor(seq_lens, dtype=torch.int32)
460
461
            self.position_ids_offsets = torch.zeros((bs,), dtype=torch.int64)

Lianmin Zheng's avatar
Lianmin Zheng committed
462
463
        self.extend_num_tokens = extend_num_tokens
        self.out_cache_loc = out_cache_loc
Liangsheng Yin's avatar
Liangsheng Yin committed
464
        self.top_logprobs_nums = [r.top_logprobs_num for r in reqs]
Lianmin Zheng's avatar
Lianmin Zheng committed
465

466
        self.batch_sampling_params(vocab_size)
Lianmin Zheng's avatar
Lianmin Zheng committed
467

468
    def check_decode_mem(self):
469
        bs = self.batch_size()
Ying Sheng's avatar
Ying Sheng committed
470
        if self.token_to_kv_pool.available_size() >= bs:
471
472
            return True

Mingyi's avatar
Mingyi committed
473
        self.tree_cache.evict(bs, self.token_to_kv_pool.free)
474

475
476
477
478
479
480
481
        if self.token_to_kv_pool.available_size() >= bs:
            return True

        return False

    def retract_decode(self):
        sorted_indices = [i for i in range(len(self.reqs))]
Liangsheng Yin's avatar
Liangsheng Yin committed
482
483

        # TODO(lsyin): improve retraction policy for radix cache
484
        sorted_indices.sort(
Liangsheng Yin's avatar
Liangsheng Yin committed
485
486
487
488
            key=lambda i: (
                len(self.reqs[i].output_ids),
                -len(self.reqs[i].origin_input_ids),
            ),
489
490
491
492
            reverse=True,
        )

        retracted_reqs = []
493
        seq_lens_cpu = self.seq_lens.cpu().numpy()
Liangsheng Yin's avatar
Liangsheng Yin committed
494
495
496
497
498
499
500
501
502
503
504
        while (
            self.token_to_kv_pool.available_size()
            < len(sorted_indices) * global_config.retract_decode_steps
        ):
            if len(sorted_indices) == 1:
                # Corner case: only one request left
                assert (
                    self.token_to_kv_pool.available_size() > 0
                ), "No space left for only one request"
                break

505
506
507
508
            idx = sorted_indices.pop()
            req = self.reqs[idx]
            retracted_reqs.append(req)

509
510
            if isinstance(self.tree_cache, ChunkCache):
                # ChunkCache does not have eviction
511
512
513
                token_indices = self.req_to_token_pool.req_to_token[req.req_pool_idx][
                    : seq_lens_cpu[idx]
                ]
514
                self.token_to_kv_pool.free(token_indices)
515
                self.req_to_token_pool.free(req.req_pool_idx)
516
517
518
519
                del self.tree_cache.entries[req.rid]
            else:
                # TODO: apply more fine-grained retraction
                last_uncached_pos = len(req.prefix_indices)
520
521
522
                token_indices = self.req_to_token_pool.req_to_token[req.req_pool_idx][
                    last_uncached_pos : seq_lens_cpu[idx]
                ]
523
                self.token_to_kv_pool.free(token_indices)
524
                self.req_to_token_pool.free(req.req_pool_idx)
525
526
527
528
529
530
531
532
533
534
535

                # release the last node
                self.tree_cache.dec_lock_ref(req.last_node)

                # NOTE(lsyin): we should use the newly evictable memory instantly.
                residual_size = (
                    len(sorted_indices) * global_config.retract_decode_steps
                    - self.token_to_kv_pool.available_size()
                )
                residual_size = max(0, residual_size)
                self.tree_cache.evict(residual_size, self.token_to_kv_pool.free)
Liangsheng Yin's avatar
Liangsheng Yin committed
536

537
            req.prefix_indices = []
538
            req.last_node = None
539
            req.extend_input_len = 0
Liangsheng Yin's avatar
Liangsheng Yin committed
540
541
542
543

            # For incremental logprobs
            req.last_update_decode_tokens = 0
            req.logprob_start_len = 10**9
Liangsheng Yin's avatar
Liangsheng Yin committed
544

545
546
        self.filter_batch(sorted_indices)

Liangsheng Yin's avatar
Liangsheng Yin committed
547
548
549
550
551
552
553
554
555
556
        # Reqs in batch are filtered
        total_decoded_tokens = sum(len(r.output_ids) for r in self.reqs)
        total_max_new_tokens = sum(r.sampling_params.max_new_tokens for r in self.reqs)

        new_estimate_ratio = (
            total_decoded_tokens + global_config.retract_decode_steps * len(self.reqs)
        ) / total_max_new_tokens
        new_estimate_ratio = min(1.0, new_estimate_ratio)

        return retracted_reqs, new_estimate_ratio
557

Liangsheng Yin's avatar
Liangsheng Yin committed
558
    def check_for_jump_forward(self, model_runner):
Liangsheng Yin's avatar
Liangsheng Yin committed
559
        jump_forward_reqs = []
Liangsheng Yin's avatar
Liangsheng Yin committed
560
561
562
        filter_indices = [i for i in range(len(self.reqs))]

        for i, req in enumerate(self.reqs):
Liangsheng Yin's avatar
Liangsheng Yin committed
563
            if req.jump_forward_map is not None:
Liangsheng Yin's avatar
Liangsheng Yin committed
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
                jump_forward_bytes = req.jump_forward_map.jump_forward_byte(
                    req.regex_fsm_state
                )
                if jump_forward_bytes is not None and len(jump_forward_bytes) > 1:
                    suffix_bytes = []
                    continuation_range = range(0x80, 0xC0)
                    cur_state = req.regex_fsm_state
                    while (
                        len(jump_forward_bytes)
                        and jump_forward_bytes[0][0] in continuation_range
                    ):
                        # continuation bytes
                        byte_edge = jump_forward_bytes.pop(0)
                        suffix_bytes.append(byte_edge[0])
                        cur_state = byte_edge[1]

                    suffix_tokens = [f"<0x{hex(b)[2:].upper()}>" for b in suffix_bytes]
                    suffix_ids = req.tokenizer.convert_tokens_to_ids(suffix_tokens)

                    # Current ids, for cache and revert
                    cur_all_ids = tuple(req.origin_input_ids + req.output_ids)[:-1]
                    cur_output_ids = req.output_ids

                    req.output_ids.extend(suffix_ids)
588
                    decode_res, new_text = req.get_next_inc_detokenization()
Liangsheng Yin's avatar
Liangsheng Yin committed
589
590
                    if not decode_res:
                        req.output_ids = cur_output_ids
Liangsheng Yin's avatar
Liangsheng Yin committed
591
592
                        continue

sglang's avatar
sglang committed
593
594
595
596
                    (
                        jump_forward_str,
                        next_state,
                    ) = req.jump_forward_map.jump_forward_symbol(cur_state)
Liangsheng Yin's avatar
Liangsheng Yin committed
597
598
599
600
601
602
603
604
605

                    # Make the incrementally decoded text part of jump_forward_str
                    # so that the UTF-8 will not corrupt
                    jump_forward_str = new_text + jump_forward_str
                    if not req.jump_forward_and_retokenize(
                        jump_forward_str, next_state
                    ):
                        req.output_ids = cur_output_ids
                        continue
Liangsheng Yin's avatar
Liangsheng Yin committed
606

607
608
609
                    # The decode status has diverged from detokenizer_manager
                    req.vid += 1

Liangsheng Yin's avatar
Liangsheng Yin committed
610
                    # insert the old request into tree_cache
611
                    self.tree_cache.cache_finished_req(req, cur_all_ids)
Liangsheng Yin's avatar
Liangsheng Yin committed
612

Liangsheng Yin's avatar
Liangsheng Yin committed
613
614
615
616
617
618
619
620
621
622
623
624
                    # re-applying image padding
                    if req.pixel_values is not None:
                        (
                            req.origin_input_ids,
                            req.image_offset,
                        ) = model_runner.model.pad_input_ids(
                            req.origin_input_ids_unpadded,
                            req.pad_value,
                            req.pixel_values.shape,
                            req.image_size,
                        )

Liangsheng Yin's avatar
Liangsheng Yin committed
625
                    jump_forward_reqs.append(req)
Liangsheng Yin's avatar
Liangsheng Yin committed
626
627
                    filter_indices.remove(i)

628
        self.filter_batch(filter_indices)
Liangsheng Yin's avatar
Liangsheng Yin committed
629

Liangsheng Yin's avatar
Liangsheng Yin committed
630
        return jump_forward_reqs
Liangsheng Yin's avatar
Liangsheng Yin committed
631

632
    def prepare_for_decode(self, input_ids=None):
Lianmin Zheng's avatar
Lianmin Zheng committed
633
634
        if input_ids is None:
            input_ids = [
635
636
                r.output_ids[-1] if r.output_ids else r.origin_input_ids[-1]
                for r in self.reqs
Lianmin Zheng's avatar
Lianmin Zheng committed
637
            ]
638
639
640
        else:
            self.penalizer_orchestrator.cumulate_input_tokens(input_ids)

Lianmin Zheng's avatar
Lianmin Zheng committed
641
642
643
644
        self.input_ids = torch.tensor(input_ids, dtype=torch.int32, device="cuda")
        self.seq_lens.add_(1)

        # Alloc mem
645
646
        bs = self.batch_size()
        self.out_cache_loc = self.alloc_token_slots(bs)
Lianmin Zheng's avatar
Lianmin Zheng committed
647
648
649
650
651
652

        self.req_to_token_pool.req_to_token[
            self.req_pool_indices, self.seq_lens - 1
        ] = self.out_cache_loc

    def filter_batch(self, unfinished_indices: List[int]):
653
654
655
656
657
658
659
660
661
        if unfinished_indices is None or len(unfinished_indices) == 0:
            # Filter out all requests
            self.reqs = []
            return

        if len(unfinished_indices) == len(self.reqs):
            # No need to filter
            return

Lianmin Zheng's avatar
Lianmin Zheng committed
662
663
664
665
666
667
        self.reqs = [self.reqs[i] for i in unfinished_indices]
        new_indices = torch.tensor(unfinished_indices, dtype=torch.int32, device="cuda")
        self.seq_lens = self.seq_lens[new_indices]
        self.input_ids = None
        self.req_pool_indices = self.req_pool_indices[new_indices]
        self.position_ids_offsets = self.position_ids_offsets[new_indices]
668
        self.out_cache_loc = None
Liangsheng Yin's avatar
Liangsheng Yin committed
669
        self.top_logprobs_nums = [self.top_logprobs_nums[i] for i in unfinished_indices]
670
        self.return_logprob = any(req.return_logprob for req in self.reqs)
Lianmin Zheng's avatar
Lianmin Zheng committed
671

672
673
        self.penalizer_orchestrator.filter(unfinished_indices, new_indices)

Lianmin Zheng's avatar
Lianmin Zheng committed
674
675
676
677
678
679
        for item in [
            "temperatures",
            "top_ps",
            "top_ks",
            "logit_bias",
        ]:
680
            self_val = getattr(self, item, None)
Mingyi's avatar
Mingyi committed
681
            if self_val is not None:  # logit_bias can be None
682
                setattr(self, item, self_val[new_indices])
Lianmin Zheng's avatar
Lianmin Zheng committed
683

684
    def merge(self, other: "ScheduleBatch"):
685
686
687
688
689
        # Penalizer orchestrator must be merged before Batch.reqs is merged. This is because
        # orchestrator.merge() depends on Batch.reqs during preparation of each penalizers, so it
        # needs to be called with pre-merged Batch.reqs.
        self.penalizer_orchestrator.merge(other.penalizer_orchestrator)

Lianmin Zheng's avatar
Lianmin Zheng committed
690
691
692
693
694
695
696
697
698
        self.reqs.extend(other.reqs)

        self.req_pool_indices = torch.concat(
            [self.req_pool_indices, other.req_pool_indices]
        )
        self.seq_lens = torch.concat([self.seq_lens, other.seq_lens])
        self.position_ids_offsets = torch.concat(
            [self.position_ids_offsets, other.position_ids_offsets]
        )
699
        self.out_cache_loc = None
Liangsheng Yin's avatar
Liangsheng Yin committed
700
        self.top_logprobs_nums.extend(other.top_logprobs_nums)
701
        self.return_logprob = any(req.return_logprob for req in self.reqs)
Lianmin Zheng's avatar
Lianmin Zheng committed
702
703
704
705
706
707

        for item in [
            "temperatures",
            "top_ps",
            "top_ks",
        ]:
708
709
710
711
712
713
714
715
716
717
            self_val = getattr(self, item, None)
            other_val = getattr(other, item, None)
            setattr(self, item, torch.concat([self_val, other_val]))

        # logit_bias can be None
        if self.logit_bias is not None or other.logit_bias is not None:
            vocab_size = (
                self.logit_bias.shape[1]
                if self.logit_bias is not None
                else other.logit_bias.shape[1]
Lianmin Zheng's avatar
Lianmin Zheng committed
718
            )
719
720
721
722
723
724
725
726
727
            if self.logit_bias is None:
                self.logit_bias = torch.zeros(
                    (len(self.reqs), vocab_size), dtype=torch.float32, device="cuda"
                )
            if other.logit_bias is None:
                other.logit_bias = torch.zeros(
                    (len(other.reqs), vocab_size), dtype=torch.float32, device="cuda"
                )
            self.logit_bias = torch.concat([self.logit_bias, other.logit_bias])
Lianmin Zheng's avatar
Lianmin Zheng committed
728

729
    def sample(self, logits: torch.Tensor, is_multi_node_tp=False):
730
        # TODO(lsyin): move this into a part of layer and run with CUDA Graph
Lianmin Zheng's avatar
Lianmin Zheng committed
731
732
733
        # Post process logits
        logits = logits.contiguous()
        logits.div_(self.temperatures)
734
735
        if self.logit_bias is not None:
            logits.add_(self.logit_bias)
Lianmin Zheng's avatar
Lianmin Zheng committed
736
737
738
739
740
741
742
743

        has_regex = any(req.regex_fsm is not None for req in self.reqs)
        if has_regex:
            allowed_mask = torch.empty_like(logits[0], dtype=torch.bool)
            for i, req in enumerate(self.reqs):
                if req.regex_fsm is not None:
                    allowed_mask.zero_()
                    allowed_mask[
Liangsheng Yin's avatar
Liangsheng Yin committed
744
                        req.regex_fsm.get_next_instruction(req.regex_fsm_state).tokens
Lianmin Zheng's avatar
Lianmin Zheng committed
745
746
747
                    ] = 1
                    logits[i].masked_fill_(~allowed_mask, float("-inf"))

748
749
        logits = self.penalizer_orchestrator.apply(logits)

Lianmin Zheng's avatar
Lianmin Zheng committed
750
        probs = torch.softmax(logits, dim=-1)
751

752
        if not global_server_args_dict["disable_flashinfer_sampling"]:
753
754
755
756
757
758
759
760
761
762
763
764
            max_top_k_round, batch_size = 32, probs.shape[0]
            uniform_samples = torch.rand(
                (max_top_k_round, batch_size), device=probs.device
            )
            batch_next_token_ids, success = top_k_top_p_sampling_from_probs(
                probs, uniform_samples, self.top_ks, self.top_ps
            )
        else:
            # Here we provide a slower fallback implementation.
            batch_next_token_ids, success = top_k_top_p_sampling_from_probs_torch(
                probs, self.top_ks, self.top_ps
            )
765

766
        if not torch.all(success):
Ke Bao's avatar
Ke Bao committed
767
            warnings.warn("Sampling failed, fallback to top_k=1 strategy")
768
            probs = probs.masked_fill(torch.isnan(probs), 0.0)
Ke Bao's avatar
Ke Bao committed
769
770
771
772
            argmax_ids = torch.argmax(probs, dim=-1)
            batch_next_token_ids = torch.where(
                success, batch_next_token_ids, argmax_ids
            )
Lianmin Zheng's avatar
Lianmin Zheng committed
773
774
775
776
777

        if has_regex:
            batch_next_token_ids_cpu = batch_next_token_ids.cpu().numpy()
            for i, req in enumerate(self.reqs):
                if req.regex_fsm is not None:
Liangsheng Yin's avatar
Liangsheng Yin committed
778
                    req.regex_fsm_state = req.regex_fsm.get_next_state(
Lianmin Zheng's avatar
Lianmin Zheng committed
779
780
781
                        req.regex_fsm_state, batch_next_token_ids_cpu[i]
                    )

782
783
        self.penalizer_orchestrator.cumulate_output_tokens(batch_next_token_ids)

784
785
786
787
788
789
790
791
792
793
        if is_multi_node_tp:
            # If the tensor parallelism spans across multiple nodes, there is some indeterminism
            # that can cause the TP workers to generate different tokens, so we need to
            # sync here
            torch.distributed.all_reduce(
                batch_next_token_ids,
                op=dist.ReduceOp.MIN,
                group=get_tensor_model_parallel_group().device_group,
            )

794
        return batch_next_token_ids
795
796


797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
def top_k_top_p_sampling_from_probs_torch(
    probs: torch.Tensor, top_ks: torch.Tensor, top_ps: torch.Tensor
):
    """A top-k and top-k sampling implementation with native pytorch operations."""
    probs_sort, probs_idx = probs.sort(dim=-1, descending=True)
    probs_sum = torch.cumsum(probs_sort, dim=-1)
    probs_sort[(probs_sum - probs_sort) > top_ps.view(-1, 1)] = 0.0
    probs_sort[
        torch.arange(0, probs.shape[-1], device=probs.device).view(1, -1)
        >= top_ks.view(-1, 1)
    ] = 0.0
    probs_sort.div_(probs_sort.max(dim=-1, keepdim=True)[0])
    try:
        sampled_index = torch.multinomial(probs_sort, num_samples=1)
    except RuntimeError:
        batch_next_token_ids = torch.zeros(
813
            (probs_sort.shape[0],), dtype=torch.int32, device=probs.device
814
815
816
817
818
819
820
        )
        success = torch.zeros(probs.shape[0], dtype=torch.bool, device=probs.device)
        return batch_next_token_ids, success

    batch_next_token_ids = torch.gather(probs_idx, dim=1, index=sampled_index).view(-1)
    success = torch.ones(probs.shape[0], dtype=torch.bool, device=probs.device)
    return batch_next_token_ids, success