CHEHAB RL: Learning to Optimize Fully Homomorphic Encryption Computations

Bilel Sefsaf, Abderraouf Dandani, Abdessamed Seddiki, Arab Mohammed, Eduardo Chielle, Michail Maniatakos and 1 other

Fully homomorphic encryption (FHE) lets a server compute on encrypted data, but it is astronomically slow — a single encrypted multiply can take about a million times longer than a plaintext one — so the key optimization is vectorization, packing many values into one ciphertext and operating on them at once, which requires finding the right sequence of program-rewriting steps while avoiding costly rotations and runaway noise; finding that sequence is intractable, and prior compilers lean on hand-tuned heuristics and expensive search; this paper (NYU Abu Dhabi — Bilel Sefsaf, Riyadh Baghdadi, and colleagues) presents CHEHAB RL, which trains a deep reinforcement-learning agent to learn a policy for applying rewriting rules that vectorizes FHE code, producing code 5.3 times faster with 2.54 times less noise while compiling 27.9 times faster than the state-of-the-art Coyote compiler.

The argument in one glance

Problem

Making encrypted computation fast means an intractable search over program rewrites

Fully homomorphic encryption (FHE) lets a server compute directly on encrypted data and return an encrypted result, so a client can outsource work without revealing anything — a powerful privacy guarantee. The catch is speed: FHE is astronomically expensive, because each homomorphic operation is really many large polynomial multiplications, so a single encrypted multiplication can take about a million times longer than a plaintext one. The main way to make FHE practical is vectorization: FHE schemes can pack a vector of many values into a single ciphertext (thousands of slots) and operate on all of them at once, doing many scalar operations in one homomorphic operation. But turning scalar code into vectorized code is hard. You cannot index into a packed ciphertext directly; reaching a specific slot requires rotation operations, which are slow and, worse, increase the ciphertext's noise. And FHE has a noise budget: every operation adds noise, and if it grows too much the result becomes undecryptable, so vectorization must also keep noise and multiplicative depth low. Finding the sequence of program transformations that vectorizes code well, minimizing latency, rotations, and noise, is intractable — and today it demands scarce cryptographic expertise.
What people did

Use hand-tuned heuristics, solvers, or program synthesis to vectorize

Prior FHE compilers attack vectorization with predefined heuristics and expensive search. Coyote, the state-of-the-art vectorizing compiler, couples hand-tuned heuristics with an integer-linear-programming solver to decide how to pack values; Porcupine uses program synthesis to enumerate and check candidate vectorizations; and compilers like CHET vectorize structured, loop-based computations over packed tensors such as neural networks.
Why it fell short

Heuristics get stuck, search is too slow, and unstructured code is unsupported

These approaches all struggle because the decisions interact in non-local ways: a packing choice made early can force expensive rotations or increase circuit depth much later, so simple greedy or heuristic rule application gets trapped in poor local optima. Escaping those traps by searching the space of vectorizations combinatorially — with an integer-linear-programming solver or program synthesis — is prohibitively slow, making compilation itself a bottleneck. And the reach is narrow: compilers like CHET handle only structured, loop-based code over packed tensors, not the unstructured, arbitrary code that many programs contain. So FHE developers face a bad set of options: fast but shortsighted heuristics that leave performance on the table, or thorough but painfully slow search that still may not cover their code. What is needed is a method that learns how to sequence the transformations well — capturing the non-local effects — without paying the cost of exhaustive search, and that works on both structured and unstructured code.
This paper's idea

Train a reinforcement-learning agent to sequence the rewriting rules

