schedule_batch.py 28.9 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
Mingyi's avatar
Mingyi committed
21
from typing import List, Union
Lianmin Zheng's avatar
Lianmin Zheng committed
22
23
24

import numpy as np
import torch
25
from flashinfer.sampling import top_k_top_p_sampling_from_probs
Liangsheng Yin's avatar
Liangsheng Yin committed
26

Liangsheng Yin's avatar
Liangsheng Yin committed
27
from sglang.global_config import global_config
28
29
from sglang.srt.constrained import RegexGuide
from sglang.srt.constrained.jump_forward import JumpForwardMap
30
from sglang.srt.mem_cache.chunk_cache import ChunkCache
31
from sglang.srt.mem_cache.memory_pool import BaseTokenToKVPool, ReqToTokenPool
32
from sglang.srt.mem_cache.radix_cache import RadixCache
Liangsheng Yin's avatar
Liangsheng Yin committed
33
34

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

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

Lianmin Zheng's avatar
Lianmin Zheng committed
44

Ying Sheng's avatar
Ying Sheng committed
45
46
47
logger = logging.getLogger(__name__)


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

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


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

Lianmin Zheng's avatar
Lianmin Zheng committed
90
91

class Req:
92
93
    """Store all inforamtion of a request."""

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

103
104
105
        # Memory info
        self.req_pool_idx = None

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

120
121
122
        # 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
123

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

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

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

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

143
144
145
146
147
        # Logprobs
        self.return_logprob = False
        self.logprob_start_len = 0
        self.top_logprobs_num = 0
        self.normalized_prompt_logprob = None
148
149
150
151
        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
152
153
154
        # 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
155

156
        # Constrained decoding
Liangsheng Yin's avatar
Liangsheng Yin committed
157
158
159
        self.regex_fsm: RegexGuide = None
        self.regex_fsm_state: int = 0
        self.jump_forward_map: JumpForwardMap = None
Liangsheng Yin's avatar
Liangsheng Yin committed
160

161
162
163
164
    # whether request reached finished condition
    def finished(self) -> bool:
        return self.finished_reason is not None

Liangsheng Yin's avatar
Liangsheng Yin committed
165
    # Based on https://github.com/vllm-project/vllm/blob/7a64d24aad69e4d2548aa0bf528d9fe63428ab01/vllm/transformers_utils/detokenizer.py#L194-L313
166
    def init_incremental_detokenize(self):
Liangsheng Yin's avatar
Liangsheng Yin committed
167
168
169
170
171
172
173
174
175
        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
176
        return all_ids[self.surr_offset :], self.read_offset - self.surr_offset
Liangsheng Yin's avatar
Liangsheng Yin committed
177

178
179
180
    def get_next_inc_detokenization(self):
        read_ids, read_offset = self.init_incremental_detokenize()
        surr_ids = read_ids[:read_offset]
Liangsheng Yin's avatar
Liangsheng Yin committed
181
182
183
184
185

        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
186
        )
Liangsheng Yin's avatar
Liangsheng Yin committed
187
188
189
190
191
192
193
        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("�"):
194
            return True, new_text[len(surr_text) :]
Liangsheng Yin's avatar
Liangsheng Yin committed
195
196

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

198
    def check_finished(self):
199
        if self.finished():
200
201
            return

Liangsheng Yin's avatar
Liangsheng Yin committed
202
203
        if len(self.output_ids) >= self.sampling_params.max_new_tokens:
            self.finished_reason = FINISH_LENGTH(len(self.output_ids))
204
205
206
207
            return

        if (
            self.output_ids[-1] == self.tokenizer.eos_token_id
208
            and not self.sampling_params.ignore_eos
209
        ):
Liangsheng Yin's avatar
Liangsheng Yin committed
210
211
212
            self.finished_reason = FINISH_MATCHED_TOKEN(
                matched=self.tokenizer.eos_token_id
            )
213
214
215
216
217
218
219
220
            return

        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
221
                if stop_str in tail_str or stop_str in self.decoded_text:
222
                    self.finished_reason = FINISH_MATCHED_STR(matched=stop_str)
223
224
                    return

Liangsheng Yin's avatar
Liangsheng Yin committed
225
    def jump_forward_and_retokenize(self, jump_forward_str, next_state):
Liangsheng Yin's avatar
Liangsheng Yin committed
226
227
228
229
230
231
        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
