ReSBM: Region-based Scale and Minimal-Level Bootstrapping Management for FHE via Min-Cut

Yan Liu, Jianxin Lai, Long Li, Tianxiang Sui, Linjie Xiao, Peng Yuan and 4 others

Running a neural network on encrypted data under RNS-CKKS means the compiler must decide where to insert two kinds of housekeeping — cheap rescaling operations that shrink a ciphertext's growing scale, and a ruinously expensive bootstrap that refreshes a ciphertext which has run out of budget — and placing them optimally is NP-hard; ReSBM (Ant Group, Tsinghua and UNSW Sydney) cuts the program into regions each holding exactly one multiplication deep of work, proves that anything inserted inside a region changes only that region's running time and never what leaves it, and then solves each region exactly with a minimum cut, adding a dynamic program over regions that lifts each ciphertext only as high as it actually needs instead of all the way to the ceiling.

The argument in one glance

Problem

Every encrypted multiplication spends a budget that must be topped up

The RNS-CKKS encryption scheme lets a server compute on data it cannot read, and it is the scheme of choice for encrypted machine learning because it handles fractional numbers and packs many values into one ciphertext. The catch is bookkeeping. Every ciphertext carries a scale — how far the real numbers were multiplied up to become integers — and a level, which is how many more multiplications it is allowed to survive. Multiplying two ciphertexts multiplies their scales together, so the scale grows explosively, and if it ever exceeds what the level can hold, the value is destroyed. Additions demand that both operands agree on scale and level exactly. So the compiler has to insert maintenance operations everywhere, and the program does not run at all without them.
What people did

Local rules for rescaling, and a separate pass that decides where to bootstrap

Two kinds of maintenance exist. Rescaling shrinks the scale and spends one level; a modswitch spends a level without touching the scale. When the level reaches zero, only bootstrapping can restore it, and bootstrapping is by far the most expensive operation in the whole scheme. The compilers that exist take these two problems separately. EVA and PARS place rescaling by a local rule about the scales of the immediate operands and result. Fhelipe then adds a dynamic program to decide where to bootstrap; DaCapo uses a liveness analysis for the same purpose. Both bootstrap to the maximum level the security parameters allow.
Why it fell short

Local rules miss the consequences, global search is too slow, and topping up to the ceiling wastes the most expensive operation there is

A local rescaling rule looks only at the operation in front of it, so it cannot see that rescaling one step earlier would have let a whole run of rotations execute at a cheaper level. The global alternatives — HECATE and ELASM — do see that, by hill-climbing over the space of plans, and they take on the order of 300 seconds to compile something as small as LeNet-5, which is why the bootstrapping-aware compilers deliberately avoid them. And the maximum-level habit is the worst waste of all, because the cost of a bootstrap depends only on the level it lifts you to. Lifting a ciphertext to the ceiling and then dropping it back down with nearly free modswitches sounds harmless and is not.
This paper's idea

Cut the program into regions where local decisions stay local, then solve each one exactly

ReSBM starts from one observation about the scheme: multiplication is the only operation that raises a scale. So it cuts the data-flow graph into regions each containing exactly one multiplication deep of work, with the multiplications at the front. Inside such a region, wherever you put a rescale or a bootstrap, the scales and levels of everything leaving the region come out the same — only the time spent inside changes. That turns a tangled global problem into a set of independent local ones, and each local one turns out to be exactly a minimum cut. On top of that sits a dynamic program that chooses which regions get bootstraps and, crucially, lifts each ciphertext only to the minimal level that will carry it to the next bootstrap rather than to the maximum.

Why this problem is worth solving

Outsourcing computation to a server you do not trust is the ordinary situation in healthcare, finance and cloud inference, and encryption normally solves it only for data at rest.

A form of encryption where the server can compute directly on the ciphertext without ever decrypting, so the result it hands back decrypts to the answer it would have produced on the plaintext. It has been possible in principle since 2009 and is still roughly ten thousand times slower than computing in the clear — a single encrypted inference on a 110-layer residual network takes about two hours on a CPU — which is why almost all the engineering effort goes into shaving constant factors off the maintenance work rather than the arithmetic itself.