CHEHAB RL treats FHE code optimization as a sequential decision-making problem and trains a deep reinforcement-learning (RL) agent to solve it, rather than using predefined heuristics or combinatorial search. The code is transformed by a Term Rewriting System (TRS) — a set of rewriting rules (for example, that multiplication commutes, plus many more) whose successive application turns scalar FHE code into vectorized code; each vectorization strategy corresponds to a different sequence of rule applications. The RL agent learns a policy for choosing that sequence: at each step it looks at the current program and picks which rule to apply and where. Because a rule can apply at many locations, the action space is huge, so CHEHAB RL uses a multi-discrete hierarchical policy with a position network — the agent first decides which transformation, then a small network selects which matching location in the program to apply it to. To guide learning it uses an analytical reward function tailored to FHE that combines operation cost, circuit depth, and multiplicative depth, capturing both performance and noise growth while being cheap enough to enable fast training (no need to actually run or decrypt). It encodes the program with a code model able to handle the long token sequences of unrolled FHE programs, and it is trained on a diverse dataset of computations synthesized by a large language model (LLM). Integrated into the CHEHAB FHE compiler and supporting both structured and unstructured code, it generates code that, against the state-of-the-art Coyote compiler, is 5.3 times faster to execute, accumulates 2.54 times less noise, and compiles 27.9 times faster (geometric means).

Why this problem is worth solving

Fully homomorphic encryption is one of the strongest tools for privacy, but its cost is what keeps it from being used, and that cost is largely a compiler problem.

FHE offers something remarkable: a server can compute on data it cannot read, so a hospital or bank could outsource analysis of encrypted records and get back an encrypted answer, with the plaintext never exposed. The obstacle has always been performance. Every homomorphic operation is far heavier than its plaintext equivalent — a single ciphertext multiplication can be around a million times slower — because under the hood it is a set of operations on large polynomials. To make this bearable, FHE schemes support packing: a vector of many integers is encoded into one ciphertext (with thousands of slots, using the Chinese Remainder Theorem), so a single homomorphic operation processes the whole vector at once. Vectorizing a program this way is the single most important optimization for FHE performance. But it is delicate. Packed ciphertexts cannot be indexed directly, so moving data between slots requires rotation operations, which are among the most expensive FHE operations and also add noise. And FHE runs on a noise budget: each operation adds noise, multiplicative depth compounds it, and once noise exceeds the budget the ciphertext can no longer be decrypted. So good vectorization must simultaneously cut operation count, keep rotations few, and hold noise and depth down. Because getting this right is what determines whether an FHE application is usable, and because it is far too intricate to do by hand, automating it well directly decides FHE’s practicality.

The reason it is hard to automate is that the choices interact, so neither fast heuristics nor thorough search wins.

Vectorizing FHE code means choosing a sequence of program transformations — how to pack values, when to rotate, how to reassociate operations — and these choices are deeply entangled. A decision made early, like how to pack a set of values, can have non-local effects: it may force extra rotations or increase the multiplicative depth many steps later, in ways that are not visible when the decision is made. This entanglement is fatal to simple approaches. Greedy or heuristic rule application, which picks whatever looks best locally, gets trapped in poor local optima because it cannot foresee the downstream cost of a choice. The alternative — searching the space of transformation sequences exhaustively — does capture the interactions, but the space is enormous, so the search (whether by an integer-linear-programming solver, as in Coyote, or by program synthesis, as in Porcupine) becomes prohibitively slow, turning the compiler itself into a bottleneck. On top of that, several prior compilers only handle structured, loop-based code, leaving arbitrary unstructured programs unsupported. So the field was caught between shortsighted speed and unaffordable thoroughness, with no method that learned to make good long-horizon transformation choices cheaply. That gap — a way to internalize the non-local structure of the problem without exhaustive search — is exactly what a learned policy is suited to fill.

What people did before, and where it broke

Hand-tuned heuristics with a solver (Coyote). Combine expert heuristics with an integer-linear-programming solver to decide how to pack values for vectorization. Where it broke. The solver-based search is expensive, making compilation slow, and the heuristics still cannot fully anticipate non-local effects.
Program synthesis (Porcupine). Enumerate and check candidate vectorizations by synthesis. Where it broke. Enumerating the huge space of candidates is prohibitively slow, so it does not scale to larger or more varied programs.
Greedy or heuristic rule application. Apply rewriting rules wherever they look locally beneficial. Where it broke. Because packing and rotation decisions have non-local effects, greedy choices get trapped in poor local optima and miss globally better vectorizations.
Structured-only vectorizers (CHET). Vectorize loop-based computations over packed tensors, such as neural networks. Where it broke. They do not support unstructured, arbitrary (non-loop) code, so many programs fall outside their scope.
The gap. No approach learned to sequence FHE program transformations well — accounting for their non-local effects and covering both structured and unstructured code — without paying the cost of exhaustive combinatorial search.

