💻 computer science

Parallel Recursive LSTM

본 논문은 균형 잡힌 계산 트리에서 토큰 상태를 재귀적으로 병합하여 로그 병렬 깊이를 달성하는 계층적 아키텍처인 병렬 재귀 LSTM(PR-LSTM)을 소개하며, 이를 통해 순환 모델의 강력한 상태 추적 능력과 병렬 처리의 효율성을 결합하여 이차 스케일링 없이 장기 컨텍스트 벤치마크에서 표준 RNN, LSTM 및 트랜스포머보다 우수한 성능을 발휘합니다.

원저자: Tristan Gaudreault, Yongyi Mao

게시일 2026-05-19

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Tristan Gaudreault, Yongyi Mao

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

거대한 퍼즐을 풀려고 하는데, 한 조각씩 엄격한 순서대로 처리해야 한다고 상상해 보세요. 1 번 조각을 집어 들고, 그다음 2 번, 3 번 조각을 차례로 집어 올립니다. 이것이 전통적인 LSTM(기억 기능을 가진 AI 의 한 종류)이 작동하는 방식입니다. 이들은 지금까지의 이야기를 기억하는 데는 뛰어나지만, 두 단계를 동시에 수행할 수 없기 때문에 느립니다. 다음 단계를 시작하려면 이전 단계가 완료될 때까지 기다려야 합니다.

반면, 트랜스포머(현대 채팅봇의 기반이 되는 AI) 는 1,000 명으로 구성된 팀이 동시에 퍼즐을 바라보는 것과 같습니다. 이들은 놀라울 정도로 빠르며, 1 번 조각과 1,000 번 조각이 어떻게 연관되는지 즉시 파악할 수 있습니다. 하지만 함정이 하나 있습니다: 퍼즐이 커질수록 그들이 수행해야 할 작업량이 폭발적으로 증가합니다. 퍼즐 크기를 두 배로 늘리면, 그들은 네 배의 작업을 수행해야 합니다. 이로 인해 매우 긴 이야기를 다룰 때는 비용이 많이 들고 매우 느려집니다.

이 논문의 저자인 트리스탄 고드보와 용이 마오는 병렬 재귀적 LSTM(PR-LSTM)이라는 새로운 방식을 고안해냈습니다. 이는 양쪽 세계의 장점을 모두 취하는 교묘한 중간 지대라고 생각하면 됩니다.

"나무" 비유

오래된 LSTM 처럼 단일 줄로 걷거나, 트랜스포머처럼 모두가 동시에 모든 것을 바라보는 대신, PR-LSTM 은 작업을 가계도나 토너먼트 브래킷처럼 조직화합니다.

준비: 처리해야 할 8 명의 사람 (토큰) 이 긴 줄로 서 있다고 상상해 보세요.
오래된 방식(순차적): 1 번 사람이 2 번 사람과 대화합니다. 그 다음 그 쌍이 3 번 사람과 대화합니다. 그 그룹이 4 번 사람과 대화합니다. 끝에 도달하는 데 7 단계가 걸립니다.
새로운 방식(PR-LSTM):
- 1 라운드: 1 번 사람이 2 번 사람과 대화하는 동시에 3 번 사람이 4 번 사람과 대화하고, 5 번 사람이 6 번 사람과 대화합니다. 모든 사람이 쌍으로 동시에 작업합니다.
- 2 라운드: (1+2) 의 결과가 (3+4) 의 결과와 대화합니다. (5+6) 의 결과가 (7+8) 과 대화합니다. 이 또한 동시에 발생합니다.
- 3 라운드: 두 개의 큰 그룹이 서로 대화합니다.

이렇게 함으로써 작업의 "깊이"가 극적으로 줄어듭니다. 8 개의 항목을 처리하는 데 7 단계가 걸리던 것이 이제 3 단계만 필요합니다. 1,000 개의 항목이 있다면, 오래된 방식은 1,000 단계를 필요로 하지만 이 새로운 방식은 약 10 단계만 필요합니다. 이것이 논문에서 로그arithmic 병렬 깊이라고 부르는 것입니다.

