💻 computer science

An In-depth Study of LLM Contributions to the Bin Packing Problem

이 논문은 거대언어모델이 생성한 휴리스틱이 불투명하고 해당 문제의 사례들이 실제로는 더 효율적이고 해석 가능하며 일반화 가능한 알고리즘으로 해결될 만큼 충분히 단순하다는 점을 입증함으로써, 거대언어모델이 빈 패킹(bin packing) 문제의 수학적 발견을 유의미하게 진전시킨다는 주장에 이의를 제기하며, 이를 통해 거대언어모델이 생성한 과학적 기여에 대한 엄격한 검증의 필요성을 강조한다.

원저자: Julien Herrmann, Guillaume Pallez

게시일 2026-06-19

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Julien Herrmann, Guillaume Pallez

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신은 거대한 창고를 운영하고 있다고 상상해 보세요. 매일 다양한 크기의 상자들이 담긴 트럭이 도착하고, 당신은 상자가 들어올 때마다 그것들을 운송 컨테이너(빈)에 담아야 합니다. 다음 상자가 어떤 모습일지는 알 수 없습니다. 당신은 그저 빠르게 결정을 내려야 합니다: "이 상자를 컨테이너 A에 넣을까, 컨테이너 B에 넣을까, 아니면 새로운 컨테이너 C를 열까?"

목표는 간단합니다. 가능한 한 적은 수의 컨테이너를 사용하는 것입니다. 이것은 **빈 패킹 문제(Bin Packing Problem)**라고 알려진 고전적인 퍼즐입니다.

최근, 유명한 연구(Romera-Paredes 등)는 LLM(에세이나 코드를 작성하는 것과 동일한 AI 기술)이 이 패킹 퍼즐을 인간보다 더 잘 해결할 수 있는 "새로운 수학적 비밀"을 발견했다고 주장했습니다. 그들은 AI가 매우 영리한 새로운 규칙을 찾아냈으며, 이것이 너무나 똑똑해서 "수학적 발견"으로 간주될 수 있다고 말했습니다.

Julien Herrmann와 Guillaume Pallez의 이 논문은 마치 조사관 역할을 하는 전문가 팀처럼 등장하여 그 주장을 조사합니다. 그들은 돋보기를 들고 이렇게 말합니다. "잠깐만, AI가 실제로 무엇을 했는지 직접 확인해 봅시다."

그들이 발견한 내용은 다음과 같습니다. 아주 쉽게 설명하겠습니다.

1. AI의 "비밀"은 별로 비밀스럽지 않았다

AI는 표준적인 인간 방식보다 상자를 약간 더 잘 채우는 일련의 컴퓨터 지침(휴리스틱)을 만들어냈습니다. 원래의 연구는 이 지침이 "해석 가능하다", 즉 인간이 그 논리를 쉽게 읽고 이해할 수 있다고 주장했습니다.

논문의 현실 점검:
저자들은 AI의 코드를 살펴보았고, 그것이 마치 생소한 방언으로 쓰인 레시피를 읽는 것과 같다는 것을 발견했습니다.

"c12" 코드: 이것은 "만약 이렇다면, 저렇다"라는 규칙들의 긴 목록이었습니다. 읽을 수는 있었지만, 논리가 엉망이었습니다. 마치 요리사가 "만약 냄비 온도가 7도에서 8도 사이라면 소금을 넣으세요. 만약 8도에서 9도 사이라면 소금을 아주 조금만 덜 넣으세요"라고 말하는 것과 같았습니다. 작동은 했지만, 왜 작동하는지는 설명해주지 못했습니다.
"c14" 코드: 이것은 훨씬 더 심각했습니다. 그것은 마치 횡설수설하는 것처럼 보이는 복잡한 수학 공식이었습니다. 저자들은 코드가 실제로 무엇을 하고 있는지 추측하기 위해 수천 번의 실험을 수행해야 했습니다. 그들은 코드가 평범한 영어(Python)로 작성되었음에도 불구하고, 그 추론 과정은 숨겨져 있다는 것을 깨달았습니다. 그것은 투명한 가면을 쓴 "블랙박스"였습니다.

비유: AI가 항상 북쪽을 가리키는 마법 나침반을 주었다고 상상해 보세요. 원래의 연구는 "보세요, 나침반이 유리로 되어 있어서 바늘이 보입니다! 완전히 이해할 수 있습니다!"라고 말했습니다. 저자들은 이렇게 말합니다. "네, 바늘은 보입니다. 하지만 우리는 그 안의 자석이 어떻게 작동하는지는 전혀 모릅니다. 단지 백만 번 테스트해 본 결과 북쪽을 가리킨다는 것만 알 뿐입니다."

