[SpecDecode] Support EAGLE in V1

[WoosukKwon]

• 1. Correctly initializing and loading the EAGLE draft model
• 2. Consider the lookahead slots in the KV cache manager
• 3. Cache draft_probs inside the model runner and correctly feed it to the rejection sampler in the next step (temporarily workaround: [V1][Spec Decode] Always use argmax for sampling draft tokens  #16899)
• 4. Handle the edge cases like when the draft model generates beyond max_pos_embeddings
• 5. Handle the seeds correctly
• 6. Do E2E correctness and performance tests
• 7. Support prefix caching. Eagle requires special handling because Eagle's i-th KV cache is coupled with the i+1-th token ID. (@LiuXiaoxuanPKU)
• 8. Properly handle the sampling parameters that are not (currently) compatible with spec decoding (e.g., min_p).
• 9. Use CUDA graphs for draft model. (@luyuzhe111)
• 10. Support Eagle 3 ([V1][Spec Decode] EAGLE-3 Support #16937)

Originally posted by @WoosukKwon in #15729 (comment)

[ekagra-ranjan]

I will take up Task 3

[wwl2755]

Hi, I would like to give a try on task 4.

[WoosukKwon]

Hi @wwl2755, the task 4 has already been addressed by #16087 and 1 is being handled by #16035. Would you be interested in others (5, 6, 7 particularly)?

[wwl2755]

Hi @wwl2755, the task 4 has already been addressed by #16087 and 1 is being handled by #16035. Would you be interested in others (5, 6, 7 particularly)?

Hi @WoosukKwon , Sorry for the typo, I meant task 5 (random seed). I'm happy to take this up.

[wwl2755]

Hi @WoosukKwon , when I tries to understand the task 7, is that mainly because the draft model won't use the first token's cache in its auto-regression head? But it seems f_how (in the figure) is used in the draft model?

From what I could see, we are supposed to take the KV cache from the target model, shift it by 1, and then append to it during the proposing process in the draft model until num_speculative_tokens. Is that correct? Thank you!

EDIT: I re-visited the details of the paper and now understand that f_how and e_can are concatenated (which we can image it as the first token in the draft model) and also f_can and e_I are concatenated (second token), that's why there is a shift-by-1. And the KV cache comes from processing these new-type tokens. Please correct me if my understanding is wrong. Thank you!

Follow-up questions:

1. Do we consider a tree-based kv cache (multiple possibilities as in the figure) or simply a contiguous one?
2. It seems the EAGLE is not fully integrated and for now it's hard to make unit tests for the cache. Would it be better to delay this task until we have merged the functional EAGLE proposer into V1?

Second EDIT: After a second thought, I think what I mentioned above should be related to task 2. Prefix caching, I assume, should be related to the same prefix sharing across requests.