KV-Aware Request Routing

Problem

Route one request using cached-prefix reuse and token-slot capacity. Each worker is {"id": string, "used": occupied slots, "capacity": total slots, "prefix": one cached token list}. Reuse is the common-prefix length of prompt and that list, stopping at the first mismatch.

Additional required slots = len(prompt)−reuse+max_new_tokens. A worker is eligible when used+required ≤ capacity. Rank eligible workers by greatest reuse, then smallest projected utilization (used+required)/capacity, then lexicographically smallest ID. Return the chosen ID, or null if none fits. Do not mutate worker usage. Cached slots are already included in used; this is a specified placement heuristic.

def route_request(prompt, max_new_tokens, workers):

Constraints

• prompt/prefix lists contain 0..32 integer tokens; 0 ≤ max_new_tokens ≤32.
• 0..16 workers with unique ASCII IDs; 0 ≤ used ≤ capacity, and 1 ≤ capacity ≤128.
• Inputs satisfy these constraints; invalid-input handling is not graded. Use only Python standard library and NumPy.

Examples

Arguments: [
  [
    1,
    2,
    3
  ],
  1,
  [
    {
      "id": "a",
      "used": 2,
      "capacity": 10,
      "prefix": [
        1
      ]
    },
    {
      "id": "b",
      "used": 3,
      "capacity": 10,
      "prefix": [
        1,
        2
      ]
    }
  ]
]
Expected result: "b"

Arguments: [
  [
    1,
    2
  ],
  2,
  [
    {
      "id": "a",
      "used": 4,
      "capacity": 5,
      "prefix": [
        1,
        2
      ]
    },
    {
      "id": "b",
      "used": 0,
      "capacity": 5,
      "prefix": []
    }
  ]
]
Expected result: "b"