Secure multi-party computation lets several servers run a neural network on data none of them can see, but every layer alternates between computing on secret shares and exchanging messages, so the GPUs sit idle 56 to 63 percent of the time — MPC-Pipe shows most of those waits are false dependencies and overlaps the two phases with three pipeline schemes, raising throughput by up to 50 percent and cutting latency by up to 16 percent without changing the protocol or its security.
The argument in one glance
-
Problem
Private machine learning with MPC is slow because compute and communication take turns
Secure multi-party computation (MPC) splits a secret value into random-looking shares held by different servers, which compute on the shares and only ever exchange data that reveals nothing. For a neural network this means every multiplication costs extra arithmetic plus a message exchange. Current frameworks run the two strictly in sequence, so one resource always waits for the other.
-
What people did
Make the operators cheaper, or move everything onto GPUs
Prior work cut the cost of individual operators, for example by replacing ReLU or Softmax with cheaper approximations, or by implementing the MPC arithmetic with fast GPU kernels, as CrypTen and CryptGPU do.
-
Why it fell short
Faster operators still wait; the GPU is idle more than half the time
Even with GPU kernels, the structure of the protocol keeps computation and communication serialized, and both are blocking calls. The authors measure that on two-party inference the GPUs are idle 63 percent of the time for ResNet and 56 percent for a Transformer, mostly during the communication-heavy ReLU and Softmax layers, while the network is idle during the compute-heavy convolution and dense layers.
-
This paper's idea
Most of the waiting is a false dependency; pipeline around it
MPC-Pipe observes that many operands are available long before the protocol uses them, so the messages carrying them can be sent early and overlapped with computation. It adds three pipeline schemes to the online phase: an inter-linear pipeline that sends the weight-related messages of the next layer while computing the current one, an inner-layer pipeline that splits the element-wise work of non-linear layers into tiles so transmission and computation of different tiles overlap, and an inter-batch pipeline that runs the linear layers of one mini-batch while another mini-batch is in its communication-heavy non-linear layers. Results are bit-identical, the protocol and threat model are unchanged, and throughput rises by up to 50 percent with latency down by up to 16 percent.
Why this problem is worth solving
A hospital wants a cloud service to run a diagnostic model on patient scans, but it cannot hand over the scans, and the model owner will not hand over the weights. Secure multi-party computation
A protocol in which several servers jointly compute a function on inputs that are split into random shares, so that no server learns the inputs or the intermediate values.
The price is speed. The paper’s measurements on two servers with GPUs and a 10 gigabit per second link show that inference of one ImageNet-sized image through VGG16 takes 14.25 seconds under MPC, and the GPUs are idle for most of that time. There are two kinds of waiting. During linear layers
Layers whose output is a weighted sum of inputs, such as convolution and dense (fully connected) layers. non-linear layers
Layers such as ReLU, MaxPool and Softmax that compare values and therefore need secret shares converted between arithmetic and binary form.
What people did before, and where it broke
- Cheaper non-linear operators. Sphynx, DeepReduce and Circa reduce or approximate ReLU; MPCFormer replaces Softmax with ReLU-based approximations. Where it broke. These change the model and its accuracy, and they do not touch the serialization between compute and communication that remains inside every layer.
- GPU implementations of MPC. CrypTen from Meta and CryptGPU run secret-share arithmetic with CUDA kernels. Where it broke. The compute got faster, but the protocol still alternates compute and communication with blocking calls, so the GPU waits on the network and the network waits on the GPU.
- Fewer communication rounds. Some protocols merge messages from many CPU threads into fewer rounds. Where it broke. A vectorized GPU implementation already sends one large broadcast per step, so there is little left to merge; the idle time comes from sequencing, not from message count.
- The gap. Overlapping communication with computation is standard in distributed training, but nobody had asked which of the waits in an MPC protocol are real data dependencies and which are habits of the implementation.
Where MPC-Pipe sits
The online phase of one secure layer, before and after
-
Offline phase
Generate Beaver triples, random correlated values, ahead of time and independent of inputs. Unchanged.
-
Local compute on shares
Each server computes masked differences such as x minus a from its own shares.
-
Broadcast and wait new
Servers exchange the masked values. In the baseline this blocks; MPC-Pipe makes it asynchronous and starts it earlier.
-
Compute the result share new
Each server combines received values with its triple shares. MPC-Pipe starts the parts that do not need the received data first.
-
Next layer new
Non-linear layers add share conversions with several message rounds; MPC-Pipe tiles them.
The idea
How a secure multiplication works. To multiply secret X by secret Y, the servers use a Beaver triple
Three secret-shared random values A, B and C with C equal to A times B, prepared offline, that let servers multiply secret shares with one message round.
Inter-linear pipeline: send what you already know, early. The weight mask W minus B depends only on the weights and the offline triple, both of which exist before the forward pass starts. So a server can compute and broadcast the weight mask for layer 2 while it is still computing layer 1, and the mask for layer 1 arrived during layer 0. The input mask X minus A does depend on the previous layer, but its broadcast can be issued without blocking, and while it is in flight the server computes conv(a, epsilon), the one term that needs only the already-received weight mask. Only the two terms involving delta wait. The paper implements a one-layer lookahead and finds it enough to hide the linear-layer communication in its setting. The same trick applies to the backward pass of training, where activations and weights are also known in advance.
Inner-layer pipeline: tile the element-wise work. A ReLU needs the sign of each element, which requires converting arithmetic shares into binary shares and then adding the binary shares with a Set-Propagate-Kill adder tree, six rounds of secure AND operations on long vectors. Every step is element-wise, so element 5 never depends on element 6. Yet the baseline broadcasts the whole vector, waits for the whole vector, and computes the whole vector. MPC-Pipe splits each vector into M tiles, issues the broadcast for tile 1 while computing tile 0, and so on. The transmissions are asynchronous and start back to back, so on a high-latency link they share one propagation delay rather than paying M of them. Four tiles work best; beyond that the tiles become too small for the GPU to process efficiently.
Inter-batch pipeline: two mini-batches, two threads. Linear layers are compute-bound and non-linear layers are communication-bound, so a single mini-batch always leaves one resource idle. MPC-Pipe runs two threads per server. One executes only linear layers, the other only non-linear layers. Two mini-batches enter the model; while mini-batch 1 is in a ReLU waiting on the network, the linear thread computes the next convolution for mini-batch 2. This raises throughput but not latency, since each individual mini-batch still takes the same time.
Tracing one convolution layer through the inter-linear pipeline
A secure convolution, baseline versus pipelined
Two servers, one convolution layer L1 with input X and weights W. Offline triple: A, B, C with C = conv(A, B). delta = X - A, epsilon = W - B. Times are illustrative, chosen so that broadcast and compute take similar time.
Step 1 of 5
Baseline: broadcast both masks
Each server computes its shares of delta and epsilon, broadcasts both, and blocks until the other server has sent its shares. The GPU does nothing during this exchange.
t = 0..2 | network: send delta, epsilon | GPU: idle
Why it works
- The waits were not real dependencies. The weight mask needs only weights and offline values. Because those exist before the pass begins, sending them early cannot violate any ordering the protocol requires. Therefore the network can be kept busy during compute with no change to what is sent.
- Element-wise operations have no cross-element dependency. Because each tile of a share-conversion vector is independent, the transmission of tile i plus 1 can overlap the computation of tile i, so the two resources work at once instead of in turn.
- Linear and non-linear layers are skewed in opposite directions. Linear layers are compute-heavy and non-linear layers are communication-heavy. Because of this, two mini-batches at different layers naturally want different resources, and running them in separate threads fills the gaps.
- Results are bit-identical. Nothing is approximated. The inter-linear pipeline only moves a broadcast earlier; tiles are concatenated at the end of a layer; mini-batches synchronize before gradients are applied. Therefore accuracy and security are exactly those of the baseline.
What it costs
- Gains are bounded by the smaller phase. Overlap can hide at most the shorter of compute and communication in each layer. In compute-bound linear layers only the communication time is recoverable, and in communication-bound non-linear layers only the compute time. That is why the layer-level throughput gains in Table 1 of the paper sit between 6.5 and 17 percent per layer type.
- Inter-batch pipelining raises throughput but not latency. Each mini-batch still takes the same time. It also requires at least two mini-batches in flight, so a single-request latency-critical service does not benefit from it.
- Tiling has a sweet spot. More tiles mean smaller GPU kernels; past four tiles the loss of parallel efficiency outweighs the extra overlap.
- Only the online phase is faster. The offline phase that generates Beaver triples is untouched, and prior work found it can be 88 percent of online plus offline time. If the offline phase cannot be done ahead of time, a 50 percent online gain becomes about 6 percent end to end.
- Semi-honest adversaries only. The paper does not address malicious parties who deviate from the protocol; those protocols have extra checks whose overlap opportunities are not studied here.
- More parties need more bandwidth. Bytes sent per server grow linearly with the number of parties, about 17 gigabytes for VGG16 with three parties and 25 gigabytes with four.
The evaluation
The authors implement MPC-Pipe on a modified CrypTen with offline and online phases separated, and use that modified CrypTen as the baseline. Each party is a server with an Intel Xeon Gold 5220R, an Nvidia Quadro RTX 5000 and a 40 gigabit per second InfiniBand card, throttled in software to 10, 20 or 40 gigabits per second, with an optional 70 millisecond delay to emulate a wide-area network. Models are VGG16, ResNet-50 and a single BERT-large-sized Transformer encoder layer with sequence length 512. Every number is an average of 50 runs.
Two-party inference and training, 10 gigabit per second local network
| Property | Baseline (modified CrypTen) | MPC-Pipe |
|---|---|---|
| VGG16 inference latency | 14.25 s | |
| VGG16 inference throughput | 4.21 images per minute | |
| Inference throughput gain, all three models | — | |
| Inference latency gain, all three models | — | |
| VGG16 training throughput | 1.81 images per minute | |
| GPU idle time, VGG16 inference / training | 60 / 35 percent | |
| Three parties, 10 gigabit LAN | — |
Check yourself
Check your understanding
1. Why can the weight mask W minus B for layer 2 be broadcast while layer 1 is still computing?
2. What makes the inner-layer pipeline possible for ReLU but not for a matrix multiplication?
3. Predict what happens to latency and throughput if only the inter-batch pipeline is enabled.
4. The paper reports up to 50 percent higher online-phase throughput. Why might the end-to-end gain be much smaller in some deployments?
5. Why does the paper say that MPC-Pipe on a 10 gigabit link is roughly as fast as the baseline on a 20 gigabit link?
Sources
The paper is “MPC-Pipe: An Efficient Pipeline Scheme for Semi-honest MPC Machine Learning” by Yongqin Wang, Rachit Rajat and Murali Annavaram, University of Southern California, published at ASPLOS 2024, DOI 10.1145/3622781.3674175. This explainer was written from the full text of the arXiv preprint (2209.13643, version 2, August 2024), whose title differs slightly from the published one. All numbers are taken from the paper’s Section 5 and its Tables 1 to 6 and Figures 6 to 9.