RELAGRAM은 신경망이 내부 상태를 여러 차례 갱신한 뒤 답을 내놓는 잠재 재귀를 차량 경로 최적화에 적용한 연구다. 이 방식이 그래프 조합 최적화 문제에도 쓰일 수 있음을 보였지만, 해의 품질은 기존 최고 성능 모델에 미치지 못했다. 연구는 NeurIPS 워크숍 MLxOR에 채택됐으며 BeNeLearn 2026에도 채택됐다.

잠재 재귀는 문제의 답을 모델 내부 상태에 담고, 같은 네트워크에 반복해서 통과시켜 개선하는 방식이다. 답을 한 번에 만들거나, 명시적인 답을 조금씩 수정하는 방식과 다르다. 연구는 이 접근이 한 번에 복잡한 조합 문제를 풀어야 하는 부담을 나누고, 명시적인 답으로 표현되지 않은 내부 정보를 다음 개선 단계까지 보존할 수 있다고 설명한다.

RELAGRAM은 용량 제한 차량 경로 문제(CVRP)를 다룬다. 물류 거점에서 차량 여러 대로 모든 고객에게 물품을 배송하되, 차량별 적재 한도를 지키면서 총 이동 비용을 최소화하는 문제다. 고객 수에 따라 가능한 해의 수가 지수적으로 증가하고, 최적해를 효율적으로 구하는 알고리즘은 알려져 있지 않다.

모델은 문제를 방향 그래프로 표현하고, 각 정점에서 가장 가까운 이웃 k개로 향하는 간선만 토큰으로 인코딩한다. 실험에서는 k를 20으로 설정했다. 답을 담는 상태와 중간 추론을 위한 작업 공간을 초기화한 뒤 잠재 재귀를 네 차례 수행한다. 각 차례에는 작업 공간을 갱신하고, 이어 답 상태를 갱신한다. 두 블록으로 구성된 작은 트랜스포머가 두 갱신을 모두 수행한다.

마지막 답 상태는 간선별 점수로 변환된다. 디코더는 이 점수를 이용해 경로를 구성하고 차량 용량 제한을 지킨다. 논문에서는 점수가 가장 높은 이동을 고르는 탐욕적 디코딩, 점수에 따라 이동을 무작위로 뽑는 확률적 디코딩, 확률적 디코딩으로 만든 경로를 탐색하는 방법을 사용했다. 학습에는 REINFORCE와 인스턴스별 평균 보상 기준선, 자기 모방 손실도 적용했다. 자기 모방은 한 문제에서 생성한 해 가운데 가장 좋은 해를 기준으로 삼아 나머지 해를 교차 엔트로피 손실로 학습하는 방식이다.

모델은 학습 때 재귀를 네 차례 수행했지만, 큰 그래프에서는 추론 단계에서 반복 횟수를 늘리면 해가 눈에 띄게 좋아졌다. 소개 페이지는 문제 크기에 맞춰 추론 계산량을 조정할 수 있으며 추가 학습이나 별도 엔지니어링이 필요하지 않다고 설명한다. 다만 RELAGRAM은 최첨단 성능에 도달하지 못했고, 간선 기반 DeepACO를 포함한 다른 모델이 더 나은 해를 냈다.

논문 읽기 · 포스터 보기