Research map / Architectures and efficiency / Attention and transformers
Training Neural Networks as Recognizers of Formal Languages
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Trains RNNs, LSTMs, and causally-masked transformers directly as binary string classifiers on 18 formal languages across the Chomsky hierarchy, introducing the FLaRe benchmark and an efficient length-controlled sampler for regular languages.
Problem
Empirical tests of neural network expressivity claims (formal language theory) typically use language modeling or string-to-string transduction, which does not match the recognizer definitions the theory is about; a recognition-based setup is needed.
Approach
Train networks as binary recognizers using positive samples from length-controlled sampling (binning semiring for regular languages) and adversarial negatives made by random edits of positives, with optional language-modeling and next-symbol prediction auxiliary losses.
Key results
- RNN and LSTM outperform the transformer on most languages; in expressivity experiments the transformer is never best except by a hair on Binary Multiplication.
- With long validation sets, RNN and LSTM reach 100% test accuracy on Even Pairs, Repeat 01, Parity, Modular Arithmetic, and First; all architectures are limited to regular languages plus Majority.
- Auxiliary losses help in isolated cases but no single loss uniformly improves performance; recognition-only is the most frequent best loss.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use an RNN or LSTM instead of a transformer | Neural recognizers · Formal-language tests, length [0, 500] | accuracy | Helped |
| Add next-symbol prediction loss (ablation) | RNN recognizer · Even Pairs | accuracy | Helped |
| Add language-modeling loss (ablation) | LSTM recognizer · Parity | accuracy | Hurt |
| Add auxiliary language-modeling and/or next-symbol prediction losses (ablation) | Neural recognizers · Formal-language tests | accuracy | Mixed |
| Use recognition loss alone rather than an auxiliary-loss variant (ablation) | Neural recognizers · Formal-language tests | accuracy | Helped |
Surprising findings
- The transformer struggles on Dyck-(2,3) despite known constructions showing it can recognize bounded Dyck languages.
- Using larger models, more adversarial examples, and more data did not fix the Cycle Navigation accuracy ceiling.
Limitations
- Rejection-based negative sampling is impractical when the complement of the language is small.
- Results limited to 5-layer models of about 64k parameters with length range 0-40 training.
Experimental setup
Datasets: FLaRe (generated from 18 formal languages)
Benchmarks: FLaRe
Metrics: accuracy cross-entropy length generalization accuracy
Baselines: MLRegTest Delétang et al. string-to-string transduction setup Weiss et al. 2018 perturbation negatives
Builds on: binning semiring weight pushing MLRegTest
Closest papers by meaning
- How Transformers Learn Regular Language Recognition: A Theoretical Study on Training Dynamics and Implicit Bias (ICML 2025 · similarity 0.88)
- In-Context Language Learning: Architectures and Algorithms (ICML 2024 · similarity 0.87)
- Neural-Symbolic Recursive Machine for Systematic Generalization (ICLR 2024 · similarity 0.87)
- Implicit Language Models are RNNs: Balancing Parallelization and Expressivity (ICML 2025 · similarity 0.87)
- Separations in the Representational Capabilities of Transformers and Recurrent Architectures (NeurIPS 2024 · similarity 0.86)
- Language Models Are Implicitly Continuous (ICLR 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.