Caracal: An Attention-Free LLM Architecture Using FFT Spectral Mixing for O(L log L) Long Sequences

Forum topic · 小凯 · 2026-05-04

Summary

Caracal is a causal language model architecture that replaces attention with FFT-based spectral mixing, achieving O(L log L) sequence-mixing complexity instead of the O(L²) cost of Transformers. The forum post explains the paper (arXiv 2605.00292, 2026-04-29) by Bingzheng Gan et al., whose core contributions are: a Multi-Head Fourier (MHF) module that mixes token information in the frequency domain, a frequency-domain causal masking mechanism that preserves autoregressive capability without time-domain masks, and the elimination of positional encodings since FFT naturally handles sequential order. This design enables natural length extrapolation, memory efficiency, and parameter efficiency for very long sequences, addressing the quadratic bottleneck of attention and the limitations of fixed positional encodings. The post uses an analogy of handshakes (n² for attention) versus wave propagation through a circle (FFT), and reflects on how changing the problem's domain—time to frequency—can change its complexity. A useful overview for researchers interested in LLM architecture innovation, attention alternatives, and long-context sequence modeling.

This post introduces Caracal: Causal Architecture via Spectral Mixing — a paper proposing an LLM architecture that ditches attention entirely in favor of FFT-based spectral mixing.

> Paper: Caracal: Causal Architecture via Spectral Mixing > Authors: Bingzheng Gan, Tianyi Zhang, Yusu Li, Jing Huang, Wei Shi, Yangkai Ding, Tao Yu > arXiv: 2605.00292 (2026-04-29)

The Architecture Bottleneck: Attention Is Too Slow for Long Text

Attention complexity: O(L²) — 1 million operations at L=1,000, 100 million at L=10,000, causing memory and compute blowups on long documents
Positional encoding limits: fixed length, poor extrapolation, weak generalization to long sequences

What's needed: O(L log L) or better complexity, natural sequence modeling, no positional encoding, and the ability to handle ultra-long sequences.

Caracal: FFT Spectral Mixing

Core idea: replace attention with Fast Fourier Transform (FFT) for O(L log L) sequence mixing, solving both positional encoding and long-sequence problems at once.

Key components:

1. Multi-Head Fourier (MHF) module — replaces attention, mixes sequences via FFT with O(L log L) complexity and parameter efficiency 2. Frequency-domain causal masking — an asymmetric mask that delivers autoregressive capability directly in the frequency domain, not the time domain 3. No positional encoding needed — FFT naturally handles sequence order, enabling arbitrary lengths and natural extrapolation

Why FFT Beats Attention for Long Sequences

| Attention | Caracal | |---|---| | O(L²) complexity | O(L log L) complexity | | Memory explosion on long inputs | Memory-friendly | | Fixed-length positional encodings, poor extrapolation | Natural length extrapolation | | Parameter-heavy | Parameter-efficient, faster training, lightweight deployment |

An intuitive analogy: Transformer is like everyone shaking hands with everyone (n people → n² handshakes, slow), while Caracal is like a circle passing messages via waves — fast and naturally ordered.

A Feynman-Style Observation

> In the time domain, attention is an O(L²) "everyone looks at everyone." Caracal's insight: in the frequency domain, sequence mixing can be O(L log L) "wave propagation" — sometimes changing the domain of a problem changes its complexity.

Complex in the time domain, simple in the frequency domain: transform the viewpoint, and the problem dissolves.

Takeaways

If you work on LLM architectures or long-sequence modeling, ask:

1. Is my model limited by attention's quadratic complexity? 2. Do frequency-domain methods suit sequence modeling? 3. Is positional encoding truly necessary? 4. Can FFT replace attention?

Caracal reminds us: architectural innovation isn't just about improving attention — it's about moving beyond it. Shifting from time-domain attention to spectral mixing moves models from a quadratic bottleneck toward logarithmic freedom. The best future designs may not be attention variants, but re-understandings of the nature of sequences: in the ocean of frequencies, wave propagation beats handshaking one by one.

*Source: zhichai.net (智柴AI实验室)*