Authors: Minchul Kang, Changyong Shin, Younghun Go, Hyunho Lee, Jinwoo Jeong, Chuck Yoo, Gyeongsik Yang
Venue: The 2026 Conference on Empirical Methods in Natural Language Processing (EMNLP 2026), Main Track, Budapest, Hungary, 2026. (Accepted) (2026)
Abstract: Selecting a parallelism strategy—the configuration of data, tensor, and pipeline parallelism degrees together with micro- and global-batch sizes—largely determines the training efficiency of large language models. State-of-the-art methods search for a parallelism strategy offline and select the single strategy that minimizes per-iteration time. But we find that they neglect the target validation perplexity and time-to-perplexity (TTP). In particular, our analysis reveals that the best strategy yielding the fastest perplexity improvement changes multiple times during training. As a result, compared with the optimum sequence that always uses the best strategy at each iteration, state-of-the-art methods are 1.8–11.4× slower in TTP. This paper proposes CONA, a new training method that introduces online strategy chaining. Instead of a single strategy selected offline, CONA ranks candidate strategies during training using a surrogate metric built from compute throughput and gradient statistics, and switches the current strategy to a new strategy with a higher metric. In our evaluation with GPT-3 1.3B, BERT-Large, and Llama-3.2-1B, CONA reaches the target validation perplexity 1.4–9.6× faster than state-of-the-art methods. Moreover, CONA closely tracks the optimum strategy sequence within 2.6%.