Extracting Finite State Machines from Transformers
<|reference_start|>Extracting Finite State Machines from Transformers: Fueled by the popularity of the transformer architecture in deep learning, several works have investigated what formal languages a transformer can learn. Nonetheless, existing results remain hard to compare and a fine-grained understanding of the trainability of transformers on regular languages is still lacking. We investigate transformers trained on regular languages from a mechanistic interpretability perspective. Using an extension of the $L^*$ algorithm, we extract Moore machines from transformers. We empirically find tighter lower bounds on the trainability of transformers, when a finite number of symbols determine the state. Additionally, our mechanistic insight allows us to characterise the regular languages a one-layer transformer can learn with good length generalisation. However, we also identify failure cases where the determining symbols get misrecognised due to saturation of the attention mechanism.<|reference_end|>
@article{adriaensen2024extracting,
    title={Extracting Finite State Machines from Transformers},
    author={Rik Adriaensen, Jaron Maene},
    journal={arXiv preprint arXiv:2410.06045},
    year={2024},
    archivePrefix={arXiv},
    eprint={2410.06045},
    primaryClass={cs.LG cs.AI}
}