Transformers는 본질적으로 간결하다

Transformer의 표현력을 평가하는 새로운 관점으로 **간결성(Succinctness)**을 제시한다. 간결성이란 특정 모델이 언어를 얼마나 압축적으로 기술할 수 있는지를 나타내는 척도다.

연구 결과, 고정 정밀도(fixed-precision) Transformer는 기존 모델들에 비해 압도적인 압축 효율을 보인다. 구체적인 비교 결과는 다음과 같다:

• LTL(선형 시제 논리) 및 **RNN(순환 신경망)**보다 지수적으로(exponentially) 더 간결하다.
• **유한 오토마타(Finite Automata)**보다는 이중 지수적으로(doubly exponentially) 더 간결하다.

이는 특정 언어들을 기술할 때, Transformer는 다항식 크기(polynomial-size)만으로 충분하지만, 동일한 언어를 LTL이나 RNN으로 표현하려면 지수적인 크기가 필요하며, 오토마타로는 이중 지수적인 크기가 필요함을 의미한다.

이러한 높은 간결성은 모델의 검증(Verification) 문제를 어렵게 만드는 원인이 된다. Transformer의 공집합 여부(emptiness)나 동등성(equivalence)을 확인하는 문제는 EXPSPACE-complete로 판명되어, 계산적으로 매우 복잡한(intractable) 문제임이 증명되었다.