Change time-to-first-token parameter to be based on number of request tokens #137

[pancak3]

resolve #137

• new params:
  • prefill-overhead: The base overhead in milliseconds for prefilling a single token. This value, in conjunction with prefill-complexity and prefill-overhead-std-dev, determines the overall time taken to prefill the entire context. It's an optional parameter with a default of 0 and is ignored if time-to-first-token is not 0.
  • prefill-complexity: Defines how the prefill time scales with the number of prompt tokens. This is required if prefill-overhead is used. Options are "n^2" and "nlog(n)", with a default of "n^2".
  • prefill-overhead-std-dev: The standard deviation in milliseconds for the time taken before the first token is returned. This is required if prefill-overhead is used, with a default of 0.
  • kv-cache-transfer-overhead: The base overhead in milliseconds for transferring the KV-cache of a single token from another vLLM instance when P/D is activated. Along with kv-cache-transfer-complexity and kv-cache-transfer-overhead-std-dev, it defines the total time for the KV-cache transfer of the entire context. This parameter is optional with a default of 0 and is ignored if kv-cache-transfer-latency is not 0.
  • kv-cache-transfer-complexity: The complexity of the KV-cache transfer relative to the number of prompt tokens. This is required if kv-cache-transfer-overhead is used. Options are "linear" and "in-place", with a default of "linear".
  • kv-cache-transfer-overhead-std-dev: The standard deviation in milliseconds for the time taken to transfer the KV-cache. This is required if kv-cache-transfer-overhead is used, with a default of 0.- [x] time-to-first-token and prefill-overhead coexist
• time-to-first-token overrides prefill-overhead (forward compatibility)
• test cases
• docs and comments
• ? consider kv-cache-size < number of prompt tokens in remote prefill senarios

[mayabar]

@pancak3 thanks for working on this issue.

I ave some general questions:

• Dependency between prefill time and number of input tokens. In the sources I read I saw that for not too long requests the dependency is "near-linear". Prefill-time=C+n*t, where C is fixed overhead and t is prefill time per token, and n is the input token count. Do you have evidence for quadratical or logarithmic dependency?

• Regarding kv-cache time per token, currently it is used only when prefill is executed on another vllm pod, and mimics time for transferring kv-cache to the current pod. We added recently ability to cache kv-blocks (it was done to be able to send kv events properly), in future we want for each request check if its prompt has part in kv-cache and calculate prefill time accordingly, but this is in a separate stage.

• In the issue associated with this PR we talked about prefill-time-per-token (PTPT), in addition, we talked about prefill-overhead that is the contain time which does not depends on number of input tokens, in case the time dependency is linear the formula will be: total_prefill_time = prefill-overhead + num-of-tokens * PTPT.

[pancak3]

@mayabar sorry to get back late.

• Dependency between prefill time and number of input tokens. In the sources I read I saw that for not too long requests the dependency is "near-linear". Prefill-time=C+n*t, where C is fixed overhead and t is prefill time per token, and n is the input token count. Do you have evidence for quadratical or logarithmic dependency?
• In the issue associated with this PR we talked about prefill-time-per-token (PTPT), in addition, we talked about prefill-overhead that is the contain time which does not depends on number of input tokens, in case the time dependency is linear the formula will be: total_prefill_time = prefill-overhead + num-of-tokens * PTPT.

I have to admit I haven't read deeply to a source but implement the previous code by impression of LLMs. Got some time reading the paper Attention Is All You Need,

$\text{Attention}(Q, K, V) = \text{softmax}\left(\frac{Q K^T}{\sqrt{d_k}}\right)V$

Convert it to computation complexity, my understanding is that, it has $O(n^2d/k)$ complexity, where n is the length of input prompts, d can simply be the model complexity, and k is the GPU performance (parallelism units). When n is less than k, the complexity could be simplified from quadratics $O(n^2d/k)$ to "near-linear" $O(nd)$.
As we are simulating, at this stage (after reading roadmap P1 plan), I agree with the simple implementation (Prefill-time=C+n*t).
But I am open to working on features for more flexible configuration ( $d=f(d_{tokenization}, d_{embedding}, d_k, d_v)$, consider k). Let me know if further discussion is needed.

• Regarding kv-cache time per token, currently it is used only when prefill is executed on another vllm pod, and mimics time for transferring kv-cache to the current pod. We added recently ability to cache kv-blocks (it was done to be able to send kv events properly), in future we want for each request check if its prompt has part in kv-cache and calculate prefill time accordingly, but this is in a separate stage.

Lovely, I will change kv cache transfer implementation, removing the "complexity" part. The calculation isKV-cache-transfer-time = n * transfer-overhead and transfer-overhead will be the argument. Let me know if kv-cache-tranfer-overhead or transfter-overhead or any other naming is preferred.

Also, I am not sure whether the network quality between pods is considered in the following phases (did not find any clue in the public roadmap doc), but personally think it is good to consider networking in the sim behavior.

One more thing to confirm, for both Prefill-time and KV-cache-transfer-time, they will be used as mean, along with their own std-dev, to get normalzed times for "P1 - Timing randomization using statistical parameters". Thank you!

[pancak3]

Hi @mayabar, sorry to block other issues, pelase review the latest change, thanks!

[mayabar]

it may stay the old code where mean and stddev are calculated according the doRemotePrefill and randomInt is called from one plase

[pancak3]

this is resolved in the below change

[mayabar]

additional variables are not required, we can use config properties directly in the calculation or function call

[pancak3]

done

[mayabar]

this check should be outside this function since it called only if time-to-first-token is defined.
in the current logic it's not possible to use for requests without disaggregated PD constant time for prefill (time-to-first-token is not 0) but in case of PD - calculate prefill time based on number of tokens

I suggest to check first doRemotePrefill and take care of each time calculation separately.
Like:

• if PD
  • if time depends on input length ---> prefill-time=kvcache-transfer * num-of-tokens
  • if time does not depends on input length ---> prefill-time=kvcache-tranfer-time
• if not PD
  • if time depends on input length ---> prefill-time=overhead + ptpt * num-of-tokens
  • if time does not depends on input length ---> prefill-time=time-to-first-token

[pancak3]

thanks for this clear suggestion! the logic is now pretty intuitive, please review

[mayabar]

do_remote_prefill=true in the request's payload means that for this request the prefill stage was done on a remote pod and the current simulator instance should process only the decode part (kv-cache copies from another pod)

do_remote_decode=true in the request's payload means that for this request the decode stage will be done on a remote pod and the current simulator instance should process only the prefill part

if both properties are false - both prefill and decode are executed locally

This is a little bit confusing but the comment is according the NIXL documentation ;) Maybe it worth to add longer explanation

[pancak3]

I was caught : D
I added some words, please review, thanks!

[mayabar]

/lgtm

/approve