{"id":"5be139e3-ca51-4c7d-88d1-ddcd627e967e","arxiv_id":"2505.20150","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":2,"one_line_summary":"No piecewise linear k-ary Janossy pooling is injective on general multisets, but simple deep sets are injective on compact domains of well-separated distinct points.","lead":"This paper proves that continuous piecewise linear Janossy pooling, a family covering deep sets and set transformers, is never injective on multisets with repeated elements. It also shows that on multisets of well-separated distinct points, even simple deep sets can be injective and bi-Lipschitz.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified","rationale":"After a careful pass over the proofs, the central negative claim (Theorem 3.1) appears sound. The reduction from F to the symmetric \\hat f is standard, Theorem 3.2 supplies a cell P0 and a decreasing n-tuple w whose every k-subtuple lies in int(P0), and the linear system S(delta)=0 has n>k unknowns and k equations, so a nonzero small perturbation delta exists that preserves cell membership and strict ordering, yielding two distinct multisets with equal F. The d>1 case correctly pulls back along an affine segment. I scrutinized the technical heart in Appendix A.1: Lemma A.1 is fine, the nesting of POLY(v_i) in Proposition A.2 is correct, and the convex-combination argument in Proposition A.4 works. The only gap is Proposition A.3's justification that v_k is in the interior of P0; the written reason is incomplete, but the conclusion follows because v_k has positive distance from the finite union of the other closed polytopes. This is fixable and does not threaten the theorem. The reader's weakest-assumption point about R(D)>0 in the positive theorem is indeed the most delicate condition, but it is explicitly assumed and proved under compactness; it is a domain restriction rather than a flaw. Minor issues such as the QM9 wording and 'covering' versus 'partition' do not affect the mathematics. Therefore the reader's ACCEPT verdict needs no change.","tokens_in":13402,"tokens_out":31886,"duration_ms":345974,"concrete_test":"For k=2,n=3, generate random polytope partitions of R^2 from arrangements of 3-5 lines and run the Appendix A.1 construction to produce w; verify that all three ordered pairs (w_i,w_j) with i<j lie in the interior of a single polytope. If any such partition defeats the construction, Theorem 3.2 would harbor a hidden flaw.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I checked Theorem 3.1 and its supporting Theorem 3.2. The symmetrization step to \\hat f is valid, the perturbation argument reduces to k homogeneous linear equations in n>k unknowns with a nonzero solution that can be scaled into the stability neighborhood, and the d>1 reduction by an affine segment is correct. The only soft spot I found is in Appendix A.3: the claim that v_k lies in int(P0) does not follow merely from v_k being in the interior of [0,1]^k and belonging to a single polytope; but it is readily repaired because the other polytopes are closed, finitely many, and do not contain v_k, so v_k has positive distance from their union. This is a presentation gap, not a load-bearing flaw. The compact-domain separation assumption in Theorem 4.3 is explicit and correctly proven in Proposition 4.4; it is a limitation, not a correctness risk. No load-bearing concern remains.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the injectivity and bi-Lipschitzness of k-ary Janossy pooling when the inner function f is continuous piecewise linear (CPwL). The main negative result (Theorem 3.1) states that if C contains a line segment and n > k, no CPwL k-ary Janossy pooling is injective on multisets of size n in M_n(C); the proof reduces to a combinatorial statement (Theorem 3.2) that every polytope partition of R^k contains a polytope P0 and a strictly ordered vector w in (0,1)^n all of whose ordered k-subvectors lie in the interior of P0, after which a homogeneous linear system in n > k unknowns yields a nontrivial perturbation with equal pooling value. The positive result (Theorem 4.3) constructs, for compact domains D of multisets with distinct elements, an explicit CPwL 1-ary pooling that is injective and bi-Lipschitz with respect to the Wasserstein distance, using a hypercube tessellation of scale R(D)/2. The paper also discusses the degenerate k=n case, the dependence of the embedding dimension on R(D), and a conjecture for bounded-multiplicity domains.","tokens_in":13551,"tokens_out":17325,"duration_ms":171028,"significance":"If correct, the negative result resolves the open question for k >= 2 and shows that injective CPwL multiset representations require either sorting-based maps or the degenerate k = n construction; this strengthens the case for bi-Lipschitz models built on sorting rather than standard Janossy pooling. The proofs are self-contained and rely on no fitted parameters: Theorem 3.1 is proven from the explicit combinatorial lemma in the appendix, and the construction in Theorem 4.3 is explicit. The compact-domain separation assumption is stated and justified in Proposition 4.4, and the limitations and conjecture are clearly identified. The main theorems give falsifiable predictions about expressivity of standard architectures, which is a useful contribution to the theory of permutation-invariant networks.","major_comments":[{"comment":"The bi-Lipschitz conclusion is justified by an unspecified auxiliary set D-hat, said to be a finite union of polytopes containing D and containing no multisets with repeated elements. This claim is not established. A finite union of grid hypercubes in the point space R^d is not a set of multisets, and the set of all multisets over such a union contains repeated points; if D-hat is intended as a set of multisets, its structure as a finite union of polytopes requires proof. Please give an explicit construction (for example, in sorted-coordinate space, fix an assignment of the n points to distinct grid cells and verify that each such region is a polytope) and prove that the constructed F is injective on that D-hat before applying [Sverdlov et al., 2024, Lemma 3.4]. As written, the bi-Lipschitz claim in Theorem 4.3 is not fully supported.","section":"Section 4, proof of Theorem 4.3, final paragraph"}],"minor_comments":[{"comment":"The sentence concluding that v_k lies in int(P0) because it lies in the interior of [0,1]^k is not a valid inference. The conclusion is nonetheless correct: since |POLY(v_k)| = 1 and the finitely many other closed polytopes do not contain v_k, there is a positive distance from v_k to their union, so a small ball around v_k is contained in P0. Please replace the argument.","section":"Appendix A.1, Proposition A.3"},{"comment":"The proof refers to a finite polytope covering of [0,1]^k, while Theorem 3.2 is stated for a partition. Please clarify that the collection is the partition into linear regions of the symmetrized function (or take a common refinement) so that Theorem 3.2 applies directly.","section":"Section 3, proof of Theorem 3.1"},{"comment":"The sentence 'the ratio was not larger than 1/10' contradicts the histogram and the preceding paragraph; it should read 'not smaller than 1/10'.","section":"Section 4.1"},{"comment":"There are numerous typos and misspellings, including 'Currenlty', 'inejctivity', 'Lipshitz', 'partion', 'elments', 'Wasserstien', 'montonely', 'represetative', and 'a a finite union'. A careful proofreading pass is needed.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The main non-injectivity theorem (Theorem 3.1) is correct and well supported; Theorem 3.2 is proven in the appendix and the linear-algebra step is valid. My major concern is limited to the final step of the proof of Theorem 4.3, where the bi-Lipschitz argument rests on an insufficiently specified set D-hat. I am confident the gap can be repaired with a short explicit construction, and I would be satisfied with a revision that supplies it. The paper makes a solid contribution to the expressivity of permutation-invariant models."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, this settles the open k>=2 case: CPwL k-ary Janossy pooling is never injective for multisets of size n>k, so sort-based bi-Lipschitz models are not just an option but necessary if you want injectivity in general. Second, the positive result is real and explicit: on compact domains with a positive minimal separation, even 1-ary CPwL deep sets can be injective and bi-Lipschitz, with embedding dimension scaling like (1/R(D))^d.\n\nThe core new piece is Theorem 3.2, a combinatorial lemma about polytope partitions of R^k. I checked the appendix proof. The induction building v_0,...,v_k, the nest property of POLY(v_i), and the convex-combination argument are all sound. The proof of Theorem 3.1 then reduces to k linear homogeneous equations in n>k unknowns, which is correct. The d>1 reduction by an affine segment is fine. The positive construction is a standard grid tessellation with local indicator and coordinate features, and the separation bound R(D)>0 via compactness is proven properly.\n\nSoft spots are minor. Appendix A.3 has a small presentation gap: the claim that v_k lies in int(P0) does not follow just from v_k being in one polytope and inside [0,1]^k; you need to use that the other polytopes are closed, finite in number, and do not contain v_k. The stress-test note caught this and it is readily repaired. Also, the text calls P a 'covering' where the theorem needs a 'partition'—clearly a wording slip. And the QM9 sentence says the ratio was 'not larger than 1/10' when the histogram and the argument need 'not smaller than 1/10'; an obvious typo that does not touch the math.\n\nI do not see a load-bearing flaw. The negative result is proven from first principles, the positive result is limited to separated domains, and the authors say so themselves in the limitations section. Citation practice is normal; the only self-citation (Sverdlov et al.) is used for the bi-Lipschitz upgrade, not for the main theorems.\n\nWho is this for: people working on expressivity of permutation-invariant networks, set transformers, and geometric GNNs. It will get cited. It deserves a serious referee. I would accept it with minor revisions.","headline":"Settles the k>=2 Janossy pooling expressivity question with a genuinely new polytope-partition lemma; a solid paper with only minor presentation gaps.","tokens_in":14119,"tokens_out":1632,"would_cite":true,"duration_ms":17000,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T07"],"pacs":[],"model":"deepseek-v4-flash","headline":"No piecewise-linear Janossy pooling is injective","keywords":["multiset functions","Janossy pooling","injectivity","bi-Lipschitz embeddings","piecewise linear functions","deep sets","set transformers","Wasserstein distance"],"falsifier":"Try to construct a CPwL function $f: \\mathbb{R}^2 \\to \\mathbb{R}$ on a partition of the unit square into four quadrants and show that its 2-ary Janossy pooling on triples is injective; the theorem predicts such injectivity is impossible, so any explicit injective example would refute it. More directly, a computational search over polytope partitions of $\\mathbb{R}^2$ for one that defeats Theorem 3.2—no strictly decreasing triple $w$ whose three ordered pairs share a polytope—would test the proof's engine.","tokens_in":13198,"feed_emoji":"🔢","tokens_out":12028,"duration_ms":112587,"temperature":0.7,"pith_summary":"This paper answers a question about the expressiveness of standard neural network layers that process unordered sets of vectors. It proves that $k$-ary Janossy pooling—the family that includes deep sets ($k=1$) and set transformers ($k=2$)—cannot be injective when the pooled function is continuous piecewise linear (the activation class of ReLU networks) and the multiset size $n$ is larger than $k$. The only exception is the degenerate $k=n$ case, where pooling over all permutations can be injective by using a sorting-based map. On the positive side, the paper shows that if the domain is restricted to compact sets of multisets with no repeated points, even 1-ary deep sets can be injective and bi-Lipschitz with respect to the Wasserstein distance. The embedding dimension of this construction grows like $(1/R)^d$, where $R$ is the minimal separation between points in the domain.","feed_headline":"Piecewise-linear multiset pooling is never injective","feed_subtitle":"Set transformers and deep sets must merge distinct multisets; only separated point sets stay faithful.","key_machinery":"The central object is the polytope-covering lemma (Theorem 3.2) that drives the negative result: for any finite partition of $\\mathbb{R}^k$ into convex polytopes, there exists a strictly decreasing vector $w$ of length $n$ whose every $k$-dimensional order-preserving subvector falls inside a single polytope $P_0$. This reduces the non-injectivity of Janossy pooling to a counting argument: around such a $w$ the pooling map is affine, and the system of $k$ equations expressing the sum of perturbations over all $k$-subtuples has a nonzero solution in $\\mathbb{R}^n$ because $n > k$. For the positive result, the key mechanism is a hypercube tessellation of $\\mathbb{R}^d$ with side length $s = R(D)/2$, where $R(D)$ is the minimal pairwise distance among points of any multiset in the compact domain $D$; each hypercube carries a CPwL indicator of membership plus a CPwL coordinate feature that equals the point's location inside the cube and interpolates to zero at the margin boundary, so the pooled sum reveals each point uniquely.","core_discovery":"The paper's central claim is Theorem 3.1: let $C$ be any subset of $\\mathbb{R}^d$ containing a line segment, let $f:(\\mathbb{R}^d)^k \\to \\mathbb{R}^m$ be continuous piecewise linear, and let $n > k$. Then the $k$-ary Janossy pooling of $f$, defined by averaging $f$ over all ordered $k$-tuples of the input, is not injective on multisets of size $n$ from $C$. The proof hinges on a new geometric lemma (Theorem 3.2): for every finite partition of $\\mathbb{R}^k$ into polytopes, there is a strictly decreasing vector $w=(w_1,\\ldots,w_n)$ in $(0,1)^n$ and a single polytope $P_0$ such that every order-preserving $k$-subvector of $w$ lies in the interior of $P_0$. This makes the pooled output affine on a neighborhood of $w$, and since summing over $k$-element subsets leaves $k$ linear equations in $n > k$ unknowns, a nonzero perturbation preserves the pooled vector while changing the multiset. The companion positive result, Theorem 4.3, constructs, on a compact domain of multisets with $n$ distinct points, a CPwL function $f$ such that 1-ary pooling is injective and bi-Lipschitz; the construction tessellates $\\mathbb{R}^d$ into hypercubes of side length $R(D)/2$ and attaches to each hypercube an indicator feature and a coordinate feature, so that the pooled output reveals every point of the multiset.","pith_inferences":["A concrete, testable consequence of Theorem 3.1: for any ReLU set transformer with $k=2$, one can run an adversarial search over pairs of size-$n$ point sets ($n>2$) and expect to find identical embeddings; such an experiment would empirically demonstrate the collision guaranteed by the theorem.","The geometric lemma may generalize beyond polytopal partitions: the argument uses only finiteness and convexity, so a similar non-injectivity could hold for any function that is affine on finitely many convex regions, e.g., hinge-type or other CPwL-like activations.","The QM9 analysis in the paper (minimal within-molecule distances above 0.1 of the diameter for all sampled molecules) suggests a rule of thumb for practitioners: small-molecule point clouds are likely in the 'well-separated' regime where deep sets suffice, while continuous surfaces or dense clouds are not.","One could implement the positive construction explicitly and measure, on real point clouds, whether the guaranteed injectivity translates into useful Lipschitz constants for downstream tasks such as learning Wasserstein distances."],"forward_implications":["Set transformers and other $k$-ary pooling models with ReLU activations cannot faithfully represent multisets of size $n > k$ in general: for every such model there exist distinct multisets that its output cannot tell apart.","The negative result provides a theoretical justification for the higher cost of sorting-based and quantile-based bi-Lipschitz encoders: no simple piecewise-linear pooling can match their injectivity guarantee.","For datasets with well-separated points, the positive result shows that ordinary deep sets are sufficient, both injective and bi-Lipschitz, with the embedding dimension determined by the minimal separation $R(D)$.","The construction's dimension scales as $(1/R(D))^d$, so the mathematical guarantee degrades as point clouds approach each other; near-duplicate points are exactly where specialized bi-Lipschitz layers are needed.","The paper's conjecture that $k$-ary pooling is injective on multisets with multiplicity at most $k$, if true, would establish a precise expressivity hierarchy across pooling orders."],"supporting_citations":[{"why":"introduces Janossy pooling, the family of multiset models whose injectivity is at issue.","marker":"Murphy et al. [2019]"},{"why":"defines the deep-sets model, the k=1 special case that the paper extends and the positive construction builds on.","marker":"Zaheer et al. [2017]"},{"why":"proves the k=1 non-injectivity result for CPwL deep sets and the fact that smooth multiset functions cannot be bi-Lipschitz, setting the baseline the paper generalizes.","marker":"Amir et al. [2023]"},{"why":"provides sorting-based injective bi-Lipschitz CPwL multiset maps used in the k=n degenerate case and as the alternative the negative result supports.","marker":"Balan et al. [2022]"},{"why":"supplies the lemma that injective CPwL multiset functions are bi-Lipschitz on compact domains, used to conclude bi-Lipschitzness in Theorem 4.3.","marker":"Sverdlov et al. [2024]"},{"why":"gives the cell-decomposition result that lets the margin around each hypercube be triangulated without new vertices, enabling the CPwL interpolation in the positive construction.","marker":"Goodman and Pach [1988]"},{"why":"provides the accessibility lemma used to show that the constructed convex combination lies in the interior of the target polytope in Theorem 3.2.","marker":"Rockafellar [1970]"},{"why":"states the convex-set separation property used to prove that a single polytope contains all iterates v0,...,vk in Theorem 3.2.","marker":"Boyd and Vandenberghe [2004]"}],"fun_headline_variants":["No piecewise linear Janossy pooling is injective","Piecewise linear Janossy pooling always merges some multisets","Geometric proof: Janossy pooling folds distinct multisets","Distinct multisets collide under piecewise linear Janossy","Janossy pooling injectivity impossible for piecewise linear"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The non-injectivity theorem depends on $f$ being continuous piecewise linear, so that its domain splits into finitely many polytopes on each of which $f$ is affine; if $f$ were smooth, injective Janossy pooling would be possible, and the theorem would no longer hold.","fun_headline_variants_meta":{"raw":{"variants":["No piecewise linear Janossy pooling is injective","Piecewise linear Janossy pooling always merges some multisets","Geometric proof: Janossy pooling folds distinct multisets","Distinct multisets collide under piecewise linear Janossy","Janossy pooling injectivity impossible for piecewise linear"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001063,"raw_usage":{"total_tokens":4520,"prompt_tokens":1073,"completion_tokens":3447,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":689,"completion_tokens_details":{"reasoning_tokens":3362}},"tokens_in":689,"tokens_out":3447,"duration_ms":23462,"temperature":1.0,"reasoning_tokens":3362,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T13:58:52.630957+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Try to construct a CPwL function $f: \\mathbb{R}^2 \\to \\mathbb{R}$ on a partition of the unit square into four quadrants and show that its 2-ary Janossy pooling on triples is injective; the theorem predicts such injectivity is impossible, so any explicit injective example would refute it. More directly, a computational search over polytope partitions of $\\mathbb{R}^2$ for one that defeats Theorem 3.2—no strictly decreasing triple $w$ whose three ordered pairs share a polytope—would test the proof's engine.","supporting_citations":[{"cited_title":"Deep sets","cited_arxiv_id":null,"evidence_quote":"defines the deep-sets model, the k=1 special case that the paper extends and the positive construction builds on."},{"cited_title":"Neural injective functions for multisets, measures and graphs via a finite witness theorem","cited_arxiv_id":null,"evidence_quote":"proves the k=1 non-injectivity result for CPwL deep sets and the fact that smooth multiset functions cannot be bi-Lipschitz, setting the baseline the paper generalizes."},{"cited_title":"Convex Optimization","cited_arxiv_id":null,"evidence_quote":"states the convex-set separation property used to prove that a single polytope contains all iterates v0,...,vk in Theorem 3.2."}],"review_version":1}