Paged Continuous Batching

Problem

Simulate a bounded serving trace with dynamic KV page growth. requests are {"id", "prompt_tokens", "new_tokens", "arrival"}, where arrival is an integer tick. Initially no request is active. Sort waiting requests by arrival then original input order. For each tick starting at 0, admit arrived requests FIFO while slots and enough pages for their prompt are available; if the head cannot fit, stop admission for that tick. Prefill is instantaneous in this model.

Then visit active requests in admission order. Each attempts one decode token. It needs ceil((prompt_tokens+generated+1)/page_size) pages. If growing its allocation would exceed total_pages, skip that request’s decode this tick. Otherwise generate one token. On reaching new_tokens, complete it and release all its pages immediately, allowing later active requests to use them in the same tick. Freed slots admit new requests only at the next tick.

Stop after max_ticks or when every request has completed. Return {"steps": [{"tick","admitted": IDs,"decoded": IDs,"completed": IDs,"pages": end-of-tick allocated pages}], "waiting": unadmitted IDs in queue order including future arrivals, "active": [{"id","generated","pages"}] in admission order}. Include idle/stalled ticks. This deliberately bounded model has no preemption or deadlock recovery; stalled requests remain visible at the limit.

def paged_continuous_batching(requests, page_size, total_pages, slots, max_ticks):

Constraints

• 0..16 requests with unique string IDs; prompt_tokens,new_tokens are positive integers ≤32; arrival is 0..16.
• 1 ≤ page_size,total_pages,slots ≤16; 0 ≤ max_ticks ≤32.
• A request may be too large to admit; never exceed total_pages or slots.
• Inputs satisfy these constraints; invalid-input handling is not graded. Use only Python standard library and NumPy.

Examples

Arguments: [
  [
    {
      "id": "a",
      "prompt_tokens": 1,
      "new_tokens": 2,
      "arrival": 0
    }
  ],
  2,
  2,
  2,
  5
]
Expected result: {
  "steps": [
    {
      "tick": 0,
      "admitted": [
        "a"
      ],
      "decoded": [
        "a"
      ],
      "completed": [],
      "pages": 1
    },
    {
      "tick": 1,
      "admitted": [],
      "decoded": [
        "a"
      ],
      "completed": [
        "a"
      ],
      "pages": 0
    }
  ],
  "waiting": [],
  "active": []
}

Arguments: [
  [
    {
      "id": "a",
      "prompt_tokens": 1,
      "new_tokens": 1,
      "arrival": 0
    },
    {
      "id": "b",
      "prompt_tokens": 1,
      "new_tokens": 1,
      "arrival": 0
    }
  ],
  2,
  1,
  1,
  5
]
Expected result: {
  "steps": [
    {
      "tick": 0,
      "admitted": [
        "a"
      ],
      "decoded": [
        "a"
      ],
      "completed": [
        "a"
      ],
      "pages": 0
    },
    {
      "tick": 1,
      "admitted": [
        "b"
      ],
      "decoded": [
        "b"
      ],
      "completed": [
        "b"
      ],
      "pages": 0
    }
  ],
  "waiting": [],
  "active": []
}