Precision Dependent Expressivity of Neural Architectures

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2266 papers433 conceptsfrozen 2026-10-04

In theoretical computer science, we often treat neural networks as idealized mathematical functions operating on real numbers. Under these assumptions, architectures like the Transformer or Recurrent Neural Networks (RNNs) are frequently proven to be Turing complete—meaning they can, in principle, simulate any computer algorithm given enough depth or time On the Turing Completeness of Modern Neural Network Architectures.

However, there is a fundamental "reliability gap" between these infinite-precision proofs and the reality of modern hardware. Physical GPUs do not compute with real numbers; they use fixed-precision floating-point arithmetic (like FP16 or BF16). This shift from infinite to finite precision is not just a minor implementation detail—it fundamentally collapses the computational complexity class of the model.

The Precision Ceiling

The most significant insight across this research is that numerical precision acts as a hard ceiling on expressivity. William Merrill and others have demonstrated that while infinite-precision RNNs are Turing complete, their finite-precision counterparts are restricted to much simpler classes of formal languages.

For Transformers, this ceiling is even more specific. David Chiang proved that Transformers—whether using "hard" or high-precision "soft" attention—are limited to the complexity class DLOGTIME-uniform $TC^0$ Transformers in Uniform TC$^0$. In intuitive terms, this means a standard Transformer is computationally equivalent to a "shallow" boolean circuit. It can perform massive parallel lookups, but it cannot solve inherently serial problems, such as evaluating nested logic or checking if a graph is connected, in a single forward pass.

The Logical Sandwich

To understand exactly what these models can "understand," researchers use formal logic to create a "mathematical sandwich" of their capabilities. David Chiang, Peter Cholak, and Anand Pillay identified a specific logic called FOC[+; MOD] that acts as a tight bound for Transformer encoders Tighter Bounds on the Expressivity of Transformer Encoders.

Similarly, Jiaoda Li and Ryan Cotterell characterized fixed-precision Transformer language models as being equivalent to a fragment of linear temporal logic (LTL[P]) Characterizing the Expressivity of Transformer Language Models. These logical mappings reveal that without positional encodings or infinite precision, Transformers are "left-deterministic"—they can track state as they move through a sequence but fundamentally cannot handle tasks like parity checking or nested parentheses (Dyck languages) that require deeper recursion or counting.

Floating Point Hacks and Absolute Counting

Interestingly, the transition from idealized real numbers to practical floating-point numbers isn't always a downgrade. In some cases, the "messiness" of hardware arithmetic provides unique computational shortcuts.

Damian Heiman and colleagues discovered an "expressivity gap" where float-based models can actually outperform real-valued models at absolute counting Expressive Power of Graph Transformers via Logic. By leveraging hardware-specific behaviors like underflow—where a very small number multiplied repeatedly eventually snaps to exactly zero—a neural network can create a natural logic gate. This allows the model to count discrete elements (e.g., "there are exactly 5 nodes with this property"), a feat that is mathematically impossible for continuous, real-valued models which are limited to relative ratios.

Trading Time for Precision

If fixed precision limits a model to shallow $TC^0$ logic, how do Large Language Models (LLMs) solve complex reasoning tasks? The answer lies in expanding the "workspace" through sequence length.

The Reliability Gap in Practice

This research direction suggests that many "failures" in AI—such as a model's inability to maintain logical consistency over long sequences—may not be purely algorithmic. Instead, they may be inherent constraints of digital hardware. Gitta Kutyniok argues that the "reliability gap" in safety-critical AI stems from the fact that digital architectures encounter fundamental mathematical barriers when training with finite precision.

As we move toward more complex architectures like State-Space Models (SSMs) or Mamba, understanding these precision-based boundaries becomes critical. For instance, Adam Dankowiakowski showed that finite-precision rounding errors can destabilize the logical states of linear models like Mamba more easily than non-linear models like xLSTM Metric Automata Theory: A Unifying Theory of RNNs. Ultimately, the expressivity of an AI is a dialogue between its high-level architecture and the low-level bit-depth of the silicon it runs on.

Papers in this version

Showing 60 of 266 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 169 papers
  2. Version 1 · 2026-10-04 · 266 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_numerical_precision_constraints_0695e3e5,
  title = {numerical precision constraints},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/numerical-precision-constraints/rdr_0695e3e5a0e64c70a60feee080a59a96},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_precision_dependent_expressivity_of_neur_0695e3e5_v1,
  title = {Precision Dependent Expressivity of Neural Architectures},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/precision-dependent-expressivity-of-neural-architectures/rdr_0695e3e5a0e64c70a60feee080a59a96/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}