그래프 월드 모델로 LLM 장기 로봇 계획을 실행 전에 검증하고 수리하는 GAVEL
GAVEL: Graph World Models for Verified and Efficient Long-Horizon LLM Task Planning
무엇인가
LLM을 로봇의 고수준 플래너로 쓰면 자연어 지시를 장기 행동 시퀀스로 바꿀 수 있지만, 생성된 계획이 실제로 실행 가능하다는 보장이 없다. 사전 조건 행동을 빠뜨리거나, 로봇의 신체(embodiment) 제약을 위반하거나, 목표 상태에 도달하지 못한 채 끝난다. 논문은 LLM 단독 플래너의 실패율이 계획 지평이 길어질수록 커지고, 특히 엣지 배포를 겨냥한 소형 모델에서 두드러진다고 지적한다. 부분 관측 환경에서 물체 위치를 모르는 상태로 여러 하위 작업을 수행해야 할 때는 문제가 더 복잡해진다. GAVEL은 이 두 문제, 즉 계획의 실행 가능성 검증과 불확실성 하의 작업 순서 결정을 하나의 명시적 그래프 월드 모델로 묶는다.
어떻게 동작하나
환경은 타입이 있는 씬 그래프 G=(V,E,Φ)로 표현된다. 정점은 방 인스턴스, 물체, 로봇으로 구성되고, 간선은 near, under, room_connect, room_inside, object_inside, on_top, next_to, holding 같은 관계를, Φ는 open, toggled, cooked, washed, dried 같은 단항 플래그를 담는다. 로봇의 숨은 실제 상태 G*와 로봇이 믿는 그래프 G를 구분하고, 각 행동 a는 그래프 값 사전조건과 효과 pre_a, eff_a를 갖는다. 행동 공간은 NavigateTo, Grasp, Release, PlaceOnTop, PlaceInside, Open, Close, ToggleOn, ToggleOff 아홉 개의 그라운딩된 프리미티브다. 사전조건은 근접성, 어포던스, 그리퍼 상태, 접근성 네 가지 실행 가능성을 포착하는데, 닫힌 용기 안의 물체는 열기 전에 NavigateTo로 겨냥할 수 없다. 효과는 관계와 상태를 갱신하며, 계획 중 연 용기는 닫아야 하고 켠 안전 필수 가전은 꺼야 한다는 복원 제약도 추적한다.
무엇과 다른가
지시는 먼저 N개의 작업으로 분해되고, Qwen3-1.7B의 경량 LoRA 어댑터 두 개가 각각 작업 관련 물체·관계와 목표 부분 그래프를 추출한다. 이 어댑터는 8,000개의 합성 지시-타깃 쌍으로 학습되고 500개 검증셋을 쓴다. 위치가 불확실한 물체에 대해서는 SEEK의 RSN 구성을 따라 방 위치 사전확률을 초기화한다. 동결 텍스트 인코더 BAAI/bge-small-en-v1.5가 384차원 임베딩을 만들고 3층 MLP(256-128-64, dropout 0.2)가 방 타입별 점수를 예측하며, 타입 점수는 해당 타입의 도달 가능한 방 인스턴스에 균등 분배된 뒤 정규화된다. 이후 LLM이 작업별 행동 계획을 한 번 생성하면, 그래프 월드 모델이 계획을 앞으로 롤아웃하며 사전조건을 확인한다. 위반이 나오면 롤아웃을 멈추고 목표 g_i와 추적 수준 안전 제약을 검사해 unmet(g_i, G_H)=∅ 및 safe(π_i) 여부를 판정한다.
어떻게 쓰나
핵심은 실패의 수리 주체를 나눈 것이다. 근접성 부족으로 실패한 Grasp는 NavigateTo를 유도하고, 닫힌 용기 안의 물체는 컨테이너로 이동한 뒤 Open을 유도하는 식으로, 행동 모델 자체가 정정을 함의하는 실패는 그래프가 직접 수리한다. 방문 집합 S로 순환 수리를 막고, 수리가 계획을 단조 개선한다는 보장이 없으므로 rk(ω,π) = (1[ω.app], 1[ω.unmet=∅], 1[ω.safe], -ω.d) 순위로 이전 최선 후보를 보존한다. 의미적 추론이 필요한 실패만 구조화된 판정과 함께 LLM으로 되돌리며, LLM 호출은 T회(예: 5)로 제한된다. 다중 작업 지시에서는 미탐색 물체의 방 위치 분포로 탐색 비용 κ_k와 기대 탐색 비용 C_srch, 국소화된 물체의 C_loc를 계산하고, J(ς) = h[ς1] + Σ A[ς_{p-1}, ς_p]로 순서 비용을 근사한다. O(N²) 롤아웃으로 h와 A를 만들고 N≤5이므로 모든 순열을 열거해 최소 비용 순서를 정확히 고른다. 최소 비용 순서의 첫 작업만 실행하고, 관측으로 믿음을 갱신한 뒤 남은 순서를 다시 최적화한다.
전제와 한계
실험은 BEHAVIOR-1K의 기호적 행동 수준에서 수행된다. 단일 작업 벤치마크는 10개 씬에 걸친 100개 장기 작업으로, 참조 계획이 평균 12.2개 프리미티브(8~17개)이고 목표 술어 240개를 포함한다. 다중 작업 벤치마크는 500개 지시로 N∈{2,3,4,5}이고 평균 18.8개 프리미티브, 4.66개 방을 넘나들며, 199개는 가전 조작으로만 만들어지는 의미 상태를 요구한다. 2D 경량 실행기를 써서 실행 시간을 계획당 약 17분에서 1초로 줄여 5,500회 평가를 가능하게 했고, 100개 단일 작업 지시를 OmniGibson에서도 돌려 성공 여부가 실행기와 모두 일치함을 확인했다. 결과는 5개 랜덤 시드 평균이다.
단일 작업에서 LLM 단독 계획은 Qwen3-4B 21.8%, Qwen3-8B 41.2%에 그쳤다. SayPlan식 검증 피드백 루프는 55.4%와 76.4%로 올렸지만 작업당 3.4회, 2.7회의 LLM 호출이 필요했다. 그래프 수리만 수행하고 LLM을 다시 부르지 않는 gavel-basic은 Qwen3-4B에서 67.7%, Qwen3-8B에서 76.2%를 기록해, Qwen3-4B에서는 피드백 전용 재계획을 12.3%포인트 앞서면서 호출은 3.4회가 아니라 1회만 썼다. 남은 의미적 실패만 LLM에 되돌리는 완전한 GAVEL은 88.8%와 91.8%까지 오르고 평균 호출은 1.7회, 1.5회다. Qwen3-4B의 계획 시간도 27.6초에서 15.0초로 줄었다.
다중 작업에서는 실패가 누적되어 LLM 단독이 19.9%에 머물렀고, SayPlan식 베이스라인은 75.6%, GAVEL은 92.6%를 달성했다. 두 방법이 모두 성공한 지시 집합에서 이동 거리는 83.01m에서 78.01m로 줄고 계획 시간도 지시당 약 12초 감소했다. 그래프 편집만으로 계획을 합성하는 EPoG식 베이스라인은 60.2%에 그쳤는데, 실패가 정확히 cooked, washed, dried 같은 가전 유발 의미 상태가 필요한 지시에 몰렸다. 접시를 씻으라는 지시는 식기세척기를 돌려야 한다는 절차를 그래프 상태 차이만으로는 지정할 수 없기 때문이다. 불확실성 추론을 분리한 결과, 최빈 방으로 믿음을 붕괴하는 gavel-map이 82.45m, 분포는 유지하되 순서를 고정한 gavel-static이 79.69m, 매 작업 후 재정렬하는 GAVEL이 78.01m로 총 4.45m(약 5.4%)를 절약했고 순서 최적화 자체는 지시당 17ms밖에 걸리지 않았다. RSN은 51개 씬, 197개 물체 범주, 37개 방 타입에 걸친 11,218개 배치로 학습해 AUC 0.904, Brier 0.057을 기록했지만, 832개 홀드아웃 질의에서 실제 방이 1위로 랭크된 비율은 47%에 불과해 최빈값 붕괴가 정보를 버린다는 점을 보여준다. 비용 모델은 4개 작업 R²=0.93, 5개 작업 R²=0.89였다. 모델 스케일링 실험에서 GAVEL 없이 Qwen3-4B 2.4%, Qwen3-8B 23.6%, GPT-5.6 Sol 24.6%, Claude Sonnet 5 38.6%였던 100개 지시 부분집합에서, GAVEL을 붙인 Qwen3-4B는 75.2%, Qwen3-8B는 89.2%로 올랐고 두 호스티드 모델은 거의 완벽에 가까운 성공률을 보였다. 호스티드 모델의 계획 시간은 GPT-5.6 Sol이 16.5초로 유지됐고 Claude Sonnet 5는 18.0초에서 18.2초로만 변했다.
개발자 관점에서 이 논문의 실용적 메시지는 LLM 호출을 줄이는 것과 신뢰성을 높이는 것이 같은 방향일 수 있다는 점이다. 계획 실패의 상당 부분이 행동 의미론만으로 정정이 결정되는 국소적 오류이므로, 그런 오류를 LLM에 되묻는 대신 그래프 전이 모델로 직접 고치면 호출 수와 지연이 함께 줄어든다. 다만 GAVEL은 방 배치와 연결성이 알려져 있고, 작업들이 서로 독립이며 목표 물체 집합이 겹치지 않는다는 전제 위에 서 있다. 행동 공간도 아홉 개 프리미티브로 고정되어 있고, 평가가 기호적 조작 수준이라 그래프가 논리적 행동 결과는 잡지만 기하학적 실행 가능성은 잡지 못한다. 저자들은 모션 수준 도달 가능성과 충돌 제약을 추가하면 같은 검증-수리 메커니즘을 물리 실행으로 확장할 수 있다고 본다. 또한 의미 사전확률이 주로 방 타입에 조건화되어 있어 반복 관측으로 환경 특화 규칙성을 학습하면 개선 여지가 있고, 남은 실패의 대부분이 그래프 계획이 아니라 지시 그라운딩에서 나온다는 점을 다음 병목으로 지목한다. 다중 작업의 38개 잔여 실패 중 21개가 물체 추출, 5개가 실행 불가 계획, 9개가 미충족 목표였다.