Let the Next Request In Without Overfilling the Cache

Why a Batch Should Not Wait for Its Longest Answer

BOTIE

Batching several requests can make a model’s hardware do more useful work at once. A fixed batch becomes awkward when the requests need different numbers of output tokens. A short answer finishes, but the longest answer is still being generated. If the membership of the batch cannot change, another request waits outside while that place is unused.

Orca’s 2022 iteration-level scheduling addressed this problem by choosing the participating requests again between generation steps. This is the idea behind the changing batch we will build. A real runtime must also decide how much work and memory each step can accept. Our smaller model admits requests in queue order and reserves their full token allowance, so we can inspect those two decisions without implementing a serving engine.

Sources for this history

One Answer Finished. Why Is Its Neighbour Still Blocking the Queue?

Two answers began together. One needed a single token; the other still has several tokens to generate. Holding the original group unchanged makes the next waiting request sit outside even though one sequence has finished.

We can reconsider the group between generation iterations. Before admitting another request, however, we need room for its saved attention state as well as a place in the group.

This checks one scheduling boundary with full-continuation reservations and a queue that cannot skip its first waiting request. It does not run a model engine or measure GPU performance.

Step 1 of 1

The next iteration can use a different group

These invented rows describe a boundary after an iteration finished.

A releases its slot and reservation in this model. B continues; C still needs an admission decision.
Request	Remaining output tokens	Reserved KV blocks
A	0	2
B	3	2
C, waiting	Not started	2

A
Remaining output tokens
0
Reserved KV blocks
2
B
Remaining output tokens
3
Reserved KV blocks
2
C, waiting
Remaining output tokens
Not started
Reserved KV blocks
2

A releases its slot and reservation in this model. B continues; C still needs an admission decision.

A batch can be reconsidered between iterations

The finished rows release resources before each newly admitted request consumes its own reservation.

Release finished sequences before admitting the queue

One answer has finished and a waiting conversation wants its place. Botie needs enough cache storage for that conversation as well as a free generation slot.

BOTIE

One answer has finished and a waiting conversation wants its place. Botie needs enough cache storage for that conversation as well as a free generation slot.

Choose an example

Current rows: id, remaining, blocks

1

id

remaining

blocks

2

id

remaining

blocks

Waiting rows: id, prompt, maxNew

1

id

prompt

maxNew

2

id

prompt

maxNew

Maximum active sequences

Total cache blocks

Tokens in a cache block

Waiting request IDs admitted at this boundary

0C

Follow the operations

1. Waiting rows: id, prompt, maxNew

[
  {
    "id": "C",
    "prompt": 2,
    "maxNew": 2
  },
  {
    "id": "D",
    "prompt": 1,
    "maxNew": 1
  }
]

2. Read one request field
1. 0C
2. 1D
3. Read one request field
1. 02
2. 11
4. Read one request field
1. 02
2. 11
5. Add
1. 04
2. 12
6. Tokens in a cache block
```
2
```
7. Reserve whole blocks for each sequence
1. 02
2. 11
8. Maximum active sequences
```
2
```

9. Current rows: id, remaining, blocks

[
  {
    "id": "A",
    "remaining": 0,
    "blocks": 2
  },
  {
    "id": "B",
    "remaining": 3,
    "blocks": 2
  }
]

10. Release sequences that have finished

[
  {
    "id": "B",
    "remaining": 3,
    "blocks": 2
  }
]

11. Count items
```
1
```
12. Subtract
```
1
```
13. Total cache blocks
```
6
```
14. Read one request field
1. 02
15. Add a list
```
2
```
16. Subtract
```
4
```
17. Admit the waiting prefix that fits
1. 0C
18. Result
1. 0C

This checks one scheduling boundary with full-continuation reservations and a queue that cannot skip its first waiting request. It does not run a model engine or measure GPU performance.

1. A batch can be reconsidered between iterations

Think of the active batch as the set of answers taking part in the next generation step. When one finishes, it can leave; a waiting request may be able to join. Allowing that membership to change as generation proceeds is called continuous batching. The scheduler is the part of the service that chooses the next group.

This does not mean arbitrary work can interrupt a GPU operation midway through its execution. The runtime defines the boundary at which it can safely change the next group.

At this boundary, finished rows leave and waiting rows can be considered for the next group.

2. A sequence limit and a token budget measure different things

We need two counts. A sequence slot is a place for one active request. The cache reservation is the storage promised to its retained tokens. A short answer and a long conversation can each take one slot while requiring very different amounts of memory.

Some runtime settings bound tokens scheduled in an iteration rather than all resident cache tokens. Read the deployed version’s definitions instead of treating every “token limit” as the same capacity.

maximum active sequences = 2
unfinished sequences after release = 1
free sequence slots = 2 - 1 = 1

One free slot does not promise that the next conversation’s cache will fit.

Check yourself

Questions on Parts 1 to 2

Question 1 of 2

Which row still owns a sequence slot?

Use the information below.

Active A has remaining=0 and B has remaining=3. The model releases finished rows at the iteration boundary.

3. Reserve the prompt and the allowed continuation

For this conservative policy, each queued request supplies prompt tokens and a maximum number of new tokens. Add them, then round up to whole blocks. This avoids promising a continuation whose reservation cannot fit. It may also leave memory unused when responses finish early.

request C: prompt 3, maximum new tokens 2
block size = 2 tokens
reservation = ceil((3 + 2) / 2) = 3 blocks

This policy reserves a complete allowance. Real engines may allocate incrementally, share prefixes, preempt sequences or apply different limits.

4. Release first, then test both limits

Remove finished rows before calculating free slots and free blocks. Walk the waiting queue in order. Admit its head only if both resources permit, then reduce both allowances before considering the next request.

Our queue follows first in, first out, or FIFO. If its first request cannot fit, we stop at that request. A later, smaller one might fit, but allowing it to pass would change the policy. We would then need to consider how long the larger request might keep waiting.

cache capacity = 6 blocks
unfinished B reserves 2 blocks
free blocks = 6 - 2 = 4
free slots = 1
C needs 3 blocks: admit C
remaining slot allowance = 0

The output is the newly admitted IDs, not all active IDs. B was already running.

5. A longer prompt trips slot-only admission

If C’s prompt grows, it may need more blocks than remain even though the slot count is unchanged. Accepting solely on free sequence slots can then overcommit memory. Conversely, spare memory does not create more supported sequence slots.

This is why a capacity test should change lengths as well as request counts. A benchmark with only tiny prompts can make a service appear ready for a workload it cannot hold.

Generation length limits also change the reservation. Keep those limits with the reported capacity assumptions.

6. What the simplified boundary leaves out

We release a finished sequence’s entire reservation immediately and ignore reusable idle cache blocks, fragmentation beyond block rounding, swapping, parallel devices and cancellation races. Prefill and decode also compete for execution time in real engines.

Evaluate an actual scheduler with arrival traces, lengths, deadlines and failure outcomes. Passing this workshop shows that the reservation arithmetic respects its two limits; it does not establish a production service rate.

The next lesson separates a request asking to stop from the engine confirming that its resources are released.

Check yourself

Questions on Parts 1 to 6

Question 1 of 4

What reservation follows this lesson’s policy?