ChordMixer: A Scalable Neural Attention Model for Sequences with Different Length

Ruslan Khalitov, Tong Yu, Lei Cheng, Zhirong YangICLR 2023

Introduction

While the Transformer architecture dominates modern sequence modeling, its core attention mechanism struggles with long-form data due to two major flaws. First, it suffers from quadratic complexity: the computational cost grows with the square of the sequence length ($N^2$), making it nearly impossible to process massive sequences like entire genomes or long books. Second, it relies on rigid lengths: to process data in batches efficiently, researchers usually pad short sequences with zeros or "chunk" long ones into fixed-size windows. This either wastes massive amounts of computation on "empty" space or loses the long-range context necessary to understand the data.

ChordMixer is a novel neural network building block designed to solve these issues. It handles sequences of varying lengths—up to 1.5 million elements—with $O(N \log N)$ efficiency. By borrowing the "logarithmic hop" strategy from Peer-to-Peer (P2P) networking, it achieves a full receptive field without the quadratic memory costs or the need for wasteful padding and chunking.

The ChordMixer Architecture

The core innovation of ChordMixer is inspired by Chord, a protocol used in P2P distributed hash tables. In a Chord network, a node can find any other node in a network of size $N$ using only $\log_2 N$ hops by jumping in powers of two ($2^0, 2^1, 2^2, \dots$).

ChordMixer translates this routing strategy into a neural network architecture consisting of two alternating layers:

  1. The Rotate Layer: This is a non-parametric (no learnable weights) layer that shifts "tracks" or channels of the sequence by different scales corresponding to powers of two. It effectively moves information across the sequence at multiple resolutions.
  2. The Mix Layer: A simple, position-wise Multi-Layer Perceptron (MLP) that mixes the newly aligned information across channels at each position.
ChordMixer Routing Mechanism

By stacking $\log_2 N$ of these blocks, the model ensures that every output position has a "full receptive field"—meaning it has integrated information from every single input position. Because the rotation is a simple memory roll and the MLP is element-wise, the model is incredibly fast and memory-efficient.

Key Insights

  • Decentrality by Design: Unlike hierarchical models (like CNNs) where some nodes are "central" to the flow of information, ChordMixer is decentralized. Every position has a nearly equal chance to interact with every other position, which is vital for data like DNA where important signals aren't always local.
  • Full-Rank Processing: Many "efficient" Transformers achieve speed by using low-rank approximations of the attention matrix. The authors prove that ChordMixer is "full-rank," meaning it doesn't suffer from the information bottlenecks inherent in those approximations.
  • Zero Padding/Chunking: Because the number of blocks can vary based on the sequence length ($\log_2 N$), the model naturally handles variable lengths. In a batch, sequences simply pass through the number of blocks required for their specific length, avoiding the computational waste of zero-padding.

Evaluation and Key Results

The authors evaluated ChordMixer across several challenging domains, demonstrating extreme scalability and strong performance:

  • Extreme Scalability (The Adding Problem): ChordMixer successfully solved a synthetic regression task requiring the model to identify and sum two specific numbers in sequences of up to 1.5 million elements. Almost all other models (Transformer, Reformer, S4, etc.) either failed this task or ran out of memory.
  • Long Range Arena (LRA) Dominance: On the LRA benchmark—a standard test for efficient Transformers—ChordMixer outperformed all "X-former" variants. Most notably, it achieved 98.63% accuracy on PathfinderX, a notoriously difficult task where standard Transformers and many efficient variants typically fail to perform better than random guessing.
  • Biological Accuracy: In DNA taxonomy classification (identifying species from GenBank sequences ranging from 32 to over 447,000 base pairs), ChordMixer maintained stable performance (84-89% ROC-AUC) even as sequence lengths increased. Competitors saw significant performance drops on the longest sequences.
  • Document Classification: The model also proved effective at categorizing academic papers (up to 131,000 characters) by processing the text directly at the character level.

Limitations and Future Work

While ChordMixer excels at global information mixing, it does not assume any inherent locality. In domains like computer vision, where nearby pixels are highly correlated, this lack of an "inductive bias" for locality might mean the model requires more training data than a CNN or a standard Transformer to learn those local relationships.

Future work for the architecture could involve:

  1. Self-supervised pre-training: Using masked language modeling to help the model learn patterns in massive unlabeled datasets.
  2. Relative Position Information: Finding economical ways to re-introduce local context or relative positioning to further boost performance on tasks where order and proximity are paramount.

Summary updated

BibTeX
@inproceedings{khalitov2023chordmixer,
  author = {Ruslan Khalitov and Tong Yu and Lei Cheng and Zhirong Yang},
  title = {{ChordMixer: A Scalable Neural Attention Model for Sequences with Different Length}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
}
Figure