Task. You have a function fits(b) that runs one training step at batch size b and reports whether it ran out of
memory (OOM). Bigger batches never use less memory, so fits is T…T F…F. Find the largest b that fits, with as
few calls as possible, given an upper limit B_max (say 65,536).
fits(b) = True for b ≤ 384, False for b > 384 → 384
ML context. This is the batch-size finder that training frameworks run before a job, and the same search sets the largest sequence length, the most concurrent requests a serving replica can hold in its KV cache, or the most images per GPU for inference. Each call allocates the model, runs a forward and backward pass, and frees everything: seconds per trial, and an OOM can leave the allocator fragmented. The number of trials is the cost.