232
        all_text = self.origin_input_text + self.decoded_text + jump_forward_str
Liangsheng Yin's avatar
Liangsheng Yin committed
233
234
        all_ids = self.tokenizer.encode(all_text)
        prompt_tokens = len(self.origin_input_ids_unpadded)
Liangsheng Yin's avatar
Liangsheng Yin committed
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256

        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
257
258
259
260
261
262

        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
263
264
            for i, old_id in enumerate(old_output_ids):
                if old_id == self.output_ids[i]:
Liangsheng Yin's avatar
Liangsheng Yin committed
265
266
267
                    k = k + 1
                else:
                    break
268
269
            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
270
            self.logprob_start_len = prompt_tokens + k
Liangsheng Yin's avatar
Liangsheng Yin committed
271
            self.last_update_decode_tokens = len(self.output_ids) - k
272

Liangsheng Yin's avatar
Liangsheng Yin committed
273
        return True
Liangsheng Yin's avatar
Liangsheng Yin committed
274

Lianmin Zheng's avatar
Lianmin Zheng committed
275
    def __repr__(self):
Liangsheng Yin's avatar
Liangsheng Yin committed
276
        return f"rid(n={self.rid}, " f"input_ids={self.origin_input_ids}, "
Lianmin Zheng's avatar
Lianmin Zheng committed
277
278


279
@dataclass
280
class ScheduleBatch:
281
282
    """Store all inforamtion of a batch."""

283
    # Request, memory pool, and cache
284
285
    reqs: List[Req]
    req_to_token_pool: ReqToTokenPool
286
    token_to_kv_pool: BaseTokenToKVPool
287
288
    tree_cache: RadixCache

289
    # Batched arguments to model runner
290
291
292
293
294
295
    input_ids: torch.Tensor = None
    req_pool_indices: torch.Tensor = None
    seq_lens: torch.Tensor = None
    prefix_lens: torch.Tensor = None
    position_ids_offsets: torch.Tensor = None
    out_cache_loc: torch.Tensor = None
296
    extend_num_tokens: int = None
Liangsheng Yin's avatar
Liangsheng Yin committed
297

298
    # For processing logprobs
299
    return_logprob: bool = False
300
    top_logprobs_nums: List[int] = None
301

302
    # For multimodal
303
    pixel_values: List[torch.Tensor] = None
shiyi.c_98's avatar
shiyi.c_98 committed
304
    image_sizes: List[List[int]] = None
305
306
    image_offsets: List[int] = None

307
    # Batched sampling params
308
309
310
311
312
313
314
315
316
    temperatures: torch.Tensor = None
    top_ps: torch.Tensor = None
    top_ks: torch.Tensor = None
    frequency_penalties: torch.Tensor = None
    presence_penalties: torch.Tensor = None
    logit_bias: torch.Tensor = None

    @classmethod
    def init_new(cls, reqs, req_to_token_pool, token_to_kv_pool, tree_cache):
317
        return_logprob = any(req.return_logprob for req in reqs)
318
319
320
321
322
323

        return cls(
            reqs=reqs,
            req_to_token_pool=req_to_token_pool,
            token_to_kv_pool=token_to_kv_pool,
            tree_cache=tree_cache,
324
            return_logprob=return_logprob,
Lianmin Zheng's avatar
Lianmin Zheng committed
325
326
        )

327
328
329
    def batch_size(self):
        return len(self.reqs) if self.reqs is not None else 0

Lianmin Zheng's avatar
Lianmin Zheng committed
330
331
332
    def is_empty(self):
        return len(self.reqs) == 0

333
    def has_stream(self) -> bool:
334
        # Return whether batch has at least 1 streaming request
335
336
        return any(r.stream for r in self.reqs)

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
    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

    def batch_sampling_params(self, vocab_size, int_token_logit_bias):
        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
        )
        self.frequency_penalties = torch.tensor(
            [r.sampling_params.frequency_penalty for r in reqs],
            dtype=torch.float,
            device=device,
        )
        self.presence_penalties = torch.tensor(
            [r.sampling_params.presence_penalty for r in reqs],
            dtype=torch.float,
            device=device,
        )

        # Handle logit bias but only allocate when needed
        self.logit_bias = None
        for i in range(bs):
            if reqs[i].sampling_params.dtype == "int":
                if self.logit_bias is None:
                    self.logit_bias = torch.zeros(
                        (bs, vocab_size), dtype=torch.float32, device=device
                    )
                self.logit_bias[i][: len(int_token_logit_bias)] = int_token_logit_bias

