Performance-aware Scale Analysis with Reserve for Homomorphic Encryption

Computing on encrypted numbers means every multiplication inflates a scale factor that must periodically be cut back, and cutting it back costs latency — this compiler tracks the leftover headroom instead of the scale, because that quantity does not change when you cut.

Why this problem is worth solving

The remedy is an operation called rescale, which divides the scale back down. The catch is that it also spends one unit of the ciphertext’s

What people did before, and where it broke

• Manage scales by hand. What the libraries expect. The programmer tracks a scale and a capacity for every intermediate value while satisfying several other constraints, which is exactly the burden compilers exist to remove.
• Scan forward and rescale at a threshold. The EVA compiler walks the program from beginning to end and inserts a rescale whenever a result’s scale exceeds a programmer-supplied waterline. Correct and simple, and structurally blind: when it decides to insert a rescale, it knows nothing about the operations that follow, so it cannot choose a placement that lowers the level of an expensive operation later.
• Leave the capacity unused. The consequence of that blindness. In the paper’s worked example the final ciphertext carries twenty bits of headroom that were never spent, which is capacity paid for and wasted.
• Search the placement space. The Hecate compiler generates candidate plans by inserting a scale operation at a random point, repairs each into a legal program, estimates the latency of each statically, and hill-climbs. It genuinely beats the forward approach, and takes 14,763 iterations and 483 seconds on a small convolutional network — with worse to come for anything larger.
• Accept the compile time. Tempting until you notice that other optimisations, such as deciding where to place the expensive ciphertext refreshes or how to lay out data, would want to invoke scale management repeatedly.
• The gap. One approach cannot see forward and the other has to try everything. Nobody had found a formulation in which the right placement could simply be computed.

How reserve changes the analysis

The idea

Pick the quantity that does not move. The whole design turns on one definition. Instead of tracking the scale, track the reserve — the ciphertext’s capacity divided by its scale, which is the unused headroom in the encoded value. Under rescale, capacity and scale are both divided by the same factor, so the reserve is unchanged. That invariance is what makes everything else work: a compiler can decide how much budget each intermediate value needs without having decided yet where the rescale operations go, because that decision would not affect the answer. The paper turns this into a type system, with a subtyping rule saying a larger reserve stands in for a smaller one, so the analysis can safely leave scale management operations out entirely and let placement be a second, separate problem. Untangling two concerns that previous compilers had forced to be solved together, by finding the formulation in which they genuinely are independent, is the same move made when compiling encrypted arithmetic by separating vectorisation from data movement, covered elsewhere on this site.

A forward scan cannot see its own consequences. The reason the conservative approach leaves headroom on the table is structural rather than a matter of tuning. Walking the program from start to finish, at the moment you decide to insert a rescale you know everything that has happened and nothing about what is coming, so you cannot choose the placement that will lower the level of an expensive multiplication three operations later. Reserve permits the opposite direction: it is a budget that succeeding operations will consume, so it propagates naturally backward from the outputs. Every allocation is then made in full knowledge of what the rest of the program will demand. Replacing a sequence of locally reasonable decisions with an analysis that sees the whole program before committing to any of them is the same correction applied when deep learning inference is optimised by global analysis rather than operator-by-operator, covered elsewhere on this site.

When the structure is right, the search becomes unnecessary. The exploration-based compiler works, and its cost is the honest cost of not knowing where to look — thousands of random placements, each repaired into legality and statically scored. What reserve provides is a way to know. Combining a value’s reserve with the waterline yields the minimum level that value can possibly have, which the paper calls its principal level; and when a multiplication’s result needs a different principal level from its operands, that is precisely and only where a rescale is required. So the placements that mattered can be identified rather than discovered, and the ordering heuristic — give the heaviest operations first claim on the budget, since their level dominates the latency — decides who benefits. The result is the same performance as searching, arrived at without searching. Building a compiler around a cost model precise enough to reason with, instead of a search loop that evaluates guesses, is the same design stance taken by frameworks for encrypted deep learning, covered elsewhere on this site.

