Cut Tracing with E-Graphs for Boolean FHE Circuit Synthesis

Giovanni De Micheli; Julien de Castelnau; Mingfei Yu

REVIEW 4 major objections 5 minor 12 references

Cut Tracing with E-Graphs for Boolean FHE Circuit Synthesis

T0 review · 4 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Cut tracing stores discarded circuit rewrites in an e-graph and extracts a lower-runtime FHE circuit, with up to 40% measured improvement.

desk verdict Genuinely new idea with honest conclusions, but the abstract oversells and the core 'never worse' guarantee is empirically broken and unverified. read the letter →

arxiv 2506.12883 v1 pith:7K2XYJKU submitted 2025-06-15 cs.CR

Julien de Castelnau , Mingfei Yu , Giovanni De Micheli This is my paper · ORCID

classification cs.CR

keywords fullyhomomorphicencryptionlogicsynthesise-graphscuttracingmultiplicativedepthcomplexitycircuitoptimizationequalitysaturation

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proposes cut tracing, a technique that prevents greedy circuit optimizers for fully homomorphic encryption (FHE) from throwing away the designs they reject. Whenever an optimizer replaces a cut of the circuit with a better one, the original and replacement are recorded as equivalent in an e-graph, so all local design choices survive until a final global extraction. The paper claims this combines a multiplicative-complexity (MC) reduction flow with a multiplicative-depth (MD) balancing flow into one optimization whose goal is overall homomorphic evaluation runtime rather than either metric alone. Running this flow on Boolean FHE benchmark circuits yields up to 40% lower evaluation runtime and a 10% average speedup over the baseline flow. The paper also claims the baseline circuit always exists in the e-graph, so results should never be worse, but its current extraction machinery regresses on several benchmarks when the e-graph contains cycles.

What carries the argument

The load-bearing mechanism is the e-graph with cut tracing. An e-graph is a compact data structure that groups semantically equivalent subcircuits into equivalence classes; cut tracing adds to it, for every cut replacement made by a cut-based optimizer, the equivalence between the original cut root and the replacement root. The traced equivalences accumulate across sequential optimization passes, so the e-graph holds a pool of local alternatives from both the multiplicative-complexity flow (cut rewriting and resubstitution) and the multiplicative-depth flow (ESOP, or exclusive-sum-of-products, balancing). Extraction then minimizes homomorphic evaluation cost, computed as $MD^2 \times MC$, using a depth-prioritized greedy extraction followed by ILP sweeps over a bounded depth range.

What would settle it

Run the traced MC-first flow on the benchmark ctrl and inspect the extracted circuit's MD and MC: the paper reports a regression even though the baseline network should be present in the e-graph, so a cycle-aware extraction that enforces topological ordering in the ILP must return a circuit no worse than the baseline unless the method's in-principle guarantee is false.

Watch

Extended reading notes

Core claim

The central discovery is that an optimizer's rejected cuts are a reusable design space, not a cost: by uniting the root of each replacement cut with the root of the original cut in the same e-class, cut tracing records every local decision without destroying any alternative. After the MC and MD flows run to convergence, a depth-bounded ILP extraction sweeps candidate multiplicative depths and selects the circuit minimizing the $MD^2 \times MC$ cost model, which approximates homomorphic evaluation time. The paper reports best-case 40% and average-case 10% runtime improvements, and shows cases where the traced e-graph recovers a better design than either ordering of the baseline flows. It further argues that, notwithstanding extraction limitations, the traced e-graph must contain at least the baseline flow's final network and therefore should never produce a worse result; Section 4.3 shows this guarantee currently fails on several benchmarks, which the authors attribute to the ILP formulation banning e-nodes that participate in cycles.

Load-bearing premise

The load-bearing premise is that the e-graph always contains the baseline flow's final circuit, because every cut the greedy optimizer visits is traced; the paper's own results show this premise fails when the extraction library bans e-nodes that sit in cycles.

Editorial extensions

If this is right

