Find+Replace Transformers

Find+Replace Transformers are a proposed architectural extension of the standard transformer model, designed to overcome a fundamental theoretical limitation: conventional transformers are not Turing complete, meaning there exist computational tasks they cannot perform regardless of scale or depth. By composing multiple transformer modules in a structured pipeline — one acting as a "find" operation to locate relevant patterns and another acting as a "replace" operation to modify or generate content based on those patterns — the architecture aims to emulate arbitrary computation in a way that a single transformer block cannot.

The core mechanism draws inspiration from string rewriting systems and symbolic computation. The "find" component identifies specific structures or conditions within an input representation, while the "replace" component applies a learned transformation conditioned on those findings. This decomposition allows the system to express iterative and conditional logic, which are prerequisites for Turing completeness. By chaining such find-replace steps, the model can in principle simulate any computable function, bridging the gap between neural network expressiveness and classical computation theory.

This matters for machine learning because many real-world tasks — multi-step reasoning, program synthesis, formal verification, and complex question answering — require forms of computation that go beyond pattern interpolation. Standard transformers handle these tasks imperfectly, often failing on out-of-distribution examples that require systematic rule application. An architecture with provable Turing completeness offers a theoretical guarantee that the representational bottleneck is removed, even if practical performance still depends on training dynamics and data.

Find+Replace Transformers were introduced in a 2024 ICLR submission by Shriyash Kaustubh Upadhyay and Etan Jacob Ginsberg. While the work remains primarily theoretical and has not yet seen widespread adoption, it contributes to a growing body of research exploring how transformer architectures can be augmented with more structured, programmable computation — a direction increasingly relevant as the field pushes toward models capable of robust, generalizable reasoning.