Fibottention: Inceptive Visual Representation Learning with Diverse Attention Across Heads

1. Problem Statement

Vision Transformers (ViTs) and their variants have achieved state-of-the-art performance in visual tasks but face two critical limitations:

1. Quadratic Computational Complexity: The standard Multi-Head Self-Attention (MHSA) mechanism computes $O(N^2)$ interactions between $N$ tokens, making it computationally prohibitive for high-resolution images or long video sequences.
2. Data Efficiency: ViTs typically require massive amounts of training data to perform well, often underperforming in low-data regimes compared to Convolutional Neural Networks (CNNs).

Existing sparse attention mechanisms (e.g., sliding windows, random attention, Top-k) attempt to reduce complexity to $O(N)$ or $O(N \log N)$ but often degrade model performance. They frequently rely on uniform sparsity patterns across all attention heads or fail to capture necessary global context, leading to a trade-off where efficiency gains come at the cost of accuracy.

2. Methodology: Fibottention

The authors propose Fibottention, a novel, deterministic, and non-adaptive sparse attention mechanism designed to replace standard MHSA. Its core innovation lies in using structured sparsity patterns derived from the Wythoff array and Fibonacci sequences to create diverse, complementary attention maps across different heads.

Key Technical Components:

• Wythoff Array & Generalized Fibonacci Sequences:
  • Instead of using fixed or random masks, Fibottention assigns a unique generalized Fibonacci sequence to each attention head $i$.
  • These sequences are derived from the Wythoff array, a mathematical structure where each positive integer appears in exactly one row. This ensures that the "dilation" (distance between attended tokens) patterns across heads are non-overlapping and cover the integer space efficiently.
  • For head $i$, the support set $\Omega_i$ consists of token pairs $(j, k)$ where the distance $|j-k|$ belongs to the $i$-th Fibonacci sequence, bounded by a window size $w_i$.
• Inceptive Diversity (Head-wise Complementarity):
  • Inspired by Inception modules in CNNs, Fibottention enforces diversity across heads. Each head focuses on different scales of interactions (local vs. global) based on its specific Fibonacci sequence.
  • The window size $w_i$ for each head is linearly interpolated between a minimum ($w_{min}$) and maximum ($w_{max}$) bound, further diversifying the receptive fields.
• Modified Wythoff Variant:
  • For tasks requiring stronger local interactions (e.g., robotics, video), a "Modified Wythoff" variant is introduced. It includes the two immediate predecessors in the Fibonacci recurrence, slightly increasing local connectivity while maintaining the overall sparse structure.
• Complexity Reduction:
  • By restricting attention to these specific diagonal offsets, the computational complexity is reduced from $O(N^2)$ to $O(N \log N)$.
  • The method is non-adaptive, meaning the sparsity pattern is fixed and does not require learning a mask, eliminating the overhead associated with adaptive sparse attention methods.

3. Key Contributions

1. Novel Sparse Mechanism: Introduction of Fibottention, the first sparse attention mechanism to systematically utilize Wythoff array-derived Fibonacci sequences to create complementary, diverse sparsity patterns across attention heads.
2. Theoretical Guarantees: Proof that the mechanism achieves $O(N \log N)$ time complexity while ensuring that the union of all head support sets covers a maximal number of relevant token interactions with minimal overlap.
3. Inductive Bias for Visual Data: The design inherently promotes multi-scale feature aggregation. By removing the main diagonal (self-attention) in many cases and focusing on structured offsets, it reduces redundancy and forces the model to learn more disentangled representations.
4. Drop-in Replacement: Fibottention is designed as a drop-in replacement for standard MHSA layers in existing Transformer architectures (ViT, Swin, ConViT, etc.) without requiring architectural redesign.

4. Experimental Results

The authors evaluated Fibottention across image classification, video understanding, and robot learning tasks.

• Image Classification (CIFAR-10/100, Tiny-ImageNet, ImageNet-1K):
  • Small/Medium Datasets: Fibottention significantly outperforms dense ViT baselines and other sparse methods (BigBird, Longformer, Top-k) on CIFAR-10/100 and Tiny-ImageNet. For example, on CIFAR-10, it achieved 91.8% accuracy vs. 84.2% for standard ViT-B, while using only ~2% of the pairwise interactions.
  • Large Datasets: On ImageNet-1K, it achieves performance on-par with dense ViT-B (75.5% vs. 75.9%) while reducing computational cost by ~98%.
• Video Understanding (TimeSformer):
  • On the Toyota Smarthome and NUCLA datasets, Fibottention (Modified Wythoff variant) improved Top-1 accuracy over standard TimeSformer and BigBird, demonstrating its ability to capture spatiotemporal dependencies efficiently.
• Robot Learning (Behavioral Cloning):
  • In robot manipulation tasks (Lift, Can, PushT), Fibottention achieved the highest average task completion rates, outperforming both dense ViT and BigBird baselines.
• Efficiency:
  • Across all experiments, Fibottention utilized only 2% to 6% of the token interactions required by dense MHSA, resulting in substantial FLOP savings (up to 48% reduction in total inference FLOPs for high-resolution inputs).
• Robustness & Diversity Analysis:
  • Head Diversity: Metrics showed Fibottention heads have significantly higher feature diversity (Frobenius distance) compared to other sparse methods, confirming the "Inceptive" design.
  • Robustness: Models trained with Fibottention showed superior robustness against image corruptions (noise, blur, weather) compared to dense counterparts.

5. Significance

• Bridging the Efficiency-Accuracy Gap: Fibottention challenges the conventional wisdom that sparse attention must sacrifice accuracy for speed. It demonstrates that structured, diverse sparsity can actually enhance representation learning, particularly in data-constrained regimes.
• Scalability: The $O(N \log N)$ complexity makes it a viable candidate for next-generation Transformers processing billions of tokens (e.g., high-resolution video, long-context reasoning) where $O(N^2)$ is infeasible.
• Inductive Bias: The work highlights the importance of designing attention mechanisms with specific inductive biases (multi-scale, non-redundant) rather than relying solely on data-driven learning to discover sparse patterns.
• Generalizability: The method's success across diverse domains (static images, video, robotics) suggests it is a fundamental improvement to the Transformer architecture rather than a domain-specific hack.

In conclusion, Fibottention offers a mathematically grounded, efficient, and high-performing alternative to dense self-attention, leveraging number theory (Wythoff/Fibonacci) to optimize the trade-off between computational cost and representational capacity.