LLM Rate Limiter

Instructions

You are building the token rate limiter that sits in front of an LLM inference service.

We know every request to the model consumes a number of tokens (prompt + completion tokens + ...), and each user is issued a key so that their usage can be tracked and limited.

Each key is assigned a tier that defines its token budget: a burst capacity, a refill amount, and a refill interval in seconds.

Implement the TokenLimiter class:

• TokenLimiter(tiers) — initializes the limiter, where each tiers[i] is a list of strings [user_key, capacity, refill_amount, refill_interval]:

  • user_key — the unique key this tier applies to.
  • capacity — the maximum token budget the key can hold at any time (its burst allowance).
  • refill_amount — tokens granted at each refill (the budget never exceeds capacity).
  • refill_interval — seconds between refills.

  Every key starts with a full budget at timestamp = 0, and refills land at t = refill_interval, 2 * refill_interval, ....

• allow_request(user_key, tokens, timestamp) — attempts to admit a request costing tokens at timestamp. If the key's budget (after applying any refills due by timestamp) holds at least tokens, deduct them and return True; otherwise leave the budget unchanged and return False, meaning the request is rejected. Requests from unknown keys return False.

Note: the limiter must enforce each key's tier independently, and must handle refills efficiently even when requests arrive at irregular times.

Example:

tl = TokenLimiter([["key-alice", "100000", "100000", "60"], ["key-bob", "50000", "50000", "120"]])

tl.allow_request("key-alice", 100000, 60)   # True  — alice is full (100k), spends it all
tl.allow_request("key-bob", 50000, 60)      # True  — bob is full (50k), spends it all
tl.allow_request("key-alice", 50000, 60)    # False — alice has 0 tokens left at t=60
tl.allow_request("key-bob", 10000, 90)      # False — bob has 0; his next refill lands at t=120
tl.allow_request("key-alice", 100000, 120)  # True  — alice refilled 100k at t=120
tl.allow_request("key-bob", 50000, 120)     # True  — bob refilled 50k at t=120

Constraints:

• 1 <= tiers.length <= 10^4
• 1 <= tokens <= 10^9
• 0 <= timestamp <= 10^9
• For each key, allow_request timestamps are non-decreasing; multiple calls may share a timestamp.
• Refill lazily on request — do not pre-schedule updates for every interval.

Function Signature

from typing import List


class TokenLimiter:
    def __init__(self, tiers: List[List[str]]):
        pass

    def allow_request(self, user_key: str, tokens: int, timestamp: int) -> bool:
        pass