Lagom: Unleashing the Power of Communication and Computation Overlapping for Distributed LLM Training Guanbin Xu † , ZhenGuo Xu † , Yuzhe Li † , Youhui Bai † , Ping Gong † , Chaoyi Ruan ‡ Cheng Li †,∘ Abstract . Overlapping communication with computation is crucial for distributed large-model training, yet optimizing it—especially when computation becomes the bottleneck—remains challenging. We present Lagom , a system that co-tunes communication parameters to balance resource usage between computation and communication. By introducing a unified cost model and a priority-based search algorithm, Lagom reduces optimization complexity from exponential to linear. Evaluations on high- and low-bandwidth GPU clusters show that Lagom achieves 1.07-1.33 × \times and 1.03-1.27 × \times speedup over NCCL and AutoCCL across diverse models and parallelizations. 1. Introduction The increasing scale of Deep Neural Networks (DNNs) is driving the need for distributed training, which is often limited by communication bottlenecks. To this end, a common optimization is to overlap communication with computation ( 19 ; 2 ; 1 ) . However, achieving optimal performance of overlap remains challenging, as communication operations contend with computation kernels for limited GPU resources. In practice, mature overlap strategies in industry often hide most communication latency ( 9 ) , shifting the primary bottleneck to computation. Yet, even in such computation - bottlenecked scenarios, communication still interferes with computation, leaving overlooked opportunities for further optimization. Existing approaches to managing contention have notable limitations. Liger ( 4 ; 30 ) mitigates contention by statically limiting communication’s GPU resources, but its fixed allocation lacks adaptability. Libra ( 12 ) models overlap cost for GPU thread selection in data parallelism, yet it ignores key parameters ( e.g. chunk size and number of channels) that we find have a greater impact on computation (Sec. 3.2 ). AutoCCL ( 29 ) , the state-of-the-art communication tuner, addresses parameter tuning and is effective when communication is the bottleneck. While these approaches address specific aspects of overlap, they fail to holistically manage the dual-bottleneck scenario, especially when computation becomes the bottleneck where our analysis reveals that communication contention still degrades the performance of the bottlenecked computation by up to 35%. Figure 1 . Side effects from tuning a single communication. Top: baseline execution. Bottom: after tuning Comm1, increased resource contention delays Comp2. Our analysis reveals that by strategically allocating fewer resources to communication, computation can utilize more resources, thereby accelerating the entire overlap. However, achieving this efficient overlap through parameter tuning is nontrivial, facing key challenges: (1) Contention Complexity : The relationship between the vast tunable parameter space and resource contention during the overlap of communication and computation operators—which must share multiple GPU resources—remains an open and poorly understood research problem. (2) Exponential Search Space : To prevent deadlock, collective communications are serialized, creating a chain of temporal dependencies. Consequently, tuning parameters for one communication (e.g., Comm1) affects not only its own execution but also cascades to delay dependent computations and other communications, as visualized in Fig. 1 . This interdependence makes the joint optimization space grow exponentially with the number of communications—i.e., exceeding 1,000,000^{N} for N communications. An exhaustive search is infeasible, as it would require hundreds of GPU hours even for moderate N. This paper presents Lagom , a novel system for tuning collective communication parameters. By introducing an overlap performance model and a resource-efficiency search heuristic, Lagom efficiently identifies near-optimal configurations for overlapping communication and computation. The main contributions are: (1) Unified Overlap Performance Model : We formalize a unified cost model for computation-communication overlap that captures performance in both computation-bound and communication-bound regimes, establishing a foundational basis for optimization. (2) Contention Analysis and Modeling : We analyze and categorize contention into two main types—SM competition and global resource contention—and model their relationship with tunable communication parameters. (3) Tuning Algorithm and Evaluation : We introduce a fast search algorithm based on model-guided heuristics that reduces the optimization complexity and achieves 1.07-1.33 \times speedup across diverse models and parallelisms. The code for Lagom will be open-sourced soon. 2. Background and Motivation 2.1. Parallelism and Overlapping Figure 2 . Overlaps of Different Parallelism As data and model scales continue to grow, distributed training has become essential ( 5 ; 26 ) . Modern systems adopt various parallelisms that exploit communication–computation overlap as Fig. 2 . The main forms include: Tensor Parallelism (TP) ( 23 ) partitions large operators across devices to ease memory pressure, but incurs synchronization overhead (e.g., AllReduce ). Domino ( 27 ) mitigates this via batch-level pipelining, though perfect overlap remains difficult. Expert Parallelism (EP) ( 22 ) distributes experts across devices and relies on frequent AlltoAll . While efforts like the dual batch method aim to overlap communication with computation by resource partitioning ( 11 ) , the cluster-specific resource allocation and AlltoAll-only implementation limit general applicability. Fully Sharded Data Parallelism (FSDP) ( ( 31 ; 20 ) ) exhibits a more intricate overlap pattern, where each layer’s computation interleaves with multiple communication phases ( AllGather and ReduceScatter ) across layers. Such multi-stage coupling makes concurrent optimization between computation and communication highly complex, often hindering ideal overlap. These parallelisms are often combined with data parallelism ( 10 ; 21 ; 28 ) and pipeline parallelism ( 6 ; 14 ) to support even larger-scale training ( 32 ; 8 ; 15 ; 9 ) . 2.2. Operators in Overlap and Parameter Tuning Overlap involves over 1,500 computational operators ( 31 ) , primarily implemented in closed-source libraries like cuBLAS ( 17 ) and cuDNN ( 18 ) , making direct modification infeasible. In contrast, collective communications benefit from optimized open-source libraries like NCCL ( 16 ) . AutoCCL ( 29 ) identified six key parameters (Algorithm, Protocol, Transport, Number of Channels, Number of Threads, Chunk Size) that govern communication performance. They make a key observation that the configuration space can be addressed using a divide-and-conquer strategy. It first partitions the space into subspaces based on implementation-related parameters (Algorithm, Protocol, Transport), then models resource-related parameters (Number of Channels, Number of Threads, Chunk Size) within each subspace. Crucially, instead of explicitly modeling complex interference patterns, AutoCCL employs online sampling with real-time performance feedback to efficiently search resource-related parameters in each subspace. We extend this finding by showing that these parameters also regulate GPU resource allocation during overlap, thereby critically affecting communication-computation contention. 2.3. Challenges However, the interaction between communication and computation is inherently difficult. The dynamic nature of multi-communication tuning expands the search space exponentially, making joint optimization challenging. These challenges mainly arise from: (1) Complex Contention Between Communication and Computation. Communication operations share core GPU resources such as Streaming Multiprocessors (SMs), global memory bandwidth, and L2 cache with computations. The degree of contention varies with communication type, message type, concurrency, and hardware design, making performance modeling highly nonlinear. (2) Exponential Growth of the Search Space for Multi-Communications. In overlapping scenarios, multiple communications interfere with each other and with computation. For instance, tuning the parameters of one communication operation may change its completion time, which, in turn, affects the overlap between subsequent communications and computation, thereby altering the overall system performance. With n communication operations each having k configuration options, the joint search space grows as k^{n} , which calls for an effective reduction in dimensionality. 3. Design 3.1. Problem Definition Table 1 . Key notations used in the cost model. Notation Description X,Y,Z Communication, computation, and total time. s_{j} j -th communication config (A, P, T, NC, NT, C). TB_{i} i -th computation’s threadblocks. \lambda Total number of SMs. D_{i} Data size per thread block in the i -th computation. \overline{B} Peak global memory bandwidth. V_{j} Global bandwidth of the j -th communication. (1) \min_{\{s_{1},...s_{N}\}}Z=\max\left(Y,X\right)=\max\left(\sum_{i=1}^{M}y_{i},\ \sum_{j=1}^{N}x_{j}^{s_{j}}\right) To address these challenges, we now introduce a unified cost model and analyze its behavior across different bottleneck scenarios in computation-communication overlap. For an overlap, let it contain M computation operators and N communication operators. We denote the execution time of the i-th computation operator as y_{i} , and the execution time of the j-th communication operator under configuration s_{j} as x_{j}^{s_{j}} . With computations and communications serialized on separate CUDA streams, the total computation time is Y=\sum_{i=1}^{M}y_{i} , the total communication time is X=\sum_{j=1}^{N}x_{j}^{s_{j}} , and the overall makespan is given by Z=max(X,Y) . As shown in Equation ( 1 ), the optimization objective is to minimize the overall makespan Z by selecting optimal configurations s_{j} for all communication operators. We now analyze the two bottleneck scenarios separately. (2) \displaystyle\min_{\{s_{1},...s_{N}\}}Z=\min_{\{s_{1}...s_{N}\}}\sum_{j=1}^{N}x_{j}^{s_{j}}=\sum_{j=1}^{N}\min_{s_{j}}x_{j}^{s_{j}} Communication Bottleneck. First, in the communication-bound case described by Equation 2 , the overlap makespan simplifies to the cumulative time of all communications. The key challenges are: (1) modeling how configuration s_{j} affects communication time x_{j}^{s_{j}} , and (2) capturing the impact of computational contention on communication. AutoCCL ( 29 ) addresses this by employing a subspace coordinate descent method for search, and leverages online sampling with real-time feedback to avoid explicit modeling of the contention. (3) \min_{\{s_{1}...s_{N}\}}Z=\sum_{i=1}^{M}y_{i} Computation Bottleneck. Symmetrically, Equation 3 describes the computation-bound scenario, where the overlap makespan is determined by the sum of computation operator times. Two key challenges arise in this case: (1) Communication parameters influence computational performance by governing how communications utilize shared resources (further discussed in Sec. 3.2 ); (2) Due to the serialized execution of communications, tuning an earlier communication changes the start time and overlap window of subsequent operators, creating a cascade effect on the computation. This requires considering the entire configuration set {s_{1},s_{2},\dots,s_{N}} jointly. With the configuration space per communication exceeding r=10^{6} options ( 29 ) , the joint search space becomes O(r^{N}) for N communication operators, which is computationally intractable for practical values of N . We now analyze how to tune communication parameters in the computation-bound overlap scenario. 3.2. Contention Modeling (a) Various NC and C (b) Various NC (c) Various C Figure 3 . Duration of FFN when AllReduce(32MB) with various NC and C (NT=128) on 8 \times A40pcie Building on AutoCCL ( 29 ) , we adopt a divide-and-conquer strategy based on implementation-related parameters (Algorithm, Protocol, Transport) before analyzing the effect of resource-related parameters. Our key finding is that while different communication configurations can achieve similar communication performance, they exhibit significant variation in how much they slow down computation. As shown in Fig. 3 , when using NC=16 versus NC=32, communication performance remains nearly identical, but computation time differs by 30.2%. We conducted separate tests on NC, NT, and C, and found that NC and C have a significant impact on computation time, while the effect of NT is negligible. Fig. 3 shows the overall impact of different NC and C configurations on computation time, measured by concurrently running a 32 MB AllReduce and an FFN operator on 8 NVIDIA A40 GPUs with PCIe interconnect. The results indicate that increasing either NC or C progressively prolongs computation time. To isolate individual factors, Fig. 3 shows how communication and computation times vary as NC increases while C=16KB . Similarly, Fig. 3 shows the effect of increasing C when NC=4 . The figures confirm that while larger NC and C values initially reduce communication time (with diminishing returns or even slight increases at larger values), they also significantly slow down computation. These findings were reproduced consistently on another cluster. (a) Computation Only (b) Communication Contention Figure 4 . SM and global resource contention. Cost Model We characterize communication-computation contention along two dimensions: SM competition and global resource competition. As illustrated in Fig. 4 , SM competition arises from shared processor occupancy, while global resource contention stems from bandwidth saturation. SM Competition. Communication operators occupy a portion of SMs, reducing the resources available for computation and increasing the number of computation waves. The assignment of threadblocks, whether for computation or communication, to an SM is constrained by the availability of threads, shared memory, and registers. Due to this multi-constraint bottleneck, NT has a negligible impact on SM competition. NC is the dominant factor governing SM occupancy. Global Resource Competition. Communication also contends for shared global resources such as memory bandwidth and cache. Each communication operator launches NC threadblocks that read/write data at a granularity of C. Memory transactions from different threads within a threadblock are coalesced, making NT’s impact on global contention relatively minor. In contrast, larger values of NC and C generate more intensive contention due to increased concurrent data movement. (4) \displaystyle y_{i} \displaystyle=\sum_{j=l}^{k}f_{ij}\times g_{ij} (5) \displaystyle g_{ij} \displaystyle=\lceil\frac{\mu_{i}}{(\lambda-NC_{j})\times TB_{i}}\rceil (6) \displaystyle f_{ij} \displaystyle=\theta_{ij}+\frac{(\lambda-NC_{j})\times TB_{i}\times D_{i}}{\overline{B}-V(NC_{j},C_{j})} Based on these observations, we build a cost model of the computation i overlapped with communication l-k . Eq. ( 4 ) decomposes computation time y_{i} into wave count g_{ij} and per-wave latency f_{ij} that is overlapped with the j-th communication. Eq.( 5 ) shows the number of computation waves g_{ij} is determined by dividing the total required thread blocks \mu_{i} by the number of available threadblocks per SM after allocating NC_{j} SMs to communication. Meanwhile, Eq. ( 6 ) shows f_{ij} consists of computation time \theta_{ij} and data transfer time, where the latter depends on the data volume D_{i} and the effective bandwidth reduced by global resource contention V(NC_{j},C_{j}) . Notation definitions are summarized in Table 1 . A higher NC occupies more SMs, reducing the resources available for computation and consequently increasing the number of waves g_{i} , while also imposing additional demand on bandwidth. A larger C, in turn, amplifies contention for global bandwidth, thereby extending the per - wave execution time f_{i} . Fig. 3 empirically validates our model: increasing NC/C beyond optimal points (e.g., NC>8) drastically prolongs computation time despite marginal communication gains. 3.3. Priority Metric When multiple communication and computation tasks execute concurrently, the central challenge lies in efficiently identifying near-optimal configurations from a combinatorial space that scales as O(1,000,000^{n}) . Brute-force searching this space is infeasible, necessitating the use of heuristic methods to find high-quality solutions within practical time constraints. A naive strategy is to optimize communications sequentially. However, this approach fails to account for critical interdependencies: tuning one communication alters its execution timeline, which cascades to affect both the communication and computation phases of subsequent tasks. These temporal and resource-contentions introduce nonlinear interactions that render sequential optimization highly suboptimal. To illustrate this, an experiment was conducted on A40 GPUs with 2 AllReduce and 7 MatMul executed concurrently. We adjust NC of one communication at a time to analyze how it impacts overall performance. As shown in Fig. 5 , increasing NC from 1 to 16 affects the two communications differently. The slope of each arrow indicates the rate of change in computation and communication times. Optimizing Communication B achieves a larger reduction in communication time with only a slight increase in computation time, resulting in a shorter total execution time. In contrast, tuning Communication A provides smaller benefits. These results reveal that optimizing different communications yields distinct trade-offs between communication gains and computational overhead. The overall performance improvement thus depends on selectively prioritizing the communications that provide higher benefits. This motivates the introduction of the metric H , which quantifies such trade - offs across concurrent communications. (a) tuning AllReduce A only (b) tuning AllReduce B only Figure 5 . Cost differences when tuning different communications in multiple communication scenarios Metric H. We define a priority metric H_{j} for the j-th communication as Equation ( 7 ). Y and Y^{\prime} denote the computation times before and after tuning, while x_{j}^{s_{j}} and x_{j}^{s^{\prime}_{j}} represent the corresponding communication times for the j-th communication. Where Y and Y^{\prime} represent the computation time before and after optimization, respectively, and x_{j}^{s_{j}} and x_{j}^{s^{\prime}_{j}} represent the communication time corresponding to the two configurations s_{j} and s^{\prime}_{j} for the j-th communication. (7) H_{j}=\frac{Y^{\prime}-Y}{x_{j}^{s_{j}}-x_{j}^{s^{\prime}_{j}}} Hence, a smaller numerator indicates a lower computational overhead, and a larger denominator implies greater communication improvement. The metric H_{j} measures the tuning efficiency, expressed as the communication improvement achieved per unit of added computation cost. A negative denominator implies that the communication is already optimal. Noted: in multi-computation scenarios, tuning one communication affects multiple overlapped computations, making explicit modeling of each interference infeasible. Since H_{j} inherently reflects the overall impact of the tuning on all computations, the analysis can be simplified by considering only the aggregate computation time Y , significantly reducing complexity. 3.4. Search Method Input : Communication config set S=\{s_{1},s_{2},...,s_{n}\} Output : fine-tuned communication config S^{\prime} S^{\prime}\leftarrow\{\} 1 Initialize all H to 0.01 2 while \exists s\in S and s.done=\text{False} do 3 s_{j}\leftarrow\arg\min\limits_{s_{i}\in M,s_{i}.done=\text{False}}H_{i} 4 s_{j}^{\prime}\leftarrow\text{ResourceEfficientTuning}(s_{j}) 5 if s_{j}^{\prime}.done then 6 S^{\prime}.\text{append}(s_{j}) 7 else 8 H_{j}\leftarrow\frac{Y^{\prime}-Y}{x_{j}^{s_{j}}-x_{j}^{s^{\prime}_{j}}} 9 end if 10 end while 11 return S^{\prime} 12 Algorithm 1 Cost-Effectiveness Algorithm In an overlap, the optimal communication configuration satisfies one of the following conditions: (1) All communications use minimal resources, and their total time cost is less than the computation time. (2) Communications are fully optimized but still take longer than computation, and further increasing communication resources prolongs both communication and computation time. (3) Increasing communication resources reduces communication time but increases computation time until the two are equal—beyond this point, further resource allocation for communication continues to speed up communication while slowing computation even more, degrading overall performance. Input : Communication config s_{j}^{\prime} 1 if s_{j}^{\prime} is not initialized then 2 s_{j}^{\prime}.NC,s_{j}^{\prime}.NT,s_{j}^{\prime}.C\leftarrow NC_{min},NT_{min},C_{min} 3 end if 4 x_{j}^{s_{j}^{\prime}},Y^{\prime},X^{\prime}\leftarrow\text{ProfileTime}(s_{j}^{\prime}) 5 if x_{j}^{s_{j}^{\prime}}-x_{j}^{s_{j}}>0\text{ or }X^{\prime}