397
    def prepare_for_extend(self, vocab_size: int, int_token_logit_bias: torch.Tensor):
Lianmin Zheng's avatar
Lianmin Zheng committed
398
        device = "cuda"
399
        bs = self.batch_size()
Lianmin Zheng's avatar
Lianmin Zheng committed
400
401
402
403
404
405
406
407
408
        reqs = self.reqs
        input_ids = [r.input_ids[len(r.prefix_indices) :] for r in reqs]
        prefix_indices = [r.prefix_indices for r in reqs]

        # Handle prefix
        extend_lens = []
        prefix_lens = []
        seq_lens = []

409
        req_pool_indices_cpu = self.alloc_req_slots(bs)
410

411
412
        for i, req in enumerate(reqs):
            req.req_pool_idx = req_pool_indices_cpu[i]
Lianmin Zheng's avatar
Lianmin Zheng committed
413
414
415
416
417
418
            extend_lens.append(len(input_ids[i]))

            if len(prefix_indices[i]) == 0:
                prefix_lens.append(0)
            else:
                prefix_lens.append(len(prefix_indices[i]))
419
                self.req_to_token_pool.req_to_token[req.req_pool_idx][
Lianmin Zheng's avatar
Lianmin Zheng committed
420
421
422
423
424
                    : len(prefix_indices[i])
                ] = prefix_indices[i]

            seq_lens.append(prefix_lens[-1] + extend_lens[-1])

425
        # Allocate memory
Lianmin Zheng's avatar
Lianmin Zheng committed
426
427
        seq_lens, prefix_lens = np.array(seq_lens), np.array(prefix_lens)
        extend_num_tokens = seq_lens.sum() - prefix_lens.sum()
428
        out_cache_loc = self.alloc_token_slots(extend_num_tokens)
Lianmin Zheng's avatar
Lianmin Zheng committed
429
430

        pt = 0
431
432
        for i, req in enumerate(reqs):
            self.req_to_token_pool.req_to_token[req.req_pool_idx][
Lianmin Zheng's avatar
Lianmin Zheng committed
433
434
435
436
437
                prefix_lens[i] : prefix_lens[i] + extend_lens[i]
            ] = out_cache_loc[pt : pt + extend_lens[i]]
            pt += extend_lens[i]

        # Set fields
438
439
440
441
442
443
        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)
            self.position_ids_offsets = torch.zeros((bs,), dtype=torch.int32)

Lianmin Zheng's avatar
Lianmin Zheng committed
444
        self.pixel_values = [r.pixel_values for r in reqs]
shiyi.c_98's avatar
shiyi.c_98 committed
445
        self.image_sizes = [r.image_size for r in reqs]
Lianmin Zheng's avatar
Lianmin Zheng committed
446
447
448
449
450
451
        self.image_offsets = [
            r.image_offset - p_len for r, p_len in zip(reqs, prefix_lens)
        ]
        self.prefix_lens = torch.tensor(prefix_lens, dtype=torch.int32, device=device)
        self.extend_num_tokens = extend_num_tokens
        self.out_cache_loc = out_cache_loc
Liangsheng Yin's avatar
Liangsheng Yin committed
452
        self.top_logprobs_nums = [r.top_logprobs_num for r in reqs]
Lianmin Zheng's avatar
Lianmin Zheng committed
453

454
        self.batch_sampling_params(vocab_size, int_token_logit_bias)
Lianmin Zheng's avatar
Lianmin Zheng committed
455

456
    def check_decode_mem(self):
457
        bs = self.batch_size()
Ying Sheng's avatar
Ying Sheng committed
458
        if self.token_to_kv_pool.available_size() >= bs:
459
460
            return True

Mingyi's avatar
Mingyi committed
461
        self.tree_cache.evict(bs, self.token_to_kv_pool.free)
462

463
464
465
466
467
468
469
        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
470
471

        # TODO(lsyin): improve retraction policy for radix cache
472
        sorted_indices.sort(
Liangsheng Yin's avatar
Liangsheng Yin committed
473
474
475
476
            key=lambda i: (
                len(self.reqs[i].output_ids),
                -len(self.reqs[i].origin_input_ids),
            ),
477
478
479
480
            reverse=True,
        )

        retracted_reqs = []