A synthesis flow can optimize FHE circuits for end-to-end evaluation time instead of for a single proxy metric, because the traced e-graph retains both MC- and MD-oriented designs.
A 40% best-case and 10% average reduction in homomorphic evaluation runtime would make FHE-based computation cheaper by that factor on the benchmark class without altering the encryption scheme.
Since tracing only records choices the optimizer already made, it can be layered on existing cut-based flows without changing their convergence behavior, making it an incremental addition to logic synthesis practice.
For cycle-free e-graphs the extracted circuit should match or beat the baseline flow's output, so cycle-aware extraction is a prerequisite for realizing the method's in-principle guarantee.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The same trace-and-extract pattern could be attached to any cut-based logic optimizer, since the only requirements are a cut enumeration procedure and an equivalence relation between old and new cuts.
A natural testable extension is to change the recording policy: the paper records only the best cut for MC rewriting and resubstitution but all cuts for ESOP balancing, so recording a small frontier of near-best cuts could enlarge the design space without bloating the e-graph.
The reported regressions suggest replacing the extraction library's cycle-banning acyclicity constraint with explicit topological-ordering constraints in the ILP; if that restores at-least-baseline extraction on the failing benchmarks, the method's in-principle guarantee would be recovered.
The $MD^2 \times MC$ cost model is itself an approximation, so a bootstrapping-aware cost that accounts for noise growth per multiplication level could change which traced designs are optimal.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Cut tracing is a genuinely new idea: instead of saturating an e-graph with rewrite rules, you record the cut replacements a greedy optimizer actually visits, then extract under a joint MD/MC cost model. That's a smart workaround for equality saturation's scalability problems on FHE circuits, and it lets you combine different optimizers without destroying alternatives. The paper also does something right that's rare: it evaluates with HELib, so the runtime numbers are independent of the MD^2*MC cost model used for extraction. The authors are honest in the conclusion, admitting the 40% is vs the MC-first baseline and that against the best ordering it's a 20% best-case and tied geomean.

But the abstract still leads with 'up to 40% improvement,' which is the MC-first comparison, not the best baseline. And the deeper problem is the 'never worse' guarantee. Section 3.2 argues the baseline network must exist in the e-graph, so extraction can't do worse. Table 1 shows six benchmarks—bar, cavlc, ctrl, dsort, int2float, osort—do worse. The authors blame egg's ILP acyclicity handling banning e-nodes in cycles. That may be right, but they don't verify it. A trace-replay test—could the extractor faithfully retrieve the exact baseline network from the traced e-graph?—would settle whether this is a fixable bug or a structural limit of cut tracing on cyclic circuits. Without that, the central claim isn't supported. Also, no code or traces are released, so the numbers aren't independently checkable.

I don't think the idea is bad. It's plausible and likely fixable. But the paper as written overclaims and under-verifies. Who's this for? Anyone working on logic synthesis for FHE, or e-graph extraction. It deserves a serious referee because the technique is new and the direction is useful. The reviewer should ask for the cycle fix, a trace-replay check, and code release. I'd send it to peer review with the expectation of major revision.

Referee Report

4 major / 5 minor

Summary. The paper proposes "cut tracing," a technique that augments existing cut-based logic synthesis flows for Boolean FHE circuits by recording the equivalence between each original cut and its replacement in an e-graph as the flow runs. After the flow terminates, an extraction step minimizes a cost model of homomorphic evaluation runtime, MD^2 * MC, over the traced e-graph. The authors apply cut tracing to a flow that first performs MC-oriented cut rewriting and resubstitution and then ESOP balancing, and they report MD, MC, and HELib evaluation runtimes on a suite of benchmarks. They claim up to a 40% best-case speedup and a 10% geomean speedup over the MC-first baseline, while acknowledging that against the best of the two baseline orderings the geomean speedup is 1.00 and the best case is 20%. The paper also states a formal guarantee in Section 3.2 that, notwithstanding extraction limitations, cut tracing should produce results at least as good as the original sequence of optimizations, because the baseline network must exist in the e-graph.

