arXiv:2510.27353v2 cs.AI

Bin Packing 문제에 대한 대규모 언어 모델(LLM)의 기여에 관한 심층 연구

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

Julien Herrmann, Guillaume Pallez

제출 2025-10-31

한국어 초록

최근 연구들은 대규모 언어 모델(LLM)이 수학적 발견에 기여할 수 있는 흥미로운 아이디어를 제공할 수 있다고 제안했습니다. 이러한 주장은 LLM 기반 유전자 알고리즘이 균일(uniform) 및 와이불(Weibull) 분포 하의 온라인 bin packing 문제에 대한 새로운 통찰을 제공하는 휴리스틱(heuristics)을 생성했다는 보고에 근거합니다. 본 연구에서는 LLM이 생성한 휴리스틱(heuristics)에 대한 상세한 분석을 통해 그 동작과 해석 가능성을 모두 검토하며 이 주장을 재평가합니다. 사람이 읽을 수 있음에도 불구하고, 이러한 휴리스틱(heuristics)은 도메인 전문가에게도 대체로 불투명하게 남아 있습니다. 이 분석을 바탕으로, 우리는 이러한 특정 bin packing 인스턴스에 맞춰진 새로운 알고리즘 클래스를 제안합니다. 도출된 알고리즘은 훨씬 더 간단하고, 효율적이며, 해석 가능하고, 일반화가 가능하여, 고려된 인스턴스 자체가 상대적으로 단순하다는 것을 시사합니다. 그런 다음 우리는 이 문제에 대한 LLM의 기여에 대한 주장의 한계를 논의하는데, 이는 해당 인스턴스가 이전에 연구되었다는 잘못된 가정에 기초하고 있는 것으로 보입니다. 우리의 연구 결과는 대신 LLM 생성 출력의 과학적 가치를 평가할 때 엄격한 검증(validation)과 맥락화의 필요성을 강조합니다.

원문 초록

Recent studies have suggested that Large Language Models (LLMs) could provide interesting ideas contributing to mathematical discovery. This claim was motivated by reports that LLM-based genetic algorithms produced heuristics offering new insights into the online bin packing problem under uniform and Weibull distributions. In this work, we reassess this claim through a detailed analysis of the heuristics produced by LLMs, examining both their behavior and interpretability. Despite being human-readable, these heuristics remain largely opaque even to domain experts. Building on this analysis, we propose a new class of algorithms tailored to these specific bin packing instances. The derived algorithms are significantly simpler, more efficient, more interpretable, and more generalizable, suggesting that the considered instances are themselves relatively simple. We then discuss the limitations of the claim regarding LLMs' contribution to this problem, which appears to rest on the mistaken assumption that the instances had previously been studied. Our findings instead emphasize the need for rigorous validation and contextualization when assessing the scientific value of LLM-generated outputs.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2510.27353v2제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2610.03316v2cs.AI공통 태그 Evolutionary Algorithms, Combinatorial Optimization, Large Language Model

LLM을 활용한 제로샷 교차 문제 일반화를 위한 다중 작업 진화

Multi-Task Evolution for Zero-Shot Cross-Problem Generalization using LLMs

다양한 조합 최적화(combinatorial optimization) 문제를 위한 효과적인 휴리스틱(heuristic)을 설계하는 것은 상당한 전문성과 반복적인 탐색을 필요로 합니다. 대규모 언어 모델(LLM)은 휴리스틱 생성과 개선을 자동화하지만, 휴리스틱 탐색은 일반적으로 최적화 대상 문제의 평가 피드백에 의존합니다. 따라서 소스 작업 피드백만을 사용하여 새로운 문제 정의로 일반화하는 것은 여전히 핵심적인 과제로 남아 있습니다. 본 논문에서는 제로샷(zero-shot) 교차 문제 일반화를 위한 LLM 기반 다중 작업 진화 프레임워크인 MECo를 소개합니다. MECo는 작업 조건부 휴리스틱 개체군을 유지하며, 교차 작업 개체군 성능에 기반한 전이 격차(transfer gap)를 활용해 이들의 상호작용을 유도합니다. 이러한 상호작용은 휴리스틱의 전이와 재조합을 가능하게 합니다. 그런 다음 상호보완적 선택 기준을 통해 각 개체가 소스 조합에 대해 제공하는 추가적인 커버리지를 보상함으로써 간결한 휴리스틱 세트를 구성합니다. 선택된 세트는 추가적인 탐색이나 적응 과정 없이 타깃 문제에 바로 적용됩니다. 차량 경로 문제(VRP) 및 유연한 잡숍 스케줄링(FJSP) 전반에 걸친 32가지 변형 문제를 대상으로 한 실험에서, MECo는 동일한 예산 하에 8개의 자동화된 휴리스틱 설계(AHD) 기준선과 비교해 가장 낮은 평균 비용을 달성함을 보여줍니다. 도메인 외(OOD) 문제에서도 각 제품군에서 가장 강력한 기준선을 능가합니다. 나아가 MECo 프레임워크를 서로 다른 AHD 방법들과 통합했을 때 두 제품군 모두에서 ID 및 OOD 성능이 향상되어, 여러 방법 전반에 걸친 유효성을 뒷받침합니다.