작동 원리 (스마트한 병합)

어려운 점은 실제 대화에서는 사물을 어떻게 결합하느냐에 따라 의미가 달라진다는 것입니다. 단순한 수학 (예: $A + B = B + A$ ) 만으로는 되지 않습니다.

문제: 대부분의 빠르고 병렬적인 방법들은 수학이 단순하고 예측 가능할 때 (숫자를 더하는 것처럼) 만 작동합니다.
PR-LSTM 의 해결책: 저자들은 나무의 모든 노드에 위치한 특별한 "병합 기계"(LSTM 인코더) 를 구축했습니다. 두 그룹의 정보가 만날 때, 이 기계는 "게이트"(스마트 스위치와 유사) 를 사용하여 무엇을 유지하고, 무엇을 잊으며, 무엇을 결합할지 결정합니다. 이는 복잡하고 비선형적인 과정이지만, 나무 구조 덕분에 이러한 병합 작업 중 많은 부분이 동시에 발생할 수 있어 속도가 빠릅니다.

발견한 점

연구자들은 이 새로운 AI 를 "형식 언어"퍼즐 세트로 테스트했습니다 (문자열에 'A'가 짝수 개 있는지 확인하거나 간단한 수학 방정식을 푸는 것 등).

결과: PR-LSTM 은 표준 LSTM 이나 트랜스포머보다 이러한 퍼즐을 푸는 데 훨씬 뛰어났으며, 특히 퍼즐이 매우 길어졌을 때 두드러졌습니다.
"누락된 중복" 승리: "누락된 중복" (긴 목록에서 반복된 항목 찾기) 이라는 특정 테스트에서 PR-LSTM 은 매우 복잡하고 메모리를 많이 사용하는 모델을 제외하고는 거의 모든 다른 모델이 실패한 상황에서 성공했습니다.
속도 대 메모리:
- 트랜스포머는 모든 조각 간의 모든 연결을 기억하려고 시도했기 때문에 퍼즐이 길어질수록 컴퓨터 메모리 (RAM) 를 빠르게 소진했습니다.
- 오래된 LSTM은 메모리가 부족하지는 않았지만, 한 번에 하나씩 작업했기 때문에 완료하는 데 매우 오랜 시간이 걸렸습니다.
- PR-LSTM은 절묘한 균형점을 이뤘습니다: 메모리가 부족하지 않았으며, "나무"방식을 사용하여 병렬로 작업했기 때문에 오래된 LSTM 보다 훨씬 빠르게 완료되었습니다.

한계점

이 논문은 이 새로운 모델이 아직 할 수 없는 것에 대해 솔직합니다:

고정된 구조: "나무"구조는 고정되어 있습니다. 항상 특정 패턴으로 이웃을 병합합니다. 때로는 이야기가 매우 비정상적인 방식으로 맨 처음에서 맨 끝으로 점프해야 할 수도 있는데, 이러한 경직된 나무 구조가 모든 유형의 문제에 완벽한 적합은 아닐 수 있습니다.
복잡성: 표준 LSTM 을 구축하는 것보다 더 복잡합니다.
테스트 범위: 연구자들은 이 특정 논리 퍼즐에 대해서만 테스트했습니다. 소설을 쓰거나 일상적인 대화를 나누는 것에는 아직 테스트하지 않았으므로, 이러한 작업에서 어떻게 수행될지는 알 수 없습니다.

결론

이 논문은 느리고 단계적인 기억 시스템 (LSTM) 을 재구성하여 기억하고 추론하는 능력을 잃지 않으면서 빠르고 병렬적인 나무 구조로 만들 수 있다고 주장합니다. "느리지만 똑똑한" 것과 "빠르지만 메모리를 많이 먹는" 것 사이에서 선택하지 않아도 된다는 것을 증명합니다. 적어도 그들이 테스트한 논리 퍼즐 유형의 경우, 효율적이면서도 심층 추론이 가능한 시스템을 가질 수 있습니다.

