Parallel Unmasking under Unknown Dependence: Exact Minimax Batching

Diffusion language models decode multiple tokens in parallel to accelerate generation, but tokens in the same batch cannot use one another's values, so parallel decoding may fail to preserve their dependencies. Existing decoders use confidence or estimated dependence to set batch sizes, yet the best worst-case guarantee remains unknown when batch sizes must be chosen without reliable dependency information. We exactly characterize this limit for every sequence length and call budget, construct a plan that attains it, and give matching targets showing no fixed deterministic plan can do better when vocabulary is large enough. The key is to track when dependence becomes relevant during decoding. Each plan can be judged by its risk at every stage, and the optimum minimizes the largest. We also quantify the gains from randomization when the chosen schedule is known, identify when online adaptation cannot improve the boundary, and exactly separate batching from predictor error. On LLaDA and Dream, theory-derived batch sizes improve generation accuracy over equal batching with the same position-selection rule and call budget.