arXiv:2610.02975v2cs.AI공통 태그 Evolutionary Algorithms, Large Language Model

불완전한 프록시 보상을 활용한 신뢰할 수 있는 자기 진화

Reliable Self-Evolution with Imperfect Proxy Rewards

대규모 언어 모델(LLM) 기반의 자기 진화 탐색은 과학적 발견을 위한 유망한 접근법입니다. 그러나 일부 영역에서는 모든 후보에 대해 고충실도(high-fidelity) 평가를 수행하는 데 엄청난 비용이 듭니다. 따라서 이러한 환경의 자기 진화 시스템은 비용이 저렴하지만 불완전한 프록시 보상(proxy reward)에 의존하며, 이는 실현 불가능한 후보에 높은 점수를 부여할 수 있습니다. 이러한 위양성(false positive)은 최종 출력뿐만 아니라 후속 세대를 유도하는 데 사용되는 피드백까지 오염시킬 수 있습니다. 이는 보다 신뢰할 수 있는 자기 진화 탐색을 위해 통계적으로 보정된 보상 구간을 도입하는 동기가 됩니다. 본 논문에서는 조건부 등분산 추론(conditional conformal inference)과 반복(iteration)별 온라인 밀도비 추정을 사용하여 후보별 보상 구간을 구성하는 CISE(Conformal Interval-Driven Self-Evolution)를 제안합니다. CISE는 진화적 피드백을 위해 보수적인 구간 기반 보상을 사용하며, 요구되는 모든 속성 구간이 각자의 실행 가능한 영역 내에 완전히 포함될 때만 후보를 반환합니다. 본 연구는 독립성 및 공변량 변화(covariate shift)에 대한 명시적 가정 하에서 고정 반복 커버리지 결과를 도출합니다. 또한 재료과학 분야의 세 가지 자기 진화 탐색 작업에서 CISE를 평가합니다. 실험 결과, 고충실도 평가에서 CISE가 반환한 모든 후보는 진양성(true positive)이었던 반면, 베이스라인들은 더 많은 후보를 반환하지만 위양성을 포함했습니다. 이러한 결과는 다운스트림 검증 예산이 제한적일 때 더 작지만 더 정밀한 후보 목록이 갖는 가치를 강조합니다. 연구 저장소는 https://github.com/MLAI-Yonsei/CISE.git 에서 확인할 수 있습니다.

arXiv:2610.03296v1cs.AI공통 태그 Combinatorial Optimization, Large Language Model

JOVE: 자원 인지형 LLM 태스크 그래프를 위한 공동 실행 및 검증

JOVE: Joint Execution and Verification for Resource-Aware LLM Task Graphs

복잡한 추론 질의는 방향성 비순환 그래프(DAG) 형태의 태스크 그래프로 분해되어 이종 대규모 언어 모델(LLM)에 분산될 수 있으며, 이를 통해 병렬 처리를 통한 지연 시간을 줄이고 더 작은 모델이 복잡한 태스크를 해결하도록 지원할 수 있습니다. 그러나 실제로는 주어진 서브태스크에 대한 특정 LLM의 적합성을 사전에 알 수 없을 수 있으며, 단순 실행만으로는 출력의 정확성을 파악할 수 없습니다. 본 논문에서는 실행기 LLM을 할당하는 동시에 유료 검증을 거칠 중간 출력을 함께 선택하는 온라인 프레임워크인 JOVE를 제안합니다. 검증은 비동기식으로 실행되며 향후 할당 결정을 개선하는 데 사용되므로, 시스템은 현재 실행에 드는 비용과 향후 학습을 위한 지출 사이의 균형을 유지해야 합니다. 본 연구에서는 확률적이며 초기에는 알려지지 않은 LLM 서비스 품질, 호출 비용 및 실행 시간 환경에서 장기 예산과 질의별 지연 시간 제약 조건 하에 이러한 트레이드오프를 최적화하는 방법을 연구합니다. JOVE는 질의별 일련의 혼합 정수 선형 계획법(MILP) 문제를 해결하여 실행 및 검증 결정을 내립니다. 온라인 학습은 검증 피드백을 기반으로 LLM 품질에 대한 태스크 의존적 추정치를 업데이트하며, 정보 이득 보너스를 통해 학습의 가치를 할당 결정에 반영합니다. 자연스러운 일련의 가정 하에 본 연구는 JOVE의 준선형(sublinear) 품질 학습 후회(regret)를 입증합니다. 4가지 추론 벤치마크 전반에서 JOVE는 표준 추론(inference) 베이스라인 대비 경쟁력 있는 정확도를 달성하는 동시에 평균 비용과 지연 시간을 최소 3.17배 단축합니다.

