Characterizing and Optimizing End-to-End Systems for Private Inference

Karthik Garimella, Zahra Ghodsi, Nandan Kumar Jha, Siddharth Garg and Brandon Reagen

Private inference lets you query someone else's neural network without revealing your data or learning their weights, and the field reports encouraging latencies by shoving 88 percent of the work into an offline phase that is assumed to happen for free beforehand; this paper (NYU and Purdue) measures the whole system instead — client on an actual embedded board rather than a server, requests arriving at a rate rather than one at a time — and finds the offline phase cannot stay offline, because each pre-computation is 41 gigabytes, cannot be reused, and takes half an hour to produce.

The argument in one glance

Problem

Asking a model a question means handing over the question

Cloud prediction services need your data to answer, and they will not show you the model because it is the product. Private inference resolves both at once using cryptography, so the server learns nothing about the input and the client learns nothing about the weights, with exact results rather than the approximate ones that noise-based privacy gives. The alternatives are worse in specific ways — trusted hardware assumes the hardware is trustworthy and has repeatedly not been, while statistical privacy degrades accuracy and works best on aggregates rather than on one persons single query.
What people did

Move the expensive cryptography before the question arrives

The leading protocols are hybrid, matching each cryptographic tool to the layer that suits it: homomorphic encryption and secret sharing for the linear layers, garbled circuits for every ReLU. The decisive optimization was splitting execution into an OFFLINE phase that depends only on the network architecture and weights, and an ONLINE phase that begins when the input arrives. Since the offline work needs no input, it can happen in advance, and reported online latencies came down to something that sounds usable.
Why it fell short

Free work is only free if you can store it and have time to do it

The offline phase is 88 percent of the total, and hiding it requires a buffer of finished pre-computations. Each one is 41 gigabytes for a mid-sized network, is consumed by exactly one inference, and cannot be amortised. The average phone has about 100 gigabytes total. Meanwhile the client-side cost is systematically understated, because the field benchmarks the client on server hardware — measure it on a real embedded board and evaluating the garbled circuits takes 200 seconds where the servers half of the same protocol takes 25.
This paper's idea

Measure the system, then move the work to whoever can afford it

This paper (NYU and Purdue — Garimella, Ghodsi, Jha, Garg and Reagen) characterises private inference end to end, with a realistic client device and a stream of requests arriving at a rate rather than one inference in isolation. That reframing exposes three bottlenecks and suggests three fixes, none of which changes what is computed or weakens the security argument. Reverse who garbles and who evaluates. Run every layers offline encryption in parallel, which is possible for a reason specific to hybrid protocols. And stop splitting the radio evenly when 81.5 percent of the bytes go one way.

Why this problem is worth solving

The protocol is a stack of four cryptographic tools with sharply different costs, and knowing which does what is most of the argument.

The goal is a two-party computation where a client obtains a prediction without the server seeing the input and without the client seeing the weights, assuming both sides follow the protocol honestly while trying to learn what they can. Different layers get different tools. Linear layers — convolutions and fully-connected layers — use HOMOMORPHIC ENCRYPTION, which computes directly on ciphertexts at a slowdown of four to six orders of magnitude but costs almost nothing in storage or bandwidth, combined with SECRET SHARING, where a value is split so that neither party alone learns anything and additions become nearly free. Every ReLU uses a GARBLED CIRCUIT instead, because Boolean logic is what garbling is good at. Encryption-only protocols exist and avoid the whole offline phase, but they must replace ReLU with a polynomial approximation, which measurably damages accuracy on deeper networks — the hybrid design exists to keep the accuracy

The costs are not distributed evenly between the two parties, and that turns out to be the lever.