2. AI는 새로운 물리 법칙을 발견하지 못했다

원래의 연구는 AI가 "수학적 발견"을 했다고 주장했습니다. 저자들은 이것이 과장되었다고 주장합니다.

논문의 현실 점검:
AI는 매우 구체적이고 좁은 시나리오(예: 모든 상자 크기가 20에서 100 단위 사이인 경우)에서 테스트되었습니다. 저자들은 AI가 새로운 사고방식을 발명한 것이 아니라, 단지 기존의 단순한 기술을 약간 변형한 버전을 찾아냈을 뿐이라는 것을 발견했습니다.

그들은 AI의 "비법 소스"가 사실 두 개의 단순한 숫자(파라미터)였다는 것을 깨달았습니다:

"만약 상자가 정말 꽉 끼게 들어간다면, 거기에 넣어라."
"만약 꽉 끼지 않는다면, 공간이 넉넉히 남은 컨테이너에 넣어라."

저자들은 이 단순한 아이디어를 가져와서 복잡한 AI 코드를 모두 제거하고, 새롭고 매우 단순한 알고리즘(ab-FirstFit 또는 ab-WorstFit)을 만들었습니다.

결과: 이 인간이 만든 알고리즘은 AI의 복잡한 코드보다 더 빠르고, 이해하기 쉬우며, 더 잘 작동했습니다. 심지어 AI의 코드는 규칙이 약간만 바뀌어도 작동하지 않는 반면, 이 알고리즘은 다양한 유형의 상자 크기에서도 작동했습니다.

비로: 이는 AI가 15개의 루프가 있는 복잡한 매듭을 발명하여 신발 끈을 묶는 더 나은 방법을 찾았다고 주장하는 것과 같습니다. 저자들은 그것을 보고 "아, 그냥 끈을 꽉 조이고 약간의 여유를 두면 됩니다"라고 깨달았으며, 단순한 이중 매듭이 더 잘 작동하고 배우기 쉬우며 매듭 이론 박사 학위가 필요 없다는 것을 보여주었습니다.

3. "발견"은 단지 선행 연구의 부재 때문이었다

원래의 연구는 이 특정 상자 크기에 대해 발표된 논문이 없었기 때문에 자신들이 "새로운 것"을 발견했다고 주장했습니다.

논문의 현실 점검:
저자들은 이 특정 상자 크기에 대해 아무도 연구하지 않은 이유는 그것이 너무 어렵거나 신비해서가 아니라, 그것이 중요하지 않았기 때문이라고 제안합니다. 이는 마치 특정 모양의 정원에 있는 조약돌을 쌓는 가장 좋은 방법을 찾아냈다고 해서 "과학적 돌파구"를 마련했다고 주장하는 것과 같습니다. 그것은 유효한 질문이지만, 근본적인 발견은 아닙니다.

저자들은 만약 AI가 진정으로 깊은 수학적 진리를 발견했다면, 다른 연구자들이 AI의 코드를 읽고, 원리를 이해하고, 이를 통해 다른 문제들을 해결할 수 있었을 것이라고 주장합니다. 대신, 그 누구도 그렇게 할 수 없었습니다. 그 "통찰력"은 AI가 작성한 특정 코드와 함께 사라졌습니다.

결론

이 논문은 AI를 사용하여 알고리즘 설계를 돕는 것은 멋진 아이디어이지만, 과장된 광고(hype)를 경계해야 한다고 결론짓습니다.

AI는 "수학적 발견"을 하지 않았습니다. 그것은 단지 시행착오를 통해 단순한 작업을 수행하는 약간 더 나은 방법을 찾았을 뿐입니다.
AI의 코드는 진정으로 "해석 가능"하지 않았습니다. 그것은 이해하기 어려웠으며, "논리"는 코드를 읽어서가 아니라 실험을 통한 추측을 통해서만 발견되었습니다.
인간이 더 잘할 수 있습니다. AI가 우연히 발견한 단순한 원리를 이해함으로써, 인간은 더 단순하고 빠르며 신뢰할 수 있는 도구를 만들었습니다.

최종 비유:
AI는 타자기를 치는 원숭이와 같았습니다. 결국 원숭이는 말이 되는 문장을 쳤습니다. 원래의 연구는 "보세요! 원숭이가 삶의 의미를 발견했습니다!"라고 말했습니다. 이 논문의 저자들은 이렇게 말합니다. "아니요, 원숭이는 단지 이 특정 문단에 적합한 문장을 쳤을 뿐입니다. 우리는 더 나은 문장을 쓸 수 있고, 명확하게 설명할 수 있으며, 원숭이 없이도 책 전체에 적용할 수 있습니다."