arXiv:2609.38806v2cs.LG공통 태그 Combinatorial Optimization, Large Language Model

전역 제약 조건 문제에서 블랙보드 지능이 자기회귀 방식을 능가할 수 있다

Blackboard Intelligence Can Surpass Autoregressive on Globally Constrained Problems

다음 토큰 예측(next-token prediction)은 대규모 언어 모델(LLM)의 눈부신 발전을 이끌어왔으나, 점차 늘어나는 연구 결과들은 복잡한 전역 제약 조건(global constraints)이 지배하는 문제에서 이러한 모델들이 어려움을 겪을 수 있음을 시사합니다. 본 연구에서는 이러한 영역에 주목하여, 이 한계 중 일부가 다음 토큰 예측 자체가 유도하는 추론 인터페이스에서 비롯되는지 질문을 던집니다. 우리는 인과적(causal)이고 좌에서 우로 진행되는 궤적에 얽매이지 않고 고정된 수정 가능한 캔버스 위에서 작업하며 후보 해 상태를 탐색하는 추론 시점(inference-time) 관점인 블랙보드 지능(blackboard intelligence)을 통해 이 문제를 연구합니다. 우리는 임의 순서 예측 인터페이스를 통해 부분적으로 채워진 해 상태에 대한 예측을 자연스럽게 제공하는 확산 언어 모델(diffusion language model)로 이 개념을 구현합니다. 우리의 핵심 관찰은 표준 마스크 기반 확산 목적함수에서 얻을 수 있는 단순한 모델 내부 수치인 평균 신뢰도(mean confidence)가 전역 일관성(global coherence)에 대한 유용한 프록시 역할을 하며 추론 시점의 탐색과 수정을 안내할 수 있다는 점입니다. 실험적으로 ZebraLogic, 간호사 근무 일정 배정(Nurse Rostering), 작업장 스케줄링(Job-Shop Scheduling, JSSP) 전반에 걸쳐 Blackboard는 파인튜닝된 LLaDA-8B-Instruct 체크포인트를 고정한 상태에서도 일관되게 추론 성능을 향상시키며 동일한 규모의 자기회귀(autoregressive) 베이스라인을 크게 능가하여 ZebraLogic-Hard에서 90.4%의 정확도, Nurse Rostering에서 76.4%의 정확한 실행 가능성(exact feasibility), JSSP에서 80.2%의 최적성(optimality)을 달성했습니다. 더 강력한 자기회귀 탐색 및 정제 기법으로도 ZebraLogic-Hard에서의 격차를 좁히지 못했으며, Blackboard는 훨씬 더 큰 규모와 강력한 테스트 시점 추론 능력을 갖춘 테스트 대상 프론티어 LLM들을 ZebraLogic-Hard 및 JSSP에서 능가했습니다. 우리는 코드베이스를 https://github.com/jwoosang1/blackboard-intelligence 에 오픈소스로 공개합니다.

arXiv:2610.00912v1cs.AI공통 태그 Combinatorial Optimization, Large Language Model

OR을 수행하는 AI를 위한 OR: OSCAR 프레임워크 내에서 에스컬레이터를 따라 LLM 라우팅하기

OR for AI That Does OR: Routing LLMs up the Escalator inside the OSCAR Framework