One party is the GARBLER. It expresses the function as a Boolean circuit, assigns two random labels to each input wire of each gate standing for zero and one, and builds an encrypted truth table per gate, costing up to two AES operations per table entry. The other party is the EVALUATOR. It receives the circuit and the labels for the garblers inputs, uses oblivious transfer to obtain labels for its own inputs without the garbler learning them, then runs the circuit gate by gate learning no intermediate value, and finally returns output labels for the garbler to decode. The security holds regardless of which party takes which role. The costs do not. Profiling shows the garbler storing 3.5 kilobytes per ReLU while the evaluator must store the circuits themselves at 18.2 kilobytes per ReLU, five times more — and in the standard protocol the evaluator is the phone

What people did before, and where it broke

Report the online latency and treat the offline phase as free. The offline work depends only on the architecture and weights, so in principle it can all happen in advance.
But 88 percent of the total runtime lives there. For a ResNet-18 on TinyImageNet the offline phase is 1,809 seconds against 243 online, so hiding it is not a rounding error but the whole result.
Benchmark one inference in isolation. Every prior evaluation studies a single request, which is the natural thing to do when comparing protocols.
But hiding offline cost requires a buffer, and buffers run out. Each pre-computation is single-use and cannot be amortised across inputs, so the question is not whether one can be hidden but whether they can be produced as fast as requests arrive.
Run the client-side code on server hardware. Convenient, and it makes the numbers comparable across papers.
But it inverts which side looks expensive. On a real embedded client, the garbled-circuit evaluation the client performs takes 200 seconds while the garbling the server performs takes 25, an asymmetry that is invisible when both run on a workstation.
Build accelerators for the homomorphic encryption. Several exist and they work, reporting encryption times in the hundreds of milliseconds.
But they leave out the ReLUs. One such result reports 198 milliseconds for a ResNet-50, where accounting for the 9.6 million ReLUs and their communication puts end-to-end latency at 215 seconds.
The gap. Every number in the field describes a component. Nobody had measured the thing users would experience, which depends on storage capacity, device asymmetry, and how often somebody asks a question.

How measuring the whole system changes the design

From a component benchmark to a protocol reorganised around who can afford what

Split the protocol into an offline and an online phase

The established hybrid design does all the homomorphic encryption and all the circuit garbling before the input arrives, leaving only secret-share arithmetic and circuit evaluation for when the question is actually asked. This is the state of the art and it genuinely reduces online latency.
↓ →
Put the client on hardware a client would actually have new

Model the client as an embedded board with four slow cores and 2 gigabytes of memory, and the server as a 32-core machine, rather than running both sides on server silicon. This alone reveals that the work assigned to the client is the expensive half of the online phase.
↓ →
Drive the system with an arrival rate instead of one request new

Feed the protocol a Poisson stream of inference requests through a queueing simulator, with a fixed client storage capacity holding the buffer of finished pre-computations. Now the offline phase either keeps up or it does not, and the answer stops being an assumption.
↓ →
Reverse the garbler and evaluator roles new

Have the client garble the ReLU circuits and the server evaluate them. The function garbled is unchanged and the security argument is unchanged, since garbling protects both parties whichever role they play. But the 41 gigabytes of circuits now sit on the server, and the slow evaluation moves to the fast machine.
↓ →
Run every layer offline encryption at once new

In a hybrid protocol the offline encryption evaluates each linear layer on randomly sampled secret shares rather than on the previous layer output, so the layers do not depend on one another and can all run simultaneously. This is embarrassingly parallel and nobody had noticed.
↓ →
Reallocate the radio to match the traffic new

The 5G standard divides a 10 millisecond frame into 10 sub-frames, each assignable to upload or download and adjustable at millisecond granularity. Since the traffic is heavily one-directional, splitting the frame to match it rather than evenly recovers a third of the communication time.

Evaluated in a queueing simulator validated against the baseline implementation to within 0.9 percent, across ResNet-32, VGG-16 and ResNet-18 on CIFAR-100 and TinyImageNet.

The idea

