Fundamental limits of learning in sequence multi-index models and deep attention networks - high-dimensional asymptotics and sharp thresholds

Aug 4, 2026

We study learning in deep attention neural networks formed by composing multiple self-attention layers with tied and low-rank weights, and connect them to sequence multi-index models that generalize classical multi-index settings to sequential covariates. Under Bayes-optimal learning with large dimension D and proportionally large sample size N, the work derives a sharp asymptotic characterization of optimal performance, including that of approximate message passing, and identifies sharp thresholds for sample complexity. It further explains how sequential layer learning emerges in realistic setups.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages36

Reading Time1 h 31 min

AccessFree to download

Abstract

Introduction

From deep attention to sequence multi-index models

Mapping and modeling of architectures

Main contributions (Bayes-optimal setting)

Fundamental limits of learning in sequence multi-index models and deep attention networks: high-dimensional asymptotics and sharp thresholds Emanuele Troiani 1 Hugo Cui 2 Yatin Dandi 1 3 Florent Krzakala 3 Lenka Zdeborov 1 Abstract In this manuscript, we study the learning of deep attention neural networks, defined as the composition of multiple self-attention layers, with tied and low-rank weights. We first establish a mapping of such models to sequence multi-index models, a generalization of the widely studied multi-index model to sequential covariates, for which we establish a number of general results. In the context of Bayes-optimal learning, in the limit of large dimension D and proportionally large number of samples N , we derive a sharp asymptotic characterization of the optimal performance as well asthe performance of the best-known polynomialtime algorithm for this setting –namely approximate message-passing–, and characterize sharp thresholds on the minimal sample complexity required for better-than-random prediction performance. Our analysis uncovers, in particular, how the different layers are learned sequentially. Finally, we discuss how this sequential learning can also be observed in a realistic setup. 1. Introduction Recent years have witnessed a shift in paradigm in the automated learning from sequential data, such as language (Brown et al., 2020 ; Kenton & Toutanova, 2019) . The backbone of many of these technological advances arguably lies in the use of transformer architectures (Vaswaniet al., 2017)– a parametrization allowing the model to dynamically focus on relevant portions of the input, and extricate increasingly complex correlations between tokens through the successive application of attention layers. They 1 Statistical Physics Of Computation Laboratory, ´Ecole Polytechnique Fdrale de Lausanne (EPFL) 2 Center of Mathematical Sciences and Applications, Harvard University 3Information Learning and Physics Laboratory, ´Ecole Polytechnique Fdrale de Lausanne (EPFL) . Correspondence to: Emanuele Troiani . Proceedings of the 42 nd International Conference on Machine Learning, Vancouver, Canada. PMLR 267, 2025 . Copyright 2025 by the author(s) . thus constitute a function class able to represent intricate dependencies between the tokens of sequential covariates. In spite of their ubiquity, the study of such models from a theoretical viewpoint is still in its infancy. This situation stands in contrast with the wealth of resultson multi-index models, central to many theoretical works e.g. (Arous et al., 2021 ; Abbe et al., 2022 ; Veiga et al., 2022 ; Ba et al., 2022 ; Arnaboldi et al., 2023 ; Collins-Woodfinet al., 2024 ; Damian et al., 2024a ; Bietti et al., 2023 ; Moniri et al., 2024 ; Berthier et al., 2024) . Multi-index models define functions based on low-dimensional subspaces ofcovariates and are popular exemplars among theoreticians. However, shallow architectures like multi-index models are structurally simpler than attention models. Specifically, they (a) lack the hierarchical structure from multiple attention layers and (b) act on less structured, non-sequential covariates. These distinctions make it unclear whether results from multi-index models apply to multilayer attention architectures. Here, we show these models share a deep formal connection, enabling a transfer of insights and analytical approaches. Namely, our first motivation is to extend the theoretical framework of multi-index models to sequence models. We consider the class of sequence multi-index (SMI) functions introduced by (Cui et al., 2024a ; Cui, 2025), and defined over length M sequences of D-dimensional tokens x ∈ RD×M of the form ySMIW(x) = g 􀀒 xD􀀓 . (1) where W ∈ RP×D is a learnable projection matrix, and g : RP×M → RK is a (possibly multi-dimensional) link function. The K−dimensional output could represent –to give an example– the predicted class pro

FAQs

What relationship does the paper establish between deep attention networks and sequence multi-index models?

It maps deep attention architectures to sequence multi-index functions, showing a formal connection that transfers theoretical tools and insights between the two model classes.

In what regime does the paper analyze learning performance and sample complexity?

The analysis targets Bayes-optimal learning when the dimension D is large and the number of samples N grows proportionally, enabling sharp asymptotic results.

How does the paper characterize learning using approximate message passing?

It derives the asymptotic optimal performance for the setting and also compares it to the performance of approximate message passing, the best-known polynomial-time algorithm for this regime.

Aug 4, 2026

Upload by Valentina