| 1 | # SPDX-License-Identifier: Apache-2.0 |
| 2 | # SPDX-FileCopyrightText: Copyright contributors to the vLLM project |
| 3 | import multiprocessing |
| 4 | from collections.abc import Iterable, Sequence |
| 5 | from concurrent.futures import Future, ThreadPoolExecutor |
| 6 | from typing import TYPE_CHECKING |
| 7 | |
| 8 | from vllm.config import VllmConfig |
| 9 | from vllm.logger import init_logger |
| 10 | from vllm.parser.engine.adapters import ParserEngineReasoningAdapter |
| 11 | from vllm.reasoning import ReasoningParserManager |
| 12 | from vllm.tokenizers import cached_tokenizer_from_config |
| 13 | from vllm.utils.import_utils import LazyLoader |
| 14 | from vllm.v1.structured_output.backend_guidance import GuidanceBackend |
| 15 | from vllm.v1.structured_output.backend_types import ( |
| 16 | StructuredOutputBackend, |
| 17 | StructuredOutputGrammar, |
| 18 | ) |
| 19 | from vllm.v1.structured_output.backend_xgrammar import XgrammarBackend |
| 20 | from vllm.v1.structured_output.utils import strip_speculative_padding |
| 21 | |
| 22 | if TYPE_CHECKING: |
| 23 | import numpy as np |
| 24 | import numpy.typing as npt |
| 25 | import torch |
| 26 | |
| 27 | from vllm.reasoning import ReasoningParser |
| 28 | from vllm.v1.request import Request |
| 29 | else: |
| 30 | torch = LazyLoader("torch", globals(), "torch") |
| 31 | |
| 32 | |
| 33 | logger = init_logger(__name__) |
| 34 | |
| 35 | |
| 36 | class StructuredOutputManager: |
| 37 | """Engine-level manager for structured output requests.""" |
| 38 | |
| 39 | def __init__(self, vllm_config: VllmConfig): |
| 40 | self.backend: StructuredOutputBackend | None = None |
| 41 | # We only store the class of the reasoner in the manager. |
| 42 | # The parser instance is request-scoped because some reasoning parsers |
| 43 | # depend on per-request chat-template kwargs. |
| 44 | self.reasoner_cls: type[ReasoningParser] | None = None |
| 45 | self.vllm_config = vllm_config |
| 46 | |
| 47 | # When in external_launcher mode, async grammar compilation causes deadlocks |
| 48 | # due to external_launcher mode having a scheduler for each TP rank. |
| 49 | # Async grammar compilation causes the |
| 50 | # WAITING_FOR_STRUCTURED_OUTPUT_GRAMMAR → WAITING transition to |
| 51 | # happen at different times on different TP ranks, |
| 52 | # breaking the determinism assumption that external_launcher relies on. |
| 53 | self._use_async_grammar_compilation = ( |
| 54 | vllm_config.parallel_config.distributed_executor_backend |
| 55 | != "external_launcher" |
| 56 | ) |
| 57 | |
| 58 | self._grammar_bitmask: torch.Tensor | None = None |
| 59 | self._full_mask = torch.tensor(-1, dtype=torch.int32) |
| 60 | |
| 61 | max_batch_size = self.vllm_config.scheduler_config.max_num_seqs |
| 62 | self.fill_bitmask_parallel_threshold = 128 |
| 63 | if self.fill_bitmask_parallel_threshold < max_batch_size: |
| 64 | self.fill_bitmask_parallel_batch_size = 16 |
| 65 | # Use: |
| 66 | # - at least 1 CPU |
| 67 | # - at most half the number of CPUs or 8, whichever is less |
| 68 | max_workers = max(1, min(multiprocessing.cpu_count() // 2, 8)) |
| 69 | self.executor_for_fillmask = ThreadPoolExecutor(max_workers=max_workers) |
| 70 | |
| 71 | if not self.vllm_config.model_config.skip_tokenizer_init: |
| 72 | # The default max_workers if not specified is the number of |
| 73 | # CPUs * 5, which is way too high since these tasks are CPU-bound, |
| 74 | # not I/O bound. We also know we would never dominate CPU usage |
| 75 | # with just grammar compilation, so we set it to half the number |
| 76 | # of CPUs. |
| 77 | max_workers = max(1, (multiprocessing.cpu_count() + 1) // 2) |
| 78 | self.executor = ThreadPoolExecutor(max_workers=max_workers) |
| 79 | self.tokenizer = cached_tokenizer_from_config( |
| 80 | model_config=self.vllm_config.model_config |
| 81 | ) |
| 82 | reasoning_parser_plugin = ( |
| 83 | self.vllm_config.structured_outputs_config.reasoning_parser_plugin |
| 84 | ) |
| 85 | if reasoning_parser_plugin and len(reasoning_parser_plugin) > 3: |
| 86 | ReasoningParserManager.import_reasoning_parser(reasoning_parser_plugin) |
| 87 | |
| 88 | reasoning_parser = ( |
| 89 | self.vllm_config.structured_outputs_config.reasoning_parser |
| 90 | ) |
| 91 | if reasoning_parser: |
| 92 | self.reasoner_cls = ReasoningParserManager.get_reasoning_parser( |
| 93 | reasoning_parser |
| 94 | ) |
| 95 | |
| 96 | self.enable_in_reasoning = ( |
| 97 | self.vllm_config.structured_outputs_config.enable_in_reasoning |
| 98 | ) |
| 99 | |
| 100 | def _get_reasoner(self, request: "Request") -> "ReasoningParser | None": |
| 101 | structured_req = request.structured_output_request |
| 102 | if structured_req is None or self.reasoner_cls is None: |
| 103 | return None |
| 104 | |
| 105 | if structured_req.reasoner is None: |
| 106 | # Lazily build the request-local parser so the structured-output |
| 107 | # gate observes the same template kwargs used by the frontend. |
| 108 | parser_kwargs = structured_req.reasoning_parser_kwargs or {} |
| 109 | structured_req.reasoner = self.reasoner_cls( |
| 110 | tokenizer=self.tokenizer, |
| 111 | **parser_kwargs, |
| 112 | ) |
| 113 | return structured_req.reasoner |
| 114 | |
| 115 | def grammar_init(self, request: "Request") -> None: |
| 116 | if request.structured_output_request is None: |
| 117 | return |
| 118 | |
| 119 | if TYPE_CHECKING: |
| 120 | assert ( |
| 121 | request.sampling_params is not None |
| 122 | and request.sampling_params.structured_outputs is not None |
| 123 | ) |
| 124 | |
| 125 | # Initialize the backend the first time it is needed. |
| 126 | # |
| 127 | # NOTE: We only support a single backend. We do NOT support different |
| 128 | # backends on a per-request basis in V1 (for now, anyway...). |
| 129 | # _backend is set in Processor._validate_structured_output |
| 130 | if self.backend is None: |
| 131 | assert request.sampling_params is not None |
| 132 | backend = request.sampling_params.structured_outputs._backend |
| 133 | vocab_size = self.vllm_config.model_config.get_vocab_size() |
| 134 | if backend == "xgrammar": |
| 135 | self.backend = XgrammarBackend( |
| 136 | self.vllm_config, |
| 137 | tokenizer=self.tokenizer, |
| 138 | vocab_size=vocab_size, |
| 139 | ) |
| 140 | elif backend == "guidance": |
| 141 | self.backend = GuidanceBackend( |
| 142 | self.vllm_config, |
| 143 | tokenizer=self.tokenizer, |
| 144 | vocab_size=vocab_size, |
| 145 | ) |
| 146 | elif backend == "outlines": |
| 147 | from vllm.v1.structured_output.backend_outlines import OutlinesBackend |
| 148 | |
| 149 | self.backend = OutlinesBackend( |
| 150 | self.vllm_config, |
| 151 | tokenizer=self.tokenizer, |
| 152 | vocab_size=vocab_size, |
| 153 | ) |
| 154 | elif backend == "lm-format-enforcer": |
| 155 | from vllm.v1.structured_output.backend_lm_format_enforcer import ( # noqa: E501 |
| 156 | LMFormatEnforcerBackend, |
| 157 | ) |
| 158 | |
| 159 | self.backend = LMFormatEnforcerBackend( |
| 160 | self.vllm_config, |
| 161 | tokenizer=self.tokenizer, |
| 162 | vocab_size=vocab_size, |
| 163 | ) |
| 164 | else: |
| 165 | raise ValueError(f"Unsupported structured output backend: {backend}") |
| 166 | |
| 167 | grammar: Future[StructuredOutputGrammar] | StructuredOutputGrammar |
| 168 | if self._use_async_grammar_compilation: |
| 169 | grammar = self.executor.submit(self._create_grammar, request) |
| 170 | else: |
| 171 | try: |
| 172 | grammar = self._create_grammar(request) |
| 173 | except Exception as e: |
| 174 | grammar = Future() |
| 175 | grammar.set_exception(e) |
| 176 | request.structured_output_request.grammar = grammar |
| 177 | |
| 178 | def _create_grammar(self, request: "Request") -> StructuredOutputGrammar: |
| 179 | struct_request = request.structured_output_request |
| 180 | assert struct_request is not None |
| 181 | # Note that the request was validated in the engine core client, |
| 182 | # so at this point we know it is a supported type of request. Grammar |
| 183 | # compilation may still fail; the Future carries that error to the |
| 184 | # scheduler so it can fail only this request. |
| 185 | try: |
| 186 | request_type, grammar_spec = struct_request.structured_output_key |
| 187 | assert self.backend is not None |
| 188 | stop_token_ids = ( |
| 189 | request.sampling_params.all_stop_token_ids |
| 190 | if request.sampling_params is not None |
| 191 | else None |
| 192 | ) |
| 193 | return self.backend.compile_grammar( |
| 194 | request_type, grammar_spec, stop_token_ids=stop_token_ids |
| 195 | ) |
| 196 | except Exception: |
| 197 | logger.exception( |
| 198 | "Failed to compile grammar for request %s", request.request_id |
| 199 | ) |
| 200 | raise |
| 201 | |
| 202 | def _fill_bitmasks( |
| 203 | self, batch: Iterable[tuple[StructuredOutputGrammar, int, bool]] |
| 204 | ) -> None: |
| 205 | assert self._grammar_bitmask is not None |
| 206 | for grammar, index, apply_bitmask in batch: |
| 207 | if apply_bitmask and not grammar.is_terminated(): |
| 208 | grammar.fill_bitmask(self._grammar_bitmask, index) |
| 209 | else: |
| 210 | # Note that for thinking support, we will need to |
| 211 | # reset the relevant part of the bitmask for consequent |
| 212 | # requests here. |
| 213 | self._grammar_bitmask[index].fill_(self._full_mask) |
| 214 | |
| 215 | def _async_submit_fill_bitmask( |
| 216 | self, batch: list[tuple[StructuredOutputGrammar, int, bool]] |
| 217 | ) -> Future: |
| 218 | return self.executor_for_fillmask.submit(self._fill_bitmasks, batch) |
| 219 | |
| 220 | def _get_constraint_start( |
| 221 | self, |
| 222 | request: "Request", |
| 223 | spec_tokens: Sequence[int], |
| 224 | spec_tokens_committed: bool = False, |
| 225 | ) -> int: |
| 226 | """Return the index into `spec_tokens` where tokens should start being |
| 227 | constrained by the grammar. |
| 228 | Assumes `spec_tokens` are stripped of -1 padding tokens. |
| 229 | Returns `len(spec_tokens) + 1` if no token should be constrained after |
| 230 | accepting all `spec_tokens`. |
| 231 | |
| 232 | `spec_tokens_committed` is True if spec_tokens is already in |
| 233 | `request.all_token_ids`. |
| 234 | """ |
| 235 | if self.enable_in_reasoning: |
| 236 | return 0 |
| 237 | |
| 238 | structured_req = request.structured_output_request |
| 239 | assert structured_req is not None |
| 240 | if structured_req.reasoning_ended: |
| 241 | return 0 |
| 242 | |
| 243 | reasoner = self._get_reasoner(request) |
| 244 | if reasoner is None: |
| 245 | return 0 |
| 246 | |
| 247 | if structured_req.reasoning_ended is None: |
| 248 | # This should be removed here, but since `openai_gptoss` |
| 249 | # is an independent code path, it is kept for now. |
| 250 | # After unifying the `openai_gptoss` and non-`openai_gptoss` styles, |
| 251 | # it can be removed. |
| 252 | if reasoner.is_reasoning_end(request.prompt_token_ids or []): |
| 253 | return 0 |
| 254 | structured_req.reasoning_ended = False |
| 255 | |
| 256 | num_spec_tokens = len(spec_tokens) |
| 257 | if num_spec_tokens <= 0: |
| 258 | return num_spec_tokens + 1 |
| 259 | |
| 260 | # Use `find_reasoning_end_offset` to find constraint start if supported |
| 261 | if ( |
| 262 | isinstance(reasoner, ParserEngineReasoningAdapter) |
| 263 | and reasoner.reasoning_end_token_ids |
| 264 | ): |
| 265 | offset = reasoner.find_reasoning_end_offset(spec_tokens) |
| 266 | if offset is not None: |
| 267 | return offset + 1 |
| 268 | |
| 269 | # Fallback to `find_reasoning_end_offset` |
| 270 | # TODO: Build a read-only Sequence view over all_token_ids |
| 271 | # instead of copying the entire all_token_ids into input_ids. |
| 272 | if spec_tokens_committed: |
| 273 | if not spec_tokens or not reasoner.is_reasoning_end_streaming( |
| 274 | request.all_token_ids, spec_tokens |
| 275 | ): |
| 276 | return num_spec_tokens + 1 |
| 277 | |
| 278 | input_ids = request.all_token_ids.copy() |
| 279 | delta_ids = list(spec_tokens) |
| 280 | else: |
| 281 | input_ids = request.all_token_ids.copy() |
| 282 | input_ids.extend(spec_tokens) |
| 283 | if not reasoner.is_reasoning_end_streaming(input_ids, spec_tokens): |
| 284 | return num_spec_tokens + 1 |
| 285 | delta_ids = list(spec_tokens) |
| 286 | |
| 287 | for i in range(num_spec_tokens - 1, 0, -1): |
| 288 | input_ids.pop() |
| 289 | delta_ids.pop() |
| 290 | if not reasoner.is_reasoning_end_streaming(input_ids, delta_ids): |
| 291 | return i + 1 |
| 292 | return 1 |
| 293 | |
| 294 | def validate_tokens(self, request: "Request", spec_tokens: list[int]) -> list[int]: |
| 295 | """Return the longest unconstrained or grammar-valid prefix of `spec_tokens`.""" |
| 296 | if not request.use_structured_output: |
| 297 | return spec_tokens |
| 298 | |
| 299 | spec_tokens = strip_speculative_padding(spec_tokens) |
| 300 | constraint_start = self._get_constraint_start(request, spec_tokens) |
| 301 | if constraint_start >= len(spec_tokens): |
| 302 | return spec_tokens |
| 303 | |
| 304 | structured_req = request.structured_output_request |
| 305 | if TYPE_CHECKING: |
| 306 | assert structured_req is not None |
| 307 | grammar = structured_req.grammar |
| 308 | if TYPE_CHECKING: |
| 309 | assert isinstance(grammar, StructuredOutputGrammar) |
| 310 | prefix = spec_tokens[:constraint_start] |
| 311 | validated = grammar.validate_tokens(spec_tokens[constraint_start:]) |
| 312 | return prefix + validated |
| 313 | |
| 314 | def grammar_bitmask( |
| 315 | self, |
| 316 | requests: dict[str, "Request"], |
| 317 | structured_output_request_ids: list[str], |
| 318 | scheduled_spec_decode_tokens: dict[str, list[int]], |
| 319 | ) -> "npt.NDArray[np.int32] | None": |
| 320 | # Prepare the structured output bitmask for this batch. |
| 321 | if not structured_output_request_ids: |
| 322 | return None |
| 323 | |
| 324 | # Covers both speculative decoding and diffusion LLMs (canvas_length). |
| 325 | max_num_spec_tokens = self.vllm_config.num_speculative_tokens |
| 326 | |
| 327 | if self._grammar_bitmask is None: |
| 328 | assert self.backend is not None |
| 329 | max_batch_size = self.vllm_config.scheduler_config.max_num_seqs |
| 330 | |
| 331 | # Allocate a bitmask for each token needing to be checked: |
| 332 | # one for each speculative position, and one more for the |
| 333 | # bonus token / non-speculative token. |
| 334 | self._grammar_bitmask = self.backend.allocate_token_bitmask( |
| 335 | max_batch_size * (1 + max_num_spec_tokens) |
| 336 | ) |
| 337 | |
| 338 | # Generate a batched bitmask for all structured output requests. |
| 339 | # When speculative decoding is enabled, we need to include multiple |
| 340 | # masks for each request, one for each possible bonus token position. |
| 341 | # These are stored inline in the tensor and unpacked by the gpu runner. |
| 342 | cumulative_index = 0 |
| 343 | |
| 344 | # Optimized parallel filling of bitmasks for |
| 345 | # non-spec, large-batch-size cases |
| 346 | if ( |
| 347 | len(structured_output_request_ids) > self.fill_bitmask_parallel_threshold |
| 348 | and max_num_spec_tokens == 0 |
| 349 | ): |
| 350 | promises = [] |
| 351 | batch = [] |
| 352 | for req_id in structured_output_request_ids: |
| 353 | request = requests[req_id] |
| 354 | structured_output_request = request.structured_output_request |
| 355 | if TYPE_CHECKING: |
| 356 | assert structured_output_request is not None |
| 357 | grammar = structured_output_request.grammar |
| 358 | if TYPE_CHECKING: |
| 359 | assert isinstance(grammar, StructuredOutputGrammar) |
| 360 | |
| 361 | apply_bitmask = self._get_constraint_start(request, ()) == 0 |
| 362 | batch.append((grammar, cumulative_index, apply_bitmask)) |
| 363 | if len(batch) == self.fill_bitmask_parallel_batch_size: |
| 364 | promises.append(self._async_submit_fill_bitmask(batch)) |
| 365 | batch = [] |
| 366 | |
| 367 | cumulative_index += 1 |
| 368 | if batch: |
| 369 | promises.append(self._async_submit_fill_bitmask(batch)) |
| 370 | |
| 371 | # Wait for all bitmask filling tasks to complete. |
| 372 | for promise in promises: |
| 373 | promise.result() |
| 374 | else: |
| 375 | # Fallback to serial filling of bitmasks for small-batch-size cases |
| 376 | for req_id in structured_output_request_ids: |
| 377 | request = requests[req_id] |
| 378 | structured_output_request = request.structured_output_request |
| 379 | |
| 380 | if TYPE_CHECKING: |
| 381 | assert structured_output_request is not None |
| 382 | grammar = structured_output_request.grammar |
| 383 | if TYPE_CHECKING: |
| 384 | assert isinstance(grammar, StructuredOutputGrammar) |
| 385 | |
| 386 | req_tokens = scheduled_spec_decode_tokens.get(req_id, list()) |
| 387 | constraint_start = self._get_constraint_start( |
| 388 | request, strip_speculative_padding(req_tokens) |
| 389 | ) |
| 390 | state_advancements = 0 |
| 391 | seen_padding = False |
| 392 | # Row filled from the last valid grammar state before a draft |
| 393 | # was rejected; later rows reuse it rather than unconstraining. |
| 394 | failed_index: int | None = None |
| 395 | bitmask = self._grammar_bitmask |
| 396 | for i, token in enumerate(req_tokens): |
| 397 | if failed_index is not None: |
| 398 | bitmask[cumulative_index].copy_(bitmask[failed_index]) |
| 399 | cumulative_index += 1 |
| 400 | continue |
| 401 | apply_bitmask = not seen_padding and i >= constraint_start |
| 402 | self._fill_bitmasks(((grammar, cumulative_index, apply_bitmask),)) |
| 403 | if token == -1: |
| 404 | seen_padding = True |
| 405 | elif apply_bitmask: |
| 406 | if not grammar.is_terminated() and grammar.accept_tokens( |
| 407 | req_id, [token] |
| 408 | ): |
| 409 | state_advancements += 1 |
| 410 | else: |
| 411 | failed_index = cumulative_index |
| 412 | logger.error( |
| 413 | "Unexpected: grammar terminated or rejected draft " |
| 414 | "token %s for request %s during bitmask fill.", |
| 415 | token, |
| 416 | req_id, |
| 417 | ) |
| 418 | cumulative_index += 1 |
| 419 | |
| 420 | # Diffusion LLMs don't sample a bonus token after the |
| 421 | # scheduled positions, so skip its bitmask in that case. |
| 422 | if not (self.vllm_config.model_config.is_diffusion and req_tokens): |
| 423 | if failed_index is not None: |
| 424 | bitmask[cumulative_index].copy_(bitmask[failed_index]) |
| 425 | else: |
| 426 | bonus_apply = not seen_padding and constraint_start <= len( |
| 427 | req_tokens |
| 428 | ) |
| 429 | self._fill_bitmasks(((grammar, cumulative_index, bonus_apply),)) |
| 430 | cumulative_index += 1 |
| 431 | |
| 432 | if state_advancements > 0: |
| 433 | grammar.rollback(state_advancements) |
| 434 | |
| 435 | bitmask_tensor = self._grammar_bitmask |
| 436 | if cumulative_index < bitmask_tensor.shape[0]: |
| 437 | bitmask_tensor = bitmask_tensor[:cumulative_index] |
| 438 | |
| 439 | # After finishing with the xgrammar operations, we convert to |
| 440 | # np.ndarray, because that is much more efficient for serialization |
| 441 | # and deserialization when sending this to the GPU workers. |
| 442 | return bitmask_tensor.numpy() |
| 443 | |
| 444 | def accept_tokens(self, request: "Request", new_token_ids: list[int]) -> bool: |
| 445 | """Advance grammar with accepted tokens. Returns False on rejection.""" |
| 446 | if not request.use_structured_output or not new_token_ids: |
| 447 | return True |
| 448 | |
| 449 | structured_req = request.structured_output_request |
| 450 | if TYPE_CHECKING: |
| 451 | assert structured_req is not None |
| 452 | grammar = structured_req.grammar |
| 453 | if TYPE_CHECKING: |
| 454 | assert isinstance(grammar, StructuredOutputGrammar) |
| 455 | |
| 456 | constraint_start = self._get_constraint_start( |
| 457 | request, new_token_ids, spec_tokens_committed=True |
| 458 | ) |
| 459 | # Early return only when the constraint hasn't started. |
| 460 | # Otherwise, latch structured_req.reasoning_ended. |
| 461 | if constraint_start > len(new_token_ids): |
| 462 | return True |
| 463 | structured_req.reasoning_ended = True |
| 464 | return grammar.accept_tokens( |
| 465 | request.request_id, new_token_ids[constraint_start:] |
| 466 | ) |
| 467 | |
| 468 | def clear_backend(self) -> None: |
| 469 | if self.backend is not None: |
| 470 | self.backend.destroy() |