Recursion in Recursion: Two-Level Nested Recursion for Length
  Generalization with Scalability
Jishnu Ray Chowdhury Cornelia Caragea
Binary Balanced Tree RvNNs (BBT-RvNNs) enforce sequence composition according
to a preset balanced binary tree structure. Thus, their non-linear recursion
depth is just $\log_2 n$ ($n$ being the sequence length). Such logarithmic
scaling makes BBT-RvNNs efficient and scalable on long sequence tasks such as
Long Range Arena (LRA). However, such computational efficiency comes at a cost
because BBT-RvNNs cannot solve simple arithmetic tasks like ListOps. On the
flip side, RvNNs (e.g., Beam Tree RvNN) that do succeed on ListOps (and other
structure-sensitive tasks like formal logical inference) are generally several
times more expensive than even RNNs. In this paper, we introduce a novel
framework -- Recursion in Recursion (RIR) to strike a balance between the two
sides - getting some of the benefits from both worlds. In RIR, we use a form of
two-level nested recursion - where the outer recursion is a $k$-ary balanced
tree model with another recursive model (inner recursion) implementing its cell
function. For the inner recursion, we choose Beam Tree RvNNs (BT-RvNN). To
adjust BT-RvNNs within RIR we also propose a novel strategy of beam alignment.
Overall, this entails that the total recursive depth in RIR is upper-bounded by
$k \log_k n$. Our best RIR-based model is the first model that demonstrates
high ($\geq 90\%$) length-generalization performance on ListOps while at the
same time being scalable enough to be trainable on long sequence inputs from
LRA. Moreover, in terms of accuracy in the LRA language tasks, it performs
competitively with Structured State Space Models (SSMs) without any special
initialization - outperforming Transformers by a large margin. On the other
hand, while SSMs can marginally outperform RIR on LRA, they (SSMs) fail to
length-generalize on ListOps. Our code is available at:
\url{https://github.com/JRC1995/BeamRecursionFamily/}.