{"id":"d654e501-4eef-44b9-9128-48d84e7bc85e","arxiv_id":"2506.12883","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A technique called cut tracing records the rewrites of MC- and MD-reducing logic synthesis flows in an e-graph, and extracts an FHE circuit traded off between multiplicative depth and multiplicative complexity to lower homomorphic evaluation runtime.","lead":"Cut tracing is a new way to combine two logic-synthesis optimizers for fully homomorphic encryption (FHE) circuits, using an e-graph to record their intermediate rewrites and then extract a circuit balanced for both multiplicative depth and complexity. It reports up to a 40% runtime speedup on some benchmarks, but the gains shrink to 20% at best against the stronger baseline ordering, and several circuits come out slower.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The never-worse guarantee depends on extraction faithfully reproducing the baseline network, but the reported regressions suggest the traced e-graph plus egg's acyclicity handling can lose it; a trace-replay check would settle this.","rationale":"The reader's weakest_assumption zeroes in on the same point: the claim that the baseline network must be in the e-graph and hence extraction cannot do worse. My concern is more precise about the failure mode: it is not merely that the ILP 'bans e-nodes detected as part of cycles,' but that the paper does not demonstrate that the traced e-graph actually contains any representation of the final baseline network for the benchmarks that regress. The attribution to egg's acyclicity handling is plausible but it is an empirical hypothesis, not a verified conclusion; Section 4.3 states it as a belief ('We believe this issue is due to...'). The central claim of the paper is the runtime improvement, and the regressions are a direct counterexample to the stronger internal guarantee. The recommended verdict is CONDITIONAL, not REJECT, because: (1) the cut-tracing idea is sound and the paper is transparent about limitations; (2) the regressions could plausibly be fixed by an improved extraction algorithm; (3) the paper already reports a 10% geomean speedup over the MC-first baseline and positive results on several benchmarks. However, the paper should not be accepted as-is without the concrete verification because the current evaluation does not establish that the method's core guarantee holds, and the abstract's 'up to 40%' framing overstates the results relative to the best baseline ordering (20%). The concrete test I propose is a single, decisive experiment: functionally compare the extracted network against the baseline network for each regressing benchmark. Seeing that paper's own numbers stay put, I would only move the verdict to CONDITIONAL rather than UNCHANGED because the acknowledged cycle-handling bug is explicitly stated by the authors as 'future work' and the current paper cannot support the stronger claim of guaranteed non-regression.","tokens_in":9494,"tokens_out":1472,"duration_ms":15071,"concrete_test":"Instrument the implementation to record, for each benchmark, the exact final network produced by the baseline flow (after MC-first rewriting/resubstitution and ESOP balancing). Then, without running Algorithm 2, directly extract that recorded network from the traced e-graph using a faithful reconstruction path: (1) hash the recorded network's nodes into the e-graph; (2) run egg's ILP extraction (as in Algorithm 2) and check whether the extracted network is functionally equivalent to the baseline network on all 2^n input patterns (or via a SAT equivalence check). Repeat for bar, cavlc, ctrl, dsort, int2float, osort.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The paper's central theoretical claim (Section 3.2) is that cut tracing is at least as good as the original optimized flow, because the e-graph contains every cut replacement made by the greedy flow, including the final baseline network. This is load-bearing: if extraction always found the baseline's exact network, the measured cut-tracing results could never be worse, and the abstract's 40% improvement would be a pure upside claim. The empirical regressions in Table 1 (bar, cavlc, ctrl, dsort, int2float, osort) break this guarantee. The authors attribute this to egg's ILP formulation banning e-nodes detected as part of cycles (Section 4.3). That is plausible, but the paper does not verify the attribution. The claim that the baseline network 'must exist in the e-graph' is not enough: the guarantee requires that the extraction machinery can actually retrieve a representation of that exact network. If real cycles in the original network cause egg to ban e-nodes that appear in every representation of the baseline network, then the trace itself loses information, and the method's core promise fails. The paper explicitly acknowledges 'notwithstanding extraction limitations' but never isolates whether the issue is: (a) egg's particular ILP formulation banning cyclic e-nodes, (b) the greedy pre-extractor (md_global_greedy_dag) returning a suboptimal starting point, or (c) an actual gap in tracing (e.g., unrecorded cut roots or hashing collisions). Without isolating this, the empirical results cannot distinguish a fixable extraction bug from a structural limitation of cut tracing on cyclic networks, and the stronger claim of guaranteed non-regression remains unverified.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":9885,"tokens_out":2786,"duration_ms":32226,"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":[{"comment":"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.","section":"Section 3.2 and Section 4.3, Table 1"},{"comment":"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":"Abstract and Section 4.3, Table 1"},{"comment":"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":"Section 4.1 and Algorithm 2"},{"comment":"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.","section":"Section 4.2, Section 4.3, and Algorithm 2"}],"minor_comments":[{"comment":"The word \"compuation\" should be \"computation\".","section":"Section 2.3"},{"comment":"The phrase \"does not not exceed\" in the description of depth_bounded_ilp contains a double negative; it should read \"does not exceed\".","section":"Section 4.1"},{"comment":"The term \"acylicity\" should be \"acyclicity\".","section":"Section 4.3"},{"comment":"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":"Section 4.3, Table 1"},{"comment":"The conclusion refers to \"sort\" benchmarks, but the table lists bsort, isort, msort, and osort; please be specific about which benchmarks are meant.","section":"Section 5, Table 1"}],"recommendation":"major_revision","confidential_remarks":"The paper is a workshop-style extended abstract with a promising idea but an overclaimed abstract and an unverified guarantee. The main fixes are straightforward in principle: re-run the evaluation with the ESOP-first traced flow, report the trace-replay verification, and temper the claims to match the best-order comparison. I would also encourage the authors to release the implementation and trace files, since the current description of the recording hooks and extraction parameters would then be checkable by others."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nBut 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.\n\nI 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.","headline":"Genuinely new idea with honest conclusions, but the abstract oversells and the core 'never worse' guarantee is empirically broken and unverified.","tokens_in":10372,"tokens_out":2377,"would_cite":true,"duration_ms":21626,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Cut tracing stores discarded circuit rewrites in an e-graph and extracts a lower-runtime FHE circuit, with up to 40% measured improvement.","keywords":["fully homomorphic encryption","logic synthesis","e-graphs","cut tracing","multiplicative depth","multiplicative complexity","circuit optimization","equality saturation"],"falsifier":"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.","tokens_in":9244,"feed_emoji":"🔐","tokens_out":11426,"duration_ms":118138,"temperature":0.7,"pith_summary":"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.","feed_headline":"Stored optimizer choices cut FHE runtime by up to 40%","feed_subtitle":"Recording discarded circuit rewrites in an e-graph lets synthesis balance multiplicative depth and complexity.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the multiplicative-complexity reduction flow, including cut rewriting and resubstitution, whose intermediate cut choices cut tracing records.","marker":"[10]"},{"why":"Supplies the ESOP-balancing algorithm that reduces multiplicative depth, the second traced flow in the combined synthesis pipeline.","marker":"[7]"},{"why":"Provides the e-graph data structure and the ILP-based extraction machinery that cut tracing relies on for global cost minimization.","marker":"[11]"},{"why":"Motivates the $MD^2 \\times MC$ cost model used by extraction as an approximation of homomorphic evaluation runtime.","marker":"[4]"},{"why":"Provides the FHE evaluation library used to measure the reported runtime speedups.","marker":"[6]"},{"why":"Supplies the Boolean FHE benchmark circuits and the prior approach to optimizing homomorphic evaluation circuits that the paper builds on.","marker":"[8]"},{"why":"Provides the logic synthesis library implementing the cut rewriting, resubstitution, and balancing routines that are instrumented with tracing hooks.","marker":"[9]"},{"why":"Provides the greedy bottom-up DAG extraction routine that the paper modifies to prioritize multiplicative depth during extraction.","marker":"[1]"}],"fun_headline_variants":["E-graph cut tracing cuts FHE runtime up to 40%","Rejecting rewrites: e-graphs slash FHE runtime by 40%","Tracing discarded cuts optimizes FHE circuits for speed","Balancing depth and complexity: e-graphs cut FHE runtime 40%","Reusing rejected rewrites in e-graphs speeds FHE synthesis"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["E-graph cut tracing cuts FHE runtime up to 40%","Rejecting rewrites: e-graphs slash FHE runtime by 40%","Tracing discarded cuts optimizes FHE circuits for speed","Balancing depth and complexity: e-graphs cut FHE runtime 40%","Reusing rejected rewrites in e-graphs speeds FHE synthesis"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000193,"raw_usage":{"total_tokens":1365,"prompt_tokens":973,"completion_tokens":392,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":589,"completion_tokens_details":{"reasoning_tokens":292}},"tokens_in":589,"tokens_out":392,"duration_ms":4389,"temperature":1.0,"reasoning_tokens":292,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T00:35:34.868243+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the ESOP-balancing algorithm that reduces multiplicative depth, the second traced flow in the combined synthesis pipeline."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Motivates the $MD^2 \\times MC$ cost model used by extraction as an approximation of homomorphic evaluation runtime."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the FHE evaluation library used to measure the reported runtime speedups."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the greedy bottom-up DAG extraction routine that the paper modifies to prioritize multiplicative depth during extraction."}],"review_version":1}