Concerto: Automatic Communication Optimization and Scheduling for Large-Scale Deep Learning

Training a giant AI model across thousands of GPUs means the GPUs must constantly exchange data, and that communication eats 20 to 40 percent of training time; today each parallelism scheme hides it with hand-tuned tricks that do not transfer to new schemes; this work from NUS, Georgia Tech, and Alibaba builds Concerto, a compiler that automatically overlaps communication with computation for any parallelism by casting the scheduling as a classic resource-constrained scheduling problem it hands to a solver, and by automatically chopping up the computation around unavoidable synchronous communication so it can be pipelined, matching or beating heavily hand-optimized frameworks like Megatron-LM and DeepSpeed.

Why this problem is worth solving

To see why communication is unavoidable, it helps to understand what parallelism actually does.

The reason the fix is subtle is that not all communication can be hidden the same way.

What people did before, and where it broke

• Bucket gradients and fire asynchronous reductions (PyTorch DDP, ZeRO). Group gradients into fixed-size buckets and start an asynchronous all-reduce per bucket to overlap with the backward pass. Where it broke. The bucket size is an empirical knob — the 25-megabyte default is wrong for many models (one large model wants 400 megabytes) — and the approach is specific to data parallelism.
• Re-implement layers to overlap their communication (Megatron-LM). Hand-rewrite the forward and backward of linear layers so the backward all-reduce overlaps with gradient computation. Where it broke. It is heavy manual engineering tied to the transformer, and it still cannot overlap the synchronous all-reduce in the forward pass, nor adapt when the compute happens to be shorter than the communication.
• Decompose specific operations for synchronous overlap (Google Decomposition). Chunk a matrix multiply so its all-reduce can pipeline with the compute. Where it broke. The decomposition patterns are fixed and hand-designed for the transformer, so they do not generalize to arbitrary models or operations.
• Use a heuristic latency-hiding scheduler (XLA). Let the compiler’s built-in scheduler reorder operations to hide communication. Where it broke. The heuristic cannot adapt to different hardware environments — its performance deteriorates badly on clusters without fast interconnects, sometimes ending up slower than the manual baselines.
• The gap. Every technique was tied to one parallelism scheme, one model family, or one fixed pattern, and the automatic scheduler was a heuristic that did not adapt. None could optimize communication generally, across arbitrary and even automatically-generated parallelism — which is exactly what scaling modern training needs.

How Concerto works

The idea

Separate what you compute from how you hide its communication. The reason prior overlap tricks never generalized is that each was fused into one parallelism scheme’s implementation — Megatron’s inside Megatron’s linear layers, DDP’s inside the data-parallel engine — so a new parallelism meant starting over. Concerto’s foundational move is to decouple the two: it lowers whatever parallelism you chose into a single, uniform graph of computation and communication operators, and then optimizes that graph without caring how the parallelism was decided. Because the optimizer sees only operators and their dependencies, the same passes work for data, tensor, pipeline, and ZeRO parallelism, and even for automatically-generated parallelism that no human hand-tuned. Prying apart two concerns that used to be welded together, so that each can be solved once and reused everywhere, is the same discipline the memory-resizing work covered elsewhere on this site follows, splitting what to resize from when to resize it so neither decision is trapped inside the other.

Turn scheduling into a formal problem and let a solver win. Once the graph is uniform, the question is what order to run everything in so that computation and communication overlap as much as possible — and the field’s answer had been hand-written schedules and fixed heuristics that could not adapt to every model and cluster. Concerto instead recognizes this as a classic resource-constrained project scheduling problem: each operator is a task with a measured duration, computation and communication are two resources that can each run one thing at a time, and the goal is the shortest schedule respecting dependencies. It encodes this as an integer linear program and hands it to an off-the-shelf solver, which finds a near-optimal overlap for the actual graph at hand. Recasting a design task as a formal optimization problem and delegating it to a solver, rather than crafting each answer by hand, is the same strategy the quantum-error-correction synthesis work covered elsewhere on this site takes, describing what a good solution must satisfy and letting a search engine find it.

Manufacture overlap by chunking the work around unavoidable communication. Scheduling can only hide communication that has independent work to overlap it; a synchronous all-reduce whose result the next operation needs has nothing to hide behind. Concerto’s second pass creates the opportunity that was missing: it identifies these critical transfers and decomposes the computation around them into chunks along a tensor axis, so that the first chunk’s result can be communicated while the second chunk is still being computed, pipelining the transfer against the compute. It does this only when a cost model says the overlap gained outweighs the inefficiency of the smaller chunks. Hiding a transfer by streaming it in pieces that overlap ongoing computation is the same technique the multi-turn LLM-serving work covered elsewhere on this site uses, moving data layer by layer so the transfer disappears into work the processor is already doing.

Following a tensor-parallel all-reduce through Concerto

All-reduce in tensor-parallel forward passes is a classic un-hideable cost.

Why it works

