Transformers Are Inherently Succinct (2025)

개요

Transformers 모델이 형식 언어를 표현하는 데 있어 고유한 간결성(succinctness)을 가지며, 이는 기존의 유한 자동자(finite automata) 및 선형 시간 논리(Linear Temporal Logic, LTL) 공식보다 훨씬 효율적인 표현력을 제공함을 증명합니다.

주요 내용

• 간결성을 새로운 표현력 척도로 제시: 본 연구는 Transformers 모델의 표현력을 측정하는 기준으로 '간결성(succinctness)'을 제안합니다. 이는 특정 개념을 얼마나 압축적으로 설명할 수 있는지를 나타냅니다.
• Transformers의 뛰어난 형식 언어 표현력: Transformers는 형식 언어를 기존의 유한 자동자나 LTL 공식과 같은 표현 방식보다 훨씬 간결하게 나타낼 수 있음을 이론적으로 증명했습니다.
• 표현력으로 인한 검증 복잡성 증가: Transformers의 높은 표현력은 부산물로, Transformers 모델이 표현하는 속성을 검증하는 문제가 본질적으로 다루기 어려움(EXPSPACE-complete)을 가지며, 이는 이론적으로 해결 불가능한 수준에 이를 수 있음을 보여줍니다.

시사점

Transformers 모델의 내재된 간결성은 복잡한 개념을 효율적으로 표현하는 능력의 지표가 될 수 있으며, 이는 동시에 해당 모델의 동작 및 속성 검증의 복잡성을 증가시키는 요인이 됩니다.