DeepMind에서 발표한 논문 Large Language Models as Optimizers 내용을 살펴보겠습니다.
이 논문은 LLM이 단순히 언어 생성 모델이 아니라, 복잡한 최적화 문제를 해결하는 최적화 도구로도 사용할 수 있다는 아이디어를 설명합니다.
최적화 문제란 주어진 목적 함수를 최소화하거나 최대화하는 변수를 찾는 문제를 의미하는데, 전통적인 최적화 알고리즘으로는 경사하강법, 유전자 알고리즘, 시뮬레이티드 어닐링 등이 있습니다. 하지만 논문에서는 LLM에서 적절한 Prompt 기술을 활용하여 최적화 문제를 해결할 수 있다고 설명합니다.
특히 최적화 문제를 해결하기 위한 Meta Prompt 아이디어를 제시하고 실제로 테스트 할 수 있는 Sample을 제공 하고 있어서 이해하는데 도움이 되었습니다.
Github Repository
논문의 저자는 Github(https://github.com/teshnizi/OptiMUS?tab=readme-ov-file)에 논문의 구현 소스를 공개하고 있고, Linear Regression, TSP 문제를 LLM으로 해결하는 소스 Sample을 제시하고 있습니다. 논문의 이해가 어려운 부분은 구현된 소스 부분을 분석해 보면 이해하는데 도움이 될 것 같습니다.
Meta Prompt로 TSP 문제 해결해보기
논문에 있는 Sample을 이용해서 TSP 문제를 해결해 보는 것을 따라해 볼 수 있습니다.
아래는 논문에서 제안하는 Meta Prompt를 이용해서 TSP 문제의 품질을 높이는 것을 테스트한 것을 옮겨 보았습니다.
2-3번의 Iteration 만으로도 품질(1323 distance → 1056 distance → 932 distance)이 급격하게 개선되는 모습을 확인 할 수 있습니다.
#Query 0
You are given a list of points with coordinates below: (0): (-4, 5), (1): (17, 76), (2): (-9, 0), (3): (-31, -86), (4): (53, -35), (5): (26, 91), (6): (65, -33), (7): (26, 86), (8): (-13, -70), (9): (13, 79), (10): (-73, -86), (11): (-45, 93), (12): (74, 24), (13): (67, -42), (14): (87, 51), (15): (83, 94), (16): (-7, 52), (17): -89, 47), (18): (0, -38), (19): (61, 58).
Below are some previous traces and their lengths. The traces are arranged in descending order based
on their lengths, where lower values are better.
<trace> 0,13,3,16,19,2,17,5,4,7,18,8,1,9,6,14,11,15,10,12 </trace>
length:
2254
<trace> 0,18,4,11,9,7,14,17,12,15,10,5,19,3,13,16,1,6,8,2 </trace>
length:
2017
Give me a new trace that is different from all traces above, and has a length lower than any of the
above. The trace should traverse all points exactly once. The trace should start with <trace> and end
with </trace>.
====
#Result 0
<trace> 0,18,8,19,3,10,13,4,6,14,12,15,5,17,9,7,11,1,16,2 </trace>
length:
1323
====
#Query 1
You are given a list of points with coordinates below: (0): (-4, 5), (1): (17, 76), (2): (-9, 0), (3): (-31, -86), (4): (53, -35), (5): (26, 91), (6): (65, -33), (7): (26, 86), (8): (-13, -70), (9): (13, 79), (10): (-73, -86), (11): (-45, 93), (12): (74, 24), (13): (67, -42), (14): (87, 51), (15): (83, 94), (16): (-7, 52), (17): -89, 47), (18): (0, -38), (19): (61, 58).
Below are some previous traces and their lengths. The traces are arranged in descending order based
on their lengths, where lower values are better.
<trace> 0,13,3,16,19,2,17,5,4,7,18,8,1,9,6,14,11,15,10,12 </trace>
length:
2254
<trace> 0,18,4,11,9,7,14,17,12,15,10,5,19,3,13,16,1,6,8,2 </trace>
length:
2017
<trace> 0,18,8,19,3,10,13,4,6,14,12,15,5,17,9,7,11,1,16,2 </trace>
length:
1323
Give me a new trace that is different from all traces above, and has a length lower than any of the
above. The trace should traverse all points exactly once. The trace should start with <trace> and end
with </trace>.
===
#Result 1
<trace> 0,19,4,6,13,3,8,18,10,2,16,1,9,7,5,11,17,15,14,12 </trace>
length:
1056
====
#Query 2
You are given a list of points with coordinates below: (0): (-4, 5), (1): (17, 76), (2): (-9, 0), (3): (-31, -86), (4): (53, -35), (5): (26, 91), (6): (65, -33), (7): (26, 86), (8): (-13, -70), (9): (13, 79), (10): (-73, -86), (11): (-45, 93), (12): (74, 24), (13): (67, -42), (14): (87, 51), (15): (83, 94), (16): (-7, 52), (17): -89, 47), (18): (0, -38), (19): (61, 58).
Below are some previous traces and their lengths. The traces are arranged in descending order based
on their lengths, where lower values are better.
<trace> 0,13,3,16,19,2,17,5,4,7,18,8,1,9,6,14,11,15,10,12 </trace>
length:
2254
<trace> 0,18,4,11,9,7,14,17,12,15,10,5,19,3,13,16,1,6,8,2 </trace>
length:
2017
<trace> 0,18,8,19,3,10,13,4,6,14,12,15,5,17,9,7,11,1,16,2 </trace>
length:
1323
<trace> 0,19,4,6,13,3,8,18,10,2,16,1,9,7,5,11,17,15,14,12 </trace>
length:
1056
Give me a new trace that is different from all traces above, and has a length lower than any of the
above. The trace should traverse all points exactly once. The trace should start with <trace> and end
with </trace>.
===
#Result 2
<trace> 0,18,8,3,10,2,16,1,9,7,5,11,17,4,6,13,19,12,15,14 </trace>
length:
932
Plain Text
복사
Reference:
