기술 요약: 예산 내 재귀적 결합: 차수-$p$ 텐서 메모리에서의 부공간 카빙(Subspace Carving)

1. 문제 정의

본 논문은 신경-기호적(neuro-symbolic) 메모리 시스템에서 **구조적 충실도(structural fidelity)**와 메모리 효율성(memory efficiency) 사이의 근본적인 긴장 관계를 다룹다.

• 텐서 곱 표현(Tensor Product Representations, TPRs) (Smolensky, 1990)은 외적(outer product)을 통해 "필러(fillers)"(내용)를 "역할(roles)"(구조)에 결합함으로써 수학적으로 엄밀한 결합을 제공하며, 완벽한 직교성과 손실 없는 회수를 보장한다. 그러나 이는 지수적인 차원 증가를 초래하며, 구조의 깊이가 $k$인 경우 $d^k$의 텐서 공간이 필요하므로, 적당한 차원에서도 깊은 재귀적 결합을 수행하기에는 불가능에 가깝다.
• 벡터 기호 체계(Vector Symbolic Architectures, VSAs) (Kanerva, 2009)는 원래의 벡터 공간으로 결합을 압축(예: 원형 컨볼루션 이용)함으로써 일정한 차원을 유지한다. 효율적이기는 하지만, 이 압축 과정은 노이즈를 유발한다. 중첩된 결합의 수가 증가함에 따라 신호 대 잡음비(SNR)가 저하되어 간섭이 발생하고, 고용량 레짐(high-capacity regime)에서 회수의 신뢰도가 떨어진다.

TPRs의 기존 희소 근사 방식들은 스케일링 문제를 완화하지만, 깊은 구조에서는 상당한 성능 저하를 겪는다. 핵심 과제는 메모리 풋프린트를 일정하게 유지하면서도, 높은 중첩(superposition)을 지원하면서 동시에 깊은 재귀적 구조를 지원하는 것이다.

2. 방법론: 직교 부공간 카빙 (Orthogonal Subspace Carving, OSC)

저자들은 텐서의 차수를 구조적 깊이로부터 분리하기 위해, 명시적인 좌표 할당 대신 투영(projection)을 통해 기하학적 직교성을 강제하는 메모리 아키텍처인 **직교 부공간 카빙(OSC)**을 제안한다.

핵심 원리

• 기하학적 배제(Geometric Exclusion): 역할을 특정 차원에 할당하는 대신, OSC는 컨텍스트(context)를 "금지된" 부공간으로 정의한다. 결합은 이러한 컨텍스트의 직교 보공간(orthogonal complement/null space)에 배치된다.
• 필러 표현: 필러가 단일 벡터인 표준 VSA와 달리, OSC의 필러는 구조화된 객체, 즉 $p$개의 벡터로 이루어진 순서쌍 $f = (v_1, \dots, v_p) \in (\mathbb{R}^d)^p$이다.
• 컨텍스트 정의: 컨텍스트 $C$는 $k$개의 상호 직교하는 방향들로 생성된 부공간 $S_C$와 연관된다. 서로 다른 컨텍스트들은 기하학적으로 연관될 필요가 없으므로, 컨텍스트 내에서는 국소적 정밀도를 유지하면서 컨텍스트 간에는 전역적 독립성을 가질 수 있다.

결합 메커니즘

1. 카빙 (투영): 필러를 컨텍스트에 결합하기 위해, 카빙 연산자 $P^\perp_C = I - B_C^T B_C$는 각 성분 벡터 $v_i$를 컨텍스트 기저 $B_C$의 영공간(null space)으로 투영한다. 이는 컨텍스트 부공간과의 모든 중첩을 제거한다.
2. 정규화 및 융합: 투영된 성분들은 정규화된 후 차수-$p$ 텐서 곱을 통해 융합된다:
   $$T_{bound} = \bigotimes_{i=1}^p \left( \frac{P^\perp_C v_i}{\|P^\perp_C v_i\|} \right)$$
   그 결과, $T_{bound}$는 컨텍스트의 직교 보공간 내에 완전히 존재하는 차수-$p$ 텐서가 된다.
3. 중첩: 메모리 $M$은 이러한 결합된 텐서들의 단순 합(중첩)으로 형성된다. 각 결합은 고유한 컨텍스트에 대해 직교하므로, 그리고 컨텍스트들이 서로 소(disjoint)인 부공간을 정의하므로, 결합들은 메모리 공간 내에서 간섭 없이 자연스럽게 분리된다.

쿼리 및 인식

OSC는 회수 패러다임을 대수적 언결합(algebraic unbinding)(벡터 재구성)에서 **판별적 인식(discriminative recognition)**으로 전환한다.

• 메커니즘: 쿼리를 수행할 때, 동일한 카빙 메커니즘을 사용하여 후보 결합을 구성한다. 회수 점수는 메모리 텐서와 후보 텐서 사이의 프로베니우스 내적(Frobenius inner product)이다.
• 어휘 탐색: 시스템은 유사도 점수가 가장 높은 후보를 선택함으로써 저장된 항목을 식별한다. 이 방식은 VSA에서 사용되는 표준 "클린업 메모리(cleanup memory)" 코드북과 호환된다.
• 이론적 보장: 정리 4.6은 $N$개의 독립적인 결합에 대해 간섭 노이즈가 $\sqrt{(N-1)/d^p}$로 스케일링됨을 입증한다. 텐서 차수 $p$나 차원 $d$를 높임으로써 노이즈를 억제할 수 있으며, 이를 통해 고용량 중첩 레짐에서도 견고한 회수를 가능하게 한다.

이론적 연결

