[기획] LLM 하나로는 흔들린 최적화, ‘전문 휴리스틱 팀’ 꾸리자 평균점수 0.945

택배 상자에 물건을 넣는다고 생각해 보자. 큰 물건부터 넣는 방법이 늘 좋은 것은 아니다. 어떤 주문은 모서리부터 채워야 하고, 어떤 주문은 이미 넣은 물건을 꺼내 다시 배치해야 빈 공간이 줄어든다. 공장 일정과 차량 경로를 짜는 일도 비슷하다. 하나의 만능 풀이법보다 서로 다른 상황에 강한 풀이법을 여럿 준비한 뒤, 주문마다 가장 좋은 결과를 고르는 편이 나을 수 있다.

연구진이 같은 OpenAI o3 Mini에 별도 프레임워크 없이 휴리스틱(빠르게 좋은 답을 찾는 경험적 알고리즘)을 직접 만들게 했을 때, CO-Bench 36개 문제의 평균 정규화 목적함수 점수는 0.571이었다. 입력과 출력 규칙, 검사 도구를 먼저 고정하고 LLM이 만든 전문 휴리스틱을 경쟁·보완시키는 LACE를 적용하자 같은 기준의 점수는 0.945로 높아졌다. 절대 차이는 0.374점이었다.

여기서 0.571과 0.945는 시험 정답률이 아니다. 각 사례에서 휴리스틱이 얻은 목적값이 최적값 또는 문헌상 최고 알려진 목적값에 얼마나 가까운지 0부터 1 사이로 나타낸 뒤 문제별로 평균하고, 다시 36개 문제를 같은 비중으로 합친 정규화 점수다. 실행 오류나 제약 위반, 시간초과가 발생하면 0점이 된다. 따라서 이 수치를 생산량이나 운송비가 얼마나 개선됐는지로 바꿔 읽어서는 안 된다.

‘전문가 팀’은 LLM 회의가 아니라 코드 포트폴리오

난양공대·홍콩이공대·리버풀대·국립대만대 연구진은 LACE를 개발해 2026년 10월 1일 연구 결과를 온라인 게재했다. LACE는 ‘LLM-driven Algorithm Construction via Complementary Evolution’의 약자로, ‘상보적 진화를 통한 LLM 기반 알고리즘 구축’이라는 뜻이다.

이름만 보면 여러 인공지능이 회의해 답을 합치는 구조처럼 보이지만 실제로는 다르다. 주 실험에서는 같은 o3 Mini가 서로 다른 전문 휴리스틱 코드를 만들었다. 연구진은 이 코드들을 실행하고 수선하며 진화시킨 뒤 문제당 10개를 최종 포트폴리오로 남겼다. 새로운 사례가 들어오면 10개 휴리스틱을 실행하고 그중 가장 좋은 목적값을 채택했다. 좁은 골목에 강한 기사, 장거리 배차에 강한 기사, 시간제약 처리에 강한 기사를 따로 키운 셈이지만, 사람이나 LLM 10개가 아니라 전문 코드 10개로 구성된 팀이다.

평가 대상인 CO-Bench는 36종, 6,482개 사례로 이뤄졌고 최대 1만1,000개 변수를 포함했다. 생산·작업·승무원 일정, 항공기 착륙, 외판원·차량경로, 시설입지·할당, 포장·절단, 배낭, 트리·그래프·집합 문제를 포괄한다. 36개 모두를 물류나 생산 문제라고 부를 수 없는 이유다. 같은 o3 Mini 조건에서 LACE의 평균은 0.945였고, 논문이 비교한 기존 LLM 기반 생성법 가운데 가장 높은 평균은 0.870이었다.

좋은 답보다 먼저 ‘틀린 답을 거르는 공정’을 만들었다

조합최적화는 수많은 선택지를 조합해 일정, 경로, 배치처럼 조건을 만족하는 좋은 해를 찾는 분야다. 여기서는 코드가 실행된다는 사실만으로 충분하지 않다. 배송거리가 아무리 짧아도 트럭 적재량을 넘기거나 한 차량을 같은 시각에 두 장소에 배정하면 해 전체가 무효가 된다. 제한시간을 넘겨도 0점이다.

LACE는 알고리즘 설계를 입력 형식(Input), 출력 형식(Output), 실행·검증 도구(Tools), 전문 휴리스틱 묶음(Heuristics)의 네 요소로 나눴다. 연구진은 이를 I–O–T–H 인터페이스이자 검증된 ‘문제 계약’으로 설명했다. 자유문으로 작업지시를 받은 뒤 결과만 기다린 것이 아니라, 입력 규격과 출력 규격을 정하고 제약검사와 시간제한이라는 안전장치를 먼저 건 셈이다.

