{"id":"d6f79975-6c74-4fe4-8a87-09c271f46b37","arxiv_id":"2507.07972","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"EinHops implements einsum notation on RNS-CKKS by decomposing every expression into an explicit sequence of permutations, broadcasts, SIMD multiplications, and rotate-and-sum reductions.","lead":"EinHops is an open-source software system that lets developers run tensor math like matrix multiplication on encrypted data using the familiar einsum notation. It maps einsum expressions to a fixed sequence of homomorphic encryption operations, making the packing strategy explicit instead of hiding it inside a compiler.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The claim that EinHops handles any valid einsum is not supported: repeated-index expressions such as 'ii->i' (diagonal) and 'ii->' (trace) are valid einsum but cannot be produced by the broadcast-multiply-reduce decomposition, and no such syntax restriction is stated.","rationale":"The reader's identified weakest assumption, the single-ciphertext size limit, is real and is explicitly acknowledged in Section 5.3.1. That limitation restricts the scale of supported tensors but does not falsify the correctness of the decomposition for inputs that fit. The more serious gap is the unacknowledged syntax fragment: valid einsum expressions with repeated labels inside one operand, such as 'ii->i' and 'ii->', require a diagonal-selection operation that is not part of the broadcast-multiply-reduce decomposition described in Sections 3 and 4. All 15 evaluated expressions use unique labels per operand, and the limitation section omits this restriction, so the paper's generality claim is not established as stated. This is a scope/correctness issue in the central claim rather than a performance issue, and it is directly testable with the released code. If the test shows these expressions fail, the paper still makes a solid contribution for a well-defined fragment, but accepting it as written would require a scope statement and, ideally, either an implementation or an explicit exclusion of repeated-label expressions. Hence the verdict should be conditional rather than unconditional acceptance. I do not see a deeper mathematical flaw in the described pipeline for the fragment it actually implements, and the open-source code plus slot-level debugging backend are significant supporting evidence.","tokens_in":20437,"tokens_out":9196,"duration_ms":117319,"concrete_test":"Run the open-source EinHops repository and evaluate einsum('ii->i', x) and einsum('ii->', x) with a CKKS-encrypted square matrix x of unpadded size, e.g., 8x8 and 128x128, using both the PyTorch cleartext backend and the desilo-fhe backend with the same padding and key setup as Section 6. If the library raises 'not supported', returns a shape mismatch, or decrypts to anything other than the diagonal or trace of x, then the paper must qualify 'any valid einsum' to the unique-label fragment; if it succeeds, the concern is refuted and only the acknowledged single-ciphertext limitation remains.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The paper's central claim is that the decomposition in Sections 3.1-3.3 and the FHE implementation in Sections 4.1-4.3 cover arbitrary valid einsum expressions. The described pipeline is expand/broadcast, element-wise multiply, rotate-and-sum reduction. This pipeline is well-defined only when each input label appears at most once per operand; expansion creates singleton dimensions, broadcasting duplicates data, multiplication combines aligned operands, and reduction sums over dimensions shared across operands. However, standard einsum also permits a label repeated within a single operand, which denotes a diagonal: 'ii->i' extracts diag(X), 'ii->' computes tr(X), and 'ijik->jk' traces over the repeated i. These are valid PyTorch and NumPy einsum expressions, yet they cannot be obtained by the three-step decomposition because the needed operation is selection of diagonal positions, not duplication or reduction of all entries. The paper nowhere states this restriction: Section 5.3 lists only single-ciphertext, bootstrap placement, permutation strategy, and jit limitations, while the abstract and introduction claim the approach is general. Therefore the central claim is overstated unless the supported einsum fragment is explicitly defined and the repeated-label case is either implemented (e.g., by a diagonal mask) or excluded.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"EinHops is a system that maps einsum tensor expressions onto RNS-CKKS homomorphic operations. The authors decompose an einsum expression into a fixed pipeline: dimension expansion and broadcasting, element-wise SIMD multiplication, and rotate-and-sum reductions over contraction dimensions. They implement this decomposition in about 1,000 lines of Python on top of the Liberate.FHE backend, evaluate it on 15 tensor operations plus an attention score computation, and report CPU/GPU runtimes and memory usage. The central claim is that this decomposition makes encrypted tensor operations simple, general, and interpretable while keeping packing decisions explicit.","tokens_in":20691,"tokens_out":9297,"duration_ms":112951,"significance":"If the scope is stated accurately, EinHops is a useful and credible systems contribution. It identifies a clean structural correspondence between einsum and FHE slot operations, implements it end-to-end, and ships open-source code. The evaluation against PyTorch's einsum is an external benchmark rather than a circular self-comparison, and the l2 discrepancies around 1e-5 are consistent with CKKS approximation error. The main limitation of the paper is that the advertised generality is broader than the actually supported einsum fragment: repeated-label expressions such as 'ii->i' are valid einsum but are not covered by the broadcast-multiply-reduce decomposition, and no syntax restriction is stated. The system's transparency and minimalism are genuine strengths, but the scope must be corrected before the central claim can be accepted as stated.","major_comments":[{"comment":"The paper's central claim that EinHops handles general einsum expressions is overstated because the described expand/broadcast/multiply/reduce pipeline does not cover repeated-index expressions. In standard einsum, 'ii->i' extracts the diagonal, 'ii->' computes the trace, and 'ijik->jk' traces over the repeated i. These operations are valid in PyTorch and NumPy, but they cannot be produced by the three-step decomposition: the repeated label denotes selection of diagonal positions rather than duplication followed by reduction. Section 5.3 lists only limitations related to single ciphertexts, bootstrap placement, permutations, and JIT support, with no restriction on repeated labels. The authors should either implement repeated-label support (e.g., via a diagonal mask or a pre-permutation) or explicitly restrict the claims to expressions in which each label appears at most once per operand, and state that restriction in the abstract and introduction.","section":"§3.1-§3.3, §4.1-§4.3, §5.3"}],"minor_comments":[{"comment":"The text says all results are averaged over 10 runs with a small standard deviation, but no variance or confidence intervals are reported; adding standard deviations or error bars to Table 1 would make the runtime claims more reproducible.","section":"§6, Table 1"},{"comment":"The phrase 'anop' appears to be a typo for 'no-op' (also in the same paragraph); please fix the wording.","section":"§4.1.2"},{"comment":"The single-ciphertext restriction (product of all input dimensions must fit in N/2 slots) is acknowledged in the limitations section, but the abstract and introduction should carry this caveat, since the current wording says the approach is 'general' and supports 'arbitrary' tensor operations without mentioning this bound.","section":"§5.3.1"},{"comment":"The paper motivates the work by asking how many multiplicative levels, rotations, and keys an operation consumes, but the evaluation reports only runtime and memory; adding columns for level consumption and rotation count per operation would directly support the paper's stated design goals.","section":"§6, Table 1"}],"recommendation":"major_revision","confidential_remarks":"The paper is likely acceptable after revision. The key issue is scope: the authors need to either support repeated-index einsum expressions or clearly restrict the supported fragment and adjust the abstract and introduction accordingly. The evaluation is solid within the tested fragment, and the open-source release is a positive feature. I would ask the authors to confirm whether their code silently rejects repeated-label expressions or produces incorrect results, since the paper currently does not document this behavior."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a genuinely useful systems paper—the first to make einsum the front-end for FHE tensor operations, with a transparent decomposition into BSGS permutations, rotate-and-sum broadcasts/reductions, and SIMD multiplications. The code is open-source, the evaluation is against PyTorch einsum, and the reported l2 discrepancies around 1e-5 are believable. I would send this to review, but the generality claim needs to be scoped down.\n\nWhat is actually new is the framing. Every primitive—BSGS, rotate-and-sum, SIMD multiply—is known, but mapping einsum syntax to an explicit FHE slot-layout plan is a clean contribution. The paper is careful about when an expansion is a no-op (outer dimensions) versus a real permutation (inner dimensions), and it justifies placing contraction dimensions outermost so reductions land in contiguous slots. The 15-operation table, including a 5-D contraction and attention scores, shows the pipeline working end to end. The system is deliberately small and readable, which helps as a baseline.\n\nSoft spots, in order of importance. First, the repeated-label gap. The decomposition as described only handles expressions where each label appears once per operand. Standard einsum also permits repeated labels within an operand, i.e. diagonal extraction ('ii->i') and trace ('ii->'). Those are not reachable by broadcast-multiply-reduce, and the paper nowhere states this restriction; Section 5.3 lists other limitations but not this one. Since the abstract claims generality, this is an overclaim. It is fixable—implement a diagonal mask or explicitly restrict the grammar—but as written the support is narrower than claimed. Second, the single-ciphertext constraint is acknowledged, but it limits the approach to small tensors; that is an acceptable scope, just not 'arbitrary'. Third, the evaluation does not report level consumption or noise growth per operation, which are the costs FHE users actually care about. The l2 error is good, but there are no error bars and only a passing mention of standard deviation.\n\nNone of this is fatal. The paper does what it claims for a substantial fragment of einsum, it is clearly written, and the transparency goal is met. The audience is FHE systems researchers and anyone needing a transparent packing baseline. It deserves a serious referee. My recommendation: send it out, and ask the authors to state the supported einsum fragment precisely and report the missing cost metrics.","headline":"Brings einsum to RNS-CKKS as a transparent packing language, but the generality claim needs to be scoped down to the fragment actually implemented.","tokens_in":21225,"tokens_out":3858,"would_cite":true,"duration_ms":38109,"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":"Einsum notation gives encrypted tensor operations an explicit three-step pipeline.","keywords":["einsum notation","RNS-CKKS","fully homomorphic encryption","tensor operations","SIMD packing","rotation-and-sum","baby-step giant-step","privacy-preserving machine learning"],"falsifier":"Take a supported einsum expression whose total input sizes fit within the $N/2$ slots, decrypt the intermediate ciphertexts after the broadcast, multiplication, and reduction stages, and compare every slot against the layout predicted by the paper's padding and slot-spacing rules; any mismatch shows the fixed pipeline is incorrect. To test the generality boundary, repeat with an expression whose total input dimension product exceeds $N/2$ and observe whether the system fails, as the stated limitation predicts.","tokens_in":20236,"feed_emoji":"🔐","tokens_out":13294,"duration_ms":137522,"temperature":0.7,"pith_summary":"Einsum notation, the compact \"ij,jk->ik\" style of expressing tensor operations, can serve as a transparent programming model for encrypted computation under the RNS-CKKS fully homomorphic encryption scheme. The paper argues that any valid einsum expression decomposes into a fixed sequence of FHE-friendly steps: aligning and broadcasting operands to a common slot layout, element-wise SIMD multiplication, and reducing along the contracted dimensions using rotations and additions. The authors implement this idea in EinHops, a minimal system that executes these steps with explicit slot-level operations and leaves the packing strategy visible to the programmer. If the argument is correct, developers can write encrypted tensor programs with a familiar notation and reason directly about how data is laid out in ciphertext slots, instead of relying on opaque compiler abstractions. The approach is currently limited to tensors whose combined dimensions fit in a single encrypted vector.","feed_headline":"Einsum notation turns encrypted tensor math into three explicit steps","feed_subtitle":"EinHops factors any einsum expression into permutations, SIMD multiplication, and rotate-and-sum reductions with the packing kept visible.","key_machinery":"The carrying mechanism is a mapping from einsum dimension labels to a fixed slot-layout plan. The plan has three reusable FHE primitives: a permutation step implemented as a baby-step giant-step (BSGS) linear transformation, which rearranges ciphertext slots using a number of rotations that grows roughly with the square root of the vector length; a broadcasting step implemented by logarithmic rotate-and-sum, which replicates values across a new dimension; and a reduction step implemented by the same logarithmic rotate-and-sum, which sums along a contraction dimension. Padding every dimension to a power of two is what makes the broadcast and reduction counts logarithmic, and placing contraction dimensions outermost is what leaves the final sums in contiguous slots without a trailing permutation.","core_discovery":"The central claim is a structural equivalence: an einsum expression is a plan for a fixed sequence of RNS-CKKS operations, not a black-box tensor call. To execute \"ij,jk->ik\", EinHops parses the dimension labels and chooses a broadcast shape that puts the contraction dimension outermost and the output dimensions innermost; it then permutes each operand into that shape with a baby-step giant-step matrix-vector product, broadcasts across the new dimensions with a logarithmic rotate-and-sum, multiplies element-wise, and reduces the contraction dimension with another logarithmic rotate-and-sum. A final mask zeros unused slots. Because the equation itself records the layout, the system is eager, interpretable, and works uniformly for transposes, sums, matrix products, batched contractions, and higher-dimensional contractions.","pith_inferences":["The paper leaves implicit that permutation, not multiplication or reduction, dominates the cost of many expressions; improving the permutation primitive would therefore improve the whole pipeline.","A natural next step it leaves open is lifting the single-ciphertext restriction; if rotations across multiple ciphertexts are defined consistently, the same broadcast-multiply-reduce pipeline could scale beyond the $N/2$ slot limit.","Because each einsum call produces an explicit plan, repeated calls could be compiled rather than eagerly executed, allowing shared permutations and rotations to be hoisted across expressions.","The same dimension-label-to-slot-plan mapping should transfer to other SIMD-capable encryption schemes, such as integer-arithmetic schemes, since their primitives also include vector addition, multiplication, and rotation."],"forward_implications":["A developer can express any supported encrypted tensor operation as an einsum string and receive an explicit plan of slot permutations, broadcasts, multiplications, and reductions, making the data layout a visible part of the program.","The same three-stage pipeline covers transposes, sums, matrix-vector products, matrix multiplication, batched matrix multiplication, bilinear transforms, and five-dimensional contractions without changing the underlying mechanism.","Users can choose a memory-efficient configuration with only power-of-two rotation keys and roughly 3 GB of working memory, or a compute-efficient configuration with additional BSGS keys and roughly 32 GB that runs faster.","The evaluation shows the pipeline runs on both CPU and GPU backends, with the GPU giving roughly a 6x speedup on most tested operations and a small-scale multi-head attention score computed in about 29 seconds.","A cleartext backend lets developers inspect every intermediate slot vector, turning debugging of encrypted tensor programs into ordinary vector arithmetic."],"supporting_citations":[{"why":"This citation defines the RNS-CKKS scheme and its SIMD primitives of addition, multiplication, and cyclic rotation that EinHops builds on.","marker":"[12]"},{"why":"This citation supplies the diagonal-based matrix-vector product method that the BSGS permutation step generalizes.","marker":"[28]"},{"why":"This citation provides the baby-step giant-step algorithm used to perform slot permutations with about a square-root number of rotations.","marker":"[11]"},{"why":"This citation gives the rotation-and-summation algorithm used for logarithmic broadcasting and reduction over dimensions.","marker":"[43]"},{"why":"This citation introduces the hoisting optimization EinHops uses to amortize key-switching within baby steps.","marker":"[29]"},{"why":"This citation provides the FHE backend that supplies SIMD addition, multiplication, and rotation on CPU and GPU.","marker":"[22]"},{"why":"This citation parses and validates einsum expressions, turning the notation into an executable plan.","marker":"[2]"}],"fun_headline_variants":["Einsum notation demystifies homomorphic tensor operations","Encrypted tensors get an explicit three-step plan","Homomorphic einsum: packing made visible","EinHops: three FHE steps for any tensor contraction","Tensor math on encrypted data, unpacked"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing assumption is that the product of all input dimensions fits inside the $N/2$ slots of a single encrypted vector (ciphertext); if a tensor is larger, the fixed pipeline would need to be reworked.","fun_headline_variants_meta":{"raw":{"variants":["Einsum notation demystifies homomorphic tensor operations","Encrypted tensors get an explicit three-step plan","Homomorphic einsum: packing made visible","EinHops: three FHE steps for any tensor contraction","Tensor math on encrypted data, unpacked"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.0002,"raw_usage":{"total_tokens":1416,"prompt_tokens":1025,"completion_tokens":391,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":641,"completion_tokens_details":{"reasoning_tokens":316}},"tokens_in":641,"tokens_out":391,"duration_ms":4350,"temperature":1.0,"reasoning_tokens":316,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T18:26:26.129267+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a supported einsum expression whose total input sizes fit within the $N/2$ slots, decrypt the intermediate ciphertexts after the broadcast, multiplication, and reduction stages, and compare every slot against the layout predicted by the paper's padding and slot-spacing rules; any mismatch shows the fixed pipeline is incorrect. To test the generality boundary, repeat with an expression whose total input dimension product exceeds $N/2$ and observe whether the system fails, as the stated limitation predicts.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"This citation defines the RNS-CKKS scheme and its SIMD primitives of addition, multiplication, and cyclic rotation that EinHops builds on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"This citation gives the rotation-and-summation algorithm used for logarithmic broadcasting and reduction over dimensions."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"This citation introduces the hoisting optimization EinHops uses to amortize key-switching within baby steps."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"This citation provides the FHE backend that supplies SIMD addition, multiplication, and rotation on CPU and GPU."}],"review_version":1}