is what closes the gap for data in use, and RNS-CKKS is the variant that made encrypted neural networks plausible, because it supports fractional arithmetic and packs thousands of values into a single ciphertext so one operation does the work of thousands.

The price is that a ciphertext is a consumable.

The operation that refreshes an exhausted ciphertext, restoring its ability to undergo more multiplications. It works by homomorphically evaluating the decryption circuit itself, which is why it is enormously expensive — it once took hours and now takes seconds. The property this paper exploits is that its cost depends only on the level it lifts the ciphertext to, not on where the ciphertext started, so bootstrapping to level 16 costs far more than bootstrapping to level 1 even though both begin from the same exhausted ciphertext.

is the only way to get that budget back, and the paper measures that dropping the target level from 16 to 14 saves 3137 milliseconds, which is about the cost of 240 ciphertext-ciphertext multiplications. That single measurement is the entire argument for why the compiler should care exactly how high it lifts things.

What people did before, and where it broke

Local rescaling rules driven by a threshold on scale. EVA rescales whenever a multiplication result would exceed the scale factor times a minimum called the waterline; PARS is lazier, allowing a larger result scale but constraining each operand. Both are fast to compute and easy to reason about. Where it broke. They only see the operation in front of them. The paper’s own worked example shows PARS being conservative enough that two rotations in a convolution end up executing one level higher than necessary, costing 12.9%. EVA has the opposite failing: it rescales so eagerly that Fhelipe, which adopts it, ends up issuing on average 21.6 times more rescaling operations than ReSBM, ranging from 5.51 times on ResNet20 to 69.12 times on VGG16.
Global search over the space of rescaling plans. HECATE and ELASM hill-climb over plans, assessing the cumulative effect of each choice rather than a local rule, and they do find better plans than the local strategies. Where it broke. Compile time. Over 300 seconds for LeNet-5, a model far smaller than anything in this paper. That is enough that the compilers which do support bootstrapping explicitly decline to use them, which means the better scale management and the bootstrapping support have never actually been combined.
Bootstrapping placement as a separate pass. Fhelipe uses dynamic programming over multiplicative depth; DaCapo uses liveness analysis to find where a refresh is needed. Both are principled and both work. Where it broke. Neither coordinates with scale management, so neither can price its own decisions accurately — the latency of an operation depends on the level it runs at, and the level depends on where rescaling happened. And both lift ciphertexts to the maximum allowed level, then use modswitches to come back down, which is precisely the wrong direction given that a bootstrap is priced by its destination.
Accept that optimal placement is NP-hard and settle for a heuristic over the whole program. This is the honest position, and it is where the field was. Where it broke. A heuristic over the whole program gives up on optimality everywhere. Nobody had asked whether there is a decomposition of the program in which the sub-problems become exactly solvable.
The gap. No compiler placed scale management and bootstrapping together, none had any optimality guarantee at any granularity, none lifted ciphertexts to anything but the maximum level, and the methods with the best scale management were too slow to compile the models people actually want to run.

How ReSBM builds a plan

From an unannotated data-flow graph to a placed rescaling and bootstrapping plan

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The whole pipeline runs in under a second on every model tested, because the cost is linear in the number of regions and neither the region size nor the level ceiling grows with the model.

The idea

Find a decomposition in which local decisions provably cannot escape. This is the move the whole paper turns on, and it comes from a small fact about the scheme rather than from anything clever about compilers: multiplications are the only operations that raise a ciphertext scale, and everything a maintenance operation does to a scale or level persists unchanged until the next multiplication. Cut the graph so each piece is exactly one multiplication deep, and you get a boundary that maintenance decisions cannot cross. Whatever you do inside a region, the ciphertexts leaving it have the same scale and the same level as they would have had under any other choice — only the time spent inside differs. That converts a problem where every decision perturbs every other decision into a pile of independent ones, which is the difference between searching and solving. Partitioning a program into blocks chosen so that local reordering is guaranteed safe, and then optimising hard inside each block, is exactly the structure of the block-wise quantum compiler framework covered elsewhere on this site, which found its own invariant to make local rewriting legal.