481
        seq_lens_cpu = self.seq_lens.cpu().numpy()
Liangsheng Yin's avatar
Liangsheng Yin committed
482
483
484
485
486
487
488
489
490
491
492
        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

493
494
495
496
            idx = sorted_indices.pop()
            req = self.reqs[idx]
            retracted_reqs.append(req)

497
498
            if isinstance(self.tree_cache, ChunkCache):
                # ChunkCache does not have eviction
499
500
501
                token_indices = self.req_to_token_pool.req_to_token[req.req_pool_idx][
                    : seq_lens_cpu[idx]
                ]
502
                self.token_to_kv_pool.free(token_indices)
503
                self.req_to_token_pool.free(req.req_pool_idx)
504
505
506
507
                del self.tree_cache.entries[req.rid]
            else:
                # TODO: apply more fine-grained retraction
                last_uncached_pos = len(req.prefix_indices)
508
509
510
                token_indices = self.req_to_token_pool.req_to_token[req.req_pool_idx][
                    last_uncached_pos : seq_lens_cpu[idx]
                ]
511
                self.token_to_kv_pool.free(token_indices)
512
                self.req_to_token_pool.free(req.req_pool_idx)
513
514
515
516
517
518
519
520
521
522
523

                # 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
524

525
526
            req.prefix_indices = None
            req.last_node = None
527
            req.extend_input_len = 0
Liangsheng Yin's avatar
Liangsheng Yin committed
528
529
530
531

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

533
534
        self.filter_batch(sorted_indices)

Liangsheng Yin's avatar
Liangsheng Yin committed
535
536
537
538
539
540
541
542
543
544
        # 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
545

Liangsheng Yin's avatar
Liangsheng Yin committed
546
    def check_for_jump_forward(self, model_runner):
Liangsheng Yin's avatar
Liangsheng Yin committed
547
        jump_forward_reqs = []
Liangsheng Yin's avatar
Liangsheng Yin committed
548
549
550
        filter_indices = [i for i in range(len(self.reqs))]

        for i, req in enumerate(self.reqs):
Liangsheng Yin's avatar
Liangsheng Yin committed
551
            if req.jump_forward_map is not None:
Liangsheng Yin's avatar
Liangsheng Yin committed
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
                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)
576
                    decode_res, new_text = req.get_next_inc_detokenization()
Liangsheng Yin's avatar
Liangsheng Yin committed
577
578
                    if not decode_res:
                        req.output_ids = cur_output_ids
Liangsheng Yin's avatar
Liangsheng Yin committed
579
580
                        continue

sglang's avatar
sglang committed
581
582
583
584
                    (
                        jump_forward_str,
                        next_state,
                    ) = req.jump_forward_map.jump_forward_symbol(cur_state)
Liangsheng Yin's avatar
Liangsheng Yin committed
585
586
587
588
589
590
591
592
593

                    # 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
594

595
596
597
                    # The decode status has diverged from detokenizer_manager
                    req.vid += 1

Liangsheng Yin's avatar
Liangsheng Yin committed
598
599
                    # insert the old request into tree_cache
                    self.tree_cache.cache_req(
600
                        rid=req.rid,
Liangsheng Yin's avatar
Liangsheng Yin committed
601
                        token_ids=cur_all_ids,
Liangsheng Yin's avatar
Liangsheng Yin committed
602
                        last_uncached_pos=len(req.prefix_indices),
603
                        req_pool_idx=req.req_pool_idx,
Liangsheng Yin's avatar
Liangsheng Yin committed
604
                    )
Liangsheng Yin's avatar
Liangsheng Yin committed
605
606
607

                    # unlock the last node
                    self.tree_cache.dec_lock_ref(req.last_node)
Liangsheng Yin's avatar
Liangsheng Yin committed
608

Liangsheng Yin's avatar
Liangsheng Yin committed
609
610
611
612
613
614
615
616
617
618
619
620
                    # 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
621
                    jump_forward_reqs.append(req)
Liangsheng Yin's avatar
Liangsheng Yin committed
622
623
624
625
626
                    filter_indices.remove(i)

        if len(filter_indices) < len(self.reqs):
            self.filter_batch(filter_indices)

Liangsheng Yin's avatar
Liangsheng Yin committed
627
        return jump_forward_reqs
