[Bug]: XGrammar-based CFG decoding degraded after 0.6.5

[AlbertoCastelo]

Your current environment

Tested in 3 environments with 8xH100:

• public.ecr.aws/q9t5s3a7/vllm-ci-test-repo:61c1d499f07d3a50e3721a38f3f54a721f3eaf65
  • CI version before v0.6.5 that contained XGrammars (v0.6.4.post2 did not contained XGrammars).
  • This image no longer exists.
• v0.6.5
• v0.6.6.post1

Model Input Dumps

extra_body = {
    "guided_grammar": grammar,
    "guided_decoding_backend": "xgrammar",  # optional
}
    
chat_completion = client.chat.completions.create(
    model=model,
    messages=messages,
    stream=True,
    temperature=0,
    max_tokens=1024,
    timeout=timeout,
    extra_body=extra_body,
    stream_options={"include_usage": True},
)

🐛 Describe the bug

XGrammars guided decoding both for Time to first token (TTFT) and overall response time. I've tested 2 versions with a Llama3-70b:

• A CI version before v0.6.5 that contained XGrammars (v0.6.4.post2 did not contained XGrammars). This is the exact image I was using: public.ecr.aws/q9t5s3a7/vllm-ci-test-repo:61c1d499f07d3a50e3721a38f3f54a721f3eaf65
  • TTFT P50: ~0.6s
• v0.6.5 and v0.6.6.post1:
  • TTFT P50: ~4s

Related issue affecting Outlines

Before submitting a new issue...

• Make sure you already searched for relevant issues, and asked the chatbot living at the bottom right corner of the documentation page, which can answer lots of frequently asked questions.

[mgoin]

Could you share the grammar used? It might be that we fallback a non-xgrammar backend due to a bad detection heuristic. FYI @russellb

[AlbertoCastelo]

Hey @mgoin! Thanks! As your message points it's indeed an issue in my grammar. I cannot share the full thing but I've replicated the issue with the example below. This is the intended structure of my response (I know it's not ideal but I cannot change it at this point):

Free text (except this sequence of characters "<|start|>"
<|start|>
do something
<|end|>

Issue

Take a look at the definition of preamble. Is there a better way to avoid a sequence of characters?

Slow grammar

the preamble avoid the "<|" sequence

root ::= message
message ::= preamble "<|start|>\n" structured-content "\n<|end|>"

preamble ::= ([^<] | "<" [^|])*
structured-content ::= ...

Faster grammar

the preamble only avoids the char "<" and takes it as indication of <|start|> block should start.

root ::= message
message ::= preamble "<|start|>\n" structured-content "\n<|end|>"

preamble ::= [^<]* 
structured-content ::= ...

Questions

• Is there a better way to avoid a sequence of characters?

[russellb]

Take a look at the definition of preamble. Is there a better way to avoid a sequence of characters?

Are you saying that this difference in preamble definition represents the speed impact? Or that given your "slow" example, it was faster with an older version of xgrammar and/or vllm?

[russellb]

One thing that changed between v0.6.4.post1 and v0.6.5 is this commit: 8b59631

commit 8b5963185512eb7799f12240570e0ac7e7462a88
Author: Michael Goin <michael@neuralmagic.com>
Date:   Fri Dec 6 10:34:29 2024 -0500

    [Core] Support Lark grammars for XGrammar (#10870)
    
    Signed-off-by: mgoin <michael@neuralmagic.com>

If your original image was in between adding xgrammar support, but before this commit, your example would have automatically fallen back to using outlines instead. That window of time was only a few days, though, but it's possible.

I'd be interested to see what results you get if you try to use outlines instead of xgrammar here.

[AlbertoCastelo]

Are you saying that this difference in preamble definition represents the speed impact?

@russellb Yes. I did find that change to lead slow generation. do you know what could be happening?

Both slow and faster grammars were tested with the same vLLM version.

[russellb]

Are you saying that this difference in preamble definition represents the speed impact?

@russellb Yes. I did find that change to lead slow generation. do you know what could be happening?

Both slow and faster grammars were tested with the same vLLM version.

I'm not sure. Maybe a report against xgrammar would provide more insight, as I don't imagine it's something in vllm causing the difference.

[denadai2]

perhaps related? dottxt-ai/outlines#1351

[gaocegege]

I’m encountering the same issue while working on the bug fix #14113

I tested using the example with the model deepseek-ai/DeepSeek-R1-Distill-Qwen-1.5B. Both guided_regex and guided_json perform as expected, with speeds around ~15-30 tokens/s. However, guided_grammar is significantly slower, generating only 0.1 tokens/s.

One observation is that token generation for the 'thinking process' in this model is fast. This process bypasses the main logic of the outlines logits processor.

# Guided decoding by Grammar
simplified_sql_grammar = """
    ?start: select_statement

    ?select_statement: "SELECT " column_list " FROM " table_name

    ?column_list: column_name ("," column_name)*

    ?table_name: identifier

    ?column_name: identifier

    ?identifier: /[a-zA-Z_][a-zA-Z0-9_]*/
"""

prompt = ("Generate an SQL query to show the 'username' and 'email'"
          "from the 'users' table.")
completion = client.chat.completions.create(
    model=model,
    messages=[{
        "role": "user",
        "content": prompt,
    }],
    extra_body={"guided_grammar": simplified_sql_grammar},
)
print("reasoning_content: ", completion.choices[0].message.reasoning_content)
print("content: ", completion.choices[0].message.content)

[supersteves]

I'm seeing similar massively slower processing when using guided_grammar. The GPUs are idle for much of the time, with a few spikes in GPU activity.

The docs appear to indicate only guided_json and guided_regex are available in combination with reasoning.
https://docs.vllm.ai/en/v0.8.1/features/reasoning_outputs.html

However I'm inclined not to trust them because their examples for your own reasoning parser point at files that have been moved around and combined since then.

[supersteves]

Interesting. I just came across this. Same issue?
#14962

Also, it's strange how guided_json is ridiculously faster than guided_grammar. I assumed gbnf was the underlying system for all guided_xyz cases but it cannot be. (Note that guided_json doesn't work with reasoning. See bug linked above.) It's not just that we're suppressing reasoning. With guided_grammar, there's a long period of apparent total inactivity before the completion appears to fire up.