Once the sub-problem is small enough, stop searching and use an exact algorithm. Inside a region, the question is where along the paths to insert rescaling operations. ReSBM encodes it as a graph where each edge carries the cost of putting a rescale on it — the cost of the rescale itself, plus how much more expensive everything upstream becomes relative to rescaling immediately at the region entrance. A cut of that graph is exactly a valid placement, its weight is exactly the resulting latency, and so a minimum cut is exactly the best placement. The paper states and proves this as a theorem, and does the same in reverse for bootstrap placement. It is a modest theorem, and that is the point: the guarantee is local, not global, and it was bought by choosing a decomposition rather than by attacking the hard problem head-on. Refusing a slow exploration in favour of a fast analysis that reasons about the same quantity is the same bet as the compile-time scale analysis covered elsewhere on this site, which also traded a search over plans for something that computes the answer directly.

Pay only for the budget you will actually use. A bootstrap costs according to the level it lifts a ciphertext to, not the level it starts from. Both existing bootstrapping-aware compilers lift to the maximum the security parameters permit, then shed the surplus with modswitches, which are essentially free. That looks harmless and is not: on the paper’s hardware, targeting level 14 instead of 16 saves 3137 milliseconds, the price of about 240 ciphertext multiplications. Because ReSBM has already decided how many levels the stretch between two bootstraps will consume, it knows the answer, and it lifts each ciphertext exactly that far. On the deepest model tested, 105 of 110 bootstraps land between levels 13 and 15 rather than at 16; tighten the ceiling and the effect grows, with all 217 bootstraps landing between levels 5 and 9 when the ceiling is 10. Refusing to over-provision a resource simply because the maximum was available is the same discipline as the arithmetic-packing work for encrypted computation covered elsewhere on this site, which likewise found the waste hiding in a budget everyone had been rounding up.

Walking one stretch of a model through ReSBM

Placing maintenance across a residual block

A convolution, a polynomial approximation of the activation, a second convolution, and a masked addition — the shape that repeats through a residual network.

Step 1 of 5

Split the block into regions

The block has a multiplicative depth of five, so it becomes six regions. Each region starts with its multiplications and then contains the rotations, additions and relinearizations that follow at that depth. Loops whose unrolled body is only one multiplication deep are left rolled up, with their latency scaled by the iteration count.

Where a node sits is not always forced. A multiplication computed at depth two but consumed at depth three can go in either region. ReSBM pushes it later, because that makes it run at a lower level, which is cheaper — and it also avoids needing a modswitch afterwards to line the levels up for the addition that consumes it.

Why it works

The region boundary is a real invariant, not a heuristic. Only multiplication raises a scale, and maintenance effects persist until the next one → anything inserted inside a one-multiplication-deep region leaves the exit scales and levels untouched → the regions can be optimised independently without any risk that a good local choice ruins a neighbour.
Small sub-problems admit exact algorithms. Placing rescales along the paths of a region is precisely a cut of a weighted graph → minimum cut solves it in cubic time in the region size, with a proof that the cut weight is the latency → the compiler gets a guarantee where previous work had only a rule of thumb.
Cost is charged where it is actually incurred. Every edge weight includes not just the price of the maintenance operation but the extra price it imposes upstream → the optimiser is comparing whole-region outcomes rather than local scale thresholds → it naturally discovers the early rescales that let long runs of rotations execute one level cheaper.
The two problems are priced together. How many levels a stretch consumes determines the bootstrap target, and where rescaling happens determines how many levels are consumed → deciding either in isolation produces a wrong estimate of the other → coordinating them is what makes minimal-level bootstrapping possible at all.
The work does not grow with the model. Region size and the level ceiling are properties of the scheme, not of the network → the total cost is linear in the number of regions, which is the multiplicative depth → every model tested compiles in under a second, with the deepest taking 0.773.