• 클리포드 대수 (Clifford Algebra): 본 논문은 TPR이 클리포드 대수에서의 결합의 특수 사례임을 보여준다. OSC는 역할과 필러가 이산적인 기저 벡터가 아닌 직교 부공간인 것으로서, 특정 직교성 제약 조건 하에서 메모리 공간을 $d^{|C|+1}$에서 $\binom{d}{|C|+1}$로 압축하면서도 정확한 회수 속성을 유지하는 자연스러운 확장으로 정식화된다.
• 절차적 생성: 컨텍스트는 역할 라벨을 해싱하여 기저 벡터를 위한 무작위 시드를 생성함으로써 절차적으로 생성될 수 있다. 이는 표현 가능한 컨텍스트의 수를 메모리 제약으로부터 분리하여, TPR의 지수적 저장 비용 문제를 피하게 한다.

3. 주요 기여

1. OSC 아키텍처: 구성 요소 벡터의 차원을 메모리 용량으로부터 분리하는 투영 기반 결합을 사용하는 새로운 메모리 아키텍처를 제안한다.
2. 아래 선형 스케일링 (Sub-linear Scaling): 고중첩 작업에서 메모리 풋프린트를 크게 줄인다. 저자들은 구성 요소 벡터가 메모리 텐서보다 수 차수 더 작으면서도 견고한 회수를 유지할 수 있음을 보여준다.
3. 준손실 회수 (Near-Lossless Retrieval): 필러 차원의 아래 선형 스케일링을 활용하여, 고중합 레짐에서도 높은 정확도를 달ей할 수 있다. 이는 더 작은 전체 풋프린트 내에서 더 큰 중첩 공간을 허용한다.
4. 클리포드 정식화: TPR이 클리포드 대수의 특수 사례임을 입증하고, OSC를 위한 클리포드 정식화를 제공한다.

4. 실험 결과

저자들은 합성 벤치마크와 극단적 다중 레이블 분류(Extreme Multi-label Classification, XML) 태스크를 통해 OSC를 14개의 기존 VSA(HRR, VTB, MAP, HLB 포함) 및 TPR과 비교 평가하였다.

• 확장성 및 효율성:
  • $d=200, p=2$인 OSC(1,000개 번들)는 99.77%의 회수 정확도를 달성하였으며, 이는 $d=4096$일 때 13.18%, $d=8100$일 때 35.88%를 기록한 최상의 VSA를 능가했다.
  • 10,000개 번들 환경에서 OSC($d=80, p=3$)는 99.85%의 정확도를 유지했다. 이를 맞추기 위해 최상위 VSA(HLB)는 $d=343,000$이 필요했으며, 이는 OSC보다 1,178배 더 큰 파라미터 풋프린트를 요구했다.
  • OSC는 코드북 크기에 대해 VSA와 유사한 유리한 로그 스케일링을 보이지만, 필러 차원의 아래 선형적 성장 덕분에 훨씬 더 낮은 총 메모리 요구량을 가진다.
• TPR과의 비교: 역할 깊이 1에 대해, OSC는 중첩 수준이 작은 임계값을 초과할 때 TPR보다 적은 파라미터로 99%의 정확도를 달성한다. 번들의 수가 증가함에 따라 압축률은 점점 더 OSC에 유리하게 작용한다.
• 다운스트림 응용 (XML): OSC는 극단적 다중 레이블 분류를 위한 신경-기호적 모델에 통합되었다. OSC는 4개의 데이터셋에 걸쳐 43.75%의 지표 케이스에서 1위를 차지하며 VTB, MAP, HLB와 비교해 경쟁력 있는 성능을 보였으며, 이를 통해 경사 하강법 기반 시스템에서의 학습 가능성을 확인했다.
• 추론 속도: OSC의 요소별 연산은 단순한 요소별 VSA 연산보다 복잡하지만, 규모가 커질수록 OSC가 더 빨라진다. 병목 현상이 계산에서 메모리 대역폭으로 이동하기 때문이다. OSC의 더 작은 메모리 풋프린트는 데이터 전송 시간을 줄여, 고중합 시나리오에서 더 낮은 실제 실행 시간(wall-clock time)을 이끌어낸다.

5. 의의 및 주장

본 논문은 OSC가 계산적으로 실행 가능하면서도 메모리 효율적인 깊은 재귀적 결합을 제공함으로써 "신경-기호적 간극(neuro-symbolic gap)"을 해결한다고 주장한다.

• 패러다임의 전환: 명시적인 차원 확장 대신 기하학적 배제(카빙)를 사용하고, 재구성에서 인식으로 전환함으로써, OSC는 TPR의 지수적 스케일링과 VSA의 노이즈 누적 문제를 피한다.
• 실용성: 컨텍스트를 절차적으로 생성할 수 있는 능력과 필러 차원의 아래 선형적 스케일링은 OSC를 막대한 메모리 비용 없이도 대규모 어휘와 깊은 구조가 필요한 응용 분야에 적합하게 만든다.
• 한계점: 저자들은 OSC가 코드북 탐색을 사용하는 기호 추론 시스템의 특성상, 임의의 벡터를 재구성하는 정확한 대수적 언결합을 지원하지 못한다는 점을 겸허히 인정하나, 이는 코드북 검색을 사용하는 시스템에서는 문제가 되지 않는다고 주장한다. 또한, OSC가 총 저장 용량 측면에서 VSA보다 메모리 효율성이 높지만, 제약 조건이 순수하게 중첩 메모리의 크기인 경우에는 VSA가 여전히 약간의 우위를 가질 수 있음을 언급한다.

본 연구는 현대적인 경사 하강법 최적화와 호환되는 확장 가능한 구조적 메모리 시스템을 향한 단계로 제시되었으며, 광범위한 실험적 검증을 통해 최첨단 베이스라인들과 비교하여 그 가치를 입증하였다.