How CHEHAB RL works

Learning a policy that rewrites scalar FHE code into fast vectorized code

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

The idea

Replace search and heuristics with a learned policy. The core bet of CHEHAB RL is that the intractable job of choosing a good sequence of FHE transformations can be learned once, as a policy, rather than re-searched from scratch for every program. A trained agent internalizes the non-local structure of the problem and then makes fast, informed choices, avoiding both greedy shortsightedness and exhaustive search. Using learning to guide compiler optimization decisions instead of hand-tuned heuristics or brute-force exploration is the same shift the work on a fast and portable Bayesian compiler optimization framework covered elsewhere on this site represents, replacing manual search of an optimization space with a data-driven one. CHEHAB RL takes this to FHE vectorization, where the payoff of learning the long-horizon consequences of each rewrite is especially large.

Optimize by applying a sequence of rewriting rules. CHEHAB RL expresses every vectorization as a path through a term rewriting system: start from scalar code and apply rules step by step until it is vectorized, so the optimization problem becomes choosing which rules to apply, in what order, and where. Framing program optimization as the automatic application of transformation rules that rewrite a program toward a better form is the same foundation the work on an abstraction for automatic tensorized program optimization covered elsewhere on this site is built on, treating optimization as a controlled sequence of program transformations. CHEHAB RL’s advance is to have an RL agent, rather than a search or a schedule template, decide that sequence, with a hierarchical policy to cope with the many places each rule could fire.

Make encrypted computation practical by compiling it better. Ultimately CHEHAB RL is about the same goal as the rest of the FHE-systems effort: driving down the cost of computing on encrypted data so it can actually be used. Attacking FHE’s crippling overhead by compiling scalar code into efficient vectorized form is the same undertaking the work on a compiler for vectorizing encrypted arithmetic circuits covered elsewhere on this site pursues, transforming FHE programs to pack and batch their operations. CHEHAB RL contributes the vectorization piece, and shows a learned optimizer can beat a state-of-the-art hand-built one on speed, noise, and even compile time.

Following a program through CHEHAB RL

Vectorizing a piece of unstructured FHE code with a learned agent

A trace, drawn from the paper, of how the RL agent turns scalar FHE code into fast vectorized code.

Step 1 of 5

Start from scalar FHE code

The agent is given an unstructured (non-loop) FHE computation that operates on values individually. Left as-is, it would run each operation on its own ciphertext, wasting the thousands of slots a packed ciphertext offers.

Unstructured code is exactly what prior structured-only compilers could not vectorize.

Why it works

A learned policy captures non-local effects without exhaustive search. Packing and rotation choices have downstream consequences greedy methods miss → but an RL agent trained across many programs learns those long-horizon effects → so it makes good sequences of choices cheaply, avoiding both local optima and slow search.
A hierarchical policy tames the huge action space. Each rule can apply at many locations, so the choices explode → but deciding the rule first and the location second with a position network factorizes the decision → so the agent can navigate the space efficiently.
An analytical reward makes training fast and FHE-aware. Measuring quality by actually running or decrypting would be far too slow → but a cost function combining operations, circuit depth, and multiplicative depth captures speed and noise → so the agent gets accurate, cheap feedback and trains quickly.
An LLM-synthesized dataset gives broad coverage. Learning a general policy needs many diverse programs, which are scarce → but a large language model can synthesize a varied dataset of FHE computations → so the agent generalizes across structured and unstructured code.
A policy compiles faster than a solver searches. Coyote must run an expensive solver per program → but a trained policy just applies its learned choices → so CHEHAB RL compiles 27.9 times faster while still producing faster, lower-noise code.