진화 과정은 두 단계로 진행됐다. 새 후보를 만드는 5개 연산자와 오류·성능을 수선하는 2개 연산자를 사용했고, 기존 후보와 새 후보를 비교했다. 마지막에는 혼합정수계획법(MILP·후보 조합을 수학적으로 고르는 방법)으로 서로의 약점을 보완할 휴리스틱을 선별했다. 핵심은 LLM에서 더 그럴듯한 답을 한 번 받아내는 데 있지 않았다. 코드를 실제로 돌리고, 실패 원인을 되돌려 보내고, 다시 고치며, 서로 다른 강점을 가진 결과를 남기는 품질검사 공정을 붙인 데 있었다.

제거실험은 이 수선 과정의 비중을 보여준다. 신규 문제까지 포함한 40개 문제 평가에서 오류수정 연산자를 빼자 평균 정규화 점수는 0.950에서 0.850으로, 유효률은 0.95에서 0.73으로 떨어졌다. 효율수선을 제거했을 때 평균은 0.878, 유효률은 0.85였다. 상보적 교차를 빼면 평균은 0.904였다. LLM이 처음부터 안정적인 코드를 내놓았다기보다 검사와 수선에 크게 의존했다는 뜻이다.

항만 문제에서도 높은 점수, 그러나 실제 항만 실증은 아니다

연구진은 항만 스케줄링 1종과 예인선 경로·일정 3종도 새로 설계했다. 기존 입력 파서와 공식 평가기를 사용한 CO-Bench와 달리, 이 4종에서는 자연어 문제 설명에서 입력·출력·도구·휴리스틱까지 구성하는 종단 간 시험을 했다. LACE는 문제별 0.97~0.99를 기록했다. 비교된 기존 LLM 기반 방법 5개는 이 4종에서 실행 가능한 알고리즘을 만들지 못했다고 연구진은 보고했다.

다만 항만 사례는 현실적 구조를 반영해 만든 합성 인스턴스다. 100~500척 범위의 사례를 사용했지만 실제 항만 운영 기록이나 기상, 장비 고장, 안전규정, 작업자 판단을 포함한 현장시험은 아니었다. 36개 CO-Bench에서도 이미 마련된 입력 파서와 공식 평가기를 이용했으므로 40개 문제 전체를 처음부터 완전 자동 설계했다고 볼 수 없다.

0.945 뒤에 놓인 계산비용과 남은 질문

0.945는 단일 알고리즘의 점수가 아니다. 사례마다 휴리스틱 10개를 실행해 가장 좋은 결과를 골랐기 때문에 단일 휴리스틱을 직접 생성한 기준선보다 후보 수와 탐색 기회가 많았다. CO-Bench에서는 휴리스틱 하나가 사례 하나를 푸는 시간이 10초였지만 포트폴리오 전체에 주어진 시간이 10초였다는 뜻은 아니다. 항만 문제의 보충실험에서도 시간예산이 30초일 때 0.918, 60초일 때 0.980, 90초일 때 0.989로 상승했다.

알고리즘을 찾아내는 준비비용도 컸다. o3 Mini를 이용해 40개 문제를 6회 진화시키는 데 약 1억5,400만 토큰이 사용됐다. 반복별 점수 증가는 +0.039, +0.026, +0.016, +0.008, +0.006, +0.003으로 점차 작아졌다. 완성된 알고리즘은 이후 반복 사용할 수 있지만, 조건이 자주 바뀌는 공장이나 물류망에서 매번 이 탐색비용을 감당할 수 있을지는 검증되지 않았다.

이번 결과는 전문 솔버를 전면적으로 이겼다는 증거도 아니다. 핵심 비교는 LLM 기반 알고리즘 생성법 사이에서 이뤄졌다. 실제 산업 적용을 판단하려면 전문 최적화 프로그램과 기업별 수작업 휴리스틱을 별도로 비교하고, 특정 현장의 최악 성능과 비용을 확인해야 한다. 공식 평가기가 진화 과정에도 사용된 만큼 새로운 데이터 분포와 제약에서 성능이 유지되는지도 살펴야 한다.

코드와 데이터, 문제별 계약, 최종 포트폴리오와 사례별 결과는 공개됐다. 전체 공개자료는 40종, 7,109개 사례를 담고 있다. 그러나 논문 공개 후 약 12일이 지난 2026년 10월 13일 현재, 제3자가 생성 과정 전체를 독립 재현한 결과나 실제 생산·물류 현장에서 검증한 공개 성과는 확인되지 않았다.

LACE의 의미는 LLM이 최적화 전문가를 대체했다는 데 있지 않다. 입력과 출력의 계약, 실행 가능성 검사, 오류와 효율의 수선, 포트폴리오 선별을 결합하면 단발성 코드 생성보다 안정적으로 전문 알고리즘을 설계할 가능성을 보여줬다는 데 있다. 결국 성능을 끌어올린 것은 더 유창한 한 번의 답변이 아니라, 틀린 답을 잡아내고 다시 고치는 공정이었다.

자료: 난양공대·홍콩이공대·리버풀대·국립대만대·카네기멜런대·Springer Nature