Significance. If the never-worse guarantee were made rigorous and the reported speedups were shown to be robust, cut tracing would be a useful contribution to logic synthesis for FHE: it offers a scalable middle ground between destructive greedy rewriting and full equality saturation, and it is the first technique in this line of work to explicitly optimize a joint MD/MC model of HE runtime. The paper is honest about its current limitations, including the missing ESOP-first traced flow and the unexplained regressions relative to the baseline. However, the central empirical claim is only partially supported: the headline 40% figure compares against a weaker baseline, and the geomean comparison against the best baseline ordering is neutral. The theoretical guarantee is also not yet substantiated because the extraction machinery can fail to recover the baseline network, as the paper's own Table 1 shows. The technique is promising, but the current evidence is insufficient for acceptance as is.

major comments (4)

[Section 3.2 and Section 4.3, Table 1] The paper's core guarantee that cut tracing is never worse than the original flow is contradicted by the empirical results: bar, cavlc, ctrl, dsort, int2float, and osort are all worse than the baseline in Table 1, and several are worse in both MD and MC. The authors attribute this to egg's ILP formulation banning e-nodes involved in cycles, but no verification is provided. Please add a direct trace-replay check: after tracing, verify that the exact baseline network (the network produced by the original sequence of optimizations) is present in the e-graph and can be extracted by an unconstrained or cycle-aware extractor. Without this check, the paper leaves open whether the failure is in tracing (missing equivalences), in the ILP cycle handling, or in the greedy pre-extractor, and the Section 3.2 guarantee remains unsupported.
[Abstract and Section 4.3, Table 1] The abstract's "up to a 40% improvement" is reported against the MC-first baseline only, not against the best ordering of the two baseline flows. Table 1 shows that the geomean speedup over the best-order baseline is exactly 1.00, and the conclusion concedes the 20% best-case figure in that comparison. The abstract and conclusion should be rewritten to clearly distinguish these two comparisons, and the claims should be stated as best-case rather than as an average improvement; otherwise readers will reasonably infer a stronger result than the data support.
[Section 4.1 and Algorithm 2] The evaluation is incomplete for the stated purpose of combining two flows: cut tracing is only applied to the MC-first ordering, because the authors report "issues in our implementation" for the ESOP-first ordering. Since the choice of ordering strongly affects the baseline results, the paper cannot yet show that cut tracing generically combines the two flows. Please either provide results for the ESOP-first traced flow or explicitly restrict the paper's claim to the MC-first flow and describe what remains for future work.
[Section 4.2, Section 4.3, and Algorithm 2] The extraction procedure uses several free parameters that are not justified by sensitivity analysis: the number of ILP iterations k=2, the cut-recording policy (best cut for rewriting/resubstitution vs. all cuts for ESOP balancing), and the ILP solver timeout of 10 minutes. The bsort discussion suggests that a depth bound of 42 was attempted but timed out and the solution was only found with a relaxed bound of 43, which is not clearly captured by Algorithm 2's loop over MD_best+i for i=0..k. Please report how the results would change with different k values and clarify the exact depth bounds used for each benchmark; otherwise the extraction results may be artifacts of these choices.

minor comments (5)

[Section 2.3] The word "compuation" should be "computation".
[Section 4.1] The phrase "does not not exceed" in the description of depth_bounded_ilp contains a double negative; it should read "does not exceed".
[Section 4.3] The term "acylicity" should be "acyclicity".
[Section 4.3, Table 1] The text refers to bsort "in blue," but the table as typeset does not indicate blue highlighting; please add the highlighting or remove the reference.
[Section 5, Table 1] The conclusion refers to "sort" benchmarks, but the table lists bsort, isort, msort, and osort; please be specific about which benchmarks are meant.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the measured speedups and the monotonicity guarantee are not constructed from the quantities they claim to predict.

full rationale

