Add a batch-asynchronous version of suffix cache update

[sfc-gh-aqiao]

Suffix decoding overheads start becoming an issue at high concurrencies. For the update operation, we should add a batch version that can run asynchronously to it can be overlapped with the main decoding loop.

Discussion: vllm-project/vllm#25784

[therealnaveenkamal]

@sfc-gh-aqiao can I pick this up?

[sfc-gh-aqiao]

@therealnaveenkamal please do!

[therealnaveenkamal]

So I tried the bench script with concurrency=64 and spec_tokens=32 and spec_tokens=12. The mean TPOT is better than n-gram...but I'm not sure why all the times are >20 ms

Method	concurrency	spec_tokens	output_len	Accepted / Draft	Mean TPOT
suffix w/o cache	64	32	256	15752 / 50755	28.78 ms
suffix with cache	64	32	256	18681 / 71575	28.87 ms
ngram [3, 5]	64	32	256	9848 / 170691	38.49 ms
ngram [5, 5]	64	32	256	5016 / 63931	32.71 ms
suffix w/o cache	64	12	256	15701 / 50140	28.70 ms
suffix with cache	64	12	256	18635 / 71148	29.10 ms
ngram [3, 5]	64	12	256	9859 / 69401	31.85 ms
ngram [5, 5]	64	12	256	4978 / 26077	31.31 ms

[sfc-gh-aqiao]

@therealnaveenkamal could it be a hardware difference?

[therealnaveenkamal]

probably yes. I'm using RTX PRO 6000.

[therealnaveenkamal]

@sfc-gh-aqiao Update:

I ran this on a H200 GPU. For concurrency=64 and spec_tokens=32 -> suffix performs better than ngram. I tried implementing an async cache update with background workers and a thread pool for speculation...but I think the overhead involved with these techniques brings pack the TPOT to the same level.

I tried something on the lines of tracking the best tree to avoid redundant speculation calls and cached the match states instead of rescanning full patterns when only new tokens are appended. suffix w cache, optimization shows a decreased TPOT of about ~0.32 ms - I feel this is negligible. I'll try adding async cache and thread pools in a better way. I'll update.

Method	concurrency	spec_tokens	output_len	Accepted / Draft	Mean TPOT
suffix w cache, optimization	64	32	256	18492 / 70996	12.09 ms
suffix w cache, optimization	64	12	256	18406 / 70539	12.01 ms
suffix w/o cache	64	32	256	15507 / 50060	12.00 ms
suffix with cache	64	32	256	18653 / 71490	12.35 ms
ngram [3, 5]	64	32	256	9833 / 170566	14.24 ms
ngram [5, 5]	64	32	256	5108 / 64442	12.59 ms
suffix w/o cache	64	12	256	15633 / 49862	11.92 ms
suffix with cache	64	12	256	18627 / 70945	12.33 ms
ngram [3, 5]	64	12	256	9622 / 68765	11.66 ms
ngram [5, 5]	64	12	256	5083 / 26292	11.72 ms

[Neo9061]

Hi @therealnaveenkamal did you see any degradation in terms of performance of n-gram / suffix decoding in compared to no-speculative decoding? vllm-project/vllm#26594 (on llama 3.1 8b there is gain, but gain disappears on more popular models like Qwen)

[fluctlux]

Hi @therealnaveenkamal did you see any degradation in terms of performance of n-gram / suffix decoding in compared to no-speculative decoding? vllm-project/vllm#26594 (on llama 3.1 8b there is gain, but gain disappears on more popular models like Qwen)

Hi, @Neo9061 Compared to Llama 3.1, the performance of Qwen3 has declined. There has been community discussion suggesting that this is due to Qwen3's larger vocabulary, which means fewer tokens are used to express the same information, thus reducing the gains from speculative decoding.
I have also observed a performance drop in suffix decoding under high concurrency compared to no spec and ngram. I guess this is caused by the linearly increasing overhead of suffix tree updates and lookups with concurrency, the extra validation overhead introduced by a lower token acceptance rate, and the rejection of more draft tokens.
I am currently looking for solutions.

[Neo9061]

Hi, @Neo9061 Compared to Llama 3.1, the performance of Qwen3 has declined. There has been community discussion suggesting that this is due to Qwen3's larger vocabulary, which means fewer tokens are used to express the same information, thus reducing the gains from speculative decoding. I have also observed a performance drop in suffix decoding under high concurrency compared to no spec and ngram. I guess this is caused by the linearly increasing overhead of suffix tree updates and lookups with concurrency, the extra validation overhead introduced by a lower token acceptance rate, and the rejection of more draft tokens. I am currently looking for solutions.

