Complex-valued Transformers process signals whose meaning lives partly in phase, such as audio spectra, radio waveforms, and rotary position codes. They are routinely described as paying a "complex tax": a complex multiply costs four real multiplies, autograd splits every tensor into real and imaginary parts, and the authors of these models list the constant-factor overhead as a main limitation. This note argues that much of that tax is self-inflicted. Most published complex attention layers score a query against a key using only the real part of the complex inner product. That real part is exactly an ordinary dot product between real vectors of twice the length. Such layers are therefore real attention in disguise. They inherit both the known fast algorithms and the known hardness results for real attention, and they can run on standard fused real kernels at about 2× rather than 4× cost.
Only one variant is computationally new. In it the attention weight itself is complex, with a magnitude set by the real part of the inner product and a phase set by the imaginary part, so that values from different positions can interfere. We call this phase-carrying attention. The proposal has three parts. We prove where its easy and hard regimes lie, with separate bounds on magnitude and phase. We build a fused GPU kernel for it. We then test on the complex-signal benchmarks used by prior work whether the extra phase ever buys accuracy worth its measured cost.
Core Claim
Write a complex query as $q = q_r + i q_i$ and a complex key as $k = k_r + i k_i$, each with $d$ complex coordinates. Stack each into a real vector of length $2d$, written $a = [q_r; q_i]$ and $b = [k_r; k_i]$. Let $J$ be the fixed real matrix that multiplies a stacked vector by $i$. Then $\mathrm{Re}(q^H k) = a^\top b$ and $\mathrm{Im}(q^H k) = a^\top J b$. Phase-carrying attention computes, for query $i$ and keys $j$,
$$ o_i = \frac{\sum_j e^{\,a_i^\top b_j}\, e^{\,\mathrm{i}\, a_i^\top J b_j}\; v_j}{\sum_j e^{\,a_i^\top b_j}}, $$
where $v_j$ is a complex value vector. The normalizer is the sum of weight magnitudes, so the weights reduce to ordinary softmax when the phase term is dropped.
Our claim has three parts. First, any complex attention that uses only $\mathrm{Re}(q^H k)$ is equivalent to real attention with head dimension $2d$ and structured projections. Its computational complexity is therefore exactly that of real attention: the entry-bound phase transition of Fast Attention Requires Bounded Entries applies with the entry bound $B$ replaced by the largest real or imaginary entry. Second, phase-carrying attention has two separate control parameters: the magnitude bound $B$ on $a^\top b$ and the phase range $T = \max |a^\top J b|$. We expect almost-linear time ($n^{1+o(1)}$ for context length $n$) when both $B^2$ and $T$ are $o(\log n)$ with $d = O(\log n)$. The reasoning is that the magnitude factor needs the low-degree Taylor approximation of prior work, while the oscillating factor $e^{\mathrm{i}t}$ on $|t| \le T$ needs a Chebyshev approximation of degree about $T + \log n$. The product of the two stays low-rank. Third, quadratic hardness for large $B$ is inherited directly, since setting all imaginary parts to zero recovers real attention.
The genuinely open regime is flat magnitude with wide phase: $B$ small, $T$ large. There, every weight has nearly equal size and only the phases differ.
Research Program
The theory work starts from three papers whose methods we reuse. Fast Attention Requires Bounded Entries frames attention as kernel density estimation and proves the $\sqrt{\log n}$ threshold. Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform extends the polynomial method to rotary position embeddings, using Toeplitz structure and fast Fourier transforms, with matching hardness. Subquadratic Algorithms and Hardness for Attention with Any Temperature gives reductions from the orthogonal-vectors problem and the dimension-dependent hardness wall.
Our contrast with this group is specific. All three study real-valued weights, where error cancellation between terms cannot occur. In phase-carrying attention, terms with opposite phase can cancel. We will prove the upper bound for the full complex kernel $\exp(a^\top (I + \mathrm{i}J) b)$, including the rotary-position case, by combining the Toeplitz construction with the complex kernel.
For the flat-magnitude regime we pursue two concrete targets. The first is an upper bound by sampling. With equal magnitudes, uniform sampling of keys gives additive error $\varepsilon$ with $O(\log n / \varepsilon^2)$ samples per query. Constant-accuracy phase-only attention is therefore easy. The second is a reduction from orthogonal vectors for inverse-polynomial error, which is the error level at which existing hardness results are stated. Either outcome is informative. A hardness proof would show that phase oscillation alone recreates the quadratic wall without any magnitude blowup. An algorithm would show that the wall really is about magnitude.
We also test Gap 3 of the file and answer it negatively. Splitting a head into $d$ one-dimensional complex planes does not lower the effective dimension, because the scores still sum over all $2d$ real coordinates.
The systems work builds one kernel. Because the normalizer depends only on $a^\top b$, the running-maximum normalization trick used by FlashAttention-style kernels carries over unchanged. The kernel computes two score tiles, $QK^\top$ and $QJK^\top$, in the same pass and accumulates complex values without ever materializing complex tensors in autograd. We will report cost per head relative to real attention at dimension $d$, and expect roughly 2–3×.
Finally, we will log the empirical $B$ and $T$ of trained complex Transformers to see which regime real models occupy.
Baselines
The naive reference point is complex attention implemented the way prior work describes it. Complex Transformer: A Framework for Modeling Complex-Valued Sequence decomposes complex attention into separate real matrix products and replaces softmax with min-max normalization. We reimplement it in standard autograd with its own normalization and also with softmax normalization. We report task accuracy, wall-clock time, peak memory, and multiply-accumulate operations. The relevant reported numbers are 74.22% average precision on MusicNet and 59.94% accuracy on the WI-FI IQ classification task. Beating this baseline means matching that accuracy within noise at lower measured latency and memory.
The strongest competitor on the efficiency question is a concatenated real Transformer running fused real attention at matched FLOPs and matched parameter count. The same paper reports this baseline at 71.30% on MusicNet and 57.57% on IQ. The evidence that it can be enough comes from Rethinking Complex-Valued Deep Neural Networks for Monaural Speech Enhancement. That study found that a real-valued DCCRN needed 4.84 G multiply-accumulate operations against 14.38 G for the complex version, at nearly identical STOI, WB-PESQ and SI-SDR (standard intelligibility, perceptual-quality and distortion scores). We give the concatenated baseline the same tuning budget, measured in sweeps per model, as every other arm.
On language modeling, the strongest existing complex-attention method is ComplexFormer: Disruptively Advancing Transformer Inference Ability via Head-Specific Complex Vector Attention. It reports 34.2 perplexity on WikiText-103 and 21.3% on GSM8K, but no baseline numbers are found on Lacuna for its comparisons. We therefore retrain both it and a rotary-position real Transformer under one budget.
Two ablations isolate the key ingredient. The first keeps complex-structured projections but scores with $\mathrm{Re}(q^H k)$ only, running on the real kernel. The gap between this arm and the concatenated baseline measures what the complex structure of the projections contributes. The gap between this arm and full phase-carrying attention measures what the phase term contributes.
Why not just…?
Why not just concatenate real and imaginary parts and use standard attention? This is the real threat. On speech enhancement it already matched complex models at a third of the compute (Rethinking Complex-Valued Deep Neural Networks for Monaural Speech Enhancement). The roughly 3-point MusicNet advantage of the complex model could come from its constrained projections rather than from anything complex about attention. Our ablation separates these explanations. If phase-carrying attention does not beat the real-scoring ablation at matched latency, the honest conclusion is that complex attention should be compiled to real attention, and we will report that.
Why not just use rotary position embeddings? Rotary embeddings are a special case of phase-carrying attention in which the phase depends only on position and the weights end up real. Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform already settles their complexity. EulerFormer: Sequential User Behavior Modeling with Complex Vector Attention and ComplexFormer report gains from content-dependent phases, for example a 9.93% NDCG@10 improvement on MovieLens-1M, but they report it as a relative gain without absolute scores. The rotary-position arm on WikiText-103 tests whether those gains survive equal compute.
Why not just use linear attention or low-order Taylor features? On The Computational Complexity of Self-Attention shows that degree-$p$ features cost $d^p$, which blows up when entries are large. The phase factor adds a second polynomial whose degree grows with $T$. Our logged $B$ and $T$ values will show whether trained models sit in the regime where such features are cheap. If they do, a Taylor-feature arm is added.
Why not just run FlashAttention on the doubled vector? For real-part scoring, that is exactly what our equivalence licenses, and we adopt it. It does not handle complex weights, whose numerator is not a softmax. That case is what the new kernel covers.
Proposed Experiments
The benchmarks are MusicNet transcription measured by average precision, the IQ classification task if the non-public data can be obtained (otherwise it is omitted), VCTK+DEMAND speech enhancement, where DCHT: Deep Complex Hybrid Transformer for Speech Enhancement reports PESQ 3.41 and STOI 0.954, and WikiText-103 perplexity at context lengths from 1k to 32k. ComplexFormer stopped at 4096 tokens.
The decisive checks are three. The first is the latency ratio of each complex arm to real attention as context grows. The second is whether real-scoring complex attention on the real kernel matches the naive complex baseline's accuracy at under half its time. The third is whether phase-carrying attention beats the real-scoring ablation by more than seed variance on any benchmark.
On the theory side, the measured $B$ and $T$ distributions of trained models, set against the proven thresholds, tell us whether hardness is a practical concern or only a worst case.
References
- Fast Attention Requires Bounded Entries
- Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform
- Subquadratic Algorithms and Hardness for Attention with Any Temperature
- Complex Transformer: A Framework for Modeling Complex-Valued Sequence
- Rethinking Complex-Valued Deep Neural Networks for Monaural Speech Enhancement
- ComplexFormer: Disruptively Advancing Transformer Inference Ability via Head-Specific Complex Vector Attention
- EulerFormer: Sequential User Behavior Modeling with Complex Vector Attention
- On The Computational Complexity of Self-Attention
- DCHT: Deep Complex Hybrid Transformer for Speech Enhancement