• Decoupling the optimizer from the parallelism lets one solution serve them all. Prior overlap tricks were welded into each parallelism scheme’s code → but Concerto works on a unified graph of computation and communication, agnostic to how the parallelism was chosen → so the same optimizer handles data, tensor, pipeline, ZeRO, and even auto-generated parallelism no one hand-tuned.
• A formal scheduling problem beats hand-tuned heuristics. Manual schedules and fixed rules like a default bucket size cannot adapt to every model and cluster → but casting the ordering as a resource-constrained scheduling problem and handing it to a solver finds a near-optimal overlap for the actual graph → so Concerto adapts where a heuristic scheduler, like XLA’s, degrades on hardware it was not tuned for.
• Decomposition creates overlap where scheduling alone finds none. Some communication is synchronous, and the next operation needs its result, so nothing independent can hide it → but chunking the surrounding computation lets one chunk communicate while the next computes, pipelining the two → so even critical communication on the critical path gets partially hidden.
• Cost-aware decomposition avoids making things worse. Splitting an operator into chunks lowers its efficiency and adds memory traffic → but Concerto profiles that overhead and decomposes only when the overlap it buys exceeds the cost → so it never spends more to hide communication than the communication would have cost.
• A blocking trick keeps an NP-hard problem tractable at real scale. Optimal resource-constrained scheduling is NP-hard and real graphs have tens of thousands of nodes → but solving overlapping half-offset blocks in an odd-even sweep propagates information across the graph in polynomial time → so the schedule approaches optimal in a few rounds while the solver never chokes.

What it costs (trade-offs and scope)

• The average speedups are modest and highly conditional. Against the heavily hand-optimized Megatron-LM the average gain is about 3.5 percent (maximum 19); the eye-catching numbers, like 42.9 percent over DeepSpeed, are specific configurations. The benefit depends on the communication-to-computation ratio — when fast NVLink makes communication cheap there is little to overlap, so Concerto helps most on commodity, non-NVLink clusters.
• It optimizes communication scheduling, not the parallelism itself. Concerto takes the parallel strategy as input, from the user or an auto-parallelizer; it decides when and how to overlap the resulting communication, not how to split the model. It is orthogonal to, and can be combined with, tools that optimize the communication primitives or co-design the hardware.
• The scheduler trades optimality for tractability. Resource-constrained scheduling is NP-hard, so the odd-even blocking method is a local-reordering heuristic that only approaches the optimum after several rounds, and how many rounds you run trades solve time against quality.
• Empirical knobs remain. The roughly twenty-percent decomposition-degradation penalty is an estimate from microbenchmarks, and the block size and number of scheduling rounds are parameters to set.
• Decomposition is not free and not always applied. It lowers hardware utilization, increases memory traffic, and adds kernel-launch and recombination overhead, so Concerto skips it whenever it would cost more than it saves.
• It relies on profiling. Operator durations are measured and cached, so the schedule is only as good as those profiles are representative of the real run.
• It was evaluated at 32 GPUs. The motivation is training across thousands of GPUs, but the experiments run on four nodes of eight A800s; behavior at much larger scale is not shown.

The evaluation

Check yourself

Sources

The paper is “Concerto: Automatic Communication Optimization and Scheduling for Large-Scale Deep Learning” by Shenggan Cheng, Shengjie Lin, Lansong Diao, Hao Wu, Siyu Wang, Chang Si, Ziming Liu, Xuanlei Zhao, Jiangsu Du, Wei Lin, and Yang You, published at ASPLOS 2025, DOI 10.1145/3669940.3707223. The authors are at the National University of Singapore, the Georgia Institute of Technology, Alibaba Group, George Mason University, and Sun Yat-sen University.

This explainer is written from the full 16-page text. Everything above comes from the paper’s own sections: the introduction and background on parallelism in distributed training (data, tensor, pipeline, ZeRO, dynamic-axial, and automatic parallelism) and the three challenges of manual communication optimization (performance, programmability, generality); the motivating measurements that the default bucket size is suboptimal and that reordering and decomposition can create overlap; the Concerto overview decoupling parallelism from communication optimization via ConcertoIR; the scheduling section formulating execution as a resource-constrained project scheduling problem, its integer-linear-program encoding, the decoding and communication-fusion optimizations, and the odd-even method that keeps the NP-hard problem tractable; the auto-decomposition section that finds critical communication, explores decomposition contexts using each operator’s sharding spec, models the degradation cost (an empirical twenty-percent penalty) and overheads, and solves for the best combined strategy with integer linear programming; the implementation on the PyTorch 2.0 compiler stack with its lightweight two-stream runtime and extensibility; and the evaluation on 32 A800 GPUs reporting the comparisons against Megatron-LM (average 3.5 percent, up to 19 percent), Jax/XLA (up to 34 percent), DeepSpeed on ZeRO (up to 42.9 percent), FastFold’s dynamic axial parallelism (up to 19.7 percent), and Alpa (up to 22.7 percent), together with the ablation, fusion, and compilation-time analyses.