기술 요약: 병렬 재귀 LSTM (PR-LSTM)

문제 제기

트랜스포머는 표현력 있는 자기-주의 메커니즘과 높은 병렬성으로 인해 시퀀스 모델링에서 지배적인 아키텍처로 자리 잡았습니다. 그러나 시퀀스 길이에 대해 이차적인 시간 및 메모리 복잡성을 겪어 긴 컨텍스트 시나리오에서 효율성이 제한됩니다. 반면, LSTM 과 같은 고전적 재귀 모델은 명시적인 비선형 상태 업데이트와 강력한 상태 추적 능력을 제공하며 선형 계산 복잡성을 가지지만, 엄격한 순차적 계산에 제약받아 효과적인 병렬화가 불가능합니다. 구조화된 상태 공간 모델 (S4, Mamba) 이나 하이브리드 아키텍처와 같은 이러한 트레이드오프를 조정하려는 최근 시도들은 병렬 스캔을 가능하게 하기 위해 전이 역학에 선형 또는 결합적 (associative) 제약을 부과하는 경우가 많으며, 이는 완전히 게이트된 재귀 네트워크에 내재된 풍부한 비선형 및 컨텍스트 의존적 계산을 희생할 수 있습니다.

방법론

저자들은 전이 역학을 선형 또는 결합적 형태로 제한하지 않고 병렬성을 드러내도록 설계된 계층적 재귀 아키텍처인 **병렬 재귀 LSTM(PR-LSTM)**을 소개합니다.

아키텍처 구조: PR-LSTM 은 표준의 왼쪽에서 오른쪽으로 이어지는 순차적 체인을 균형 잡힌 계산 트리 위의 재귀적 비선형 상태 구성으로 대체합니다.
- 상태 임베딩: 입력 토큰은 상태 임베딩 모듈을 통해 잠재 상태 $(h, c)$ 로 독립적으로 매핑되어 시퀀스 전체에 걸쳐 완전한 병렬화를 가능하게 합니다.
- 재귀적 구성: 학습된 LSTM 인코더는 병렬 스캔 축소와 유사한 균형 축소 일정에 따라 인접한 상태 쌍을 재귀적으로 병합합니다. 이 과정은 시퀀스 길이 $T$ 에 대해 $\log T$ 단계로 수행됩니다.
- LSTM 인코더: 핵심 구성 연산자는 두 상태를 병합하는 이진 구성을 수행한 후 단일 결과 상태를 변환하는 단일 정제를 수행하는 수정된 LSTM 셀입니다. 이 두 단계 과정은 트랜스포머 인코더 블록의 조직화와 loosely(대략적으로) 유사하지만, 전역 어텐션을 통한 것이 아니라 계층적으로 정보를 집계합니다.
실행 일정: 핵심적으로 PR-LSTM 은 결합적 연산자가 필요한 결합적 접두사 계산이 아닌, 학습된 비결합적 비선형 게이트 구성 연산자에 대한 고정 실행 일정으로서 병렬 스캔 축소 패턴을 활용합니다. 이를 통해 모델은 비선형 재귀의 표현력을 유지하면서 병렬 하드웨어를 활용할 수 있습니다.
복잡도: 이 아키텍처는 표준 RNN 의 $O(T)$ 인 재귀적 병렬 깊이를 $O(\log T)$ 로 줄이면서도 선형 총 작업량 ( $O(T)$ ) 을 유지하여 어텐션 메커니즘과 관련된 이차적 활성화 증가를 피합니다.

주요 기여

PR-LSTM 아키텍처: LSTM 스타일 계산을 엄격한 순차적 체인이 아닌 상태 업데이트의 균형 잡힌 계층 구조로 재구성한 재귀 아키텍처.
다단계 인코더: 인접한 잠재 상태를 비선형 게이트 업데이트를 통해 병합하여 균형 잡힌 계층 구조에서의 재귀 계산을 가능하게 하는 새로운 LSTM 기반 인코더.
비결합적 병렬성: 결합적 재귀 관계를 가정하지 않고 병렬성을 드러내기 위해 병렬 스캔 축소 패턴을 실행 일정으로 활용함.
실증적 검증: PR-LSTM 이 어텐션의 이차적 스케일링을 피하면서 병렬 깊이를 줄이면서도 강력한 형식 언어 길이 일반화를 달성함을 입증.

결과

저자들은 Delétang 등 (2023) 이 제안한 형식 언어 벤치마크에서 PR-LSTM 을 평가했으며, 정규 (R), 결정적 컨텍스트 자유 (DCF), 컨텍스트 민감 (CS) 언어에 걸친 15 가지 작업을 포함했습니다.

일반화 성능: PR-LSTM 은 15 개 작업 중 6 개에서 성공적으로 일반화 (점수 $\ge$ 90%) 하여 표준 RNN(4/15), LSTM(5/15), 트랜스포머 인코더 (2/15) 를 능가했습니다. 특히, 이전에 메모리 증강 Tape-RNN 에 의해서만 달성된 "Missing Duplicate" 작업을 해결함으로써 계층 구조가 장거리 정보 검색을 지원함을 시사했습니다.
효율성: 훈련 역학에서 PR-LSTM 은 대부분의 작업에서 LSTM 및 트랜스포머 베이스라인보다 더 빠르게 낮은 훈련 손실에 도달했습니다.
스케일링 동작: 추론 시간과 메모리 소비를 증가하는 시퀀스 길이에 대해 측정했습니다. PR-LSTM 은 순차적 LSTM 에 비해 (로그 깊이에 부합하는) 현저히 낮은 추론 시간 증가와 선형 메모리 증가를 보였습니다. 반면, 트랜스포머는 이차적 스케일링으로 인해 더 짧은 시퀀스 길이에서 메모리 한계에 도달했고, 순차적 LSTM 은 추론 시간 임계값에 의해 제한되었습니다.
애블레이션 연구:
- 파라미터 수: 성취된 이득은 단순히 증가된 파라미터 때문이 아니었으며, 파라미터가 일치된 변형도 유사한 일반화 능력을 유지했습니다.
- 정제 깊이: 정제 단계를 제거 (0 단계) 하면 여러 작업에서 성능이 저하되어 이진 구성 후 추가적인 비선형 처리가 유익함을 나타냈습니다.
- 게이팅 메커니즘: LSTM 인코더를 단순한 ReLU 변환 (PR-RNN) 으로 대체하면 장거리 상태 추적이 필요한 작업에서 특히 성능이 크게 감소하여 게이트된 메모리 역학의 필요성을 확인시켰습니다.

의의 및 주장

이 논문은 PR-LSTM 이 엄격한 순차적 재귀와 완전한 어텐션 기반 모델링 사이의 "중간 지대"를 나타낸다고 주장합니다. 저자들은 비선형 재귀 계산을 전이 역학을 선형 또는 결합적 형태로 제한하지 않고 병렬 하드웨어를 더 잘 활용하도록 계층적으로 재구성할 수 있다고 주장합니다.

이 연구의 의의는 다음을 입증하는 데 있습니다:

재귀 모델은 카운팅 및 장기 상태 추적과 같은 핵심 능력을 유지하면서 로그 병렬 깊이를 달성할 수 있다.
병렬 스캔 축소 패턴은 고정된 균형 트리 계산 일정으로 해석될 경우 비결합적 비선형 연산자에 적용될 수 있다.
재귀의 계층적 재구성은 어텐션의 이차적 비용을 피하면서도 게이트된 재귀 네트워크의 표현력을 유지하는 확장 가능한 시퀀스 모델링을 위한 실현 가능한 경로이다.

저자들은 이러한 발견의 범위에 대해 겸손하게 접근하며, 평가가 형식 언어 작업과 통제된 길이 일반화에 국한됨을 지적합니다. 그들은 PR-LSTM 을 대규모 언어 모델링, 멀티모달 학습, 개방형 추론 벤치마크에서 평가하기 위한 추가 작업이 필요하다고 명시적으로 언급합니다.