What it costs (trade-offs and scope)

Training the agent is an upfront cost. The speed at compile time comes from a policy that must first be trained on a large synthesized dataset with reinforcement learning; that training is a one-time investment, but it is substantial and must be redone if the rule set, cost model, or target scheme changes materially.
The reward is an analytical proxy. CHEHAB RL optimizes an analytical FHE cost function (operations, circuit depth, multiplicative depth) rather than measured runtime, which is what makes training fast; the results validate that this proxy tracks real performance well, but any proxy can diverge from true cost on cases it models poorly.
Quality depends on the rewriting rules and the training data. The agent can only compose the rules in its term rewriting system, and it generalizes from LLM-synthesized programs; transformations outside the rule set are unreachable, and programs far from the training distribution may be optimized less well.
It is a learned optimizer, so its choices are not guaranteed optimal. Unlike an exhaustive solver that (slowly) searches for a provably good packing, a policy makes fast heuristic-like choices; it beats Coyote on the benchmarks, but it offers no optimality guarantee and could underperform a full search on some program.
The gains are against one baseline on a benchmark suite. The 5.3 times, 2.54 times, and 27.9 times figures are geometric means versus Coyote on the paper’s benchmarks; other baselines, workloads, or FHE schemes could shift the numbers.

The evaluation

Vectorizing FHE code

Property	Heuristics plus solver (Coyote)	Program synthesis (Porcupine)	CHEHAB RL
How the transformation sequence is chosen
Handles non-local effects
Supports unstructured code
Execution speed and noise of output
Compilation time

A comparison of ways to vectorize FHE code. CHEHAB RL learns a reinforcement-learning policy to sequence rewriting rules, generating code 5.3 times faster with 2.54 times less noise than the state-of-the-art Coyote compiler, while compiling 27.9 times faster (geometric means), and supporting both structured and unstructured code.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

This explainer is based on the paper’s full text (arXiv:2601.19367). The mechanism described is the paper’s: CHEHAB RL uses deep reinforcement learning to automate FHE code optimization, formulating it as a sequential decision-making problem and training an agent to learn a policy for applying a sequence of rewriting rules (from a Term Rewriting System) that vectorizes scalar FHE code while reducing instruction latency and noise growth, supporting both structured and unstructured code. To handle the large action space (each rule applicable at many locations), it uses a multi-discrete hierarchical policy with a position network (the agent chooses a rule, then a location). It uses an analytical reward function tailored to FHE that combines operation cost, circuit depth, and multiplicative depth (capturing performance and noise growth) for fast training, encodes programs with a code model suited to long token sequences, and trains on a dataset of computations synthesized by a large language model. Integrated into the CHEHAB FHE compiler and compared against Coyote, a state-of-the-art vectorizing FHE compiler, it reports code that is 5.3 times faster in execution, accumulates 2.54 times less noise, and compiles 27.9 times faster (geometric means). Exact rule sets, network architectures, reward details, the dataset, and full results should be read from the paper.

Background

Why compilers are increasingly learning instead of searching

It helps to see CHEHAB RL as part of a broad move to bring machine learning into compiler optimization. Compilers have always faced enormous decision spaces — which transformations to apply, in what order, with what parameters — and the interactions between choices make the spaces rugged and full of traps. Traditionally, compilers navigated this with hand-crafted heuristics (fast but shortsighted) or with explicit search (thorough but slow), and both grow harder as the target gets more specialized. Machine learning offers a third path: learn from data how good choices tend to look, so the compiler can make fast, well-informed decisions without re-searching every time, and reinforcement learning fits especially well when optimization is naturally a sequence of dependent choices with a measurable objective. This has been applied to loop scheduling, tensor-program tuning, and instruction selection, and FHE is a particularly compelling target because its costs are extreme, its transformation choices have long-range effects, and expert time is scarce. The broader effort to make heavily specialized code fast without demanding that every developer be a domain expert is the same undertaking the work on a framework for developing and optimizing fully homomorphic encryption programs covered elsewhere on this site takes on, lowering the expertise barrier to efficient FHE. CHEHAB RL argues that a learned agent can not only match but exceed a carefully engineered search-based FHE compiler, hinting that learned optimization may become the default for such hard, specialized domains.

