Do Better Scheduling Bounds Survive Contact with Encrypted Workloads?

Computing on encrypted data with fully homomorphic encryption (FHE) means a server evaluates arithmetic on data it cannot read. It is slow, and the cost of each job depends heavily on its multiplicative depth, the longest chain of sequential multiplications in the job's circuit. Each multiplication adds noise to the ciphertext. Deeper circuits therefore need larger encryption parameters, which slow down every operation. Once a job's depth exceeds what a machine's parameters can absorb, the machine must run bootstrapping, a ciphertext refresh that takes seconds. A server farm with a mix of CPUs and memory-limited GPUs, handling a mix of encrypted jobs (neural network inference, decision trees, statistical transforms), therefore faces a real assignment problem. How long a job takes depends on the job and the machine together, and in an irregular way.

Scheduling theory has a precise model for exactly this: minimizing total weighted completion time on unrelated machines, where every job–machine pair has its own processing time. Over the last decade the best provable approximation ratio has fallen from 1.5 to $3/2 - c$, then 1.488, then $1.36+\epsilon$. None of these algorithms has ever been run. This note proposes to build native implementations of them, generate unrelated-machine instances whose irregularity comes from depth and bootstrapping costs measured on real FHE pipelines, and settle three questions. Do the post-1.5 rounding schemes beat simple greedy rules in schedule quality? Do they still win once their own solve time is counted? And does the language they are implemented in change the answer?

Core Claim

FHE serving produces processing-time matrices that are heavy-tailed and machine-specific in a principled way. A job whose depth slightly exceeds one machine's level budget pays an extra bootstrap there but not on a machine with larger parameters. Our hypothesis is that these step-shaped cost jumps are the regime where the theory predicts a difference. Independent randomized rounding will sometimes pile several expensive, high-weight jobs onto one machine. Correlated rounding is designed to prevent such collisions. Greedy rules that ignore the step structure should misplace jobs near level boundaries.

The claim can fail in an informative way. If simple weighted-shortest-processing-time greedy rules land within a few percent of the linear-programming lower bound on these instances, then the 1.5→1.36 progress has no practical consequence for this workload. A negative result of that kind is worth publishing, because no one has measured it. Either way, the contribution is the first empirical ratio-to-lower-bound and wall-clock data for this algorithm family, on instances that are not arbitrary random matrices.

Where the Instances Come From

The FHE directions supply the cost model, not a new algorithm. Machine $i$ runs a parameter set with polynomial ring dimension $N_i$ and level budget $L_i$, the number of multiplications a ciphertext can absorb before refresh. GPUs with limited memory for evaluation keys get smaller $N_i$ and $L_i$. Job $j$ has an operation profile $n_j$ (counts of multiplications, rotations, additions) and depth $d_j$. Its processing time on machine $i$ is modeled as

$$p_{ij} = n_j \cdot c_i(N_i) + \left(\lceil d_j / L_i \rceil - 1\right) B_i,$$

where $c_i(N_i)$ is the measured per-operation cost vector on machine $i$ at that ring dimension, and $B_i$ is its measured bootstrap time. The ceiling term creates the step structure.

Each job may come in a depth-minimized and an operation-minimized variant. This is the Pareto front that Generating One-Hot Maps under Encryption quantifies between conserving noise budget and maximizing throughput. We take $p_{ij}$ as the minimum over variants. This adds no algorithmic difficulty, but it makes the matrix more unrelated, because different variants win on different machines. The decision-tree workloads are an example: Level Up and Non-Interactive Private Decision Tree Evaluation compress decision paths to logarithmic depth.

The job mix is drawn from published pipelines that span orders of magnitude, which motivates the heavy-tail claim:

  • ResNet-20 and ResNet-50 as compiled by Orion. Orion reports 8.98 hours single-threaded for ResNet-50 on ImageNet.
  • SqueezeNet and Inception variants from HEMET. HEMET reports latencies of 72.7 s versus 29.6 s for SqueezeNet before and after depth-aware redesign.
  • Non-polynomial statistics from De Bello Homomorphico. That paper reports roughly 10 s per basic function and 4.09 hours for Box–Cox in OpenFHE.

We calibrate $c_i$ and $B_i$ by profiling OpenFHE on CPU configurations. We add a GPU profile where a GPU backend in the style of Leveraging GPU in Homomorphic Encryption is available. Before any scheduling result is reported, we validate the model against measured end-to-end job times on held-out jobs.

Research Program

Algorithms. We implement five algorithms in C++ against a shared time-indexed linear-programming relaxation where the algorithms allow it:

Li's algorithm needs care in two places. It relies on job-size and weight swapping plus a three-class grouping that the paper states its analysis is restricted to, so we implement it as described and report separately how often instances fall outside its analyzed regime. Its configuration LP is the main practical cost. We test whether the solver techniques of Nearly-Linear Time LP Solvers and Rounding Algorithms for Scheduling Problems make it tractable at hundreds to thousands of jobs.

Language comparison. Every algorithm also gets a straightforward Python/NumPy implementation calling the same LP solver. This lets us separate algorithmic cost from interpreter cost (loop dispatch, object boxing, foreign-function marshaling). Efficient L1 Regularized Logistic Regression shows why this matters: there, a C implementation of a competitor beat a MATLAB prototype on one dataset purely through lower overhead, and conclusions drawn from mixed-language comparisons can flip. ALE-Bench likewise reports that compiled C++ and Rust solutions systematically beat Python on CPU-bound optimization.

We make a falsifiable prediction about where interpreter overhead matters. Individual FHE operations take milliseconds to seconds, so Python orchestration of the FHE execution itself should be a negligible fraction of runtime. Interpreter overhead should matter for the scheduler's own rounding loops, which perform many cheap graph operations. We measure both.

Role of each direction. The scheduling papers supply the methods under test. The depth-optimization papers supply the instance structure. The interpreted-language work constrains how the comparison is run. The validation gap, documented for this exact $(1.36+\epsilon)$ result ("Datasets: Not discussed"), is the motivation.

Relation to existing systems. The closest systems, Orion and Porcupine, schedule within one circuit, using shortest-path bootstrap placement and SMT search over 10–12-instruction blocks respectively. Neither assigns many jobs across machines, and neither has a bound. We do the reverse: we take each compiled circuit as fixed and study cross-job assignment. Orion and Porcupine are complementary upstream components, not competitors.

Baselines

Naive reference. The do-nothing point is first-come-first-served assignment to the earliest-available machine. It is depth-blind and weight-blind, and represents what a generic job queue in front of an FHE cluster does.

Strongest heuristic. The strongest simple competitor is a weighted greedy rule. Jobs are taken in decreasing order of the ratio $w_j / \min_i p_{ij}$. Each job is placed on the machine that minimizes its marginal increase in total weighted completion time. Each machine then runs its jobs in Smith's ratio order, which is optimal for a fixed assignment. We also run this rule followed by pairwise swap-and-move local search, given the same wall-clock budget the LP methods use. This is the competitor most likely to embarrass the theory: it is cheap, it already uses the true $p_{ij}$, and Smith ordering removes intra-machine suboptimality.

Strongest existing method. The strongest provable method is Li's iterative rounding, with the 1.488 and lift-and-round schemes as intermediate points. For none of these does the file contain a reported empirical result. Concretely, there is no reported result found on Lacuna for any unrelated-machine weighted-completion-time algorithm, greedy or LP-based, on any benchmark. The only quantitative references are the FHE job latencies used to build instances, such as Orion's reported 2.38× speedup over Fhelipe on ResNet-20 and the HEMET and De Bello latencies quoted above.

Fairness and success criteria. All methods see identical instances and identical $p_{ij}$ matrices, run on the same hardware, and are given equal wall-clock budgets when scheduler time is charged. An LP-based method "beats" greedy-plus-local-search only if both of the following hold:

  • its mean ratio to the LP lower bound is at least two percentage points lower across instance families, with a paired confidence interval excluding zero;
  • the advantage persists after adding its own solve time to every job's completion time.

Ablations. Two ablations isolate the key ingredients. The first holds the LP solution fixed and swaps only the rounding step (independent versus correlated), so any difference is attributable to collision avoidance. The second replaces the depth-aware cost model with a depth-blind one built from operation counts only. Schedules are computed from the blind model and evaluated under the true model. This measures how much of the scheduling problem's difficulty, and of any method's advantage, comes from the bootstrap step structure.

Why not just…?

Why not just use the greedy Smith-ratio rule and skip the LPs? This is the real threat, and the proposal is built so it can win. Worst-case theory says greedy rules have unbounded or poor ratios on unrelated machines. The file's evidence that greedy is weak, HeuriGym's roughly 0.6 quality score for LLM-written heuristics, comes from different problems and says nothing about Smith-rule scheduling. If greedy-plus-local-search matches correlated rounding within two points on FHE instances, we report that as the main finding. The rounding-only ablation and adversarial instance families (built to force collisions) will show whether any gap exists only in contrived cases.

Why not just solve the scheduling problem exactly with a mixed-integer solver? For small instances we do, to get ground truth. A serving system must schedule hundreds of jobs repeatedly, though, and the exact program grows with jobs × machines × time slots. We measure the instance size at which exact solving exceeds the time a batch would wait anyway. Below that crossover the approximation algorithms are unnecessary, and we will say so.

Why not just optimize depth and ignore scheduling? Depth-aware redesign alone gives HEMET roughly a 59% latency cut, likely larger than any scheduling gain. But depth optimization fixes each job's circuit; it does not decide which job goes where once machines with different level budgets coexist. The depth-blind ablation quantifies what remains. If the residual scheduling gain over first-come-first-served is small relative to circuit-level gains, that bounds the value of this whole line.

Why not just prototype in Python like most research code? The scheduler's rounding phase runs many cheap graph operations, exactly where interpreter dispatch dominates. A Python implementation of Li's algorithm could look impractical for reasons that have nothing to do with the algorithm. The dual implementation measures this directly. We will report the instance sizes at which the language, rather than the algorithm, determines the ranking.

Proposed Experiments and Decisive Checks

Instance families. There are three:

  • realistic FHE serving mixes, from the Orion, HEMET, decision-tree and De Bello workloads, on 4–32 heterogeneous machine profiles, with weights set by client priority classes;
  • the same mixes with level budgets perturbed to move many jobs near bootstrap boundaries;
  • synthetic adversarial matrices that stress independent rounding.

Metrics. We report, per instance:

  • total weighted completion time divided by the LP lower bound, an empirical ratio comparable directly to 1.5, 1.488 and 1.36;
  • the same ratio with scheduler solve time charged to completions;
  • scheduler wall-clock in C++ and Python;
  • cost-model error against measured OpenFHE runtimes.

Decisive checks. Four results settle the questions:

  • Whether any method's empirical ratio approaches its worst-case guarantee. We expect not, but Li's computer-assisted analysis makes it worth checking for gross mismatches.
  • Whether correlated rounding beats independent rounding on the boundary-perturbed family specifically. The collision hypothesis predicts the gap is largest there.
  • Whether greedy-plus-local-search is within two points of the best LP method on realistic mixes. If it is, the practical case for post-1.5 rounding in this domain fails.
  • The job count at which C++ and Python implementations of the same algorithm swap ranks against greedy, which isolates interpreter overhead as a confound in algorithm comparisons.