Liangsheng Yin's avatar
Liangsheng Yin committed
628

629
    def prepare_for_decode(self, input_ids=None):
Lianmin Zheng's avatar
Lianmin Zheng committed
630
631
632
633
634
635
636
637
638
        if input_ids is None:
            input_ids = [
                r.output_ids[-1] if r.output_ids else r.input_ids[-1] for r in self.reqs
            ]
        self.input_ids = torch.tensor(input_ids, dtype=torch.int32, device="cuda")
        self.seq_lens.add_(1)
        self.prefix_lens = None

        # Alloc mem
639
640
        bs = self.batch_size()
        self.out_cache_loc = self.alloc_token_slots(bs)
Lianmin Zheng's avatar
Lianmin Zheng committed
641
642
643
644
645
646
647
648
649
650
651
652
653

        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]):
        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.prefix_lens = None
        self.position_ids_offsets = self.position_ids_offsets[new_indices]
654
        self.out_cache_loc = None
Liangsheng Yin's avatar
Liangsheng Yin committed
655
        self.top_logprobs_nums = [self.top_logprobs_nums[i] for i in unfinished_indices]
656
        self.return_logprob = any(req.return_logprob for req in self.reqs)
Lianmin Zheng's avatar
Lianmin Zheng committed
657
658
659
660
661
662
663
664
665

        for item in [
            "temperatures",
            "top_ps",
            "top_ks",
            "frequency_penalties",
            "presence_penalties",
            "logit_bias",
        ]:
666
            self_val = getattr(self, item, None)
Mingyi's avatar
Mingyi committed
667
            if self_val is not None:  # logit_bias can be None
668
                setattr(self, item, self_val[new_indices])
Lianmin Zheng's avatar
Lianmin Zheng committed
669

670
    def merge(self, other: "ScheduleBatch"):
Lianmin Zheng's avatar
Lianmin Zheng committed
671
672
673
674
675
676
677
678
679
680
        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.prefix_lens = None
        self.position_ids_offsets = torch.concat(
            [self.position_ids_offsets, other.position_ids_offsets]
        )
681
        self.out_cache_loc = None
Liangsheng Yin's avatar
Liangsheng Yin committed
682
        self.top_logprobs_nums.extend(other.top_logprobs_nums)
683
        self.return_logprob = any(req.return_logprob for req in self.reqs)
Lianmin Zheng's avatar
Lianmin Zheng committed
684
685
686
687
688
689
690
691

        for item in [
            "temperatures",
            "top_ps",
            "top_ks",
            "frequency_penalties",
            "presence_penalties",
        ]:
692
693
694
695
696
697
698
699
700
701
            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
702
            )
703
704
705
706
707
708
709
710
711
            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
712
713
714
715
716

    def sample(self, logits: torch.Tensor):
        # Post process logits
        logits = logits.contiguous()
        logits.div_(self.temperatures)
717
718
        if self.logit_bias is not None:
            logits.add_(self.logit_bias)
Lianmin Zheng's avatar
Lianmin Zheng committed
719
720
721
722
723
724
725
726

        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
727
                        req.regex_fsm.get_next_instruction(req.regex_fsm_state).tokens
Lianmin Zheng's avatar
Lianmin Zheng committed
728
729
730
731
732
                    ] = 1
                    logits[i].masked_fill_(~allowed_mask, float("-inf"))

        # TODO(lmzheng): apply penalty
        probs = torch.softmax(logits, dim=-1)
733

734
        if not global_server_args_dict["disable_flashinfer_sampling"]:
735
736
737
738
739
740
741
742
743
744
745
746
            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
            )
747

748
        if not torch.all(success):
Ke Bao's avatar
Ke Bao committed
749
            warnings.warn("Sampling failed, fallback to top_k=1 strategy")
750
            probs = probs.masked_fill(torch.isnan(probs), 0.0)
Ke Bao's avatar
Ke Bao committed
751
752
753
754
            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
755
756
757
758
759

        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
760
                    req.regex_fsm_state = req.regex_fsm.get_next_state(
Lianmin Zheng's avatar
Lianmin Zheng committed
761
762
763
                        req.regex_fsm_state, batch_next_token_ids_cpu[i]
                    )

764
        return batch_next_token_ids
765
766


767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
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(
            (probs_sort.shape[0],), dtype=torch.int64, device=probs.device
        )
        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