유한 정밀도 순환 모델의 표현력을 도구 사용이 언제 증가시키는가
When Does Tool Use Increase the Expressive Power of Finite-Precision Recurrent Models?
한국어 초록
현대의 시퀀스 모델은 토큰 생성과 외부 도구 호출을 교차하는 에이전트로 점점 더 많이 배포되고 있다. 우리는 이러한 도구 접근이 계산적 표현력을 증가시키는 시점에 대한 정확한 아키텍처 수준의 설명을 제시한다. 우리는 $B$비트의 내부 상태를 가진 유한 정밀도 상태 공간 모델(SSM)을 포함하여, 임의의 고정된 유한 정밀도 순환 시퀀스 모델을 유한 명령/관측 인터페이스를 통해 오라클과 상호작용하는 결정론적 유한 상태 제어기로 모델링한다. 우리의 결과는 명확한 이분법을 형성한다. 첫째, 유한 상태인 도구는 본질적으로 아무것도 추가하지 않는다: 곱 상태 시뮬레이션은 유한 메모리 집합 $M$을 가진 임의의 유한 상태 경계 인터페이스 오라클을 단 $\log_2 |M| + O(1)$비트의 추가 비용으로 내재화하므로, 보강된 시스템은 유한 상태로 남는다. 둘째, 단일 최소 무한 상태 도구, 즉 로컬 $\mathtt{read}$, $\mathtt{write}$, $\mathtt{move}$ 명령만을 지원하는 테이프는 시스템을 튜링 완전하게 만든다: 상태 집합 $Q$와 테이프 알파벳 $Γ$를 가진 모든 단일 테이프 튜링 기계에 대해, $O(\log |Q| + \log |Γ|)$비트의 내부 메모리를 가진 제어기가 이를 시뮬레이션하며, 우리는 구체적인 지수적 분리를 제시한다: $\mathrm{EQ}_n$은 도구 없이 $2^n$개의 상태를 필요로 하지만 테이프 도구를 가진 단일 상수 크기 제어기로 해결된다. 셋째, 우리는 이 구성이 이진 원-핫 은닉 상태, $\{0,1\}$ 전이 행렬, 영 편향을 가진 자연스러운 1층 유한 정밀도 선택적 아핀 SSM 제어기에 의해 정확히 실현됨을 보인다. 선택성은 이 구성에 필수적이다. 보충 자료에서, 우리는 모든 상수를 명시하고, $O(\log B)$의 순환 비트가 임의의 $B$-상태 튜링 기계를 시뮬레이션하기에 충분함을 보이는 로그적 오라클 보조 범용 시뮬레이션을 증명하며, 그에 대응하는 불가능성 결과를 증명한다.
원문 초록
Modern sequence models are increasingly deployed as agents that interleave token generation with calls to external tools. We give an exact, architecture-level account of when such tool access increases computational expressivity. We model any fixed finite-precision recurrent sequence model, including finite-precision state-space models (SSMs) with $B$ bits of internal state, as a deterministic finite-state controller interacting with an oracle through a finite command/observation interface. Our results form a sharp dichotomy. First, tools that are themselves finite-state add essentially nothing: a product-state simulation internalizes any finite-state bounded-interface oracle with finite memory set $M$ at a cost of only $\log_2 |M| + O(1)$ additional bits, so the augmented system remains finite-state. Second, a single minimal infinite-state tool, namely a tape supporting only local $\mathtt{read}$, $\mathtt{write}$, and $\mathtt{move}$ commands, makes the system Turing complete: for every single-tape Turing machine with state set $Q$ and tape alphabet $Γ$, a controller with $O(\log |Q| + \log |Γ|)$ bits of internal memory simulates it, and we exhibit a concrete exponential separation: $\mathrm{EQ}_n$ requires $2^n$ states without tools but a single constant-size controller with the tape tool. Third, we show that this construction is realized exactly by a natural one-layer finite-precision selective affine SSM controller with binary one-hot hidden states, $\{0,1\}$ transition matrices, and zero biases. Selectivity is essential to the construction. In the supplementary material, we make all constants explicit, prove a logarithmic oracle-assisted universal simulation, where $O(\log B)$ recurrent bits suffice to simulate any $B$-state Turing machine, and prove a matching impossibility result.
요약
유한 정밀도 순환 모델이 외부 도구를 사용할 때 계산 표현력이 언제 증가하는지를 이론적으로 분석하여, 유한 상태 도구는 표현력을 거의 높이지 못하지만 로컬 read/write/move 명령을 지원하는 테이프 도구 하나만으로도 시스템이 튜링 완전(Turing complete)해짐을 증명한다. 또한 이 구성이 이진 원-핫 은닉 상태를 가진 단층 유한 정밀도 선택적 아핀 SSM으로 정확히 실현됨을 보이며, $O(\log B)$의 순환 비트로 임의의 $B$-상태 튜링 기계를 시뮬레이션할 수 있다는 자원 효율성 결과도 함께 제시한다.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2607.06155v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
PyDPF: 미분 가능한 파티클 필터링을 위한 Python 패키지
PyDPF: A Python Package for Differentiable Particle Filtering
상태 공간 모델(SSM)은 시계열 분석에서 널리 사용되는 도구입니다. 실제 데이터에서 비롯되는 복잡한 시스템에서는 일련의 관측값에 대응하는 은닉 상태를 추정하기 위해 효율적인 몬테카를로(Monte Carlo) 기법인 파티클 필터링(PF)을 사용하는 것이 일반적입니다. 파티클 필터링을 적용하려면 시스템의 매개변수 형태와 파라미터가 모두 지정되어야 하지만, 이는 알려지지 않은 경우가 많아 추정해야 합니다. 표준 파티클 필터는 필터 자체가 미분 가능하지 않기 때문에 그래디언트 기반 최적화(optimization) 기법을 직접 적용할 수 없습니다. 그러나 최근 제안된 여러 방법은 리샘플링 단계를 수정하여 파티클 필터링을 미분 가능하게 만듭니다. 본 논문에서는 널리 사용되는 PyTorch 프레임워크를 기반으로 구축된 통일된 API를 통해 이러한 여러 미분 가능한 파티클 필터(DPF)의 구현을 제시합니다. 본 연구의 구현은 더 넓은 연구 커뮤니티에서 이러한 알고리즘에 쉽게 접근할 수 있도록 하며, 알고리즘 간의 직접적인 비교를 용이하게 합니다. 우리는 기존 여러 연구의 실험을 재현하여 프레임워크를 검증하고, 상태 공간 모델링의 여러 일반적인 과제를 해결하기 위해 DPF를 어떻게 적용할 수 있는지 보여줍니다.
고정된 범용 트랜스포머
Fixed Universal Transformers
본 논문에서는 적절한 입력 임베딩(embedding)을 통해 주어진 클래스 내의 모든 트랜스포머(transformer)를 시뮬레이션할 수 있는 고정된 트랜스포머인 \emph{범용 트랜스포머(universal transformers)}를 제안합니다. 범용 튜링 기계와 유사하게, 모든 내부 파라미터가 고정된 상태에서 입력 임베딩이 대상 모델(model)에 대한 설명을 인코딩합니다. 저자들은 임베딩 차원이 충분히 클 때 보편성(universality)을 달성하는 명시적인 희소(sparse) 구조를 제시하며, 나아가 보편성이 일반적(generic)임을 보입니다. 즉, 무작위로 초기화된 트랜스포머는 거의 확실하게(almost surely) 보편적이며, 이는 Zhong 및 Andreas(2024)의 최근 실증적 결과와도 일치합니다. 또한 괄호 균형 맞추기(parenthesis balancing) 및 다단계 추론(multi-hop reasoning)과 같은 알고리즘 과제에서 이러한 이론을 실험적으로 검증합니다. 본 연구 결과는 트랜스포머의 표현 능력 중 상당 부분이 학습된 가중치보다는 입력 표현에 내재되어 있을 수 있음을 시사합니다.
MambaX: 상태 예측 제어를 이용한 이미지 초해상도
MambaX: Image Super-Resolution with State Predictive Control
이미지 초해상도(SR)는 센서의 근본적인 하드웨어 한계를 극복하기 위한 핵심 기술이다. 그러나 기존 접근법들은 주로 최종 해상도를 직접적으로 향상시키는 데 초점을 맞추고 있어, 중간 단계에서 발생하는 오차의 전파와 누적에 대한 효과적인 제어를 간과하는 경우가 많다. 최근 맘바(Mamba)는 전체 복원 과정을 다수의 노드를 가진 상태 시퀀스(state sequence)로 표현함으로써 중간 개입을 가능하게 하는 유망한 접근법으로 부상하였다. 그럼에도 불구하고, 맘바의 고정된 선형 매퍼(linear mapper)는 좁은 수용 영역(receptive field)과 제한된 유연성으로 인해 세밀한 이미지에서의 효과가 저해된다는 한계가 있다. 이를 해결하기 위해, 우리는 연속적인 스펙트럼 밴드를 잠재 상태 공간(latent state space)으로 매핑하고, 제어 방정식의 비선형 상태 파라미터를 동적으로 학습함으로써 SR 과제를 일반화하는 비선형 상태 예측 제어 모델인 MambaX를 구축하였다. 기존의 시퀀스 모델들과 비교하여, MambaX는 1) 동적 상태 예측 제어 학습을 사용하여 상태 공간 모델(state-space model)의 비선형 미분 계수를 근사하고, 2) 다중 모달(multimodal) SR 융합을 위한 새로운 상태 교차 제어(state cross-control) 패러다임을 도입하며, 3) 점진적 전이 학습(progressive transitional learning)을 활용하여 도메인 및 모달리티 변화(shift)로 인한 이질성을 완화한다. 우리의 평가는 단일 이미지 SR과 다중 모달 융합 기반 SR 과제 모두에서 동적 스펙트럼-상태 표현 모델의 우수한 성능을 보여주며, 임의의 차원과 모달리티에 걸쳐 스펙트럼적으로 일반화된 모델링을 발전시킬 수 있는 상당한 잠재력을 강조한다.
언어 식별을 위한 전역 일관 채색 방식
Globally Consistent Coloring Schemes for Language Identification
우리는 적대적 언어 학습을 가능하게 하는 데 필요한 추가 정보의 최솟값을 연구한다. Gold의 극한에서의 언어 식별 모델에서, 학습자는 가산 언어 집합에서 선택된 미지의 언어에 속한 문자열들의 열거를 제공받는다. 학습자는 열거가 진행되는 동안 언어의 정체를 추측하며, 결국 모든 추측이 올바른 언어로 수렴하면 성공한 것으로 본다. Gold와 Angluin의 고전적 결과는 많은 자연스러운 언어 집합이 이 방식으로 학습될 수 없음을 보였다. 언어 학습에서 사고 과정(thinking-trace) 전략의 성공에 동기를 얻은 트레이스 채색(trace coloring)에 관한 최근 연구는, 모든 문자열의 모든 기호에 색을 주석으로 달아 이 장애물을 극복한다. 우리는 학습자가 이 색 시퀀스 전체를 필요로 하는지, 아니면 각 문자열의 끝에 색 하나(종단 채색)만으로 언어 식별에 충분한지를 묻는다. 우리는 문자열당 단 하나의 종단 비트만으로 모든 가산 무한 언어 집합에 대해 충분함을 보인다. 나아가, 이 채색은 집합에 무관하게 선택될 수 있다: 즉, 모든 무한 언어에 대해 2색 종단 채색을 단 한 번 배정하면, 동일하게 사전 배정된 채색이 모든 가산 부분 집합을 식별한다. 따라서 이 모델에서 전체 색 트레이스는 각 예시의 끝에 붙는 1비트로 압축될 수 있다. 우리의 전역 구성은 초한 재귀(transfinite recursion)를 사용하며, 이러한 비구성성(nonconstructivity)이 유한한 수의 색에 대해 불가피함을 증명한다. 구성성의 개념으로는 보렐 사상(Borel map)의 형식(자연스럽고 명시적인 구성이 만족하는 정칙 조건)을 사용한다. 유한 개의 색을 사용하는 보렐 사상으로 정의된 전역 종단 채색은 모든 가산 부분 집합을 식별할 수 없음을 보인다. 반면, 기존의 트레이스 채색 구성은 종단 채색으로 인코딩될 때 보렐이지만, 무한히 많은 색을 필요로 한다.
토큰이 아닌 고유 항목을 기억하기: 상태공간 모델과 어텐션 사이의 학습 가능한 Dirichlet-Process 캐시
Remembering Distinct Items, Not Tokens: A Learnable Dirichlet-Process Cache Between State-Space Models and Attention
고정 상태 시퀀스 모델은 무한한 과거를 유한한 상태로 압축하므로, 연상 재현율이 대략 상태 차원 수준으로 제한된다. 어텐션은 모든 토큰에 대해 키-값 항목을 유지함으로써 이 제한을 피하지만, 이차(quadratic) 연산량과 시퀀스 길이에 따라 증가하는 캐시를 요구한다. 우리는 그 중간 지점을 연구한다: 입력이 새로운 경우에만 슬롯을 할당하는 희소 캐시로, 그 크기가 토큰 수가 아닌 고유 항목의 수를 추적한다. 할당 규칙은 Dirichlet-process 혼합의 소분산 극한인 DP-means 클러스터링 규칙으로, 잠재변수 추론이 아닌 심층 순환 백본의 키-값 메모리 연산자로 활용된다. 우리는 이를 두 가지 형태로 개발한다: 고정된 농도(concentration)를 갖는 정적 캐시와, 농도가 최근 새로움 비율을 따르는 놀라움 적응형(surprise-adaptive) 변형이다. 중복이 있는 제어된 연상 재현율 벤치마크에서, 이 캐시가 고유 항목만 저장하면서 완전 어텐션의 재현율에 필적하고, 재현율 대 크기 프론티어에서 고정 예산 제거(eviction) 캐시를 능가하며, 상태공간 백본에서 테스트된 모든 모델 중 가장 낮은 메모리로 재현율 질의와 장거리 집계 모두에 응답함을 보인다. 할당은 end-to-end로 학습 가능하다: 작업 손실만으로 학습된 두 매개변수 새로움 임계값 게이트가 규칙을 정확히 복원하는 반면, 과매개변수화된 게이트는 실패하므로, 핵심 요소는 용량이 아닌 귀납적 바이어스임을 나타낸다. 증거는 적당한 규모의 제어된 메커니즘 연구 집합으로, 고유 항목 속성이 네 가지 실제 스트림(추천, 시스템 로그, 임상 이벤트, 보험 청구)에서 확인되었다. 실제 백본과 실제 코퍼스를 이용한 언어 검증은 동반 연구에서 추구된다.
불연속 게이팅을 가진 선택적 SSM의 정칙성 및 안정성 특성
Regularity and Stability Properties of Selective SSMs with Discontinuous Gating
Mamba와 같은 선택적 상태 공간 모델(SSM)은 장시퀀스 모델링의 핵심으로 자리잡았다. 그러나 이들의 안정성은 아직 충분히 이해되지 않았다: 상태 공간 계수가 토큰(token) 의존적 게이팅 신호에 의해 온라인으로 변조되어, 그 순환(recurrence)은 선형 시불변(linear time-invariant)도 고전적 비선형도 아닌 특성을 지닌다. 우리는 수동성(passivity), 소산성(dissipativity), 입력-상태 안정성(Input-to-State Stability, ISS)을 통해 연속 시간 선택적 SSM을 연구하며, 선택 신호 $x(\cdot)$를 구동 입력 $u(\cdot)$로부터 명시적으로 분리한다. 우리는 네 가지 결과를 도출한다: 엄격한 소산성 하에서의 지수적 망각; 불연속 게이팅을 수용하는 선택 고정 서브시스템에 대한 정준 $\mathrm{AUC}_{\mathrm{loc}}$ 이차 저장; 범용 커널(kernel) 제약 및 "비가역적 망각"을 포함하는 범용 이차 저장 하에서의 파라메트릭 LMI; 그리고 허용 가능한 선택 스케줄 전반에 걸쳐 균일한 전역 ISS에 대한 충분 조건. 이후 우리는 Mamba 선택적 스캔 코어에 대한 샘플링된 블록 LMI를 도출함으로써 실용적 연결을 구축하며, 이를 미분 가능한 학습(training) 시간 정규화기로 활용한다. 7개의 표준 시계열 데이터셋과 4개의 예측 지평에 걸쳐, 해당 정규화기는 28/28 쌍에서 샘플링된 Mamba 코어 LMI 위반을 약 92% 감소시키며, 클린 MSE 비용은 0.018% 미만이다. 또한 주입된 교란 하에서 내부 Mamba 수동성 및 상태 노름 진단을 개선한다. 우리의 결과는 고전적인 제어 이론적 도구를 선택적 SSM에 대한 검증 가능한 구조적·학습 기준으로 전환하는 동시에, 어떤 보장이 심층 선택적 스캔 아키텍처로 이전되는지를 솔직하게 범위 한정한다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.