이 논문은 과학자들에게 엄격함을 갖출 것을 촉구합니다. AI가 결과물을 내놓았다고 해서, 그것이 진정으로 문제를 이해했거나 수학에 대한 생각을 바꾸는 발견을 했다는 뜻은 아닙니다.

기술 요약: 빈 패킹 문제(Bin Packing Problem)에 대한 LLM의 기여에 관한 심층 연구

1. 문제 정의 및 배경

본 논문은 로메라-파레데스 등[2024]이 조합 최적화 분야에서 대규모 언어 모델(LLM)이 "수학적 발견"에 기여한다는 주장의 타당성을 조사한다. 구체적으로는, 다양한 크기의 아이템이 순차적으로 도착하며 미래의 아이템에 대한 정보 없이 고정된 용량의 빈(bin)에 채워져야 하는 **온라인 빈 패킹 문제(Online Bin Packing Problem, OBPP)**에 초점을 맞춘다. 목표는 사용되는 총 빈의 수를 최소화하는 것이다.

본 연구는 진화 알고리즘 내에서 LLM(Codey)을 사용하여 특정 확률적 OBPP 인스턴스에 대한 휴리스틱을 생성하는 FunSearch 프레임워크를 정밀 검토한다. 대상 인스턴스는 Uniform(20, 100) 및 Weibull(3.0, 45) 분포에서 추출된 아이템 크기를 포함한다. 로메라-파레데스 등은 LLM이 생성한 휴리스틱이 새로운 과학적 발견을 나타내며 해석 가능하다고 주장하지만, 본 논문은 해당 인스턴스들이 상대적인 단순함 때문에 이전에 연구되지 않았던 것이며, 생성된 휴리스틱이 진정한 해석 가능성과 일반화 능력을 결여하고 있다고 주장한다.

2. 방법론

저자들은 LLM 생성 휴리스틱을 재평가하기 위해 다각적인 방법론을 채택한다:

코드 분석 및 해석 가능성 평가: 저자들은 가장 성능이 좋은 LLM 생성 휴리스틱(Uniform의 경우 c12, Weibull의 경우 c14, 그리고 Liu 등[2024]의 EoH 휴리스틱)의 소스 코드를 수동으로 분석한다. 이들은 로직이 도메인 전문가에게 투명한지, 아니면 이해를 위해 광범위한 실험이 필요한지를 평가한다.
행동 역공학(Behavioral Reverse Engineering): 불투명한 휴리스틱(특히 c14)에 대해, 저자들은 기저 결정 규칙을 추론하기 위해 베이스라인 전략(예: WorstFit, BestFit)과 아이템 단위 비교를 수행한다. 이들은 잔여 빈 용량과 결정 임계값을 분석하여 알고리즘 동작에 대한 인간이 읽을 수 있는 근사치를 공식화한다.
단순화된 알고리즘 도출: 행동 분석을 바탕으로, 저자들은 새로운 클래스인 두 파라미터 휴리스틱(denote ab-FirstFit, ab-BestFit, ab-WorstFit)을 제안한다. 이 알고리즘들은 관찰된 패턴을 다음과 같이 공식화한다:
1. 만약 빈이 아이템을 수용하여 남은 공간이 $\le a$ 가 된다면(타이트 핏), 특정 전략(예: BestFit)을 적용한다.
2. 만약 남은 공간이 $> b$ 라면(루즈 핏), 베이스라인 전략(예: FirstFit 또는 WorstFit)을 적용한다.
3. 그렇지 않으면, 새로운 빈을 연다.
경험적 평가: 제안된 ab-Baselines를 원래의 분포 및 추가적인 변형(다른 Uniform 및 Weibull 파라미터)에 대해 LLM 생성 휴리스틱(c12, c14, EoH) 및 표준 베이스라인(BestFit, FirstFit)과 벤치마킹한다. 평가는 사용된 빈의 수와 일반화 능력을 측정한다.

3. 주요 기여

