KVCacheAware Plugin Scoring Latency Too High — Optimize with Caching

[YaoZengzeng]

Problem

The KVCacheAware.Score plugin in the kthena-router introduces significant latency per request, typically ranging from 30ms to 100ms per scoring call. Under concurrent workloads (e.g., multi-turn conversations), this latency adds up and becomes a bottleneck for request routing.

Observed Latency (from production logs)

KVCacheAware.Score: completed in 57.139784ms
KVCacheAware.Score: completed in 31.290123ms
KVCacheAware.Score: completed in 85.288769ms
KVCacheAware.Score: completed in 100.34733ms
KVCacheAware.Score: completed in 76.064469ms
KVCacheAware.Score: completed in 72.113914ms
...

Average latency is approximately 50-60ms, with spikes exceeding 100ms. Under high concurrency scenarios, this significantly impacts overall request throughput and tail latency.

Test Script

The issue was reproduced using the following multi-turn conversation benchmark script:
https://github.com/YaoZengzeng/scripts/blob/master/aiperf/multi-turn-conversation.sh

Environment

• Model: Qwen (0.6B) with 3-4 replicas
• Backend: vLLM
• KV cache metadata stored in Redis

Root Cause Analysis

The Score function (pkg/kthena-router/scheduler/plugins/kvcache_aware.go) performs two expensive operations on every single request:

1. Tokenization (normalizeAndTokenizePrompt): Each incoming prompt must be tokenized to compute block hashes. This involves loading and invoking the tokenizer for the target model on every request, even for multi-turn conversations where prior turns have already been tokenized.

2. Redis Query (queryRedisForBlocks): After tokenization, the plugin queries Redis via a pipeline to check which pods have cached the corresponding KV blocks. Even though pipelining is used, the network round-trip and per-block hash lookup add consistent overhead.

Both operations are performed from scratch on every scoring call, with no reuse of previously computed results.

[FAUST-BENCHOU]

What is the ideal time? I have no concept of score latency......

[YaoZengzeng]

During my test, raw TTFT (router <-> vLLM) is 450ms and plus this score latency, average 50ms, the total TTFT would be 500ms.

Then it means we would add 50ms to TTFT for every request. And I think it's unacceptable.

[FAUST-BENCHOU]

/assign
i just recently been reviewing the kvcacheaware code,will give a first try

[hzxuzhonghu]

Is there a fine-grained latency, There are tokenize + token blocks hash + redis query+ score

[FAUST-BENCHOU]

(.venv-liccheck) (base) zhoujinyu@zhoujinyudeMacBook-Air kthena % kubectl logs -n kvcache-bench deploy/kthena-router --since=1m | grep 'KVCacheAware.Score'

I0520 02:28:59.827262       1 kvcache_aware.go:168] KVCacheAware.Score: called for model="Qwen/Qwen2.5-0.5B-Instruct", pods=[qwen25-0-5b-vllm-76fb5fb959-mz44z], promptTextLen=0, messagesLen=1
I0520 02:28:59.942663       1 kvcache_aware.go:186] KVCacheAware.Score: tokenization took 114.722417ms, tokens=51, err=<nil>
I0520 02:28:59.942939       1 kvcache_aware.go:194] KVCacheAware.Score: generated 4 block hashes from 51 tokens (blockSize=16)
I0520 02:28:59.943584       1 kvcache_aware.go:208] KVCacheAware.Score: Redis query took 635.584µs, blocksWithHits=0/4
I0520 02:28:59.943613       1 kvcache_aware.go:220] KVCacheAware.Score: completed in 116.372709ms, finalScores=map[]
I0520 02:29:13.939865       1 kvcache_aware.go:168] KVCacheAware.Score: called for model="Qwen/Qwen2.5-0.5B-Instruct", pods=[qwen25-0-5b-vllm-76fb5fb959-mz44z], promptTextLen=0, messagesLen=1
I0520 02:29:13.964603       1 kvcache_aware.go:186] KVCacheAware.Score: tokenization took 24.579084ms, tokens=51, err=<nil>
I0520 02:29:13.964717       1 kvcache_aware.go:194] KVCacheAware.Score: generated 4 block hashes from 51 tokens (blockSize=16)
I0520 02:29:13.965316       1 kvcache_aware.go:208] KVCacheAware.Score: Redis query took 590.708µs, blocksWithHits=0/4
I0520 02:29:13.965345       1 kvcache_aware.go:220] KVCacheAware.Score: completed in 25.497916ms, finalScores=map[]

mostly caused by Tokenization

[FAUST-BENCHOU]

Is there a fine-grained latency, There are tokenize + token blocks hash + redis query+ score

the hash and score takes almost no latency i think

[hzxuzhonghu]

tokenization took 114.722417ms, tokens=51, err=

Does this mean 51 tokens takes more than 100ms? If 100K tokens, does the latency increase linearly?

