Scheduling Backwards for LLM Batching under Progress Constraints

Requests in an LLM decode batch generate their next tokens together, even though their attention workloads differ with context length. This motivates controlling resource disparity within a batch. We study an offline, nonpreemptive scheduling model with $B$ slots and a budget $\alpha$ on generated-token progress differences; for equal prompt lengths, this also bounds context-length disparity. The constraint creates admission blackouts: a slot can be free even though no new request can join the running batch. We introduce Right-Aligned scheduling (RA), which constructs schedules backwards to coordinate request starts. A window invariant proves that RA never has a larger makespan than sorted static batching on any instance. Refined idle-time accounting yields a $(2-(11B-2)/(9B^2))$-approximation, with a tight $3/2-1/(2B)$ factor on instances of at most $2B$ requests for $B\ge 3$. An observation-based retiming rule preserves feasibility under valid duration upper bounds. On held-out conversational snapshots at a prespecified operating point, the retimed implementation improves logical throughput by $8.9\%$ over the strongest tested same-budget forward baseline, and by $4.6\%$ under bounded forecast perturbations.