해석 가능성에 대한 비판: 본 논문은 LLM 생성 코드가 구문론적으로는 읽기 쉽지만, 의미론적으로는 해석 가능하지 않음을 보여준다. 휴리스틱 c14와 EoH는 근저에 깔린 로직을 드러내지 않는 불투명한 수학적 연산(예: 이웃 의존적 점수 업데이트, 복잡한 지수 항)을 포함하고 있다. 이들의 동작을 이해하기 위해서는 코드 검사가 아닌 실험적 관찰이 필요했으며, 이는 이들이 "해석 가능한" 통찰을 제공한다는 주장에 반한다.
기저의 단순성 식별: 저자들은 LLM 휴리스틱의 성능 향상이 두 가지 특정 조건에 의존함을 보여준다: (H1) 스케줄링될 아이템의 수가 많아야 하며, (H2) 아이템 크기에 양의 하한선이 존재해야 한다(매우 작은 아이템이 큰 틈을 채우는 것을 방지). 이러한 조건들은 특정 인스턴스를 상대적으로 단순하게 만든다.
우월하고 일반화 가능한 휴리스틱 제안: 저자들은 단순한 두 파라미터 알고리즘 클래스인 ab-Baselines를 도입한다. 이 휴리스틱들은:
- 훈련된 분포에서 LLM 생성 휴리스틱과 대등하거나 약간 더 나은 성능을 보인다.
- 계산 효율성이 훨씬 높다(수백만 번의 LLM 쿼리 대신 몇 분간의 튜닝만 필요).
- LLM 휴리스틱이 특정 훈련 클러스터 외부에서 실패하는 것과 달리, 다른 Uniform 및 Weibull 파라미터 설정에도 효과적으로 일반화된다.
"수학적 발견"의 재평가: 저자들은 연구된 인스턴스들(Uniform(20, 100) 및 Weibull(3.0, 45))이 어려워서가 아니라, 아마도 커뮤니티에서 무관하거나 사소하다고 간주되었기 때문에 연구되지 않았던 것이라고 주장한다. LLM은 새로운 개념적 통찰을 생성하기보다는 확률적 탐색을 통해 알려진 최적화 패턴(타이트 핏 대 루즈 핏)을 재발견한 것에 불과하다.

4. 결과

성능: Uniform(20, 100) 분포에서 단순화된 ab-FirstFit( $a=5, b=24$ )은 LLM 휴리스틱 c12보다 평균 0.71%, BestFit보다 2.71% 더 우수한 성능을 보인다. Weibull(3.0, 45) 분포에서 ab-WorstFit( $a=1, b=21$ )은 c14보다 0.12%, BestFit보다 3.39% 더 우수한 성능을 보인다.
일반화: LLM 휴리스릭은 다른 파라미터를 가진 분포에서 테스트할 때 성능이 크게 저하되는 반면, ab-Baselines는 다양한 Uniform 및 Weibull 구성에서도 견고한 성능을 유지한다.
효율성: ab-Baselines의 도출 및 튜닝은 개인용 노트북에서 몇 분 만에 완료되었으며, 이는 c12와 c14를 생성하는 데 필요한 수일간의 훈련 및 수백만 번의 LLM 쿼리와 극명한 대조를 이룬다.
해석 가능성 격차: 저자들은 c14의 로직을 단순한 규칙(타이트 핏에는 BestFit, 루즈 핏에는 WorstFit, 그 외에는 새 빈)으로 성공적으로 역공학하였으며, 이를 통해 "발견"이 새로운 알고리즘 개념이 아니라 기존 전략의 재매개변수화였음을 입증했다.

5. 의의 및 주장

본 논문은 과학적 발견에서 LLM의 역할에 대해 겸손하지만 비판적인 재평가로 결론을 맺는다:

"발별"에 대한 반박: 저자들은 LLM 기반 진화 프레임워크가 새로운 이론적 이해나 개념적 돌파구를 제공한다는 의미에서의 "수학적 발견"을 만들어내지 못했다고 단언한다. 대신, 이는 특정하고 좁으며 이전에 연구되지 않은 인스턴스에 대해 파라미터를 최적화하는 강력한 하이퍼-휴리스틱(hyper-heuristic) 역할을 했을 뿐이다.
현재 주장의 한점: 빈 패킹 사례 연구를 통해 LLM이 확립된 난제를 해결할 수 있다는 주장은 충분히 뒷받침되지 않는다고 간주된다. 해당 특정 분포들에 대한 선행 연구가 부족한 것은 문제가 어려워서가 아니라 중요성이 낮게 인식되었기 때문일 가능성이 크다.
향atic 방향: 본 논문은 엄격한 검증 프로토콜을 옹호한다. LLM이 진정한 과학적 기여를 인정받으려면, 단순히 좁은 합성 인스턴스에서 경험적 이득을 얻는 것이 아니라, 기존 최고의 문헌보다 개선된 솔루션을 제공하고 전이 가능한 개념적 통찰을 제시할 수 있는 중요하고 잘 확립된 문제에 적용되어야 한다.
LLM의 역할: 저자들은 LLM을 유전 알고리즘의 탐색 공간을 확장하고 휴리스틱 설계를 자동화하는 도구로 위치시키지만, 이 맥락에서는 이론적 통찰을 가진 에이전트라기보다는 경험적 최적화 도구로서 기능한다고 강조한다.