Papers for

neural network theorists

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Virtual extension complexity can vastly outperform classic extension complexity

Two Linear Programs are Better than One

Abstract: The extension complexity $\operatorname{xc}(P)$ of a polytope $P$ is the minimum number of facets of a polytope that projects onto it. Motivated by the complexity of neural networks, Hertrich and Loho introduced the virtual extension complexity $\operatorname{vxc}(P)$ of a polytope $P$, which is the minimum of $\operatorname{xc}(Q) + \operatorname{xc}(R)$ among all polytopes $Q$ and $R$ such that $P+Q=R$. We show the following results pertaining to virtual extension complexity. First, we resolve the core open problem on the topic by showing the virtual extension complexity can be exponentially smaller than extension complexity. Second, we show there are matroid base polytopes with exponential virtual extension complexity by adapting a semi-algebraic counting argument by Hrubeš that extends the counting arguments of Rothvoss. Finally, we show that the maximum virtual extension complexity of a polygon with $n$ vertices is $Θ(\sqrt{n})$. This resolves an analogue of a question on extension complexity of Fiorini, Rothvoss, and Tiwary in 2011 in the case of virtual extension complexity.

Sun 11 OctComputational ComplexityDiscrete MathematicsMachine Learning
The gist
When trying to represent shapes called polytopes, it's important to measure how complicated that representation is. The authors study a new measure called virtual extension complexity, which looks at how combining two simpler shapes can represent a complex one more easily. They show that using two shapes instead of one can make this complexity much smaller, sometimes exponentially so. They also find examples where this simplification isn't enough and explore how complicated polygons behave under this measure.
Open → 2610.15909v1

Symmetry and rank shape attention mechanisms in large language models

On attention heads and bilinear forms

Abstract: We study the symmetric and antisymmetric parts of bilinear forms in the attention heads of trained large language models. We introduce an orthogonally invariant profile map from real bilinear forms to a three-dimensional simplex and observe that profiles of trained bilinear forms accumulate near profiles of rank-one bilinear forms. We prove that the symmetric part of a bilinear form in an attention head is the sum of a hyperbolic form and a zero form for a Zariski-dense subset of query-key matrices.

Sat 19 SeptMachine Learning
The gist
Attention heads in large language models use certain mathematical forms, called bilinear forms, to decide how words relate to each other. The authors studied how these forms can be broken down into symmetric and antisymmetric parts and found that after training, they mostly look like simple rank-one forms. They also proved that the symmetric parts behave in a predictable way related to special types of mathematical forms, which holds for a large set of these models. This helps us understand the math behind how language models focus on information.
Open → 2609.22990v1