What it costs (trade-offs and scope)

Optimality is per-region only, and the paper says so and shows a failing case. Global bootstrapping placement is NP-hard and ReSBM does not solve it. Its own section on limitations gives a small polynomial where ReSBM produces a sub-optimal plan with three bootstraps, which becomes optimal only after common subexpression elimination merges two of them, or after constant folding is applied first. The recommendation is to pair ReSBM with ordinary compiler optimisations, which is reasonable and is also an admission.
Fhelipe compiles faster than ReSBM, not slower. On every model in the table — 0.088 against 0.128 seconds on ResNet20, 0.540 against 0.773 on ResNet110. The headline compile-time claim of 4250.2 times is against DaCapo only.
That compile-time comparison is against published numbers on different hardware. DaCapo’s times are taken from its own paper, measured on a Core i7-12700, while ReSBM runs on a Xeon Platinum 8369B. The gap is far too large to be explained by the processors, but it is not a like-for-like measurement.
DaCapo is never compared on inference speed at all. Its runtime with bootstrapping support was proprietary at the time of writing and its implementation targets GPUs while ReSBM targets CPUs, so the entire runtime comparison rests on Fhelipe, whose approach the authors reimplemented inside their own framework rather than running as shipped.
The runtime win is real but moderate, and the ablations are smaller still. The average improvement over Fhelipe is 12.1%, ranging from 7.0% on MobileNet to 21.0% on VGG16. Against its own variants, ReSBM is ahead by 1.05 times with EVA-style scale management substituted in, 1.07 times with maximum-level bootstrapping substituted in, and 1.21 times with the PARS combination. Each individual mechanism contributes a few percent; the 1.21 comes from stacking them.
The benefit at different level ceilings is not monotone. On ResNet110 the improvement over Fhelipe is 8.8%, 5.0%, 26.0% and 36.6% as the ceiling drops from 16 to 14 to 12 to 10. The large numbers appear only at the tighter ceilings, and the value at 14 is lower than at 16.
Accuracy is preserved on average but not uniformly. The mean loss against unencrypted inference is 0.3%, with a peak of 1.7% on ResNet44 — larger than the 0.1% to 0.6% range the paper cites for expert hand-tuned implementations of the same networks. Only 1,000 images per model were tested, because a single ResNet110 inference takes about two hours.
One image per ciphertext, CIFAR-10 only. Every input fits in a single ciphertext, matching what the two comparison systems do. The authors state plainly that methods for partitioning larger images across several ciphertexts are not yet established, so whether the results carry over is an expectation rather than a measurement.

The evaluation

Three ways to place scale management and bootstrapping in an encrypted network

Property	DaCapo (liveness analysis plus PARS)	Fhelipe (dynamic programming plus EVA)	ReSBM (regions, min-cut, minimal levels)
How rescaling is placed
How high a bootstrap lifts a ciphertext
Compile time
Encrypted inference speed
Optimality guarantee

Measurements on an Intel Xeon Platinum 8369B with a level ceiling of 16, over ResNet20/44/110, AlexNet, VGG16, SqueezeNet and MobileNet on CIFAR-10.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

The two halves of the headline point in different directions. The compile-time claim of 4250.2 times is measured only against DaCapo, using DaCapo’s published numbers on a different processor, and the other comparison system compiles faster than ReSBM does on every single model. The inference claim of 12.1% is measured only against Fhelipe, reimplemented inside the authors’ own compiler rather than run as shipped, because DaCapo’s bootstrapping runtime was proprietary and targets GPUs. The ablations are honest and modest: swapping in EVA-style scale management costs 1.05 times, swapping in maximum-level bootstrapping costs 1.07 times, and the 1.21 times figure comes from combining the two substitutions. The optimality theorem is genuine but strictly local, and the paper supplies its own example where the global plan is worse than it should be. None of this makes the work less useful — a compiler that finishes in under a second and gives back a tenth of the runtime is worth having — but the numbers describe a careful engineering improvement, not a change of regime.

