- Rating
- 2
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper proves that Janossy pooling networks and shallow linear Transformers with a single head universally approximate continuous statistical functionals, and establishes an exponential separation in latent dimension that favors linear Transformers, answering an open question from a previous paper.
Critical strengths
- The paper is generally well written and structured.
- The attempt to answer an open question from previous work is rewarding.
Critical weaknesses
The paper does not sufficiently motivate the practical implications of its theoretical findings. While the mathematical derivations are the central focus, the absence of empirical validation—even on toy datasets or synthetic benchmarks—leaves the practical relevance of the theorems unclear. Furthermore, in an era where formal verification (such as Lean) and automated reasoning are increasingly accessible, unverified theoretical claims without accompanying empirical grounding or reproducible code have limited actionable value for practitioners.
Questions for authors
- Could the authors provide a more self-contained explanation and intuitive background on "exponential separation" early in the text to improve readability for a general ML audience?
- Why is establishing an exponential separation in this setting practically meaningful? The current framing appears primarily descriptive rather than offering constructive guidance.
- Could the authors clarify the motivation for analyzing linear Transformers instead of standard softmax Transformers? Does the analysis rely on linearity for tractability, or does it reflect a specific practical use case?
- What actionable takeaways—if any—do the separation results between Janossy pooling and linear Transformers provide for researchers designing or deploying these architectures?
3 comments
We next address the reviewer’s questions (Q1–Q4) point by point.
[Q1] Explanation and backgroud on "exponential separation"
We have expanded the Introduction to briefly introduce statistical functionals and motivate exponential separation from the perspective of approximation efficiency. We also provide an intuition for the exponential latent-dimension lower bound: since statistical functionals encompass permutation-invariant inputs of variable lengths, features extracted for one sequence length may not remain informative for another. Accommodating different lengths may therefore require distinct feature representations, potentially leading to exponential growth in the aggregate latent dimension. We further clarify the structural source of the separation in Remark 3.10 and provide a concrete illustrative example in Appendix B.1 of the revised manuscript.
[Q2] Practical implications for exponential separation under statistical functionals.
Statistical functionals provide a natural framework for modeling permutation-invariant functions on variable-length inputs. Specifically, an unordered set can be represented by its empirical measure , allowing a permutation-invariant function to be viewed as a functional of . This formulation is particularly relevant to applications such as point-cloud classification and operator learning, where the number of input points may vary. Establishing exponential separations in this setting provides practical guidance for architecture design: it identifies the limitations of single-stage pooling and highlights the advantages of multistage information aggregation for efficiently representing permutation-invaraint functions of variable length. Our results help inform the design and selection of architectures for such tasks.
[Q3] Motivation for Linear Transformers
We focus on linear Transformers in the main text because they admit a simpler and more transparent theoretical analysis. Indeed, the exponential separation stems from the contrast between the single-stage pooling of -ary Janossy networks and the two-stage information aggregation of Transformers, which also holds with standard softmax attention. In particular, we construct a hard functional establishing an analogous exponential separation between softmax Transformers and -ary Janossy pooling networks. We have added a brief discussion in Remark 3.10 and provided the detailed construction and proof in Appendix B.5 of the revised manuscript.
[Q4] Architectural Takeaways
Our results suggest that, for practical variable-length permutation-invariant tasks, such as point-cloud classification and operator learning, single-stage -ary Janossy pooling may be insufficient when target functions require multistage information interactions. In such settings, attention-based Transformer architectures are preferable, as stacking attention blocks enables repeated global information aggregation and adaptive feature extraction, thereby enhancing expressivity and potentially improving performance.
We hope our responses address the reviewer’s questions and concerns. We would be happy to provide further clarification if needed. Thank you for your time and constructive feedback.
We would like to briefly follow up on our previous responses and the updated manuscript. We would greatly appreciate your feedback on whether our clarifications have addressed your concerns, and we would be glad to provide further explanations if needed. Thank you for your time and consideration.
We thank the reviewer for recognizing the theoretical contributions and clear presentation of our work, and for highlighting the need for empirical validation and clearer practical implications. We address the concerns and questions point by point below. All corresponding changes in the revised manuscript are highlighted in blue.
Given the character limit, we split our response into two comments: the first addresses the reviewer’s stated weakness, while the second addresses the questions raised. We begin with the response to the weakness.
We have added synthetic experiments on two tasks: learning the hard functional constructed in our manuscript and principal eigenvector estimation under the classical rank-one spiked covariance model (Johnstone, 2001). For principal eigenvector estimation, We sample an unknown direction v∼Unif(Sd−1) and generate i.i.d. observations xi=ziv+ni, where zi∼N(0,1) and ni∼N(0,Id). The objective is to give an estimation v, evaluated using the absolute cosine similarity ∣⟨v,v⟩∣.
We compare DeepSets, Relational Networks, and Linear Transformers across latent dimensions M. The results are as follows:
Hard-functional learning (MSE, lower is better)
Principal eigenvector estimation (cosine similarity, higher is better):
Linear Transformers consistently outperform the two pooling architectures. Increasing M brings limited gains for DeepSets, while pairwise interactions yield only marginal improvements for Relational Networks.
Mechanism. Both tasks require multistage information aggregation. For hard-functional learning, it needs first computing the barycenter mρ and then extracting the adaptive feature ∣⟨x,mρ⟩∣. Linear attention naturally implements these two stages, whereas Janossy pooling relies on fixed feature maps. For principal eigenvector estimation, single-stage pooling can yield the empirical covariance N−1∑i=1Nxixi⊤→Id+vv⊤, whose leading-to-noise eigenvalue ratio is 2:1. In contrast, with identity query, key, and value maps, pooling after aggregation via linear attention can yield N−1∑i=1NAttni(X)Attni(X)⊤→Id+7vv⊤, increasing the eigenvalue ratio to 8:1. This illustrates how multistage information aggregation amplifies the principal direction.
These experiments are presented in Section 5, with detailed experimental setups provided in Appendix C of the revised manuscript. Reproducible code is available at the Anonymous Repository.
References