Cache-Aware Request Routing Across Replicas

Problem statement

In production LLM serving systems, multiple model replicas serve inference requests. Each replica maintains a KV cache of previously computed prefixes. When a new request arrives, routing it to a replica that already has its prefix cached can avoid expensive recomputation, dramatically reducing time-to-first-token (TTFT).

Implement a cache-aware request router that assigns incoming requests to model replicas. For each request, the router should:

  1. Compute the longest matching prefix between the request's token sequence and each cached prefix on every replica
  2. Calculate a composite routing score per replica that balances cache affinity against current load
  3. Assign the request to the highest-scoring replica and update that replica's load
  4. Skip replicas that have reached their maximum capacity (unless all replicas are full, in which case pick the one with the lowest load ratio and still compute cache affinity)

The routing score for a replica is: score = alpha (longest_match_length / request_length) - beta (active_requests / max_capacity)

Process requests sequentially, updating replica load after each assignment.

Return a dictionary containing:

  • 'assignments': list of replica indices (one per request)
  • 'cache_hit_rates': list of floats (match_length / request_length for each assignment, rounded to 2 decimals)
  • 'avg_cache_hit_rate': float (mean of cache_hit_rates, rounded to 2 decimals)
  • 'load_distribution': list of ints (final active_requests per replica after all routing)

Details:

  • Write cache_aware_route(replicas, requests, alpha=0.7, beta=0.3). Do not modify the input replicas; work on a copy of the loads.
  • The match length for a replica is the longest common prefix (from position 0) between the request tokens and any one of its cached prefixes. Cached prefixes do not change during routing.
  • A replica is full when active_requests >= max_capacity. Among non-full replicas, pick the highest score; on a tie, pick the lowest index. If every replica is full, pick the lowest active_requests / max_capacity (lowest index on a tie).
  • avg_cache_hit_rate is the mean of the already-rounded per-request rates, rounded to 2 decimals, or 0.0 if there are no requests.

Example

Input:

replicas = [
    {'cached_prefixes': [[1, 2, 3, 4, 5]], 'active_requests': 0, 'max_capacity': 5},
    {'cached_prefixes': [[6, 7, 8, 9, 10]], 'active_requests': 0, 'max_capacity': 5},
    {'cached_prefixes': [[1, 2, 3, 11, 12]], 'active_requests': 0, 'max_capacity': 5}
]
requests = [
    {'tokens': [1, 2, 3, 4, 5, 13, 14]},
    {'tokens': [6, 7, 8, 9, 15]},
    {'tokens': [1, 2, 3, 11, 12, 16]}
]
alpha = 0.7, beta = 0.3

Output:

{'assignments': [0, 1, 2], 'cache_hit_rates': [0.71, 0.8, 0.83], 'avg_cache_hit_rate': 0.78, 'load_distribution': [1, 1, 1]}

Reasoning: Request 1 has tokens [1,2,3,4,5,13,14]. Replica 0 matches prefix [1,2,3,4,5] for 5 tokens (hit rate 5/7=0.71), Replica 2 matches 3 tokens (hit rate 3/7=0.43), Replica 1 matches 0. Since all loads are 0, Replica 0 wins with score 0.7*0.71=0.50. Request 2 tokens [6,7,8,9,15] best match Replica 1 with 4 tokens (hit rate 0.8). Request 3 tokens [1,2,3,11,12,16] best match Replica 2 with 5 tokens (hit rate 5/6=0.83). Each replica gets one request.

Show hint

For a single cached sequence, how do you measure how much of the request's beginning is already computed?

Relevant roles: LLM Engineer, MLOps Engineer, AI Engineer and AI Architect.

Related free problems