A cost that has been moved is not a cost that has been removed. The offline phase is a beautiful optimization on paper, because it depends only on the model and can therefore be done at any convenient earlier moment. The paper does not dispute that; it asks what the earlier moment is made of. Hiding offline cost requires a stock of completed pre-computations, and this stock has two properties that ruin it. Each item is consumed by exactly one inference and cannot be reused or amortised. And each item is 41 gigabytes for a mid-sized network on 64-by-64-pixel images, against roughly 100 gigabytes of total storage on an average phone, with full-resolution ImageNet needing hundreds of gigabytes, which is why the literature quietly does not study it. So the buffer holds one or two items at best. Once you ask questions at a rate rather than once, that buffer drains and the 88 percent that was supposed to be invisible arrives in the critical path. Discovering that an optimization was validated against a scenario too small to exercise its failure mode is the same benchmarks-hid-the-real-regime correction covered elsewhere on this site where a technique looks decisive on a single unit of work and stops working when units arrive continuously.

Who does the work matters more than how much work there is. The second methodological fix is almost embarrassingly simple: benchmark the client on a client. Prior work runs both halves on server hardware, which makes the two roles in a garbled circuit look symmetric when they are not — the evaluator stores five times more per ReLU and, on a real embedded board, spends 200 seconds where the garbler spends 25. Once the asymmetry is visible the fix follows immediately, and it is not an optimization of anything. It is a swap. The client garbles, the server evaluates, the function garbled is identical, and the security argument is untouched because garbling protects both parties whichever role they hold. Client storage drops from 41 gigabytes to 8 and the online evaluation drops from 200 seconds to 11.1. There is a real price — oblivious transfer moves into the online phase, pushing online communication from 27.1 to 101 seconds, and client energy rises 1.8 times because garbling needs more encryptions than evaluating — and the authors are explicit that with none of the system constraints, the original arrangement is the sensible one. Reassigning work according to which party can actually bear it, rather than making the work cheaper, is the same put-it-where-the-resources-are move covered elsewhere on this site where an offloading scheme is rebalanced once somebody measures the weak end of the link.

The parallelism was hiding in the cryptography, not the computation. The homomorphic encryption in these protocols is over 80 percent of compute latency, and the obvious assumption is that neural network layers must be processed in order because each consumes the previous output. That is true of the inference. It is not true of this encryption, because in a hybrid protocol the offline encryption evaluates each linear layer on the clients randomly sampled SECRET SHARES, which are drawn independently per layer and do not depend on anything the previous layer produced. So all seventeen layers of a ResNet-18 can run at once, cutting encryption from 17.76 minutes to 2.35, a 9.7 times speedup bounded only by the slowest single layer. The consequence is genuinely counter-intuitive: a hybrid protocol combining encryption with secret sharing can be FASTER than an encryption-only protocol despite doing strictly more total work, because the encryption-only version evaluates on real layer inputs and is therefore forced to be sequential. Finding parallelism by looking at the data dependencies of the protocol rather than of the algorithm it implements is the same the-dependency-you-assumed-is-not-there discovery covered elsewhere on this site where a chain believed to be inherently serial turns out to have been serialised by an implementation choice.

Following one inference request through a loaded system

Why an offline phase stops being offline

All figures for ResNet-18 on TinyImageNet unless noted, from the paper measurements and its queueing simulator.

Step 1 of 5

Look at one inference and it seems almost tolerable

The online phase totals 243 seconds. Most of that is the client evaluating garbled ReLU circuits, at 200 seconds, plus 42.5 seconds of communication and under a second of secret-share arithmetic. This is roughly the number the field reports, and on its own it suggests private inference is slow but not absurd.

the offline phase behind it totals 1,809 seconds, of which 1,080 is homomorphic encryption and 704 is communication
that offline portion is 88 percent of the end-to-end cost, and the entire published case rests on it being invisible

Why it works

