Exponential Separation between Linear Transformers and Janossy Pooling Networks from a Functional Perspective

Permutation-invariant architectures, including Janossy pooling networks and linear Transformers, are ubiquitous in modern deep learning, yet their relative theoretical strengths remain insufficiently understood. Through the approximation of statistical functionals, we systematically compare these architectures and establish an exponential separation in representational efficiency favoring linear Transformers. We establish their universal approximation property (UAP) for continuous functionals of probability measures. Despite this universality, we construct a normalized hard functional involving two-stage feature extraction, exactly representable by a shallow linear Transformer with a scalar pooled representation. Nevertheless, DeepSets require a latent dimension exponential in the input dimension for fixed nontrivial $L^2$ accuracy under a suitable input-measure distribution. We further extend this separation to $r$-ary Janossy pooling networks under the uniform norm. These lower bounds hold for arbitrary continuous real-valued feature maps and readouts, regardless of their expressivity. The separation stems from a structural distinction: linear Transformers use multistage information aggregation to implement input-distribution-dependent feature maps, whereas Janossy pooling employs fixed feature maps. Our results expose an intrinsic information bottleneck of single-stage fixed-arity pooling that UAP alone does not capture.