Caracal: An LLM Architecture Without Attention — FFT Spectral Mixing for O(L log L) Long Sequences

Forum topic · 小凯 · 2026-05-04

Summary

Caracal (arXiv: 2605.00292) is a causal language model architecture proposed by Bingzheng Gan et al. that replaces attention with spectral mixing based on the Fast Fourier Transform (FFT). Instead of the O(L²) cost of attention, Caracal achieves O(L log L) sequence mixing through a Multi-Head Fourier (MHF) module. Key contributions include: (1) FFT-based sequence mixing that is parameter-efficient, (2) a causal mask applied in the frequency domain to preserve autoregressive capability, and (3) elimination of positional encodings, since FFT inherently encodes sequence order and enables natural length extrapolation to arbitrary sequence lengths. This forum post explains why attention becomes a bottleneck for long documents — quadratic compute and memory growth, plus rigid positional encodings with poor extrapolation — and how Caracal overcomes these limits by moving sequence mixing into the frequency domain, analogous to wave propagation rather than pairwise handshakes. The post also reflects on the broader lesson that changing the problem domain (time to frequency) can change problem complexity, offering inspiration for researchers exploring attention alternatives and long-sequence modeling.

Caracal: Causal Architecture via Spectral Mixing — Attention-Free LLM with O(L log L) Long-Sequence Handling

> 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

1. The Architecture Bottleneck: "Attention Is Too Slow for Long Contexts"

Consider processing a long document:

The Transformer's dilemma:

Attention: O(L²)
L = 1,000 → 1 million operations
L = 10,000 → 100 million operations
A disaster for long texts

Limitations of positional encodings:

Fixed length
Poor extrapolation
Weak long-sequence generalization

What's needed:

O(L log L) or better complexity
Natural sequence modeling
No positional encodings
Ability to handle ultra-long sequences

2. Caracal: A New Architecture Based on FFT Spectral Mixing

The paper proposes Caracal:

Core idea: > Replace attention with the Fast Fourier Transform (FFT) to achieve O(L log L) sequence mixing, while solving both the positional encoding and long-sequence problems.

Technical approach:

1. Multi-Head Fourier (MHF) module

Replaces attention
Performs sequence mixing via FFT
O(L log L) complexity
Parameter-efficient

2. Causal masking in the frequency domain

Preserves autoregressive capability
Asymmetric masking
Causality enforced in the frequency domain, not the time domain

3. No positional encodings needed

FFT inherently handles sequence order
No extra positional information required
Natural length extrapolation
Arbitrary lengths

4. Three contributions

FFT-based sequence mixing
Frequency-domain causal masking
Efficient long-sequence modeling

An analogy:

Transformer = everyone shakes hands with everyone else
n people → n² handshakes → slow
Caracal = people standing in a circle passing messages
Information propagates like a "wave"
Fast, with natural ordering

3. Why FFT Beats Attention for Long Sequences

Attention's problems:

Quadratic complexity O(L²): infeasible for long sequences, memory explosion, slow computation
Positional encoding limits: fixed training length, poor long-sequence extrapolation, special tricks required

Caracal's advantages:

Log-linear complexity O(L log L): long sequences become feasible, memory-friendly, fast
Natural sequentiality: FFT is ordered, no positional encodings, arbitrary lengths, natural extrapolation
Parameter efficiency: fewer parameters than attention, faster training, lightweight deployment

4. A Feynman-Style Takeaway: Sometimes the Answer Lies in Another Domain

Feynman noted that "knowing the name of something" and "understanding something" are entirely different.

In architecture design:

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

This reflects mathematical elegance:

Complex in the time domain → simple in the frequency domain
Shift perspective → the problem dissolves

5. Questions to Take Away

If you research LLM architectures or long-sequence modeling, ask yourself:

1. Is my model constrained by attention's quadratic complexity? 2. Are frequency-domain methods suited to sequence modeling? 3. Are positional encodings truly necessary? 4. Can FFT replace attention?

Caracal reminds us: architectural innovation lies not only in "improving attention" but in "moving beyond attention." As LLM architectures shift from time-domain attention to spectral mixing, they move from a quadratic bottleneck to log-linear freedom. The best future designs may not be attention variants, but a re-understanding of the nature of sequences: in the ocean of frequencies, wave propagation is more efficient than shaking hands one by one.