RAISE: LLM-based Automated Heuristic Design with Robust Adversary Instance Search
원문 초록
Automated Heuristic Design (AHD) with Large Language Models (LLMs) has shown remarkable progress in discovering high-quality heuristics. However, existing LLM-based AHD methods optimize heuristics for a fixed training instance set and may fail catastrophically when deployed under real-world distributional shifts. We propose Robust Adversary Instance Search (RAISE), a framework that integrates constrained worst-case instance search within a principled neighborhood of the training distribution into the LLM-based evolutionary search loop. RAISE treats robust AHD as a constrained adversarial instance search problem: the outer loop evolves heuristics via LLM operators, while an LLM-free inner loop efficiently identifies hard instances within an epsilon-ball around the training instance set using a basis distribution parameterization with boundary projection. Comprehensive experiments on Online Bin Packing (OBP), Online Job Shop Scheduling (OJSP), and Online Vehicle Routing (OVRP) across five distribution families demonstrate that existing LLM-based AHD methods degrade by up to 19 times under distribution shift, while RAISE consistently maintains strong performance across all tested distributions and problem scales
요약
LLM 기반 자동 휴리스틱 설계(AHD)가 고정된 학습 인스턴스 분포에 과적합되어 실제 배포 시 분포 이동(distribution shift)에 취약한 문제를 해결하기 위해, RAISE 프레임워크는 LLM 진화 탐색의 외부 루프와 LLM-free 적대적 인스턴스 탐색의 내부 루프를 결합한 이중 수준 구조를 제안한다. Online Bin Packing, Job Shop Scheduling, Vehicle Routing 등 세 가지 조합 최적화 과제에서 기존 LLM 기반 AHD 방법이 분포 이동 시 최대 19배 성능 저하를 보인 반면, RAISE는 모든 테스트 분포와 문제 규모에서 일관되게 강건한 성능을 유지하였다.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2606.31801v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
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 성능이 향상되어, 여러 방법 전반에 걸친 유효성을 뒷받침합니다.
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배 단축합니다.
불완전한 프록시 보상을 활용한 신뢰할 수 있는 자기 진화
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 에서 확인할 수 있습니다.
LLM에서의 전문가 격리 및 비활성화를 통한 백도어 억제
Backdoor Containment via Expert Quarantine and Shutdown in LLMs
영공간 투영을 통한 LoRA 미세조정 LLM의 백도어 정제
Backdoor Purification for LoRA-Tuned LLMs via Null-Space Projection
입력 시퀀스 변화에 대한 대규모 언어 모델(LLM)의 강건성 평가 및 개선
Evaluating and Improving the Robustness of Large Language Models to Input Sequence Variations
프로덕션 시스템에서 운영되는 대규모 언어 모델(LLM)은 프롬프트 인젝션(prompt injection), 트로이목마(trojan, 백도어), 그리고 자동 품질 지표 조작 공격에 직면한다. 본 논문은 적대적 입력 시퀀스 변화에 대한 LLM의 강건성을 평가하고 개선하기 위한 모델, 방법, 알고리즘을 개발한다. 우리는 작은 입력 교란(perturbation) 하에서 단계별 출력 분포 간의 Jensen-Shannon 발산(divergence)에 기반한 생성적 강건성 지표인 R_stab(f)를 제안한다. 국소적(localized) 공격에 대해서는 V(h) <= 1 - R_class(h)를 증명하며, 여기서 R_class(h)는 의사결정 연산자 h가 작은 교란 하에서도 자신의 결정을 유지할 확률이다. 비국소적(non-localized) 공격에 대해서는 보정된(calibrated) 경험적 모델을 제안한다. LLM-as-a-judge 시스템에 대해서는 적응형 진화 블랙박스 공격인 ASA를 개발했으며, 이는 최대 73.8%의 공격 성공률(ASR)을 달성하고 오픈 모델 간 전이(transfer) 시에도 최대 62.6%를 기록한다. Trojan Detection Challenge 2023 데이터(Pythia-1.4B)에서는 대리(surrogate) 트리거가 REASR ~0.99에 도달하는 반면, 실제 트리거에 대한 재현율은 기준선 ~0.14에 비해 ~0.17에 불과하다. SaTML CTF 2024에서는 다층(multi-layer) 방어를 우회하는 네 가지 유형을 체계화했으며, 이를 통해 ASR을 90%에서 15~25%로 감소시켰다. 5~7개의 이질적(heterogeneous) 모델로 구성된 위원회(committee)는 Gemma-3-4B의 ASR을 47~55퍼센트포인트 감소시켜, 7개 모델 사용 시 19.3%까지 낮춘다. Model Context Protocol(MCP) 기반 에이전트형(agentic) 시스템에 대해서는, 호출당 0.1ms 미만으로 HMAC으로 보호된 패킷을 사용해 도구 호출(tool call)을 증명(attest)하는 AttestMCP와 Commit Boundary 격리 패턴을 제안한다. 847개 시나리오로 구성된 MCPBench 벤치마크(benchmark)에서 이들 방법은 평균 ASR을 53.7%에서 12.4%로 감소시킨다. 이 방법들은 JudgeGuard 및 TrojanArmor 소프트웨어 스위트와 MCPSec 모듈로 구현되었다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.