[Feature] Fully Overlap with spec v2 + Constrained Decoding

[JustinTong0323]

Required when tool_choice="required"

related: #13106

Demonstration

Naive version (#13425) has been merged. Here is a simple tutorial about how overlap scheduling works with constrained decoding.

Normal Overlap Scheduling

Delay Sampling + Overlap Ccheduling

Advanced Delay Launching + Overlap Scheduling

[hnyls2002]

We have a test for this: #12635, if anyone is interested in it, they can start from the test (currently broken due to some misalign)

[pdasgup]

@hnyls2002 @JustinTong0323 i can help with the test. is there any context i need here?

[hnyls2002]

@pdasgup Great, you can start by finding the incompatibility issues in #12635

[pdasgup]

@hnyls2002 @JustinTong0323 need to look deeper but i assume it's because there's no grammar backend reference in v2 file https://github.com/sgl-project/sglang/blob/main/python/sglang/srt/speculative/eagle_info_v2.py unlike v1 file https://github.com/sgl-project/sglang/blob/main/python/sglang/srt/speculative/eagle_info.py#L9

[jiapingW]

@hnyls2002 @JustinTong0323 need to look deeper but i assume it's because there's no grammar backend reference in v2 file https://github.com/sgl-project/sglang/blob/main/python/sglang/srt/speculative/eagle_info_v2.py unlike v1 file https://github.com/sgl-project/sglang/blob/main/python/sglang/srt/speculative/eagle_info.py#L9

I debugged the program and found that since Spec v2 does not introduce any grammar-related operations, it does not perform the relevant processing. The batch.spec_info.grammar is None.

[pdasgup]

thanks @jiapingW . will you be raising the fix for this?

[hnyls2002]

Adapt these two logics from worker v1 to worker v2

• sglang/python/sglang/srt/speculative/eagle_worker.py

  Lines 670 to 687 in 85b8c5c

  	if batch.has_grammar:
  	# Generate the logit mask for structured output.
  	# Overlap the CPU operations for bitmask generation with the forward pass.
  	vocab_mask = generate_token_bitmask(
  	batch.reqs,
  	spec_info,
  	retrieve_next_token_cpu,
  	retrieve_next_sibling_cpu,
  	draft_tokens_cpu,
  	batch.sampling_info.vocab_size,
  	)
  	if vocab_mask is not None:
  	assert spec_info.grammar is not None
  	vocab_mask = vocab_mask.to(spec_info.retrive_next_token.device)
  	# NOTE (sk): otherwise, this vocab mask will be the one from the previous extend stage
  	# and will be applied to produce wrong results
  	batch.sampling_info.vocab_mask = None

• sglang/python/sglang/srt/speculative/eagle_worker.py

  Lines 653 to 658 in 85b8c5c

  	if batch.has_grammar:
  	retrieve_next_token_cpu = spec_info.retrive_next_token.cpu()
  	retrieve_next_sibling_cpu = spec_info.retrive_next_sibling.cpu()
  	draft_tokens_cpu = spec_info.draft_token.view(
  	spec_info.retrive_next_token.shape
  	).cpu()

[Ubospica]

I am starting to work on a PR to support it this week. I would be more than happy to collaborate if anyone have already started or have some work/ideas! cc @JustinTong0323 @pdasgup @jiapingW