[FAUST-BENCHOU]

tokenization took 114.722417ms, tokens=51, err=

Does this mean 51 tokens takes more than 100ms? If 100K tokens, does the latency increase linearly?

I don't think so. I think the latency here is primarily related to the environment. On my resource-constrained machine, I can tolerate this high latency.

I feel like most of the time is spent waiting for the vLLM's tokenize interface rather than experiencing router latency itself. I tried optimizing the router with a connection pool and did A/B testing, but the results weren't good.

[nXtCyberNet]

Hi @FAUST-BENCHOU and @hzxuzhonghu , I think @hzxuzhonghu is right — token size will increase the latency since we are currently using the vLLM tokenizer endpoint:

gofunc (m *TokenizerManager) createTokenizerFromPods(model string, pods []*datastore.PodInfo) Tokenizer {
    // Randomly select a pod to start with
    startIdx := rand.Intn(len(pods))
    // Try pods starting from random index, wrapping around if needed
    for i := 0; i < len(pods); i++ {
        podIdx := (startIdx + i) % len(pods)
        podInfo := pods[podIdx]
        endpoint := fmt.Sprintf(m.config.EndpointTemplate, podInfo.Pod.Status.PodIP)
        config := RemoteTokenizerConfig{
            Engine:             "vllm",
            Endpoint:           endpoint,  // <-- vLLM pod IP endpoint
            Model:              model,
            AddSpecialTokens:   true,
            ReturnTokenStrings: false,
        }
        tok, err := NewRemoteTokenizer(config)
        // ...
    }
}

Could we switch to https://github.com/huggingface/tokenizers? Currently all routes go through this step, and for very long inputs like 100k–200k tokens it will have significantly higher latency around 200–300ms, which we could reduce. I tested this on Google Colab (not an ideal environment, but it gives a directional approach) with a local tokenizer and got this data:

json{
  "prompt_type": "long",
  "chars": 48100,
  "tokens": 10101,
  "blocks": 632,
  "tokenizer_avg_ms": 34.474087530004454,
  "tokenizer_p50_ms": 24.41384000007929,
  "tokenizer_p95_ms": 82.28628100005153,
  "tokenizer_p99_ms": 126.17143199986458,
  "hash_avg_ms": 2.61054228667111,
  "hash_p50_ms": 1.7884999999751017,
  "hash_p95_ms": 5.65656100002343,
  "hash_p99_ms": 10.366200000134995,
  "total_avg_ms": 37.084739756673265,
  "total_p50_ms": 26.209781000034127,
  "total_p95_ms": 89.19423299994378,
  "total_p99_ms": 136.53777200011064,
  "tokens_per_sec_total": 272376.1867085062
}

Additionally, there is currently no awareness of vLLM pod load during tokenizer pod selection. The current implementation randomly selects a pod, which means it can route tokenization requests to a pod that is already inference-heavy. In that case, memory backpressure on that pod will further increase the tokenization latency on top of the baseline overhead — making the latency unpredictable and harder to bound under high concurrency.
What do you think?

[FAUST-BENCHOU]

kvcache-aware tokenization is not general text segmentation; instead, it aims to produce the exact same token ID sequence that vLLM uses for inference on that model. Do you mean fetching the corresponding model's vocabulary locally and then using a local tokenizer?

[nXtCyberNet]

i dont think this is the problem as vllm was also using that exact tokenizer (https://github.com/vllm-project/vllm/blob/main/vllm/tokenizers/hf.py) , and the tokenid sequence cant be diff , and i dont think that we can find any other way for this issue

Additionally, there is currently no awareness of vLLM pod load during tokenizer pod selection. The current implementation randomly selects a pod, which means it can route tokenization requests to a pod that is already inference-heavy. In that case, memory backpressure on that pod will further increase the tokenization latency on top of the baseline overhead — making the latency unpredictable and harder to bound under high concurrency. What do you think?

[FAUST-BENCHOU]

no i mean getting the tokenizer file of specific model is hard to implement.Like merge.txt or tokenizer.json these things?since different model has different tokenizer file.I know the tokenizer rule is the same.

Additionally, there is currently no awareness of vLLM pod load during tokenizer pod selection. The current implementation randomly selects a pod, which means it can route tokenization requests to a pod that is already inference-heavy. In that case, memory backpressure on that pod will further increase the tokenization latency on top of the baseline overhead — making the latency unpredictable and harder to bound under high concurrency. What do you think?

this make sense but however, I think the definition of load here needs further discussion. Is the pod with the lowest load the one with the smallest RequestRunningNum, the smallest RequestWaitingNum, or the smallest KVCacheUsage? I believe further discussion is needed to define these accurately.

[nXtCyberNet]

hmm , ig lets wait for maintainer response as the tokenizer file we can take directly from the hugging face from the model repo , but your concern about the load definition is a real