Poor performance with bursty workloads

[dagrayvid]

What happened:
While doing performance experiments comparing Knative requests-based load balancing with llm-d load-aware routing, I have found some cases where llm-d inference scheduler underperforms requests-based load balancing.

For example, with 8 replicas of Llama-3.3-70b-fp8 on 2xH100 per replica (TP=2), with prefix caching and prefix-aware routing disabled (queue-scorer and kv-cache-scorer only, each with weight 1.0), if we run guidellm with 1000 ISL, 1000 OSL, in concurrency mode with concurrency=800, we get slightly lower throughput with llm-d:

and significantly worse TTFT

vllm:num_requests_waiting metrics show quite a bit of queuing at some replicas throughout the test

I believe this is because this workload is quite bursty, being concurrency based with fixed sequence lengths per request. Requests come in waves and when many requests arrive simultaneously they get routed to the same Pod.

Please note that this is a corner-case, picked because it is the best case scenario for knative. In cases where the sequence lengths are heterogeneous or prefix caching comes into play, llm-d significantly outperforms knative.

What you expected to happen:
Ideally we would like to see on-par or better performance from llm-d-inference-scheduler intelligent routing.

Anything else we need to know?:
Related issue: #228, but an alternative solution may be to introduce a random filter, so that we can introduce some randomness into the scheduler, e.g. pick 2 random endpoints and route to the better of two (power of two choices).

Environment:
llm-d 0.2.0 installed with llm-d-infra quickstart/examples, including inference-scheduling and precise-prefix-cache-aware.

I will continue experimentation to try to better understand the root-cause of the issue and test some potential improvements, but wanted to open this issue to get the discussion started!

[nirrozenbaum]

I don’t think a random scorer is the solution.
I think we need to replace the max score picker with probability based picker, where the probability of each pod to get selected is is based on its score.
This is called Weighted Random Sampling.

[Jooho]

I created an issue for a new picker Weighted Random Sampling and sent a PR about it. Please review the PR @nirrozenbaum @dagrayvid

[liu-cong]

The root cause of this is likely due to the metrics update delay for very bursty traffic. Imagine a fresh deployment, where initially all pods have 0 k-v cache utilization. When we send a burst of traffic with shared prefixes, all of them are routed to the same pod due to the prefix scorer, until 50ms (the metric refresh interval) later, this pod gets lower score due to high queue and k-v cache. As mentioned in the bug, this is a "corner case" - it only happens when you send a very bursty traffic with shared prefixes, which in practice is likely rare.

While the weighted random sampling can help mitigate this, I am also concerned that it may dilute the prefix affinity, so some careful benchmarking is needed.

I think a short term mitigation is to shorten the metric refresh interval. A better long term solution is to also consider inflight requests (a new scorer perhaps). @vMaroon mentioned an active request scorer being developed.

[Jooho]

I agree with you but I feel GPU utilization is just as important as cache hit efficiency.
Weighted random sampling can efficiently utilize GPUs while still maintaining a high probability of selecting the pod with the highest score. It doesn’t fully solve the root cause (metrics delay), but may serve as a reasonable short-term approach.

[nirrozenbaum]

I think inflight or active request scorer is eventually another scorer. it may help scoring the pods but scoring is based on weights of all the scorers.

I think having a random weighted picker is orthogonal and generally should give better results than the max score picker, as selecting always by max score is not always ideal.

think for example about scorer that scores 10 pods:
8 pods get score 0, 1 gets score 0.5 and the last one gets score 0.499.
does it mean we should always select the one with 0.5?

[liu-cong]

I agree with you but I feel GPU utilization is just as important as cache hit efficiency.

@Jooho

Just wanna clarify, as mentioned above, I think this hot spot issue only happens in an extreme case where traffic is bursty, and with shared prefixes. In most real world use cases, I don't believe this is the case. There will be many different prefixes which will be distributed on different servers, and overall achieving almost equal GPU utilization. If you see otherwise, please share, I'd like to learn more.

[liu-cong]

think for example about scorer that scores 10 pods:
8 pods get score 0, 1 gets score 0.5 and the last one gets score 0.499.
does it mean we should always select the one with 0.5?

Agree some randomness helps if the scores are very close (e.g, practically there is probably no difference between a 0.5 vs 0.499 score). I tried something like bucketizing the scores and treat the same bucket as the same in the past. However, if we pick a pod with 0.1 due to the randomness over a 0.5, this may dilute the cache hit affinity, causing a cache to cost twice storage as high (e.g, distribute a prefix to 2 pods where 1 pod can hold it). I will be very cautious about the latter (pick a much lower score due to randomness).

[nirrozenbaum]

we could potentially filter out some of the candidate pods and leave only the ones that are either max score or "close" to max score (e.g., not less than 30% of it). so if our max score pod has score of 0.5, this rule will filter out all the pods with score lower than 0.35 and than we do random weight picking from the ones that are relatively reasonable to pick.

[nirrozenbaum]

that was just an example with some magic number of 30%, we could have it as configuration param

[Jooho]

Agree some randomness helps if the scores are very close (e.g, practically there is probably no difference between a 0.5 vs 0.499 score). I tried something like bucketizing the scores and treat the same bucket as the same in the past. However, if we pick a pod with 0.1 due to the randomness over a 0.5, this may dilute the cache hit affinity, causing a cache to cost twice storage as high (e.g, distribute a prefix to 2 pods where 1 pod can hold it). I will be very cautious about the latter (pick a much lower score due to randomness).

This can be achieved using a Top-N approach, which ensures that pods with low scores are not selected. I updated PR to use TopN.

[vMaroon]

I don't think randomness is the answer - TopN (with a closeness threshold perhaps) is sensible as an additional layer, but I believe the real value will come from smart tuning of the two scorer families we have. I'll quote a section from a doc @liu-cong and I worked on a while ago:

EPP scorer plugins generally fall into two categories:

• Context-aware: these include session aware, prefix-cache estimation based, and KV-cache aware. These scorers utilize different levels of knowledge to estimate the localities of KV-caches on the vLLM pods, with estimations becoming more precise as the levels get more granular:
  • For example, the first scorer utilizes a session-id header that translates to a growing chat, while the third is informed by KV-cache events coming from vLLM pods directly.
• Load-aware: these focus on metrics such as queue lengths, active request counts, or KV-cache memory utilization. Their goal is to evenly distribute inference load to prevent hotspots and maximize throughput.

These two categories often pull in opposite directions: context-aware scorers bias toward sticky routing (to improve KV-cache hit rates), while load-aware scorers favor spreading requests across the cluster to reduce queuing delays. Finding the right balance between them is key to minimizing end-to-end latency and maximizing system efficiency - but doing so with static weights may be challenging and suboptimal.

To address this, the EPP should support dynamic weight tuning for scorer plugins. For instance, when cluster-level load imbalance is detected, the system can temporarily increase the weight of load-aware scorers to steer traffic away from overloaded vLLM nodes. Once balance is restored, weights can gradually shift back to favor context-aware routing. This adaptive weighting approach enables the scheduler to respond intelligently to changing cluster conditions.

I think it could be time to get started with this.

[nirrozenbaum]

@vMaroon I disagree with your analysis.
while dynamic adaptation of scorers weights could be helpful it’s not meant to solve bursty workloads.
you can’t expect dynamic scoring weights to get updated while handling a burst. it could be helpful in other scenarios though.
I think that is out of scope of the problem that was reported in this issue.