Hiding an offline phase requires buffering its output, and each output is 41 gigabytes and single-use → the buffer holds one or two items on a real device → so beyond a low arrival rate the offline cost necessarily surfaces online.
Garbled circuit security is independent of which party garbles, but the costs are not → the roles can be swapped freely to put the 18.2-kilobyte-per-ReLU storage and the slow evaluation on the server → cutting client storage 5 times and online evaluation from 200 seconds to 11.1.
Offline encryption operates on independently sampled secret shares rather than on real layer inputs → the layers have no data dependence and all run at once → giving a 9.7 times speedup bounded only by the slowest individual layer.
The protocol sends 81.5 percent of its bytes in one direction while 5G splits a frame into ten independently assignable sub-frames → the split can be matched to the traffic instead of left even → recovering up to 35 percent of communication time.
Storage rather than compute is what limits the original protocol → a faster client device does not help it, sustaining about one request per 30 minutes regardless → whereas the reorganised protocol converts extra client speed into throughput.

What it costs (trade-offs and scope)

The client now spends more energy. Garbling requires more encryptions than evaluating, measured at 2.33 against 1.25 joules per unit of work on the embedded board, so client energy rises 1.8 times.
For a single inference the original arrangement is better. The authors state it plainly: Server-Garbler beats Client-Garbler by 13 percent on one isolated request. The reversal only appears once storage limits and arrival rates are in the picture.
Two of the three fixes help the baseline too. Layer-parallel encryption and the radio split are protocol-agnostic and cut the original protocol end-to-end latency by 54.6 percent, so the role swap is a smaller share of the headline than it looks.
Layer parallelism loses to request parallelism given enough storage. With 140 gigabytes buffered, processing whole independent requests in parallel sustains one request per 10 minutes against 17, because layer parallelism leaves cores unevenly loaded. It wins only under realistic storage limits.
The conclusion is still that this is impractical. Even with an ideal client and a four-times server, latencies remain minutes long, and the paper own projection needs garbled circuits 100 times faster, encryption 1000 times faster, ten times the bandwidth and ten times fewer ReLUs to reach six seconds.

The evaluation

Measurements come from the reference implementation of the baseline protocol on real hardware — an embedded client board and a 32-core server — and feed a queueing simulator that replays Poisson arrivals over a simulated day, averaged over 50 runs, validated against the baseline system to within 0.9 percent. The sweep covers three networks on two datasets and three client storage capacities. The most informative result is not the speedup but the sensitivity study, which shows the baseline protocol pinned at roughly one request per 30 minutes no matter which client device it is given, because what limits it is storage rather than speed.

Property	As the field evaluated it	Baseline, measured end to end	Roles swapped, parallel, re-split
What is being measured
Where the client code runs
Client storage per inference
Offline encryption time
Sustainable request rate

Combined, the three changes give 1.8 times lower mean inference latency and sustain a 2.24 times greater request rate than the state of the art. On TinyImageNet the baseline cannot engage in an offline phase at all with 16 or 32 gigabytes of client storage, since it needs 41, so it starts at nearly an hour of mean latency even at low arrival rates.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

The arrival-rate results, which carry the argument, come from a simulator rather than a deployment. It is built on real measurements of both phases on real hardware and validated against the reference implementation to within 0.9 percent, but it models one client and one server with a FIFO queue, and the multi-client case is discussed rather than evaluated. Several of the paper own numbers cut against its headline and are reported anyway. For a single isolated inference the original role assignment is 13 percent faster, and the authors say directly that without storage constraints, device asymmetry and multiple requests it is the natural choice. Two of the three optimizations — parallel encryption and the radio split — apply to the baseline as well and improve it by 54.6 percent, so the role swap contributes less of the 1.8 times than the framing implies. Layer parallelism also loses to simply processing independent requests in parallel once storage is ample, sustaining one request per 17 minutes against 10 at 140 gigabytes, because it distributes uneven work across cores; the authors expect the two to be combined in future. Client energy rises 1.8 times. And the honest conclusion is negative: with an ideal client and a four-times faster server, latencies remain minutes long, and the projection at the end stacks four optimistic assumptions — garbled circuits 100 times faster, encryption 1000 times faster, ten times the bandwidth, ten times fewer ReLUs — to reach six seconds, which is still nowhere near plaintext.

Background

When the benchmark is smaller than the failure mode

