먼저 쉬운 답부터. 배송 순서나 공장 작업 순서를 잘 정하는 알고리즘은 상황에 따라 강점이 다르다. LACE는 LLM에게 완성 코드 하나를 부탁하는 대신, 먼저 입출력과 검증 도구를 맞추고 서로 다른 사례를 잘 푸는 휴리스틱 묶음을 진화시킨다. 논문의 평균 점수 0.945보다 먼저 볼 것은 이 역할 분리다. 0.945는 실제 물류비를 94.5% 줄였다는 뜻이 아니다.[1][2]
#첫 도식 읽기: 입력·출력·검증·후보를 분리한다
이 도식은 원논문의 그림을 복제한 것이 아니라 공개된 I-O-T-H 구조를 설명하는 자체 교육 도식이다. 왼쪽의 문제 설명과 사례 파일이 입력 형식, 출력 형식, 도구 모음으로 정리되고 그 안에서 휴리스틱이 실행된다. 도구 모음의 두 질문은 “제약을 지켰나?”와 “목적값이 얼마인가?”다. 실행 결과가 좋지 않으면 후보를 수정하지만, 채점기 자체가 잘못됐다면 높은 점수도 의미가 없다. 원논문 Figure 1의 구조 설명과 공개 저장소의 모듈 구분을 함께 읽을 수 있다.[1][3]
처음 읽는 분 조합최적화와 휴리스틱을 처음 읽는다면 그림으로 보기
조합최적화는 여러 선택을 묶어 제약을 만족하면서 좋은 답을 찾는 문제다. 예를 들어 작업 세 개를 한 기계에서 처리할 때 가능한 순서가 여섯 개라면 전부 비교할 수 있다. 작업이 많아지고 납기·장비·인력 제약이 붙으면 모든 조합을 확인하기 어려워진다. 휴리스틱은 정해진 시간 안에 괜찮은 해를 찾는 전략이지, 언제나 최적이라는 증명은 아니다.
같은 배송 문제도 목적이 다를 수 있다. 총 이동거리 최소화와 가장 늦게 도착하는 차량의 지연 최소화는 다른 평가다. 실행 가능한 해(feasible solution)는 제약을 지킨 답이고 좋은 해는 그중 목적값이 우수한 답이다. 문법이 맞는 Python 코드, 오류 없이 끝난 프로그램, 제약을 만족하는 해, 높은 품질의 해는 각각 다른 단계다. LACE를 읽을 때 이 네 층을 섞지 않는 것이 출발점이다.
#1. 왜 완성 알고리즘을 한 번에 생성하면 어려운가
LLM은 그럴듯한 탐색 전략을 설명하면서도 입력 파일의 단위를 혼동하거나 작업의 중복 배정을 허용할 수 있다. 알고리즘 아이디어가 좋아도 파서가 사례를 잘못 읽으면 결과를 비교할 수 없다. 반대로 실행은 끝나도 금지된 경로를 이용하거나 자원 용량을 초과하면 해가 아니다. 직접 프롬프팅은 이런 문제 정의와 구현, 탐색을 동시에 맞춰야 한다.[1][3]
공장 일정의 한 제약을 추가하는 일도 단순한 문장 수정에 그치지 않는다. 입력 스키마에 필드가 생기고 출력의 의미가 바뀌며, 검증기와 목적함수도 이를 반영해야 한다. 그래서 자동 알고리즘 설계에서 중요한 것은 더 긴 코드를 생성하는 능력만이 아니다. 같은 문제를 모든 후보가 같은 의미로 풀고, 동일한 규칙으로 평가받게 만드는 기반이 필요하다.
이번 연구의 질문은 이 기반을 먼저 구성하면 LLM의 탐색 능력을 더 잘 사용할 수 있는가다. 입력·출력·도구·휴리스틱의 경계를 분리하고 실행으로 확인한 뒤 높은 수준의 전략을 바꾼다. 전문가가 알고리즘을 손으로 전부 만드는 방식과 완성 프로그램을 한 번에 생성하는 방식 사이에, 검증 가능한 반복 개발 과정을 둔 셈이다.[1][2]
#2. I-O-T-H는 네 종류의 책임을 나누는 계약이다
I는 입력 스키마, O는 출력 스키마, T는 도구 모음, H는 휴리스틱 포트폴리오다. 공개 구현에는 입력·출력·도구를 설계하는 생성 과정이 있으며, 이미 배포된 문제에는 계약이 포함돼 있다. 따라서 “모든 계약을 사람이 직접 작성해 줬다”와 “아무런 검증 없이 LLM이 전부 알아서 한다”는 설명은 둘 다 부정확하다. 계약 생성도 자동화하되 실제 휴리스틱이 끝까지 실행되는지 확인하는 단계가 있다.[2][3]
도구에는 is_feasible()과 objective() 같은 검증·평가 기능이 있다. 새로운 후보는 이 인터페이스에 맞춰 답을 만들고, 같은 도구로 제약과 목적값을 평가받는다. 매번 입출력과 채점 코드를 다시 생성하는 대신 공통 계약을 사용하면 비교의 일관성이 높아지고, LLM의 수정 노력을 탐색 전략에 집중시킬 여지가 생긴다.
다만 스모크 테스트는 형식 명세의 완전한 증명이 아니다. 예제 하나가 통과했다고 모든 경계 조건에서 목적함수가 맞는 것은 아니다. 특히 생성기와 검증기가 같은 오해를 공유하면 오류가 눈에 띄지 않을 수 있다. 실제 적용에서는 기준 해, 금지된 해, 빈 입력, 극단적인 용량과 동률 사례를 사람이 이해한 규칙과 대조해야 한다. 이는 이번 결과를 부정하는 조건이 아니라, 자동화된 계약을 운영에서 신뢰하기 위한 별도의 책임이다.
#3. 좋은 한 개보다 상보적인 여러 개를 고른다
LACE의 두 번째 단계는 제한 시간 아래에서 후보를 생성·수정하고 포트폴리오를 갱신하는 과정이다. 공개 자료는 다섯 생성 연산과 두 복구 연산을 구분한다. 기존 후보의 변형, 반성적 재설계, 상보적 교차, 비교 종합, 다양성 주입으로 새 전략을 만들고, 실행 오류와 시간 초과에 대해서는 별도의 복구를 수행한다. 일곱 연산을 모두 독립적인 새 알고리즘 가족이라고 부르는 것은 아니다.[2][3]
선택에서 중요한 것은 평균 점수 상위 열 개를 무조건 유지하는 것이 아니다. 비슷한 사례에서 모두 잘하고 같은 사례에서 모두 실패하는 열 개는 서로 보완하지 못한다. 사례별 순위를 사용한 혼합정수선형계획(MILP) 선택은 서로의 약점을 메우는 조합을 찾는다. 배포된 포트폴리오는 문제마다 열 개의 진화된 휴리스틱을 포함한다.[2][3]
#두 번째 도식 읽기: 색은 우열이 아니라 담당 영역을 보여준다
도식의 A·B·C와 사례 X·Y·Z는 실험 결과가 아닌 교육용 예시다. A가 X에서, B가 Y에서, C가 Z에서 강하면 한 알고리즘의 평균만 보는 평가와 조합의 최선 성능을 보는 평가가 달라진다. 실제 논문에서는 개발 사례에 대한 순위 행렬로 포트폴리오를 선택한다. 그림은 그 직관만 설명하며 원논문의 MILP 계수나 실제 성능 행렬을 재현하지 않는다.
포트폴리오의 상보성을 수식으로 읽으면? 기호·연산·계산 과정 펼치기
m은 개발 사례 수, S는 남길 휴리스틱 집합, r은 사례 i에서 휴리스틱 h의 순위이며 작을수록 좋다고 둔다. 예를 들어 A의 순위가 1·3·2이고 B가 3·1·1이면 A만의 평균은 2다. 둘을 묶었을 때 사례별 최선 순위는 1·1·1이라 평균은 1이다. 이는 상보적 선택을 설명하는 간단한 형태이며 실제 구현의 모든 MILP 변수·제약을 적은 식은 아니다. 둘을 평가하는 계산비용이 공짜라는 뜻도 아니다.
사례별로 최선의 결과를 선택하는 포트폴리오는 단일 휴리스틱과 실행 조건을 맞춰 비교해야 한다. 열 개를 각각 긴 시간 실행한 결과와 한 개를 짧게 실행한 결과를 무심코 비교하면 전략 효과와 계산량 효과가 섞인다. 논문은 시간 제한과 제거 실험을 제시하지만, 실제 시스템에서는 전체 벽시계 시간과 병렬 자원, 실패 처리까지 함께 기록해야 한다.[2]
#4. 0.945는 무엇을 측정한 숫자인가
논문은 36개 기존 CO-Bench 문제에서 평균 점수 0.945를 보고한다. 가장 강한 기존 LLM 기반 비교 방법은 0.870, 별도 프레임워크 없는 직접 프롬프팅은 0.571이다. 같은 논문 안에서 비교된 평가값이라는 맥락을 유지해야 한다. 이 값을 성공률, 최적해 대비 비율 또는 현실의 비용 절감률로 다시 이름 붙이면 안 된다.[1]
| 비교 | 보고 결과 | 읽어야 할 범위 |
|---|---|---|
| 기존 CO-Bench 36개 문제 | LACE 0.945 | 논문이 정의한 평균 벤치마크 점수 |
| 가장 강한 기존 LLM 방법 | 0.870 | 해당 모델·실험 설정의 비교값 |
| 직접 프롬프팅 | 0.571 | 프레임워크 없이 생성한 비교 기준 |
| 새로운 항만 물류 문제 4개 | 0.97–0.99 | 네 문제 모두 항만·예인선 계열 |
| 공개 재현 자료 | 40개 문제, 7,109개 사례 | 사례 수와 원본 파일 수는 다름 |
0.945−0.870=0.075라는 차이는 같은 점수 척도에서의 차이다. 이를 7.5%p의 정확도 상승이라고 부를 수 있는지는 지표가 정확도인지 먼저 확인해야 한다. 여기서는 그렇다고 확인되지 않았으므로 점수 차이로 표현한다. 36개 문제의 평균만으로 모든 문제와 모든 사례에서 이겼다고 추론할 수도 없다. 세부 분포와 실패 사례, 문제별 시간 비용을 함께 읽어야 한다.
새로운 네 문제에서 비교한 다섯 LLM 기반 방법이 실행 가능한 알고리즘을 만들지 못했다는 결과는 문제 정의와 제약 처리가 중요하다는 해석을 지지한다. 그러나 네 문제 모두 항만 물류 영역이므로, 이것만으로 의료·전력망·로봇 계획의 완전히 다른 조건에 그대로 일반화했다고 할 수 없다. “새로운 문제”는 시험한 구조와 영역 안에서의 표현이다.[1][2]
#5. 공개 코드로 확인할 것과 재현했다고 말할 수 없는 것
저장소는 프레임워크, 40개 문제의 계약, 정확히 7,109개 시험 사례의 매니페스트, 문제당 열 개의 휴리스틱, 평가·재현 스크립트와 Colab을 제공한다. 원본 파일 하나가 여러 사례를 담을 수 있어 파일 수가 7,109보다 작을 수 있다. 숫자를 검증할 때는 디렉터리의 파일 개수가 아니라 매니페스트의 사례 식별자를 기준으로 해야 한다.[3]
또 이미 만들어진 포트폴리오 평가와 처음부터 새 포트폴리오를 진화시키는 실행은 다르다. 전자는 제공된 후보를 재실행하는 경로이고, 후자는 외부 LLM API와 생성 설정을 사용한다. 저장소와 고정 아카이브가 있어도 모델 공급자의 버전·샘플링·호출 결과가 달라지면 새 탐색이 같은 후보를 만들지 않을 수 있다. 공개는 재현의 출발점이지 모든 실행의 결정성을 보증하는 문구가 아니다.[3]
이 글에서는 공개 README·아키텍처 설명과 보충자료의 관련 절을 대조했다. 외부 API를 호출해 새 휴리스틱을 만들거나 공개 코드를 실행해 7,109개 사례를 독립 재현하지 않았다. 생성된 Python을 자신의 작업용 컴퓨터에서 무제한 실행하는 절차도 제공하지 않는다. 실제 자동 설계 시스템은 코드 실행의 권한·파일 접근·시간·메모리를 제한한 격리 환경이 필요하다.
#6. 현실에서 가장 어려운 것은 채점기를 정의하는 일이다
벤치마크는 입력과 제약, 목적함수가 비교적 명시적이다. 현실에서는 여러 문서의 규칙이 충돌하거나 현장 담당자마다 중요하게 보는 비용이 다를 수 있다. 센서 오차와 취소된 작업, 갑자기 늘어난 수요도 들어온다. 이런 경우 “좋은 알고리즘을 찾아라” 이전에 무엇이 허용되고 무엇을 좋다고 볼지 합의해야 한다.
같은 일정도 목적함수가 달라지면 평가가 바뀌는 이유 기호·연산·계산 과정 펼치기
이 식은 논문의 실제 목적함수가 아니라 설명용 예다. D를 이동거리 비용, T를 지연 비용, V를 제약 위반 벌점으로 두고 λ로 단위를 맞춘다고 하자. 거리는 짧지만 지연이 큰 일정은 지연 가중치가 커지면 순위가 뒤집힐 수 있다. 또한 절대로 위반하면 안 되는 안전 제약을 작은 벌점으로만 처리하면 위험한 답이 높은 점수를 얻을 수 있다. 금지 조건은 검증기로 거절할지, 허용 가능한 불편은 비용으로 처리할지 먼저 구분해야 한다.
보충자료에는 정해진 조건의 수리계획 비교도 있지만, 모든 상용 MILP·CP 해결기를 모든 하드웨어와 실행 예산에서 이겼다는 결론은 아니다. 재사용할 가치가 있는 것은 알고리즘 설계의 분해와 보완적 탐색이며, 어떤 현장의 비용 우위를 주장하려면 같은 데이터와 목적, 시간·자원 예산의 비교가 추가로 필요하다.[2]
#7. 다음에 확인할 것은 더 높은 평균 하나가 아니다
후속 검증에서는 항만 밖의 새로운 문제에서 계약을 얼마나 정확히 생성하는지, 잘못된 제약을 어떻게 발견하는지, 동일한 실행 예산에서 고전적 해결기와 어떤 차이가 나는지를 확인해야 한다. 포트폴리오가 실패한 사례를 단순히 평균에 숨기지 않고, 탐색·검증·시간 초과 가운데 어느 단계에서 실패했는지도 보고하는 편이 유용하다.
또 개발 사례에서 선택한 포트폴리오를 별도 시험 사례에 평가해야 한다. 후보를 시험 점수로 반복 선택하면 모델 훈련 때의 시험집합 누출과 같은 문제가 생긴다. 목적함수나 현장 제약이 바뀔 때 기존 포트폴리오의 어떤 부분을 폐기하고 다시 검증할지도 운영 정책으로 남겨야 한다. 모델이 코드를 작성해 주더라도 변경 관리가 사라지는 것은 아니다.
이 논문은 공식 수상작이라는 근거로 선정한 것이 아니다. 첨부의 99점은 편집 판단이며 과학적 확률이 아니다. 저자들은 이해관계가 없다고 선언했다. 정확한 결론은 검증 가능한 계약을 중심으로 LLM이 상보적 휴리스틱을 탐색하는 방식이 강력한 벤치마크 결과를 보였다는 것이다. 알고리즘 엔지니어를 전부 대체하거나 실물 물류망의 비용 절감을 이미 입증했다는 선언과 구분해야 한다.[1]
#출처와 열람 범위
[1] Gong 외, Large language models discover complementary heuristics for combinatorial optimization. Nature Machine Intelligence, 2026-10-01, DOI 10.1038/s42256-026-01307-8. 공개 초록·그림 설명·발행 정보 [2] 동일 논문 Supplementary Information. 문제 정의, 비교 실행 예산, 자동 계약 생성 및 선택·실행 예산 제거 실험 [3] PJ-NTU/LACE 공식 구현, README·ARCHITECTURE·재현 안내·사례 매니페스트. 고정 아카이브 DOI 10.5281/zenodo.21886438편집일은 2026년 10월 2일, 이 해설의 작성·출처 재확인일은 10월 5일이다. 출판사 본문 PDF 요청은 공개 소개 페이지로 연결돼 본문 전체를 내려받지 못했다. 공개 초록, 보충 PDF의 관련 절과 공식 저장소를 근거로 작성했으며 본문 전체 독립 검증이나 모든 실험 재현을 주장하지 않는다. 출판사 도판의 재게시 허가는 확인되지 않아 링크로 안내하고, 글 안의 두 도식은 원도판이 아닌 자체 교육 자료로 표시했다. 기존 후보 24개를 이번 작업에서 새로 전수 검색한 것은 아니다.