The paper's central claim is empirical: cut tracing records cut-replacement equivalences produced by existing MC/MD flows into an e-graph, and extraction under an MD^2*MC cost model yields lower HELib evaluation runtime. The evaluation runtime is measured with HELib, an external library, so the reported speedups are not definitionally forced by the extraction cost model. The Section 3.2 guarantee that results are at least as good as the baseline is conditional on the baseline network being present in the e-graph and on the extractor being able to retrieve it; this is a monotonicity argument, not a circular one, and the paper explicitly acknowledges regressions due to extraction limitations in Section 4.3. The choices of recording policy and ILP iteration count are heuristic tuning on the same benchmarks, which is an overfitting/correctness concern rather than a reduction of a prediction to a fitted input. Self-citations to [7], [9], and [10] identify the baseline flows and the implementation library; those baselines are measured and externally published, not imported as an unverified premise. No equation or fitted parameter is defined in terms of the reported runtime, so no derivation step reduces to its own inputs.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The central claim rests on the MD^2*MC cost model and on the e-graph extraction guaranteeing no worse than the baseline. The second premise is empirically broken, so the method's core promise is not delivered in the current implementation.

free parameters (3)

ILP iteration count k = 2
Section 4.2: 'we fix the number of iterations k to 2, observing that the best HE cost design is usually found close to the optimal depth.' Tuned by hand to the benchmark suite.
Cut recording policy = best cut for MC flows, all cuts for ESOP balancing
Section 4.1: 'Based on empirical observations, for cut rewriting & resubstitution, we choose to record only the best cut; for ESOP balancing, we record all cuts.' Chosen by hand.
ILP solver timeout = 10 minutes
Section 4.2: 'We use a timeout of 10 minutes for the ILP solver.' Affects whether the optimal solution is found.

assumptions (4)

domain assumption HE cost is modeled as MD^2 * MC
Section 4.1: 'Our extraction method targets HE cost, an approximation of the runtime of FHE circuits calculated from MD and MC as MD^2 * MC, based on analyses of the cost of FHE runtime in the literature [4]'.
domain assumption The e-graph contains the baseline flow's best network
Section 3.2: 'its results must be at least as good as the network produced by the original sequence of optimizations, since this form must exist in the e-graph.' Empirically violated in Section 4.3 due to acyclic constraint handling.
standard math Underlying cut rewriting, resubstitution, and ESOP balancing implementations are correct
The paper builds on mockturtle implementations from [7], [10]; no independent verification of these tools is provided.
domain assumption Benchmarks in [8] are representative of FHE workloads
Section 4.2: benchmarks are sourced from [8]; no diversity analysis.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Cut Tracing with E-Graphs for Boolean FHE Circuit Synthesis." pith.science (2026). https://pith.science/paper/7K2XYJKU

@misc{pith2026250612883,
  author       = {Pith},
  title        = {Pith review of: Cut Tracing with E-Graphs for Boolean FHE Circuit Synthesis},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7K2XYJKU}},
  note         = {Machine review of arXiv:2506.12883}
}

read the original abstract

Fully Homomorphic Encryption (FHE) is a promising privacy-preserving technology enabling secure computation over encrypted data. A major limitation of current FHE schemes is their high runtime overhead. As a result, automatic optimization of circuits describing FHE computation has garnered significant attention in the logic synthesis community. Existing works primarily target the multiplicative depth (MD) and multiplicative complexity (MC) of FHE circuits, corresponding to the total number of multiplications and maximum number of multiplications in a path from primary input to output, respectively. In many FHE schemes, these metrics are the primary contributors to the homomorphic evaluation runtime of a circuit. However, oftentimes they are opposed: reducing either depth or complexity may result in an increase in the other. To our knowledge, existing works have yet to optimize FHE circuits for overall runtime, only considering one metric at a time and thus making significant tradeoffs. In this paper, we use e-graphs to augment existing flows that individually optimize MC and MD, in a technique called cut tracing. We show how cut tracing can effectively combine two state-of-the-art MC and MD reduction flows and balance their weaknesses to minimize runtime. Our preliminary results demonstrate that cut tracing yields up to a 40% improvement in homomorphic evaluation runtime when applied to these two flows.