If you remember only three things

1. Fully homomorphic encryption (FHE) computes on encrypted data but is astronomically slow (an encrypted multiply can be about a million times slower than plaintext), so the key optimization is vectorization: packing many values into one ciphertext (thousands of slots) and operating on them together. Vectorizing is intractable to do well — packed ciphertexts cannot be indexed, so slot movement needs expensive, noise-adding rotations, and FHE has a noise budget — and choices have non-local effects, so greedy heuristics get stuck and combinatorial search (as in Coyote or Porcupine) is prohibitively slow.
2. CHEHAB RL frames FHE optimization as sequential decision-making and trains a deep reinforcement-learning agent to learn a policy for applying rewriting rules (a term rewriting system) that vectorizes scalar code. It handles the huge action space with a hierarchical policy (choose a rule, then a location via a position network), guides learning with a cheap analytical reward combining operation cost, circuit depth, and multiplicative depth (capturing speed and noise), encodes long programs with a code model, and trains on an LLM-synthesized dataset — supporting both structured and unstructured code.
3. Integrated into the CHEHAB compiler and compared with the state-of-the-art Coyote, CHEHAB RL produces code 5.3 times faster to execute with 2.54 times less noise, while compiling 27.9 times faster (geometric means), because a learned policy just applies its choices instead of running an expensive solver. The trade-offs: training the agent is a substantial upfront cost, it optimizes an analytical proxy rather than measured runtime, it is limited to its rule set and training distribution, and as a learned optimizer it offers no optimality guarantee.

Check yourself

Check your understanding

1. Why is vectorizing FHE code both essential and hard?
2. How does CHEHAB RL choose how to vectorize code, and how does that differ from prior compilers?
3. Why does CHEHAB RL use an analytical reward function and a hierarchical policy?
4. Predict: compared with Coyote, why would CHEHAB RL compile much faster (27.9 times) while also producing faster, lower-noise code?

Sources

The paper is “CHEHAB RL: Learning to Optimize Fully Homomorphic Encryption Computations” by Bilel Sefsaf, Abderraouf Dandani, Abdessamed Seddiki, Arab Mohammed, Eduardo Chielle, Michail Maniatakos, and Riyadh Baghdadi (New York University Abu Dhabi), published at ASPLOS 2026, DOI 10.1145/3779212.3790138.

This explainer is written from the paper’s full text (arXiv:2601.19367). Fully homomorphic encryption (FHE) enables computation directly on encrypted data but is very expensive, and writing efficient FHE code requires cryptographic expertise, with the optimal sequence of program transformations often intractable to find. CHEHAB RL leverages deep reinforcement learning to automate FHE code optimization: instead of predefined heuristics or combinatorial search, it trains an agent to learn a policy for applying a sequence of rewriting rules (from a Term Rewriting System) to automatically vectorize scalar FHE code while reducing instruction latency and noise growth, supporting both structured and unstructured code. Because each rule can apply at many locations, the action space is large, so the method uses a multi-discrete hierarchical policy with a position network (choose a rule, then a location); it uses an analytical reward function tailored to FHE that combines operation cost, circuit depth, and multiplicative depth (capturing performance and noise) to enable fast training; it encodes programs with a code model able to handle the long token sequences of unrolled FHE programs; and it trains on a diverse dataset of computations synthesized by a large language model. Integrated into the CHEHAB FHE compiler and evaluated against Coyote, a state-of-the-art vectorizing FHE compiler, CHEHAB RL generates code that is 5.3 times faster in execution, accumulates 2.54 times less noise, and compiles 27.9 times faster (geometric means). No numbers beyond the paper’s own have been introduced; exact rule sets, network architectures, reward details, the dataset, and full results should be confirmed in the paper.