Following one small program through the compiler

The level cannot be known before allocation, so it is estimated from how many multiplications lie on the path to the output. Operations with identical structure and depth are grouped, which removes duplicated analysis.

Why it works

• Reserve is invariant under the operation being placed. Rescale divides capacity and scale equally → the reserve is unchanged → so the analysis can allocate budgets before deciding placements, which is what splits one intractable problem into two tractable ones.
• The budget is a demand, so it flows backward. Reserve describes what succeeding operations will consume → it propagates from outputs to inputs → and every allocation is therefore made knowing the requirements of everything downstream.
• The minimum level falls out of the reserve. Combining reserve with the waterline gives the lowest level a value can have → a mismatch between the result level of an operation and the levels of its operands is exactly where a rescale is required → so the necessary placements are computed rather than searched for.
• Subtyping lets the analysis ignore placement. A larger reserve substitutes for a smaller one, since the scale can always be raised later → the type system tolerates mismatches implicitly → so scale management operations need not appear during analysis at all.
• Heavy operations get first claim. Latency is dominated by the level of the expensive multiplications → processing them first in the allocation order gives them the most room to have their levels lowered → and cheap operations absorb whatever constraints are left.

What it costs (trade-offs and scope)

• It is locally optimal, not globally. The paper says so about both halves. Reserve allocation guarantees only that each step is optimal given the previous ones, and rescale hoisting can miss globally better arrangements. The authors note that pushing toward global optimality would start to resemble the exploration they set out to avoid — and that the exploration-based alternative only reaches local optima itself.
• It loses to the search on some configurations. Up to 6.5% slower on some parameter settings for the regression benchmarks, traced to the hoisting algorithm failing to move rescales optimally when a value has several uses.
• The headline improvement is against the conservative baseline. The 41.8% is over the forward-scanning compiler. Against the exploration-based one, performance is essentially a tie — the win there is entirely compile time.
• Rescale placement contributes nothing on some benchmarks. It targets additions between two different ciphertexts, so on the regression workloads the full system shows no gain over reserve allocation alone.
• The programmer still supplies a waterline. The minimum scale is an input to the whole analysis, and the results are reported across a sweep of parameter settings rather than for one chosen automatically.
• The evaluation is modest in scale. Eight benchmarks on a single desktop processor with one encryption library, the largest being a small convolutional network on CIFAR — which is the standard set in this area, and not evidence about anything large.

The evaluation

Check yourself

Sources

The paper is “Performance-aware Scale Analysis with Reserve for Homomorphic Encryption” by Yongwoo Lee, Seonyoung Cheon, Dongkwan Kim, Dongyoon Lee and Hanjun Kim, published at ASPLOS 2024 Volume 1, pages 302-317, DOI 10.1145/3617232.3624870. The authors are at Yonsei University and Stony Brook University, and the compiler is open-sourced.

This explainer is written from the full text, read from the author-hosted copy at the Yonsei CoreLab. All figures above come from the paper’s own sections 2 through 8: the definition of reserve as coefficient modulus divided by scale and its invariance under rescale, the reserve type system with its subtyping rule, the three-stage reserve analysis of allocation ordering, allocation and redistribution, the rescale hoisting algorithm and its dynamic programming over three cost factors, the measured operation latencies showing ciphertext multiplication rising from level one to level five, the 14,763 iterations and 483 seconds of compilation time reported for the exploration-based compiler on LeNet-5, the 41.8% latency improvement over the forward-scanning compiler, the parity with the exploration-based compiler at up to 8.7% better and 6.5% worse on individual settings, the 15,526-fold reduction in scale management time and 24.44-fold reduction in total compilation time, and the ablation separating backward analysis, reserve allocation and rescale placement. The authors state the local rather than global optimality of both their analysis and their placement algorithm in sections 6.4 and 7.