Figures

Figures reproduced from arXiv: 2506.12883 by the authors.

**Figure 1.** The expression (𝑥1 × 𝑥2) × (𝑥1 + 𝑥2) as an FHE circuit. 𝑥1 and 𝑥2 are ciphertexts and ×, + correspond to homomorphic multiply and add, respectively. The limiting factor in most FHE schemes is the runtime overhead of multiplication, with addition being comparatively cheap. Therefore, when considering an FHE circuit, the total number of multiplications, the MC, is a major performance indicator. However, multiplicati… view at source ↗

**Figure 2.** XAGs representing a full adder circuit, along with the e-graph after 2 iterations in egg using Boolean laws as rewrite rules. Dashed edges represent complement i.e. a NOT gate, which is considered to be free in terms of FHE as it can be implemented with XOR. Algorithm 1 Structure of cut-based optimization Require: Logic network 𝑁 = (𝑉 , 𝐸), optimization function 𝑂𝑃𝑇 (𝐶), cut identifying function 𝐶𝑈𝑇𝑆 (𝑛), gain func… view at source ↗

**Figure 3.** A visualization of cut tracing. The top shows a cut of a logic network being replaced, while the bottom shows the operation being traced in the e-graph by adding the new cut root to the same e-class. The purple region denotes sharing between the two cuts. and ESOP balancing completely circumvent this issue. They do not use structural rewriting at all, but rather identify a replacement cut implementing the same Boole… view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: MC + MD optimization flow incorporating cut tracing. all cuts, even those that do not improve the depth locally, as we found that cut tracing can take advantage of these options. After the flow completes and the e-graph is filled with traced candidates, it is extracted…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 8 canonical work pages

[1]

[n. d.]. GitHub - egraphs-good/extraction-gym: benchmarking e-graph extraction — github.com.https://github.com/egraphs-good/extraction- gym. [Accessed 16-04-2025]

work page 2025
[2]

Sergiu Carpov, Pascal Aubry, and Renaud Sirdey. 2017. A multi-start heuristic for multiplicative depth minimization of boolean circuits. Cryptology ePrint Archive, Paper 2017/483. https://eprint.iacr.org/ 2017/483

work page 2017
[3]

Chen Chen, Guangyu Hu, Dongsheng Zuo, Cunxi Yu, Yuzhe Ma, and Hongce Zhang. 2024. E-Syn: E-Graph Rewriting with Technology- Aware Cost Functions for Logic Synthesis. In Proceedings of the 61st ACM/IEEE Design Automation Conference (San Francisco, CA, USA) (DAC ’24). Association for Computing Machinery, New York, NY, USA, Article 124, 6 pages. doi: 10.1145...

work page arXiv 2024
[4]

Anamaria Costache and Nigel P. Smart. 2015. Which Ring Based Somewhat Homomorphic Encryption Scheme is Best? Cryptology ePrint Archive, Paper 2015/889. https://eprint.iacr.org/2015/889

work page 2015
[5]

Charles Gouert, Dimitris Mouris, and Nektarios Georgios Tsoutsos

work page
[6]

Shai Halevi and Victor Shoup. 2020. Design and implementation of HElib: a homomorphic encryption library. Cryptology ePrint Archive, Paper 2020/1481. https://eprint.iacr.org/2020/1481

work page 2020
[7]

Thomas Häner and Mathias Soeken. 2022. Lowering the T-depth of Quantum Circuits via Logic Network Optimization. ACM Transactions on Quantum Computing 3, 2, Article 6 (March 2022), 15 pages. doi:10. 1145/3501334

work page 2022
[8]

