On the Ability of Transformers to Verify Plans

이 논문은 변환기 (Transformer) 모델이 주어진 계획 (Plan) 이 특정 계획 문제 (Planning Instance) 를 올바르게 해결하는지 검증하는 능력과, 특히 훈련 데이터의 길이보다 긴 계획에 대한 일반화 (Length Generalization) 능력에 대한 이론적 및 실험적 분석을 다룹니다. 기존에 LLM 이 계획 작업에서 일관되지 않은 성과를 보인 이유를 이론적으로 규명하고, 어떤 구조적 속성이 일반화를 가능하게 하는지 제시합니다.

주요 내용은 다음과 같습니다.

1. 문제 정의 (Problem)

• 배경: 변환기 기반 대규모 언어 모델 (LLM) 은 다양한 작업에서 뛰어난 성능을 보이지만, AI 계획 (AI Planning) 분야에서는 종종 실패합니다. 특히 계획이 길어질수록 세계 상태 (World State) 를 놓치거나 적용 불가능한 행동을 제안하는 등 성능이 급격히 저하됩니다.
• 핵심 질문: "짧은 계획으로 훈련된 변환기가 긴 계획을 검증할 수 있는가?" (Length Generalization)
• 도전 과제: 기존 연구들은 훈련과 추론 시 토큰 어휘 (Vocabulary) 가 동일하다는 가정 하에 일반화를 분석했습니다. 하지만 실제 계획 문제에서는 객체의 수가 증가함에 따라 유효 입력 알파벳 (Effective Input Alphabet) 이 커지는 상황 (Variable Universe) 이 발생합니다. 이는 기존의 C-RASP 기반 분석 프레임워크로는 다루기 어려운 문제입니다.

2. 방법론 (Methodology)

2.1. 이론적 프레임워크: C*-RASP 도입

• C-RASP 확장: 기존 C-RASP (Counting RASP) 언어를 확장하여 C-RASP*를 제안했습니다. 이는 훈련 시와 추론 시에 시퀀스 길이와 어휘 크기 (Vocabulary Size) 가 동시에 증가하는 상황을 모델링할 수 있도록 설계되었습니다.
• 심볼릭 리미트 변환기 (Symbolic Limit Transformer): 훈련 데이터의 길이나 객체 수가 무한히 증가할 때 수렴하는 변환기의 알고리즘을 정의했습니다. 이 모델은 절대적인 위치나 객체 ID 에 의존하지 않고, **상대적 차이 (Translation Invariance)**와 **국소성 (Locality)**을 기반으로 작동해야 합니다.
• 매치 프리디케이트 (Match Predicate): C*-RASP 에 새로운 연산자를 추가하여, 고정된 알파벳이 아닌 가변적인 객체 ID 들 간의 일치를 국소적인 패턴 매칭을 통해 확인할 수 있도록 했습니다. 이는 객체의 구체적인 이름에 의존하지 않고 구조적 관계를 파악하는 능력을 의미합니다.

2.2. 계획 하위 클래스 분석

논문은 계획 도메인을 다음과 같이 분류하여 변환기의 검증 능력을 분석했습니다:

1. Delete-Free (삭제 없는): 행동이 긍정적 효과만 가지는 경우.
2. Well-Formed (잘 형성된): 행동이 적용될 때 상태가 반드시 변하는 경우 (중복된 상태 전이 없음).
3. STRIPS: 조건부 효과가 없는 표준 형식.
4. Conditional Effects (조건부 효과): 행동의 효과가 현재 상태에 따라 달라지는 경우.

2.3. 실험 설계

• 도메인: Heavy Grippers (로봇 팔), Colors (색상 가방), Lights Out (전등 스위치) 세 가지 도메인을 사용하여 데이터셋을 생성했습니다.
• 변형: 각 도메인에 대해 'Well-Formed', 'Delete-Free', 'STRIPS', 'Conditional Effects' 등 다양한 변형을 만들어 훈련 (길이 11100) 및 테스트 (길이 101200, 객체 수 증가) 를 수행했습니다.
• 모델: GPT-2 아키텍처를 기반으로 한 디코더 전용 변환기를 사용했습니다.

