Implement page-aware cache admission

Advanced60 min

Implement admit_requests(requests, budget_bytes, bytes_per_token, page_tokens=16) to reserve full prompt-plus-output cache capacity and admit requests deterministically.

Your task

Each request is a tuple (id, prompt_tokens, max_new_tokens). IDs must be unique nonempty strings; prompt_tokens must be a positive integer and max_new_tokens a nonnegative integer.
Require integer budget_bytes >= 0, bytes_per_token > 0, and page_tokens > 0. Reject booleans as integers.
Round each request total tokens upward to a whole page before converting to bytes.
Scan in input order, admitting a request only when its entire reservation fits. Skip a non-fitting request and continue checking later ones.
Return {"admitted": [ids], "deferred": [ids], "used_bytes": integer, "free_bytes": integer}. Validate the complete input and raise ValueError on invalid data.

Examples

EXAMPLE 1

Input[("a", 17, 0), ("b", 16, 0)], budget=96, bytes_per_token=2, page_tokens=16

Output{"admitted": ["a", "b"], "deferred": [], "used_bytes": 96, "free_bytes": 0}

The 17-token request reserves 32 slots; the 16-token request reserves 16.

def admit_requests(requests, budget_bytes, bytes_per_token, page_tokens=16):
    raise NotImplementedError