DongKwon Lee, Woosuk Lee, Hakjoo Oh, and Kwangkeun Yi. 2020. Optimizing homomorphic evaluation circuits by program synthesis and term rewriting. InProceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation (London, UK) (PLDI 2020). Association for Computing Machinery, New York, NY, USA, 503–518. doi: 10.1145/3385412.3385996

arXiv 2020

Show all 12 references

[9]

Mathias Soeken, Heinz Riener, Winston Haaswijk, and Giovanni De Micheli. 2018. The EPFL Logic Synthesis Libraries. CoRR abs/1805.05121 (2018). arXiv:1805.05121 http://arxiv.org/abs/1805. 05121

2018 arXiv
[10]

Eleonora Testa, Mathias Soeken, Heinz Riener, Luca Amaru, and Gio- vanni De Micheli. 2020. A Logic Synthesis Toolbox for Reducing the Multiplicative Complexity in Logic Networks. In 2020 Design, Au- tomation & Test in Europe Conference & Exhibition (DATE) . 568–573. doi:10.239...

2020
[11]

Max Willsey, Chandrakana Nandi, Yisu Remy Wang, Oliver Flatt, Zachary Tatlock, and Pavel Panchekha. 2021. egg: Fast and exten- sible equality saturation. Proc. ACM Program. Lang. 5, POPL, Article 23 (Jan. 2021), 29 pages. doi:10.1145/3434304

2021 doi
[2023]

Proceedings on Privacy Enhancing Tech- nologies 2023, 3 (July 2023), 154–172

SoK: New Insights into Fully Homomorphic Encryption Libraries via Standardized Benchmarks. Proceedings on Privacy Enhancing Tech- nologies 2023, 3 (July 2023), 154–172. doi:10.56553/popets-2023-0075

2023 doi

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

[n. d.]. GitHub - egraphs-good/extraction-gym: benchmarking e-graph extraction — github.com.https://github.com/egraphs-good/extraction- gym. [Accessed 16-04-2025]

work page 2025

[2] [2]

Sergiu Carpov, Pascal Aubry, and Renaud Sirdey. 2017. A multi-start heuristic for multiplicative depth minimization of boolean circuits. Cryptology ePrint Archive, Paper 2017/483. https://eprint.iacr.org/ 2017/483

work page 2017

[3] [3]

Chen Chen, Guangyu Hu, Dongsheng Zuo, Cunxi Yu, Yuzhe Ma, and Hongce Zhang. 2024. E-Syn: E-Graph Rewriting with Technology- Aware Cost Functions for Logic Synthesis. In Proceedings of the 61st ACM/IEEE Design Automation Conference (San Francisco, CA, USA) (DAC ’24). Association for Computing Machinery, New York, NY, USA, Article 124, 6 pages. doi: 10.1145...

work page arXiv 2024

[4] [4]

Anamaria Costache and Nigel P. Smart. 2015. Which Ring Based Somewhat Homomorphic Encryption Scheme is Best? Cryptology ePrint Archive, Paper 2015/889. https://eprint.iacr.org/2015/889

work page 2015

[5] [5]

Charles Gouert, Dimitris Mouris, and Nektarios Georgios Tsoutsos

work page

[6] [6]

Shai Halevi and Victor Shoup. 2020. Design and implementation of HElib: a homomorphic encryption library. Cryptology ePrint Archive, Paper 2020/1481. https://eprint.iacr.org/2020/1481

work page 2020

[7] [7]

Thomas Häner and Mathias Soeken. 2022. Lowering the T-depth of Quantum Circuits via Logic Network Optimization. ACM Transactions on Quantum Computing 3, 2, Article 6 (March 2022), 15 pages. doi:10. 1145/3501334

work page 2022

[8] [8]

DongKwon Lee, Woosuk Lee, Hakjoo Oh, and Kwangkeun Yi. 2020. Optimizing homomorphic evaluation circuits by program synthesis and term rewriting. InProceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation (London, UK) (PLDI 2020). Association for Computing Machinery, New York, NY, USA, 503–518. doi: 10.1145/3385412.3385996

arXiv 2020