For the single-DC case, the time complexity of the DynP algorithm is
𝑂
(
𝑆
𝐿
2
𝐺
2
)
O(SL
2
G
2
).
As the model depth and the number of GPUs continue to grow, do the authors anticipate scalability challenges in practical deployments of CDynP?
Are there any plans to incorporate pruning techniques, approximate dynamic programming, or heuristic methods to further reduce the computational cost?
Yes, as model depth (L) and GPU count (G) grow, the O(S L² G²) complexity of the single-DC DynP algorithm could pose challenges for extremely large-scale deployments. However, CDynP mitigates this through its chain-based decentralized approach, which partitions the problem across K data centers, effectively reducing the search space to O(S (L/K)² G²) per node and avoiding the combinatorial explosion of a global optimization. Our evaluations in Section V.B.3 demonstrate that CDynP maintains practical search times—e.g., 39.27 seconds for a 32-GPU setup—which is 13.4× faster than SPP, as it leverages compressed state summaries to limit computational overhead. While the current framework prioritizes privacy and near-optimality, we acknowledge that further scalability may require enhancements. In future work (Section VI), we plan to explore adaptive techniques, such as heuristic pruning for layer splits or approximate dynamic programming, to reduce costs without compromising solution quality. These methods could integrate with CDynP’s chain structure to handle exponential growth in model parameters, ensuring robustness for next-generation AI training. Thus, although complexity is a consideration, CDynP’s design already provides a balanced trade-off, and ongoing efforts aim to enhance efficiency for larger deployments.