This paper sits in the site’s security and ML systems clusters and rhymes with several ideas covered elsewhere on this site. Its closest sibling is the encrypted compute offload page, which makes the identical methodological complaint from the other direction — that every system in this area tunes the server and ignores the client — and reaches similar conclusions once the weak end of the link is measured. Its central finding, that an optimization validated on one unit of work collapses once work arrives continuously, is the same benchmarks-too-small correction the memory disaggregation and graph mining pages make when a technique that looks decisive in isolation stops scaling under load. Its treatment of pre-computed state as a buffer that drains rhymes with the serverless warm-start pages, where keeping work ready in advance only pays while you can afford to hold it and the interesting question is always the refill rate. Its diagnosis that ReLU, an afterthought in ordinary inference, becomes the dominant cost under encryption is the same the-cost-model-is-inverted-here observation the homomorphic encryption compiler pages build on, where operations that are free in plaintext dominate and operations that are expensive become cheap. And its closing projection, which stacks four future improvements and still lands far from practical, is the same honest-about-the-gap accounting the quantum compilation pages offer.

If you remember only three things

1. Private inference combines homomorphic encryption and secret sharing for linear layers with garbled circuits for every ReLU, and its headline result comes from splitting execution into an offline phase depending only on the model and an online phase beginning when the input arrives. The field reports the online number. This paper measures the whole thing and finds the offline phase is 88 percent of the total, that hiding it requires buffering completed pre-computations, and that each one is 41 gigabytes for a mid-sized network, is consumed by a single inference, and cannot be amortised — against roughly 100 gigabytes of total storage on an average phone.
2. Once requests arrive at a rate rather than one at a time, that buffer drains and the hidden cost surfaces: the offline phase enters the mean latency at one request every two hours, queueing begins at one every 70 minutes, and by one every 30 minutes each request pays everything plus queue time. A second correction compounds it. Prior work benchmarks the client on server hardware, which makes the two garbled-circuit roles look symmetric when the evaluator stores five times more per ReLU and, on a real embedded board, spends 200 seconds against the garbler 25.
3. The three fixes change who does the work rather than what the work is. Swapping the garbler and evaluator roles is free of security implications, since garbling protects both parties whichever role they play, and it cuts client storage from 41 gigabytes to 8 and online evaluation from 200 seconds to 11.1. Offline encryption turns out to be embarrassingly parallel across layers, because it operates on independently sampled secret shares rather than on real layer inputs, giving 9.7 times. And matching the 5G frame split to traffic that is 81.5 percent one-directional recovers up to 35 percent of communication. Together, 1.8 times lower latency at 2.24 times the request rate — and still minutes per inference.

Check yourself

Check your understanding

1. The offline phase depends only on the model and not on the input, so in principle it can all be done in advance. Predict why the paper finds it cannot stay offline in practice.
2. Reversing the garbler and evaluator roles cuts client storage from 41 gigabytes to 8 and online circuit evaluation from 200 seconds to 11.1. Predict why nobody had done this, given that it requires no new cryptography.
3. Neural network layers consume the previous layer output, so processing them out of order seems impossible. Yet the paper runs every layer offline homomorphic encryption simultaneously for a 9.7 times speedup. Predict how.
4. The sensitivity study gives the baseline protocol progressively faster client devices and finds its sustainable throughput barely moves, staying near one request per 30 minutes. Predict what that reveals.

Sources

Karthik Garimella, Zahra Ghodsi, Nandan Kumar Jha, Siddharth Garg and Brandon Reagen. “Characterizing and Optimizing End-to-End Systems for Private Inference.” ASPLOS 2023, Vancouver. New York University and Purdue University. DOI 10.1145/3582016.3582065. Preprint at arXiv 2207.07177.
Full text of the paper was used for this explainer, including the primer on the four cryptographic primitives and the baseline protocol in Section 2, the methodology and simulator validation in Section 3, the storage, computation, communication and arrival-rate characterisation in Section 4, the three proposed optimizations and the comparison against request-level parallelism in Section 5, and the projection of future improvements in Section 6.
The authors open-sourced their private inference simulator.