- Rating
- 3
- Confidence
- 3(+1)
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper introduces FHEvolve, a constraint-guided evolutionary code optimization framework for fully homomorphic encryption (FHE) programs. The paper argues that generic LLM-based evolutionary coding systems struggle on FHE workloads because they lack explicit representations of cryptographic constraints, tend to remain within a single algorithmic strategy family, and receive unstructured FHE runtime failures. FHEvolve addresses these issues with four components: a Spec Compiler, a depth-tiered Strategy Library, a Hierarchical Strategy Evolver, and a Crypto-Typed Repair Classifier. The framework is evaluated on eight workloads spanning seven CKKS FHERMA challenges and one BFV matrix-vector multiplication task. Compared with Vanilla OpenEvolve, FHEvolve improves the combined accuracy-latency score on workloads with sufficient search headroom, while roughly matching Vanilla on depth-saturated workloads. The paper additionally reports component ablations, comparisons with FHE-Coder and three FHE compilers, convergence analysis, token/compute costs, and a held-out evaluation on encrypted fraud classification.
Critical strengths
- Strong and well-controlled empirical validation. The comparison with Vanilla OpenEvolve is well controlled. The two systems share the same evolutionary engine, seeds, evaluator, and search budget, and FHEvolve adds domain-aware mechanisms. The main gains are concentrated on workloads with actual search headroom, making the observed pattern internally coherent.
- The paper identifies an important failure mode of optimization agents. The Eth-Fraud study shows optimizing binary agreement alone is faster but less generalizable program, while adding a probability error constraint gives a speedup with preserved agreement on held-out examples. This is a useful insight for the broader design of LLM-based optimization systems.
Critical weaknesses
- I'm wondering whether the main results are dependent on the chosen optimization objective. The combined metric is reasonable for the benchmark, but its scalarization and workload-specific reference latencies can affect which programs are selected. The Eth-Fraud study demonstrates that changing the selection criterion can lead to substantially different solutions and generalization behavior. It would therefore be useful to evaluate the robustness of the main conclusions under alternative reasonable accuracy–latency trade-offs.
- The generalization of the curated strategy space is not fully established. The strategy library contains 13 manually defined FHE strategy templates, and the evaluated workloads largely fall into the corresponding workload families. This is a reasonable way to inject reusable FHE knowledge, but it leaves open how well the approach handles workloads requiring substantially different algorithmic strategies or strategy families that are not represented in the current library. The paper's broader claims about reusable strategy-guided search would therefore benefit from evaluation on such cases.
Questions for authors
- How do the main improvements generalize to unseen inputs? Since most FHERMA workloads are evaluated on the same fixed vectors used during search, do the authors have additional held-out evaluations or random test inputs for Softmax, ReLU, Sign, and the other workloads?
- How sensitive are the main comparisons to the choice of optimization metric? In particular, would FHEvolve still consistently outperform Vanilla OpenEvolve under alternative reasonable accuracy-latency scalarizations or under a constrained formulation?
- How does FHEvolve behave when the optimal solution is not covered by the current strategy library? In particular, can the system discover or expand to a new strategy family without additional manually authored templates, or is the library intended to define the search space?
4 comments
Question 2. How sensitive are the main comparisons to the choice of optimization metric? In particular, would FHEvolve still consistently outperform Vanilla OpenEvolve under alternative reasonable accuracy-latency scalarizations or under a constrained formulation?
The main comparisons do not depend on the scalarization. The one exception is Sign under an accuracy-first scalarization.
We re-ranked all explored candidates of both methods under four alternatives to the metric of Section 2.2 (line 149) and Appendix C (lines 696-699): reference latency halved (M1) and doubled (M2), accuracy first with latency as tie-break (M3), and the constrained formulation accuracy >= 0.99 with minimum latency (M4). Under the paper's metric, this re-ranking reproduces Table 1.
| Workload | M1 | M2 | M3 | M4 |
|---|---|---|---|---|
| ReLU | FHEvolve | FHEvolve | FHEvolve | FHEvolve |
| Softmax | FHEvolve | FHEvolve | FHEvolve | FHEvolve |
| Sign | FHEvolve | FHEvolve | Vanilla | no feasible program |
| Sigmoid | tie | tie | tie | tie |
| GeLU | tie | tie | tie | tie |
Sigmoid and GeLU tie within noise, as in Section 5.3 (lines 325-327). Under M3, Vanilla's best Sign programs reach 0.972 accuracy at about three times FHEvolve's latency. An accuracy-first scalarization favors slower programs, so it selects a different accuracy-latency trade-off. In the revised draft, we will add this table and analysis to Appendix C, next to the metric definition.
Question 3. How does FHEvolve behave when the optimal solution is not covered by the current strategy library? In particular, can the system discover or expand to a new strategy family without additional manually authored templates, or is the library intended to define the search space?
The library is not intended to define the search space. It filters the strategies the prompt offers to those within the FHE budget (Section 4, lines 221-230). Mutations edit the program directly, not the templates, so the model can write code outside the current strategy library.
Our evaluation has no workload whose optimal solution is not covered by the library. Our limitations (Section 7, line 483) state that the author-written seeds and the thirteen-entry library bound FHEvolve's autonomy.
To expand to a new strategy family without additional manually authored templates, the system can detect evolved programs that match no library entry and add them as new entries. The rule-based strategy classifier (Section 4, lines 241-244) can do this detection. In the revised draft, we will state in Section 4 that the library does not define the search space, and add library expansion as future work in Section 7.
The authors have provided useful additional experiments and clarifications. The analysis substantially addresses my concern about dependence on the optimization objective, and the random-input evaluations provide useful evidence beyond the fixed search vectors. The clarification that the strategy library guides generation rather than strictly defining the search space is also helpful. The additional tests support generalization on several activation workloads, although Softmax remains sensitive to the input.
Overall, the additional evidence strengthens the empirical evaluation and clarifies the remaining limitations. I will maintain my current rating with greater confidence.
Response to Reviewer bkv5
We thank the reviewer for the constructive questions. We ran two new experiments: an evaluation on random test inputs and a comparison under alternative scalarizations and a constrained formulation. Questions 2 and 3 also answer the two weaknesses.
Question 1. How do the main improvements generalize to unseen inputs? Since most FHERMA workloads are evaluated on the same fixed vectors used during search, do the authors have additional held-out evaluations or random test inputs for Softmax, ReLU, Sign, and the other workloads?
ReLU, Sign, Sigmoid, and GeLU generalize to unseen inputs. Softmax is more sensitive to the input vector, for both methods. As Section 2.2 (lines 146-148) states, only Eth-Fraud has a held-out set, and the FHERMA workloads ship one fixed vector each. We therefore evaluated the other workloads on random test inputs.
We scored each method's best program on random test inputs not used during search, with the workload's evaluator and the 1e-3 tolerance. For ReLU, Sign, Sigmoid, and GeLU, we drew one input vector uniformly over the range of the fixed vector. For Softmax, we drew 20 input vectors from a normal fitted to the fixed vector.
On the first four workloads, accuracy on random test inputs is within 0.15 points of accuracy on the fixed vector for both methods, because these programs approximate the function over the whole input range. Both Softmax programs subtract a constant taken from the fixed vector in place of the input maximum (FHEvolve 25.86, Vanilla 25.0). Accuracy on a random vector tracks how close its maximum is to this constant. In the revised draft, we will add this table to the appendix and refer to it from Section 2.2 (lines 146-148).