# Theoretical Analysis of Hierarchical Language Recognition and Generation by Transformers without Positional Encoding

arXiv: https://arxiv.org/abs/2410.12413 · HTML: https://mlsanity.com/paper/2410.12413/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 46 references that are in the map.
- First posted on arXiv 16 Oct 2024.

## Builds on (most cited first, 9 of 9)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [Pointer Sentinel Mixture Models](https://mlsanity.com/paper/1609.07843/) (2016)
- [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021)
- [NormFormer: Improved Transformer Pretraining with Extra Normalization](https://mlsanity.com/paper/2110.09456/) (2021)
- [Average-Hard Attention Transformers are Constant-Depth Uniform Threshold Circuits](https://mlsanity.com/paper/2308.03212/) (2023)
- [Transformers Generalize Linearly](https://mlsanity.com/paper/2109.12036/) (2021)

## Built on by (most cited first, 1 of 1)

- [Dissociating Decodability and Causal Use in Bracket-Sequence Transformers](https://mlsanity.com/paper/2604.22128/) (2026)

## Abstract (arXiv)

In this study, we provide constructive proof that Transformers can recognize and generate hierarchical language efficiently with respect to model size, even without the need for a specific positional encoding. Specifically, we show that causal masking and a starting token enable Transformers to compute positional information and depth within hierarchical structures. We demonstrate that Transformers without positional encoding can generate hierarchical languages. Furthermore, we suggest that explicit positional encoding might have a detrimental effect on generalization with respect to sequence length.