Submodular Max-Delay Batch Timer

Integrate this at the dynamic batching queue immediately before a Transformer forward pass or a batched MoE dispatch. Each queued request r has arrival time a(r), token count, sequence length, and routing or device metadata. For a candidate batch B, estimate M(B) as the predicted service cost: for inference this can be measured FLOPs plus padding overhead, while for MoE it can be the number of expert-token transfers and active expert kernels. Maintain the current batch B and periodically inspect the oldest not-yet-served request r_next. Pseudocode: initialize B empty; on arrival append r; at every scheduler tick compute M(B), M(B union {r_next}), and the merging saving DeltaM=M(B)+M({r_next})-M(B union {r_next}); compute the current oldest-request delay DeltaD=t-a(r_oldest); if DeltaM < (1-theta)*DeltaD, flush B, otherwise keep waiting until the next tick or a hard deadline. Use a short-horizon dynamic program over the last K arrivals when several possible boundaries are available: F[j]=min_{i<j}(F[i-1]+w(S_{i:j})+max_delay(i:j)), and choose the minimizing interval as the proposed flush boundary. The paper supplies the submodular inequality and h_theta potential; M, delay predictions, and hardware service times are estimated online. First test on a 1B-parameter decoder with Poisson and bursty request arrivals, comparing fixed 10, 20, and 50 ms timeouts and token-count batching. Measure tokens per second, p95 and p99 latency, average oldest-request delay, and GPU utilization. Success means at least 10% higher throughput at equal p99 latency, or lower p99 latency at equal throughput, without unstable oscillation between tiny and oversized batches.