한국어 초록
이 논문의 목표는 서로 다른 출력 domain을 갖는 함수들에 걸쳐 정규성의 Nerode식 특성화를 위한 통합 모델을 제안하는 것이다. 통신 복잡도(communication complexity)에서 Hauser의 연구를 바탕으로, 계산 가능성 가정을 완화하고 비Boolean 출력 domain을 허용함으로써 설정을 일반화한다. 우리는 유한 알파벳 $Σ$와 임의의 domain $\domain$에 대해, $Σ^* \to \domain$ 타입의 함수를 고려한다. 여러 domain에 대해, 이 모델이 알려진 계산 모델과 일치함을 보인다. 우리는 또한 현재 정규성에 대한 Nerode식 특성화가 부족한 다른 domain들에 대해서도 유사한 대응 관계가 성립할 것이라고 추측하며, 이를 뒷받침하는 충분한 증거를 제시한다. 이 모델에서 입력 문자열 $w$는 $w = w_1 w_2$로 분할되어 협력하는 두 당사자 Alice와 Bob에게 배분되며, 그들은 상수 개의 메시지를 교환하여 함수 값을 계산한다. 각 메시지는 출력 domain의 원소이거나 유한 신호 집합에서 뽑힌 신호이며, 당사자들은 모든 허용 가능한 분할 $w = w_1 w_2$에 대해 올바른 출력을 생성해야 한다. 우리는 nominal sets 설정에서 무한 알파벳으로 프레임워크를 더 확장하고, 원자(atoms)를 갖는 단어들의 언어에 대한 표현력을 조사한다.
원문 초록
The goal of this paper is to propose a unifying model for Nerode-style characterizations of regularity across functions with different output domains. Building on Hauser's work in communication complexity, we generalize the setting by relaxing the computability assumptions and allowing non-Boolean output domains. We consider functions of type $Σ^* \to \domain$, where $Σ$ is a finite alphabet and $\domain$ is an arbitrary domain. For several domains, we show that the model coincides with known models of computation. We further conjecture that an analogous correspondence holds for other domains that currently lack a Nerode-style characterization of regularity, and we provide ample supporting evidence. In the model, an input string $w$ is split as $w = w_1 w_2$ and distributed between two cooperating parties, Alice and Bob, who exchange a constant number of messages to compute the value of the function. Each message is either an element of the output domain or a signal drawn from a finite set of signals, and the parties must produce the correct output for every admissible split $w = w_1 w_2$. We further extend the framework to infinite alphabets in the setting of nominal sets, and investigate its expressiveness on languages of words with atoms.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2607.13782v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
순환 언어 모델의 표현력에 대한 대수적 관점
An Algebraic View of the Expressivity of Recurrent Language Models
순환 신경망 언어 모델은 어떤 형식 언어를 인식할 수 있는가? 문헌의 형식적 결과들은 상충된다: 일부 저자는 튜링 완전성을 보고하는 반면, 다른 저자들은 정규 언어와의 동등성을 보여준다. 이러한 불일치의 이유는 기저 산술 모델이 다르기 때문이다. 본 논문은 다양한 산술 모델에 대한 형식적 설명에서 시작하여, 순환 신경망의 표현력에 대한 통합된 대수적 설명을 제시한다. 이 설명은 표현력을 대수적 질문, 예를 들어 네트워크의 구문 모노이드(syntactic monoid)가 특정 wreath product를 나누는지 여부로 환원한다. 사례 연구로, 본 논문은 대각 상태 공간 모델을 다시 살펴본다: 동일한 아키텍처는 부동소수점 순환이 강제되면 짝수 계수 카운터를 구현할 수 없지만, 부호 없는 정수 양자화 하에서는 모든 짝수 계수 카운터를 구현한다.
포지션: 자연어는 형식 언어를 완전히 대체해서는 안 된다
Position: Natural Language Should Not Fully Replace Formal Languages
최근 대규모 언어 모델(LLM)의 발전과 광범위한 채택으로, 자연어가 소프트웨어 설계를 위한 프로그래밍 언어와 같은 형식 언어를 완전히 대체할 수 있다는 주장이 제기되고 있다. 본 포지션 논문에서 우리는 이러한 관점이 자연어의 근본적인 언어적 특성, 특히 개방형 맥락에서 과소 명시(underspecification)에 최적화되어 있다는 점을 간과한다고 주장한다. 우리는 작업 특이성(task specificity)을 중심으로 한 형식적 프레임워크를 제안하며, 이를 사용자의 구체적인 요구 사항이 주어졌을 때—가능한 모든 이미지와 같은—출력 공간에서의 불확실성을 정보 이론적으로 줄이는 것으로 정의한다. 우리는 특이성 교차 정리(specificity crossover theorem)를 증명하여, 형식적 요구 사항을 자연어로 표현하는 비용이 직접적인 형식 명세의 비용을 초과하는 임계값의 존재를 보인다. 이미지 생성, 코드 합성, 오디오 제작과 같은 다양한 모달리티에 걸친 사례 연구를 분석함으로써, 자연어는 낮은 특이성 작업에서 뛰어난 반면 형식 언어는 더 엄격한 요구 사항을 갖는 작업에서 유리함을 보여준다. 우리는 자연어와 형식 언어가 상호 보완적인 도구이며, 사용자가 특이성 스펙트럼을 넘나들 수 있게 하는 하이브리드 시스템의 개발을 주장한다.
Destination-Labeled Self-Looping Systems with Dwell: Intrinsic Characterization, Realization Cost, and Recognition
트랜스포머에서 지역 어텐션의 표현력 특성화
Characterizing the Expressivity of Local Attention in Transformers
트랜스포머는 언어 모델링을 위한 가장 널리 쓰이는 신경 아키텍처이다. 트랜스포머의 핵심은 전역(global) 어텐션 메커니즘이며, 이는 모델이 다음 토큰을 생성하기 전에 이전의 모든 토큰으로부터 정보를 집약하게 한다. 어텐션의 한 흔한 변형은 지역(local) 어텐션이라 불리며, 각 토큰이 선행 토큰들의 유한한 윈도우에서만 정보를 집약하도록 제한하여 전역 어텐션의 이차(quadratic) 비용을 선형(linear)으로 줄인다. 이 제한은 보통 효율성 때문에 도입되지만, 모델 품질을 향상시키는 것으로도 밝혀졌으며, 이 현상은 지금까지 만족스러운 설명이 없었다. 우리는 인식기(recognizer) 표현력의 관점에서 이 현상에 대한 형식적 설명을 제공한다. 고정 정밀도의 전역 어텐션 트랜스포머가 단일 과거(past) 연산자를 포함하는 선형 시간 논리(linear temporal logic)의 한 단편(fragment)에 대응함이 밝혀졌다. 또한 지역 어텐션을 추가하면 두 번째 시간 연산자가 도입되어 인식 가능한 정규 언어(regular languages)의 클래스를 엄격히 확장함을 증명한다. 더 나아가 전역 어텐션과 지역 어텐션은 표현력 측면에서 상보적이다: 어느 쪽도 다른 쪽을 포괄하지 않으며, 이 둘을 결합하면 가장 풍부한 단편이 된다. 형식 언어 인식과 자연어 모델링 실험이 이론을 뒷받침하며, 전역-지역 하이브리드 트랜스포머가 전역만 사용하는 트랜스포머보다 우수함을 보여준다.
Space-Efficient Language Generation in the Limit
괄호 시퀀스 트랜스포머에서 디코딩 가능성과 인과적 사용의 분리
Dissociating Decodability and Causal Use in Bracket-Sequence Transformers
계층적 구조에 대한 이해가 필요한 작업으로 학습될 때, 트랜스포머는 잔차 스트림(residual stream)의 기하학적 구조와 후입선출(LIFO) 순서를 유지하는 스택 형태의 어텐션(attention) 패턴이라는 뚜렷한 방식으로 이 계층 구조를 표현하는 것으로 밝혀졌습니다. 그러나 이러한 표현들이 실제로 인과적으로 사용되는지 아니면 단순히 해독 가능한 것인지는 여전히 불분명합니다. 우리는 계층적 실제 값(ground truth)이 명시적인 균형 잡힌 괄호 시퀀스의 형식 언어인 Dyck 언어로 학습된 트랜스포머에서 이러한 격차를 조사합니다. 잔차 스트림과 어텐션 패턴에 대해 프로빙(probing) 및 개입(intervention)을 수행한 결과, 깊이(depth), 거리(distance), 스택 최상단(top-of-stack) 신호는 모두 해독 가능하지만, 그 인과적 역할은 서로 다름을 발견했습니다. 구체적으로, 실제 스택 최상단 위치에 대한 어텐션을 마스킹하면 장거리 정확도가 급격히 떨어지는 반면, 저차원 잔차 스트림 부분 공간을 제거(ablation)하는 것은 비교적 적은 영향을 미칩니다. 템플릿화된 자연어 설정으로 확장되는 이러한 결과들은, 관련 계층적 변수가 알려진 통제된 설정에서조차도, 해독 가능성만으로는 인과적 사용을 의미하지 않음을 시사합니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.