Caracal: An LLM Architecture Without Attention — FFT Spectral Mixing Achieves O(L log L) Long-Sequence Modeling

> 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 Texts"

When processing long documents, Transformers face two problems:

The attention dilemma:

• Attention complexity: O(L²)
• L = 1,000 → 1 million operations
• L = 10,000 → 100 million operations
• Long-text disaster

Limitations of positional encodings:

• Fixed length
• Hard to extrapolate
• Poor generalization to long sequences

What is needed:

• O(L log L) or better complexity
• Natural sequence modeling
• No positional encoding required
• Ability to handle very long sequences

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 simultaneously solving the positional encoding and long-sequence problems.

Technical design:

1. Multi-Head Fourier (MHF) module

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

2. Frequency-domain causal masking

• Enables autoregressive capability
• Asymmetric masking
• Causality implemented in the frequency domain
• Not a time-domain mask

3. No positional encoding needed

• FFT inherently handles sequences
• No extra positional information required
• Natural length extrapolation
• Arbitrary lengths

Three contributions:

• FFT 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 a message via waves
• Uses wave propagation
• Fast, with natural ordering

Why FFT Beats Attention for Long Sequences

Attention's problems:

• Quadratic complexity: O(L²)
• Infeasible for long sequences
• Memory explosion
• Slow computation
• Positional encoding constraints: fixed training length, poor 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 encoding, arbitrary length, natural extrapolation
• Parameter efficiency: fewer parameters than attention, faster training, lighter deployment

A Feynman-Style Observation: Sometimes the Answer Lies in Another Domain

Feynman said:

> "Knowing the name of something and truly understanding something are completely 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 beauty:

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

Takeaways

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

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

Caracal reminds us: architecture innovation lies not just 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-scale freedom. In the future of model architecture, the best design may not be an attention variant, but a re-understanding of the nature of sequences.

In the ocean of frequencies, wave propagation is more efficient than handshakes one by one.