TensorTonic
Study Plans
Study Plan
Simulate Continuous Decode Batching
Language ModelsInference
Hard

Simulate continuous decoding in integer time steps. Each request contains id, arrival_step, prompt_tokens, and max_new_tokens. Admission reserves its full prompt-plus-generation footprint until completion. Consider arrived waiting requests by arrival time, breaking ties by input order. If one does not fit, leave it waiting and continue considering later requests.

In each recorded step, admission occurs before decoding and again after completions release capacity. Every request active for the decode phase generates one token. Requests admitted afterward start decoding next step. A zero-generation request finishes immediately on admission. Skip idle gaps before the next arrival.

Record the state after the second admission pass. admitted lists that step's admissions in occurrence order; active lists remaining requests in admission order; finished lists completions in occurrence order, using active order for simultaneous decode completions. Actual KV use counts each active prompt plus its tokens generated so far, not its reserved footprint.

Return a Python list of step dictionaries in increasing time order. Each contains step and kv_tokens_in_use as Python integers, plus admitted, active, and finished as lists of request IDs. Empty input returns an empty list.

Loading visualization...

Examples

Input: requests = [{"id":"A","arrival_step":0,"prompt_tokens":2,"max_new_tokens":2},{"id":"B","arrival_step":0,"prompt_tokens":1,"max_new_tokens":1}], kv_capacity = 4

Output: [{"step":0,"admitted":["A"],"active":["A"],"finished":[],"kv_tokens_in_use":3},{"step":1,"admitted":["B"],"active":["B"],"finished":["A"],"kv_tokens_in_use":1},{"step":2,"admitted":[],"active":[],"finished":["B"],"kv_tokens_in_use":0}]

Explanation: A reserves the initial capacity, then its completion lets B enter during the second admission pass.

Input: requests = [{"id":"Z","arrival_step":3,"prompt_tokens":1,"max_new_tokens":0}], kv_capacity = 2

Output: [{"step":3,"admitted":["Z"],"active":[],"finished":["Z"],"kv_tokens_in_use":0}]

Input: requests = [{"id":"A","arrival_step":0,"prompt_tokens":1,"max_new_tokens":1},{"id":"B","arrival_step":0,"prompt_tokens":1,"max_new_tokens":1}], kv_capacity = 4

Output: [{"step":0,"admitted":["A","B"],"active":[],"finished":["A","B"],"kv_tokens_in_use":0}]

Hint 1

Python sorting is stable when two keys compare equal.

Hint 2

A separate generated-token counter distinguishes actual use from reservation.

Hint 3

Build a new waiting list when requests are admitted during a scan.

Requirements

  • Use Python lists, dictionaries, strings, and integers for the documented records.
  • Respect the reserved capacity while reporting actual KV use separately.
  • Do not modify request records.

Constraints

  • requests is a Python list of dictionaries with unique string IDs and nonnegative integer arrival_step, prompt_tokens, and max_new_tokens.
  • Every prompt-plus-generation footprint is at most kv_capacity.
  • kv_capacity is a positive Python integer.
  • Empty requests and zero-generation requests are valid.
Try Similar Problems
Route Cache-Aware Prefill RequestsHardFind Reusable Prefixes in a KV TrieMediumDecode Attention with a KV CacheHardPerform Exact Speculative SamplingHardPlan KV-Cache CapacityMediumMeasure Kernel Timeline UtilizationMediumRecover an IsoFLOP Compute-Optimal FrontierHardFit a Data Power Law with a Noise FloorHardImplement Speculative Decoding and Token VerificationHardBeam Search DecodingHardImplement Prefix Cache Matching and ReuseMediumText Generation SamplingMedium

Accepts: array

Accepts: number

You must run your code first.

Simulate Continuous Decode Batching

Language ModelsInference
Hard

Simulate continuous decoding in integer time steps. Each request contains id, arrival_step, prompt_tokens, and max_new_tokens. Admission reserves its full prompt-plus-generation footprint until completion. Consider arrived waiting requests by arrival time, breaking ties by input order. If one does not fit, leave it waiting and continue considering later requests.

In each recorded step, admission occurs before decoding and again after completions release capacity. Every request active for the decode phase generates one token. Requests admitted afterward start decoding next step. A zero-generation request finishes immediately on admission. Skip idle gaps before the next arrival.

Record the state after the second admission pass. admitted lists that step's admissions in occurrence order; active lists remaining requests in admission order; finished lists completions in occurrence order, using active order for simultaneous decode completions. Actual KV use counts each active prompt plus its tokens generated so far, not its reserved footprint.

Return a Python list of step dictionaries in increasing time order. Each contains step and kv_tokens_in_use as Python integers, plus admitted, active, and finished as lists of request IDs. Empty input returns an empty list.

Loading visualization...

Examples

Input: requests = [{"id":"A","arrival_step":0,"prompt_tokens":2,"max_new_tokens":2},{"id":"B","arrival_step":0,"prompt_tokens":1,"max_new_tokens":1}], kv_capacity = 4

Output: [{"step":0,"admitted":["A"],"active":["A"],"finished":[],"kv_tokens_in_use":3},{"step":1,"admitted":["B"],"active":["B"],"finished":["A"],"kv_tokens_in_use":1},{"step":2,"admitted":[],"active":[],"finished":["B"],"kv_tokens_in_use":0}]

Explanation: A reserves the initial capacity, then its completion lets B enter during the second admission pass.

Input: requests = [{"id":"Z","arrival_step":3,"prompt_tokens":1,"max_new_tokens":0}], kv_capacity = 2

Output: [{"step":3,"admitted":["Z"],"active":[],"finished":["Z"],"kv_tokens_in_use":0}]

Input: requests = [{"id":"A","arrival_step":0,"prompt_tokens":1,"max_new_tokens":1},{"id":"B","arrival_step":0,"prompt_tokens":1,"max_new_tokens":1}], kv_capacity = 4

Output: [{"step":0,"admitted":["A","B"],"active":[],"finished":["A","B"],"kv_tokens_in_use":0}]

Hint 1

Python sorting is stable when two keys compare equal.

Hint 2

A separate generated-token counter distinguishes actual use from reservation.

Hint 3

Build a new waiting list when requests are admitted during a scan.

Requirements

  • Use Python lists, dictionaries, strings, and integers for the documented records.
  • Respect the reserved capacity while reporting actual KV use separately.
  • Do not modify request records.

Constraints

  • requests is a Python list of dictionaries with unique string IDs and nonnegative integer arrival_step, prompt_tokens, and max_new_tokens.
  • Every prompt-plus-generation footprint is at most kv_capacity.
  • kv_capacity is a positive Python integer.
  • Empty requests and zero-generation requests are valid.
Try Similar Problems
Route Cache-Aware Prefill RequestsHardFind Reusable Prefixes in a KV TrieMediumDecode Attention with a KV CacheHardPerform Exact Speculative SamplingHardPlan KV-Cache CapacityMediumMeasure Kernel Timeline UtilizationMediumRecover an IsoFLOP Compute-Optimal FrontierHardFit a Data Power Law with a Noise FloorHardImplement Speculative Decoding and Token VerificationHardBeam Search DecodingHardImplement Prefix Cache Matching and ReuseMediumText Generation SamplingMedium

Accepts: array

Accepts: number

You must run your code first.