3. 주요 기여 및 결과 (Key Contributions & Results)

3.1. 이론적 결과

• 일반화 가능 영역: Delete-Free 및 Well-Formed인 계획 도메인은 C*-RASP 로 표현 가능하므로, 변환기가 객체 수와 계획 길이가 동시에 증가하더라도 완벽하게 일반화할 수 있음이 증명되었습니다.
• 일반화 불가능 영역: 일반적인 STRIPS 도메인이나 **조건부 효과 (Conditional Effects)*가 포함된 도메인은 C-RASP 로 표현할 수 없습니다. 이는 'Flipflop'이나 'PARITY' 언어와 같은 계산적 복잡성을 내포하고 있어, 변환기가 긴 계획이나 새로운 객체 집합에 대해 일반화하지 못함을 의미합니다.
• 구조적 속성의 중요성: 계획 문제의 일반화 가능성은 단순히 객체 수나 행동 수의 문제가 아니라, **행동과 상태의 구조적 속성 (Well-Formedness 등)**에 의해 결정됨을 규명했습니다.

3.2. 실험적 결과

• Well-Formed/Delete-Free: Heavy Grippers 와 Colors 도메인의 Well-Formed 및 Delete-Free 변형은 훈련 데이터보다 훨씬 긴 계획과 더 많은 객체가 포함된 테스트 데이터에서도 **높은 정확도 (거의 100%)**를 보였습니다.
• STRIPS/Conditional Effects:
  • Colors 의 STRIPS 변형은 Well-Formed 에 비해 성능이 떨어졌습니다.
  • Lights Out 의 조건부 효과 (Conditional Effects) 변형은 **우연 수준 (Chance level)**의 성능만 보였으며, 객체 수가 고정된 경우에도 일반화에 실패했습니다.
  • 반면, 동일한 Lights Out 문제를 Well-Formed 형식으로 재구성 (행동 수를 기하급수적으로 늘려 조건부 효과를 제거) 했을 때는 완벽한 일반화 성능을 보였습니다.

4. 의의 및 시사점 (Significance)

1. 이론적 설명의 제공: LLM 이 계획 작업에서 왜 일관되지 않은 성과를 보이는지에 대한 명확한 이론적 근거를 제시했습니다. 즉, 문제의 구조가 Well-Formed 여부에 따라 일반화 가능성이 결정된다는 것을 증명했습니다.
2. 실용적 함의: 많은 실제 계획 벤치마크 (IPC 등) 와 학습용 도메인이 Well-Formed 특성을 가지고 있으므로, 변환기를 활용한 계획 검증은 특정 조건 하에서 매우 유망함을 시사합니다.
3. 문제 재구성 (Reformulation) 의 중요성: 조건부 효과가 있는 복잡한 문제를 Well-Formed 형식으로 변환 (Compile) 하면, 변환기의 학습 능력을 극적으로 향상시킬 수 있음을 보여주었습니다. 이는 계획 문제의 표현 방식이 모델의 성능에 결정적임을 의미합니다.
4. 새로운 분석 도구: C*-RASP 와 Symbolic Limit Transformer 는 어휘가 확장되는 환경에서의 변환기 일반화 능력을 분석하는 새로운 표준 프레임워크를 제공합니다.

결론

이 논문은 변환기가 계획 검증에서 실패하는 원인을 단순히 모델의 한계가 아니라, 문제의 구조적 복잡성과 학습 가능한 알고리즘의 표현 가능성에서 찾았습니다. 특히 Well-Formed 또는 Delete-Free인 도메인에서는 변환기가 훈련 데이터의 길이와 객체 수를 넘어선 일반화가 가능하다는 것을 이론적으로 증명하고 실험적으로 입증함으로써, AI 계획 분야에서 LLM 의 적용 가능성을 명확한 조건 하에 제시했습니다.