Barriers to Discrete Reasoning with Transformers: A Survey Across Depth, Exactness, and Bandwidth (2026.eacl-long)
Copied to clipboard
Michelle Yuan, Weiyi Sun, Amir H. Rezaeian, Jyotika Singh, Sandip Ghoshal, Yao-Ting Wang, Miguel Ballesteros, Yassine Benajiba
| Challenge: | despite advances in transformers, their theoretical limitations in discrete reasoning remain a critical open problem. |
| Approach: | They synthesize recent advances from three theoretical perspectives to clarify structural and computational barriers transformers face when performing symbolic computations. |
| Outcome: | The proposed models excel at pattern matching and interpolation, but they face bottlenecks in communication and depth constraints. |
Similar Papers
Unravelling the Logic: Investigating the Generalisation of Transformers in Numerical Satisfiability Problems (2025.acl-long)
Copied to clipboard
| Challenge: | Transformer models exhibit minimal scale and noise invariance, along with limited vocabulary and number invariancy. |
| Approach: | They probe the generalisation prowess of Transformer models with respect to the hitherto unexplored domain of numerical satisfiability problems. |
| Outcome: | The proposed models exhibit minimal scale and noise invariance, along with limited vocabulary and number invariancy. |
Circuit Complexity Bounds for RoPE-based Transformer Architecture (2025.emnlp-main)
Copied to clipboard
| Challenge: | Recent studies provide the circuit complexity bounds to Transformer-like architectures. position embedding has emerged as a crucial technique in modern large language models. |
| Approach: | They propose to use position embedding to improve Transformer-like architectures by analyzing their circuits and analyzing the results. |
| Outcome: | The proposed model is able to solve canonical tasks without embedding positional information. |
The Parallelism Tradeoff: Limitations of Log-Precision Transformers (2023.tacl-1)
Copied to clipboard
| Challenge: | Existing work on transformers established their Turing completeness, albeit with assumptions like infinite precision and arbitrarily powerful feedforward subnets. |
| Approach: | They propose to simulate transformers whose arithmetic precision is logarithmic in the number of input tokens by constant-depth logspace-uniform threshold circuits. |
| Outcome: | The proposed model emerges from the transformer architecture’s high parallelizability, suggesting a potential inherent weakness of the scaling paradigm. |
Saturated Transformers are Constant-Depth Threshold Circuits (2022.tacl-1)
Copied to clipboard
| Challenge: | Recent work shows that transformers with hard attention are limited in power, but hard attention is a strong assumption. |
| Approach: | They propose a generalization of hard attention that captures attention patterns in transformers with saturated attention. |
| Outcome: | The proposed generalization of hard attention more closely captures the attention patterns learnable in practical transformers. |
Identifying the limits of transformers when performing model-checking with natural language (2023.eacl-main)
Copied to clipboard
| Challenge: | Recent studies have focused on transformer models’ ability to perform reasoning on text, but the above question has not been adequately answered. |
| Approach: | They investigated the problem of model-checking with natural language to determine whether transformers can comprehend logical semantics in natural language. |
| Outcome: | The proposed model-checking problem is suited to address this issue but is untouched in natural language inference research. |
On the Ability and Limitations of Transformers to Recognize Formal Languages (2020.emnlp-main)
Copied to clipboard
| Challenge: | Existing studies on LSTMs have not revealed their ability to model syntactic properties. |
| Approach: | They propose to build a Transformers model for a subclass of counter languages and find that their learning mechanism strongly correlates with their construction. |
| Outcome: | The proposed model generalizes well on counter languages and its learned mechanism correlates with it. |
A Symbolic Framework for Evaluating Mathematical Reasoning and Generalisation with Transformers (2024.naacl-long)
Copied to clipboard
| Challenge: | evaluating the generalisability of Transformers to out-of-distribution mathematical reasoning problems is a challenge for many open-source models. |
| Approach: | They propose a method for generating and perturbing detailed derivations of equations at scale, aided by a symbolic engine, and compare their results to sequence classification tasks. |
| Outcome: | The proposed framework outperforms GPT-4, GPT-3.5 and a canon of fine-tuned BERT models in classification tasks . perturbations to input reasoning can reduce their performance by up to 80 F1 points . |
Can Transformers Reason in Fragments of Natural Language? (2022.emnlp-main)
Copied to clipboard
| Challenge: | Recent work on natural language inference has identified two strands of research . |
| Approach: | They investigate whether neural networks have acquired logical principles from natural language . they use transformer-based models to detect valid inferences in controlled fragments of natural language. |
| Outcome: | The proposed model overfits to superficial patterns in the data rather than acquiring the logical principles governing reasoning in natural language fragments. |
SparseFlow: Accelerating Transformers by Sparsifying Information Flows (2024.acl-long)
Copied to clipboard
| Challenge: | SparseFlow is an efficient method to sparsify the dense information flows within transformers. |
| Approach: | They propose a method to sparsify the dense pathways of token representations across all transformer blocks by parameterizing them to be sparse. |
| Outcome: | The proposed method reduces computational costs by half on average without compromising task accuracy. |
Understanding and Overcoming the Challenges of Efficient Transformer Quantization (2021.emnlp-main)
Copied to clipboard
| Challenge: | Recent advances in transformer quantization have shown remarkable improvement in many Natural Language Processing tasks and beyond. |
| Approach: | They propose a novel quantization scheme for transformers that can be quantized to ultra-low bit-widths, leading to significant memory savings with a minimum accuracy loss. |
| Outcome: | The proposed methods achieve state-of-the-art results on the GLUE benchmark using BERT, while preserving memory and accuracy. |