source/authored/main.tex

\documentclass{article}
\usepackage[margin=1in]{geometry}  % 1 inch margins all around

\usepackage{soul}
\usepackage{microtype}
\usepackage{graphicx}
\usepackage{subcaption}
\usepackage{booktabs} % for professional tables
\usepackage{bbm}
\usepackage{dsfont}
\usepackage{authblk}  % for multiple authors and affiliations

\usepackage{hyperref}


\newcommand{\theHalgorithm}{\arabic{algorithm}}

\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{mathtools}
\usepackage{amsthm}
\usepackage{thmtools}
\usepackage{natbib}
\usepackage{enumitem}
 \usepackage[nameinlink]{cleveref}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% THEOREMS
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{assumption}[theorem]{Assumption}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\title{Expressivity-Efficiency Tradeoffs for Hybrid Sequence Models}

\author[*1]{John Cooper}
\author[1]{Ilias Diakonikolas}
\author[*1]{Mingchen Ma}
\author[1]{Frederic Sala}

\affil[1]{Department of Computer Sciences, University of Wisconsin-Madison}

% Optional: email addresses
\affil[ ]{\texttt{\{jfcooper2, mingchen\}@cs.wisc.edu}}

\date{}

\input{mathcommands}

\begin{document}

\maketitle

\begin{abstract}
        Hybrid sequence models---combining Transformer and state-space model layers---seek to gain the expressive versatility of attention as well as the computational efficiency of state-space model layers. Despite burgeoning interest in hybrid models, we lack a basic understanding of the settings where—and underlying mechanisms through which—they offer benefits over their constituent models. In this paper, we study this question, focusing on a broad family of core synthetic tasks. For this family of tasks, we prove the existence of fundamental limitations for non-hybrid models. Specifically, any Transformer or state-space model that solves the underlying task requires either a large number of parameters or a large working memory. On the other hand, for two prototypical tasks within this family—namely selective copying and associative recall—we construct hybrid models of small size and working memory that provably solve these tasks, thus achieving the best of both worlds. Our experimental evaluation empirically validates our theoretical findings. Importantly, going beyond the settings in our theoretical analysis, we empirically show that learned---rather than constructed---hybrids outperform non-hybrid models with up to $6 \times$ as many parameters. We additionally demonstrate that hybrid models exhibit stronger length generalization and out-of-distribution robustness than non-hybrids. \footnote{Code is available \href{https://github.com/SprocketLab/hybrid-expressivity}{in this link}. * denotes equal contribution.}
\end{abstract}

\input{sections/introduction}

\input{sections/prelim_and_notation}

\input{sections/func_comp_and_construct}

\input{sections/upper_bound}

\input{sections/tasks}

\input{sections/experiments}

\input{sections/conclusion}



\bibliography{reference}
\bibliographystyle{plainnat}
% \bibliographystyle{plain}



\newpage
\appendix

\section*{Supplementary Material}
We provide supplementary materials here. In \Cref{app relate work}, we provide related works. In \Cref{app notations}, we give a complete list of preliminaries and notations. In \Cref{app proof lb}, we present omitted proofs in \Cref{sec lb}, establishing hardness results for SSMs and transformers. In \Cref{app:constructions}, we provide omitted proofs in \Cref{sec merge}, providing concrete hybrid model constructions. In \Cref{app experiments}, we provide additional details to our empirical experiments.

\input{sections/related}

\input{appendix/app_prelim}

\input{appendix/construction_conventions}

\input{appendix/missing_proof_lb}

\input{appendix/constructions}

\input{appendix/experiment_details}

\end{document}