Background

Where this sits in the encrypted inference stack

Encrypted inference is roughly ten thousand times slower than the same computation in the clear, and almost none of that factor is the arithmetic — it is the maintenance the scheme demands and the enormous cost of refreshing exhausted ciphertexts. That is why so much of the field is compiler work rather than cryptography, and why the same question keeps returning in different forms: given a fixed budget of noise and levels, how much useful computation can you fit inside it before you have to pay for a refresh. This paper answers it by finding a decomposition that makes part of the question exactly solvable. The broader frameworks for running deep learning under this scheme covered elsewhere on this site sit one layer above, deciding how a network is laid out into ciphertexts in the first place, and the two concerns compound — a layout that consumes fewer levels leaves the placement problem an easier one.

If you remember only three things

1. ReSBM cuts an encrypted program into regions each one multiplication deep, which makes the placement of rescaling and bootstrapping inside a region provably invisible from outside it — turning a globally entangled problem into independent local ones.
2. Each local problem is then exactly a minimum cut, giving the first scale-management placement with an optimality proof, and a dynamic program on top lifts every ciphertext only to the level the next stretch will actually consume rather than to the maximum, which matters because a bootstrap is priced by its destination.
3. The result compiles every model tested in under a second and runs encrypted inference 12.1% faster than the leading alternative on average — a solid engineering gain, though the optimality is local only, the compile-time headline is measured against a different system than the runtime one, and each individual mechanism contributes just a few percent.

Check yourself

Check your understanding

1. Why can ReSBM optimise each region independently without the regions interfering?
2. Why is it wasteful to bootstrap a ciphertext to the maximum level and then bring it down with modswitches?
3. What does the minimum-cut formulation actually guarantee?
4. How should the headline claims of 4250.2 times faster compilation and 12.1% faster inference be read together?

Sources

The paper is “ReSBM: Region-based Scale and Minimal-Level Bootstrapping Management for FHE via Min-Cut” by Yan Liu, Jianxin Lai, Long Li, Tianxiang Sui, Linjie Xiao, Peng Yuan, Xiaojing Zhang, Qing Zhu, Wenguang Chen and Jingling Xue, published at ASPLOS 2025 Volume 1, pages 924-939, DOI 10.1145/3669940.3707276. The authors are at Ant Group in Shanghai, with Wenguang Chen and Jingling Xue as corresponding authors, and the work is open-sourced inside the ANT-ACE compiler framework. It is open access under a Creative Commons licence.

This explainer is written from the full text, read through a proxy of the ACM Digital Library copy. Everything above comes from the paper’s own sections 2 through 5: the table of scale and level effects for each RNS-CKKS operation and the constraint that a level must cover the logarithm of the scale; the statement that bootstrapping latency depends only on the target level; the worked residual-block example with its region partition, its 131.832 against 142.616 and 143.860 millisecond region latencies, and its choice of level 1 rather than level 3 for the second bootstrap; the three-tier structure of the region partitioner, the scale manager, the two min-cut placement algorithms and the dynamic program above them; the two optimality theorems and their proofs; the complexity analysis showing the cost is linear in the number of regions; the section on limitations with its own sub-optimal example fixed by common subexpression elimination; the compile-time table with ReSBM under one second on every model against Fhelipe faster still and DaCapo at 15.8 to 1042.3 seconds; the 21.6 times average and 5.51 to 69.12 times range in rescaling counts; the 12.1% average inference improvement with its 7.0% to 21.0% range; the ablations at 1.05, 1.07 and 1.21 times; the level-ceiling sweep with its 8.8%, 5.0%, 26.0% and 36.6% improvements and its bootstrap level distributions; and the accuracy table with its 0.3% average and 1.7% peak loss over 1,000 images per model.