Padding waste was never about the batch

Part five reported that padding waste converges on 50% once request lengths spread out, because the maximum inside a batch pins to the ceiling as the batch grows. The remedies got named and left unmeasured.

That number carried an unstated premise: requests are taken in the order they arrive. Allow them to be reordered and the question changes.

Not the batch, the pool

Fix the batch at 32 and vary only how many requests are collected before grouping. Lengths are uniform from 1 to 128; the pool is sorted by length and then cut into groups of 32 from the front.

pooled   groups   waste (sorted)   waste (arrival)
    32        1            47.4%            47.4%
    64        2            32.2%            48.0%
   128        4            18.7%            46.8%
   256        8            10.4%            46.6%
   512       16             5.5%            47.3%
  1024       32             2.9%            47.6%
  4096      128             0.7%            47.9%

The batch is 32 throughout. All that changes is how many were waiting in front of it, and the waste goes from 47.4% to 0.7%.

With one group, sorting achieves nothing: sort 32 requests into one group of 32 and only the order changes, not the maximum. At two groups the long ones start separating from the short ones, and at 128 groups the spread of lengths inside a group narrows to about one.

Arrival order does not move from 47% however many requests turn up. The maximum of 32 random draws is near the ceiling regardless of how many you drew from.

Part five’s 50% was not a property of batching but the consequence of declining to reorder.

The price is paid in waiting

Not free. Pooling 4096 requests means waiting for 4096 requests. The first to arrive stands in the queue until others of similar length show up, and that time becomes latency.

It is part five’s throughput-against-latency trade with a different dial. There, batch size bought latency; here, waiting buys waste - with the batch held at 32 the whole time.

Removing all the waste halves nothing

One more thing has to be measured. If the waste falls from 47% to 0.7%, does the time follow? No.

Holding the batch at 32 and varying only the cache length:

cache length   time (us)
           1         723
          16         901
          32         873
          64        1171
         128        1398

Going from 1 to 128 adds 675 us. So 48.3% of a step depends on length and 51.7% does not: the linear layers push one token through no matter how long the cache is, and part five’s fixed overhead a is unchanged. Padding attaches to attention and nowhere else.

So for 256 requests at batch 32, taking the waste from 46.4% to 10.2% predicts a time gain of 1.24. What was removed was 40% of the half of a step that depends on length at all.

Confirming that 1.24 by measurement does not resolve on this laptop. Alternating arrival order and sorted, seven paired ratios, the median at batch 32 is 1.36 with a range of 0.87-1.68, and at most batch sizes the range straddles 1.0. The first single run gave 1.22, agreeing with the prediction nicely; re-measuring the same configuration gave 0.91. A number that agreed once is not a result. The waste figures reproduce exactly given the list of lengths, which is where these tables rest.

What is left

Sorting is a one-shot arrangement. Requests finish at different times, so a short one’s seat stays empty until the long ones are done. Filling it immediately is continuous batching, and this experiment did not go there.

The lengths used here are uniform from 1 to 128. Real request lengths bunch at the short end with a long tail, where arrival-order waste would be higher and sorting would gain more - unmeasured.

So

• 50% was not a property of batching. It followed from declining to reorder
• Holding the batch at 32 and growing the pool from 32 to 4096 takes the waste from 47.4% to 0.7%
• With one group sorting does nothing. It needs somewhere to separate things into
• Arrival order sits at 47% however many arrive; the maximum of 32 draws is always near the ceiling
• The price is waiting. Part five bought latency with batch size; this buys waste with pooling
• Removing the waste does not halve the time. Only 48.3% of a step depends on length