Thanks for the reply @fluctlux. Regrading this assumption There has been community discussion suggesting that this is due to Qwen3's larger vocabulary, which means fewer tokens are used to express the same information, thus reducing the gains from speculative decoding. There is a code editing task blazedit which is used in the above benchmarking and also mentioned in the hybrid decoding: n-gram + eagle-2 PR. The output and input have a high ratio of overlapping. Even under this task that is perfectly designed for n-gram, it still fails and underperforms than no-spec decoding, making me wonder there are more underlying reasons. And do you have links on the community discussion?

Plus 1 on performance drop at high concurrency level. If i understand it correctly, there is no batch level operation for n-gram and suffix decoding as of now. Do you see a path forward to address both issues? we are interested at using suffix decoding + eagle in a hybrid approach.

[sfc-gh-aqiao]

#211 should improve the speculation time by 3x and reduce the high-concurrency overheads a bit. Also hoping #208 can help as well after merging in.

[fluctlux]

Hi, @Neo9061 Compared to Llama 3.1, the performance of Qwen3 has declined. There has been community discussion suggesting that this is due to Qwen3's larger vocabulary, which means fewer tokens are used to express the same information, thus reducing the gains from speculative decoding. I have also observed a performance drop in suffix decoding under high concurrency compared to no spec and ngram. I guess this is caused by the linearly increasing overhead of suffix tree updates and lookups with concurrency, the extra validation overhead introduced by a lower token acceptance rate, and the rejection of more draft tokens. I am currently looking for solutions.

Thanks for the reply @fluctlux. Regrading this assumption There has been community discussion suggesting that this is due to Qwen3's larger vocabulary, which means fewer tokens are used to express the same information, thus reducing the gains from speculative decoding. There is a code editing task blazedit which is used in the above benchmarking and also mentioned in the hybrid decoding: n-gram + eagle-2 PR. The output and input have a high ratio of overlapping. Even under this task that is perfectly designed for n-gram, it still fails and underperforms than no-spec decoding, making me wonder there are more underlying reasons. And do you have links on the community discussion?

Plus 1 on performance drop at high concurrency level. If i understand it correctly, there is no batch level operation for n-gram and suffix decoding as of now. Do you see a path forward to address both issues? we are interested at using suffix decoding + eagle in a hybrid approach.

here is the discuss in Zhihu: https://zhuanlan.zhihu.com/p/1916965162755285553

Hi, @Neo9061 Compared to Llama 3.1, the performance of Qwen3 has declined. There has been community discussion suggesting that this is due to Qwen3's larger vocabulary, which means fewer tokens are used to express the same information, thus reducing the gains from speculative decoding. I have also observed a performance drop in suffix decoding under high concurrency compared to no spec and ngram. I guess this is caused by the linearly increasing overhead of suffix tree updates and lookups with concurrency, the extra validation overhead introduced by a lower token acceptance rate, and the rejection of more draft tokens. I am currently looking for solutions.

Thanks for the reply @fluctlux. Regrading this assumption There has been community discussion suggesting that this is due to Qwen3's larger vocabulary, which means fewer tokens are used to express the same information, thus reducing the gains from speculative decoding. There is a code editing task blazedit which is used in the above benchmarking and also mentioned in the hybrid decoding: n-gram + eagle-2 PR. The output and input have a high ratio of overlapping. Even under this task that is perfectly designed for n-gram, it still fails and underperforms than no-spec decoding, making me wonder there are more underlying reasons. And do you have links on the community discussion?

Plus 1 on performance drop at high concurrency level. If i understand it correctly, there is no batch level operation for n-gram and suffix decoding as of now. Do you see a path forward to address both issues? we are interested at using suffix decoding + eagle in a hybrid approach.

The issue you mention about the degradation of ngram performance does not report the acceptance rate of draft tokens, but I guess that a lower prompt look up min would lead to a higher rejection rate and validation overhead?
Here is a discussion on the impact of the Qwen3 vocabulary on speculative decoding effectiveness:
https://zhuanlan.zhihu.com/p/1916965162755285553

Regarding the cost of suffix tree update and speculative, I saw @sfc-gh-aqiao proposed some other ideas for optimization like async cache update #208. I guess implementing batch speculation in a C++ suffix tree might be difficult.