대규모 언어 모델(LLM)은 비즈니스 설명을 최적화 모델(optimization model)로 변환할 수 있지만, 실행 가능한 코드가 제약 조건이나 목적 함수를 잘못 나타낼 수 있습니다. 이 경우 솔버(solver)는 잘못된 문제에 대한 최적해를 반환할 수 있습니다. 해당 해가 의도한 운영 규칙을 만족하더라도 더 나은 계획이 존재할 수 있습니다. 최적화 모델링을 반복적으로 사용하는 조직의 경우, LLM 기반 프레임워크는 저비용으로 정확한 수식화를 생성해야 하며 이상적으로는 로컬에서 실행되어야 합니다. 본 연구에서는 개선 사항을 검증하고 가격 및 성능이 서로 다른 LLM 간에 시도를 어떻게 할당할지 연구합니다. 우리는 라벨링된 결정 예시를 바탕으로 검증된 오프라인 시뮬레이터(Simulator)를 사용하여 후보들을 비교하고 단순 실행 가능성을 넘어 탐색을 지속하는 OSCAR(Optimization modeling by Simulator, Coder, And Reviewer)를 개발합니다. 우리는 다음으로 검증된 개선안을 찾는 과정을 관측되지 않은 난이도 하에서의 순차적 의사결정(어떤 LLM을 호출하고 언제 중단할지)으로 모델링합니다. 사전 확률이 알려진 단순화된 환경에서 비용 순서에 따른 에스컬레이션(cost-ordered escalation)이 최적이 되는 조건을 제시합니다. 일반적인 메뉴에 대해서는 사전 확률에 구애받지 않는(prior-free) 경쟁적 보장을 도출합니다. 5개의 벤치마크 문제에서 OSCAR는 단일 GPU에 로컬 배포 가능한 두 개의 소형 오픈 가중치(open-weight) LLM을 사용하여 보고된 설정 기준 95%에서 100%의 정확도를 달성합니다. 이 모델들의 단일 시도 정확도는 평균 29% 및 48%입니다. 문제당 5회 실행에서 Codex와 Claude Code는 OSCAR에 비해 각각 평균 3.1배, 5.8배의 토큰 비용을 발생시킵니다. OSCAR는 예산 및 기밀성 요구사항에 따라 로컬 또는 클라우드에서 오픈 가중치 모델을 지원합니다. 기업은 자연어 운영 규칙을 명확히 하기 위해 실행 가능한 결정과 실행 불가능한 결정에 대한 라벨링된 결정 예시를 유지 관리해야 합니다. OSCAR는 LLM의 해석이 이들과 충돌할 때 이러한 라벨을 따릅니다. LLM 성능과 가격이 변화함에 따라, OSCAR의 단순한 운영 규칙과 조정 가능한 설정은 기업이 모델 선택을 적응시키고 이러한 발전을 활용할 수 있도록 돕습니다.

arXiv:2610.01119v1cs.AI공통 태그 Evolutionary Algorithms, Large Language Model

AbsorbEvo: 마이크로파 흡수체의 자율 역설계를 위한 에이전트 프레임워크

AbsorbEvo: An Agentic Framework for Autonomous Inverse Design of Microwave Absorbers

고성능 마이크로파 흡수체 설계는 전자기 이론, 재료 과학 및 시뮬레이션 프로그래밍에 대한 전문적인 지식을 요구하며, 많은 시간이 소요되는 최적화(optimization) 과정을 수반합니다. 본 논문에서는 자연어 성능 목표를 전파(full-wave) 시뮬레이션으로 검증된 설계로 변환하는 자율 역설계 에이전트(agent) 프레임워크인 AbsorbEvo를 제시합니다. 본 프레임워크의 후보 진화 전략은 언어적 추론, 물리 기반 예측 및 과거 피드백을 통합합니다. 대규모 언어 모델(LLM)은 작업 목표와 계산 기록을 바탕으로 매개변수 조정의 방향과 크기를 제안합니다. 시스템은 방향성이 있는 증분과 전역 샘플링을 결합하여 후보를 생성하고, 저비용 예측 모델을 물리적 사전 지식(prior)으로 사용하여 순위를 매깁니다. 높은 순위를 기록한 설계만이 전파 시뮬레이션을 거칩니다. 물리적 타당성 검사를 통과한 결과는 성능을 평가하고 후속 탐색을 안내하는 데 사용됩니다. 학습 작업에서 얻은 경험은 텍스트 형태의 스킬로 추가 증류(distillation)되며, 이는 새로운 작업에 사용되기 전에 독립적으로 검증됩니다. 공개되지 않은 AbsorbBench-36 작업에서 동일한 제안 예산 조건하에 AbsorbEvo는 79.17%의 작업 성공률을 달성하여, 일반적인 에이전트의 25.00% 및 무작위 탐색(random search)의 12.50%와 대비되는 성과를 보였습니다. 평균 최고 커버리지는 각각 0.6434와 0.6448이었던 데 반해 0.7816을 기록했습니다. AbsorbEvo는 언어 추론과 물리 기반 피드백을 설계 결정에 통합함으로써, 자연어 기반 마이크로파 흡수체 자율 역설계를 위한 방법론적 기반을 제공합니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.