Why Transformers Fail at Modular Counting and Periodic Logic

20 concepts11 papers4 proposals

Modern sequence models exhibit a striking computational paradox. A Transformer can synthesize code, translate languages, and reason through complex hierarchical structures, yet it frequently fails at basic tasks like determining if a character appears an even or odd number of times in a string.

This blind spot is not a matter of training data scale or optimization tuning. Instead, it reflects a fundamental architectural limitation shared by Transformers and many gated recurrent networks: an inability to natively process modular arithmetic and periodic patterns. Understanding why this bottleneck exists requires looking at how these models aggregate information across time.

Why Attention Smooths Away Discrete Cycles

At the core of the Transformer architecture is the self-attention mechanism. To understand why it struggles with periodic logic, consider the classic parity problem (determining whether a specific token appears an even or odd number of times).

As Satwik Bhattamishra et al. demonstrate in On the Ability and Limitations of Transformers to Recognize Formal Languages, self-attention fundamentally operates as a weighted average over sequence elements. When a model computes attention weights, it normalizes them via a softmax function and uses them to scale the value vectors.

Averaging vs. Tracking Cycles:
Sequence:  [A, A, A, A, A]  (Count = 5, Odd)
Attention: [0.2, 0.2, 0.2, 0.2, 0.2] -> Smooths out the discrete step-by-step state changes.

Weighted averaging is excellent for capturing context and fuzzy semantic relationships, but it is structurally unsuited for tracking discrete, step-based periodic states. Parity tracking requires a strict, non-linear toggle mechanism ($0 \to 1 \to 0$). Averaging a set of representations across a sequence washes out this precise, step-by-step counting logic, especially as sequences grow longer. As a result, Anna Mészáros et al. found in Rule Extrapolation in Language Modeling: A Study of Compositional Generalization on OOD Prompts that standard Transformers often perform below chance level when evaluating regular languages that require tracking parity.

Magnitude Accumulation vs. Phase Transitions

The issue extends beyond self-attention to how neural networks represent numerical states. Standard real-valued architectures typically represent quantities by accumulating magnitude along a continuous vector space.

In Representing Unordered Data Using Complex-Weighted Multiset Automata, Justin DeBenedetto et al. point out that real-valued architectures fail at periodic or modular tasks because they lack an inherent mechanism to track cyclic states. When a model simply adds to a hidden state vector to count occurrences, it moves linearly through the state space. To solve a modular problem (like $x \pmod m$), the model must map this linear trajectory back onto a repeating cycle. Without specialized positional encodings or complex-valued representations that naturally model phase transitions, continuous networks struggle to maintain the boundaries between repeating cycles.

The Discontinuity of Wrap-Around Logic

This architectural limitation becomes a severe bottleneck when neural networks encounter modular arithmetic at scale, such as in cryptographic applications or abstract algebra.

In modular arithmetic, operations are bound by a modulus $M$. When a sum exceeds $M$, it "wraps around" to the beginning ($M-1 \to 0$). This wrap-around behavior introduces sharp mathematical discontinuities. Standard neural networks are smooth function approximators; they operate on the principle that a small change in the input should lead to a small change in the output. However, crossing a modular boundary means a tiny increment in the input causes a massive, discontinuous jump in the output.

Linear Addition:  10 -> 11 -> 12 -> 13 (Continuous, predictable trajectory)
Modulo 12 Math:   10 -> 11 ->  0 ->  1 (Discontinuous jump at the boundary)

This property severely limits the application of machine learning to cryptanalysis. For instance, the security of Post-Quantum Cryptography often relies on the Learning with Errors (LWE) problem. In studies attempting to use machine learning to break LWE, such as those by Cathy Yuanchen Li et al. in SALSA VERDE: a machine learning attack on LWE with sparse small secrets and Emily Wenger et al. in Benchmarking Attacks on Learning with Errors, neural networks were found to be effective only when the secrets were extremely sparse. When secrets are sparse, the underlying mathematical terms rarely cross the modular boundary. The moment the parameters scale and the math wraps around the modulus multiple times, standard Transformer architectures fail completely.

Similarly, Eshika Saxena et al. noted in Teaching Transformers Modular Arithmetic at Scale that models experience severe optimization hurdles when sums wrap around large prime moduli. This performance gap is also visible in symbolic algebra; Hiroshi Kera et al. showed in Gröbner basis computation via learning that Transformers can successfully identify the symbolic structure of polynomial ideals over infinite fields, but their accuracy plummets when forced to compute exact numerical coefficients over finite fields due to the required modular arithmetic.

Formal Language Theory and State Space Models

To formalize this limitation, researchers often turn to the Chomsky hierarchy and automata theory. In What Makes Instruction Learning Hard? An Investigation and a New Challenge in a Synthetic Environment, Kyle Richardson et al. isolated instruction-following failures to tasks requiring "non-star-free" regular languages—the exact class of languages that contain periodic logic like counting and parity.

This is not a weakness unique to standard attention. Kazuki Irie et al. confirmed in Practical Computational Power of Linear Transformers and Their Recurrent and Self-Referential Extensions that Linear Transformers also fail to recognize non-star-free regular languages because they cannot track cumulative state changes across a sequence.

Even modern State Space Models (SSMs), designed to replace Transformers on long-context tasks by acting as continuous-time recurrent systems, inherit this flaw. In On the Expressiveness of State Space Models via Temporal Logics, Eric Alsmann et al. mathematically mapped the expressivity of SSMs. They proved that diagonal-gated architectures with fixed precision are fundamentally incapable of recognizing simple periodic patterns or modular predicates (such as distinguishing between even and odd sequence positions). A diagonal matrix scales hidden states independently along each dimension, meaning it can decay or amplify signal magnitude but cannot rotate states to form a discrete cycle. To track modular predicates, an architecture requires time-invariant transition matrices capable of acting as cyclic permutation counters.

Designing Around the Torus

To overcome this bottleneck, researchers are exploring architectural modifications that shift from linear vector spaces to periodic geometries.

Because modular arithmetic naturally maps to the geometry of a circle or a multi-dimensional ring (a discrete torus), forcing a model to process these problems using standard linear embeddings creates an unnecessary representation gap. In Salsa Fresca: Angular Embeddings and Pre-Training for ML Attacks on Learning With Errors, Emily Wenger et al. bypassed this scaling hurdle by introducing angular embeddings. By natively mapping the input data onto a periodic coordinate system, the network no longer has to learn how to approximate the discontinuous "wrap-around" logic of the modulus; the geometry of the network's representation space matches the geometry of the math itself.

Until such periodic inductive biases are natively integrated into foundational models, tracking cycles, parity, and modular boundaries will remain a fundamental boundary line for standard sequence architectures.

Key Foundational Work

What Makes Instruction Learning Hard? An Investigation and a New Challenge in a Synthetic Environment (2022) — contributed 3 concept elements to this direction.
On the Ability and Limitations of Transformers to Recognize Formal Languages (2020) — contributed 3 concept elements to this direction.
Representing Unordered Data Using Complex-Weighted Multiset Automata (2020) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_modular_counting_limitation_5f4475f6,
  title = {modular counting limitation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/modular-counting-limitation/rdr_5f4475f60a9540f8b1d3c3e671fc34b4},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_modular_counting_limitation_5f4475f6_v1,
  title = {modular counting limitation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/modular-counting-limitation/rdr_5f4475f60a9540f8b1d3c3e671fc34b4/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake