Understanding LLM Failures: A Multi-Tape Turing Machine Analysis of Systematic Errors in Language Model Reasoning

논문 요약: 대규모 언어 모델 (LLM) 실패의 이해 - 다중 테이프 튜링 머신을 통한 체계적 오류 분석

1. 문제 제기 (Problem)

대규모 언어 모델 (LLM) 은 겉보기에 단순한 작업에서도 실패하는 경향이 있습니다. 예를 들어, "Strawberry"라는 단어에 'r'이 몇 번 등장하는지 세는 작업이나, 중첩된 문장 구조 (예: "The cat that the dog that the mouse feared chased...") 를 완성하는 작업에서 LLM 은 인간에 비해 현저히 낮은 성능을 보입니다. 기존 연구들은 이러한 현상을 기하학적 비유나 경험적 스케일링 법칙 (Scaling Laws) 으로 설명하려 했으나, 어떤 단계에서 왜 오류가 발생하는지에 대한 엄밀한 계산적 분석과 오류 국소화 (Localization) 에는 한계가 있었습니다.

2. 방법론 (Methodology)

저자는 LLM 의 상호작용 과정을 **결정론적 다중 테이프 튜링 머신 (Deterministic Multi-Tape Turing Machine, TM)**으로 형식화하여 분석합니다. 이 모델은 LLM 의 파이프라인을 7 개의 독립적인 테이프와 해당 테이프를 조작하는 상태 전이 함수로 세분화합니다.

• 7 개의 테이프 구성:

  1. Tape 1 (Chars-in): 원시 입력 문자 (Raw prompt).
  2. Tape 2 (Tokens): 토큰화 된 시퀀스 (정수 ID 로 저장).
  3. Tape 3 (Tokeniser + Vocab): BPE 병합 규칙, 어휘, 역어휘 매핑 등 토크나이저 정보.
  4. Tape 4 (Model spec): 모델 아키텍처 메타데이터 및 파라미터 (가중치).
  5. Tape 5 (Work): 중간 활성화 값, KV 캐시, 어텐션 및 피드포워드 계산에 사용되는 임시 스크래치 공간.
  6. Tape 6 (Logits/Probs): 다음 토큰의 점수 또는 확률 분포.
  7. Tape 7 (Chars-out): 디토크나이징을 거쳐 생성된 최종 문자 출력.

• 운영 단계:

  • 토크나이징: Tape 1 의 문자를 Tape 3 의 규칙을 참조하여 Tape 2 의 토큰 ID 로 변환.
  • 순전파 계산 (Forward Computation): Tape 2 의 토큰을 Tape 4 의 파라미터와 Tape 5 의 워크스페이스를 사용하여 어텐션 및 피드포워드 연산을 수행, 결과를 Tape 6 에 기록.
  • 토큰 선택: Tape 6 의 확률 분포에서 그리디 (Greedy) argmax 를 통해 다음 토큰 선택.
  • 디토크나이징: 선택된 토큰을 Tape 3 의 역어휘를 통해 문자로 변환하여 Tape 7 에 기록.

이 형식화를 통해 LLM 의 동작을 재귀 이론 (Recursion Theory) 의 관점에서 분석하고, 계산 가능성과 한계를 규명합니다.

3. 주요 기여 (Key Contributions)

1. LLM 추론의 다중 테이프 TM 형식화: 각 테이프에 고유한 역할을 부여하여 LLM 파이프라인을 명확히 정의.
2. 오류 국소화: 토크나이징 (Tokenization) 과 순전파 계산 (Forward Computation) 등 특정 파이프라인 단계에서 실패가 발생하는 원인을 구체적으로 규명.
3. 계산적 한계 명확화: 명시적 서브루틴이 없으면 접근 불가능한 계산적 단순 작업 (예: 문자 단위 카운팅) 을 식별하여 휴리스틱 전략의 형식적 한계를 밝힘.
4. Chain-of-Thought (CoT) 의 재해석: CoT 를 출력 테이프 (Tape 7) 에 중간 계산 과정을 외부화 (Externalisation) 하는 과정으로 해석하여 그 장점과 한계를 설명.
5. 어텐션 메커니즘의 형식적 분석: 다중 테이프 연산을 통해 어텐션 메커니즘이 어떻게 구현되고 실패하는지 정밀하게 분석.

4. 결과 및 분석 (Results)

• Strawberry 카운팅 문제:

  • 원인: 토크나이징 과정에서 "Strawberry"가 하나의 토큰으로 처리되거나 (Whole-word), 부분적으로만 분할될 경우 (Subword), 모델 내부에서 문자 수준의 반복적 카운팅 루틴이 존재하지 않습니다.
  • 해석: Tape 5 에서 토큰 ID 에 대한 활성화만 누적될 뿐, 문자 단위의 구조를 탐색하는 명시적 서브루틴이 부재하여 정확한 카운팅이 불가능합니다. 이를 해결하려면 qcount 와 같은 명시적 상태 전이가 필요합니다.

• 재귀적 중첩 구조 (Recursive Centre-Embedding):

  • 원인: "The cat that the dog that the mouse feared chased..."와 같은 문장은 문맥 민감적 문법 (Context-sensitive grammar, Type 1) 이 필요하지만, 표준 트랜스포머의 유한한 어텐션 창과 명시적 스택 (Stack) 메커니즘 부재로 인해 문맥 자유 문법 (Context-free, Type 2) 수준으로만 근사됩니다.
  • 해석: qpush, qpop, qcheck 와 같은 스택 기반 상태가 없으므로, 깊은 중첩 구조에서 의존성 추적이 실패합니다.

• Chain-of-Thought (CoT) 의 역할과 한계:

  • 역할: CoT 는 Tape 7 에 중간 추론 단계를 기록함으로써, Tape 5 의 내부 상태 메모리 부담을 줄이고 모델이 자신의 이전 출력을 참조하여 계산할 수 있게 합니다 (외부 스크래치 패드).
  • 한계: CoT 는 계산의 복잡도 클래스를 변경하지 않습니다. 명시적 카운팅 서브루틴이 없으면 CoT 를 통해 철자를 나열하더라도 정확한 카운팅은 불가능하며, 무한한 재귀나 역설 해결은 여전히 모델의 능력 밖입니다.

5. 의의 및 결론 (Significance)

이 연구는 LLM 의 동작을 기하학적 비유가 아닌 **엄밀한 계산 모델 (Turing Machine)**로 재정의함으로써 다음과 같은 의의를 가집니다.

• 오류의 근본 원인 규명: LLM 의 실패가 단순히 데이터 부족이 아니라, 토크나이징의 구조적 결함이나 명시적 알고리즘 서브루틴의 부재와 같은 계산적 한계에서 비롯됨을 보여줍니다.
• CoT 에 대한 이론적 기반: CoT 가 왜 작동하는지 (중간 계산의 외부화) 그리고 왜 실패하는지 (계산 복잡도 한계) 를 통합된 이론적 모델로 설명합니다.
• 향후 연구 방향 제시: 확률적 샘플링, 재귀적 메모리 구조, 외부 도구 사용 등을 위한 확장 가능성을 제시하며, LLM 의 능력 향상을 위한 체계적인 분석 프레임워크를 제공합니다.

결론적으로, 이 형식화는 LLM 의 능력을 경험적 관찰을 넘어 계산 이론의 관점에서 이해하고, 어떤 문제가 원칙적으로 해결 가능한지, 어떤 것이 근본적으로 제한되는지를 규명하는 강력한 도구가 됩니다.