arXiv:2604.19753v3 cs.AI

텍스트 임베딩을 통해 도메인 지식 없이 수행하는 알고리즘 선택

Algorithm Selection with Zero Domain Knowledge via Text Embeddings

Stefan Szeider

제출 2026-03-20

한국어 초록

수작업으로 설계된 인스턴스 특징 대신 사전학습(pre-training)된 텍스트 임베딩(embedding)을 활용하는 특징 없는 알고리즘 선택 접근법인 ZeroFolio를 제안합니다. 이 방법은 원시 인스턴스 파일을 일반 텍스트로 읽어 사전학습된 임베딩 모델로 임베딩한 후, 가중치 적용 k-최근접 이웃(weighted k-nearest neighbors)을 통해 알고리즘을 선택합니다. 우리의 접근법은 사전학습된 임베딩이 어떠한 도메인 지식이나 태스크별 학습(training) 없이도 문제 인스턴스를 구별할 수 있다는 관찰에 기반합니다. ZeroFolio는 텍스트 기반 인스턴스 형식을 가진 모든 문제 도메인에 적용할 수 있습니다. 7개 도메인(SAT, MaxSAT, QBF, ASP, CSP, MIP 및 그래프 문제)에 걸친 11개 ASlib 시나리오에서 접근법을 평가합니다. ZeroFolio는 11개 시나리오 중 9개에서 수작업 특징으로 학습된 랜덤 포레스트(random forest)보다 우수한 성능을 보이며, 종종 큰 폭의 성능 향상을 기록하고, 그중 8개 시나리오에서는 모든 직렬화 시드(serialization seed)에 대해 뛰어난 성능을 보입니다. 시나리오별로 튜닝된 랜덤 포레스트를 상대로도 11개 시나리오 중 8개에서 승리합니다. 2015 ICON 챌린지에서 공개된 AutoFolio 결과가 있는 3개 시나리오에서, ZeroFolio는 시나리오별 튜닝 없이도 AutoFolio와 근소한 마진 내의 성능을 달성합니다. SAT12-ALL에 대한 절제 연구(ablation study)는 역거리 가중치(inverse-distance weighting)와 라인 셔플링이 성능을 향상시킴을 보여줍니다. 나아가 직렬화 시드에 대한 접근법의 민감도를 분석합니다. 랜덤 포레스트가 더 강력한 SAT12-ALL 시나리오의 경우, 소프트 보팅(soft voting)을 통해 두 방식을 결합함으로써 추가적인 성능 향상을 얻을 수 있습니다.

원문 초록

We propose ZeroFolio, a feature-free approach to algorithm selection that uses pretrained text embeddings instead of hand-crafted instance features. It reads the raw instance file as plain text, embeds it with a pretrained embedding model, and selects an algorithm via weighted k-nearest neighbors. Our approach is based on the observation that pretrained embeddings can distinguish problem instances without any domain knowledge or task-specific training. ZeroFolio applies to any problem domain with text-based instance formats. We evaluate our approach on 11 ASlib scenarios spanning 7 domains (SAT, MaxSAT, QBF, ASP, CSP, MIP, and graph problems). ZeroFolio outperforms a random forest trained on hand-crafted features in 9 of 11 scenarios, often substantially, and in 8 of them with every serialization seed. It wins 8 of 11 scenarios against a per-scenario-tuned random forest. On the three scenarios with published AutoFolio results from the 2015 ICON Challenge, ZeroFolio comes within a small margin of AutoFolio without any per-scenario tuning. Our ablation study on SAT12-ALL shows that inverse-distance weighting and line shuffling improve performance. We further analyze the sensitivity of our approach to the serialization seed. On the SAT12-ALL scenario, where the random forest is stronger, both methods can be combined via soft voting to achieve further improvements.

제출 이력

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

  1. arXiv:2604.19753v3

함께 살펴볼 논문

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

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

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:2607.24162v2cs.AI공통 태그 Model Selection, Combinatorial Optimization

Agent-UCT: 비용 인식 에이전트 워크플로 최적화를 위한 트리에 적용된 상한 신뢰 경계

Agent-UCT: Upper Confidence Bounds Applied to Trees for Agentic Workflow Optimization with Cost-Awareness

검색-증강 생성(RAG) 파이프라인과 같은 에이전트 워크플로의 최적화는 엄격한 평가 예산 하에서 이산적 구성 요소 선택의 조합 공간을 탐색해야 한다. 기존 접근법—휴리스틱 탐색, 블랙박스 최적화, 표준 트리 탐색 방법—은 이러한 워크플로의 구성적 구조를 명시적으로 활용하지 않아 중복 계산과 비효율적인 예산 배분을 초래한다. 우리는 Agent-UCT(Agent-based Cost-Aware Upper Confidence Bounds Applied to Trees)를 제안한다. 이는 이분 접두 문맥 재사용 그래프에서 유도된 재사용 인식 정규화 항으로 UCT를 확장한 트리 탐색 알고리즘이다. Agent-UCT는 이전에 구체화된 구성 접두 문맥을 활용하는 분기를 선호하도록 선택을 편향시켜, 효과적인 탐험을 유지하면서 중복 실행을 줄인다. 우리의 프레임워크 RAGSpace는 LongRAG, LightRAG, Self-RAG의 이질적 RAG 구성 요소를 5차원 구성 공간으로 통합하여 체계적인 프레임워크 간 재조합을 가능하게 한다. WTB(Workflow Test Bench)는 결정적 재생, 콘텐츠 주소 지정 캐싱, 트랜잭션 일관성을 제공하여 중간 상태가 한 번 구체화되어 탐색 전반에 재사용되도록 보장한다. HotpotQA와 UltraDomain에서의 실험은 Agent-UCT가 평가된 고정 프레임워크 프리셋 중에서 가장 높은 표본 외 성능을 갖는 구성을 식별함을 보여준다. 전체 풀 평가에서 이분 접두 문맥 재사용은 접두 공유 없음 비용 상한 대비 논리적 탐색 비용을 73.6% 줄인다. 전체 풀 평가와 비교하여, 샘플링 기반 평가는 추가로 wall-clock 기준 4.2배 속도 향상을 달성한다. Agent-UCT, RAGSpace, WTB는 함께 비용 인식적이고 재현 가능하며 구성적으로 효율적인 에이전트 워크플로 최적화를 위한 통합 프레임워크를 제공한다.

arXiv:2607.22621v1cs.AI공통 태그 Model Selection, Combinatorial Optimization

Opti-Q: 다중 LLM 질문 계획을 위한 제약 기반 최적화 프레임워크

Opti-Q: A Constraint-Based Optimization Framework for Multi-LLM Question Planning

대규모 언어 모델(LLM)은 강력한 질의응답(QA)을 가능하게 하지만, 예산 내 배포는 비결정성과 이질적인 자원 프로파일(비용, 지연시간, 에너지)로 인해 복잡해진다. 우리는 다중 LLM 오케스트레이션을 위한 실행 전 계획(plan-before-execute) 패러다igm을 구현하는, 데이터베이스에서 영감을 받은 비용 기반 옵티마이저 OPTI-Q를 제안한다. OPTI-Q는 LLM 호출을 실행 방향성 비순환 그래프(DAG)의 물리적 연산자로 모델링하고, 각 질문에 대해 사용자가 지정한 자원 제약 하에서 답변 품질(QoA)을 최적화하면서 금전적 비용, 지연시간, 에너지 간 트레이드오프를 고려하는 계획을 탐색한다. 계획에는 중간 답변을 컨텍스트로 전달하는 순차 연산자와, 모델을 동시에 실행하고 출력을 병합하는 병렬/블렌드 연산자가 포함될 수 있다. 각 후보 계획을 실행하지 않고 이 공간을 탐색하기 위해, OPTI-Q는 벤치마크와 실행 트레이스로 채워지고 갱신되는 통계 카탈로그 PERFDB를 사용하여 개별 연산자와 구성된 하위 계획 모두의 QoA와 자원 비용을 추정한다. 이 추정치를 활용하여 OPTI-Q는 파레토 프론티어 탐색을 수행하고 사용자 선호에 따라 최종 계획을 선택한다. 사용자가 지정한 예산 하에서 MMLU-Pro와 SimpleQA에서 OPTI-Q는 유사한 비용에서 베이스라인 대비 평균 QoA를 각각 약 58% 및 41% 향상시켰으며, 이는 데이터베이스 스타일 계획이 다중 LLM QA에서 더 나은 품질-자원 트레이드오프를 제공함을 보여준다.

arXiv:2607.23997v1cs.AI공통 태그 Model Selection, Combinatorial Optimization

콘텐츠 민감형 자원 할당을 통한 예산 제약 이미지 분류 탐구

Exploring Budgeted Image Classification with Content-Sensitive Resource Allocation

인공지능(AI)의 지속적으로 증가하는 도입은 다양한 컴퓨팅 환경에서 심층 신경망(Deep Neural Networks)을 배포할 필요를 만들어낸다. 우리는 컴퓨팅 요구사항이 변화하는 동적 환경을 고려하며, 변화하는 컴퓨팅 제약을 충족하면서 AI 분류 시스템의 복잡도를 어떻게 조정해야 정확도를 최대화할 수 있는지라는 질문을 제기한다. 우리는 이 문제를 예산 제약 이미지 분류(Budgeted Image Classification)라고 부르며, 이를 자원 할당 정수 프로그램(integer program)으로 공식적으로 정식화한다. 주어진 컴퓨팅 예산, 배치의 이미지, 그리고 서로 다른 복잡도로 결정을 내릴 수 있는(여러 결정 지점을 갖는) 분류 시스템이 주어졌을 때, 우리는 사용 가능한 예산 내에서 정확도를 최대화하기 위해 이미지를 결정 지점에 할당하는 전략을 탐구한다. 원래의 정수 프로그램은 NP-Hard이므로, 우리는 연속 완화(continuous relaxation)를 제안하며, 이는 이미지의 특정 콘텐츠를 고려하지 않고 결정 지점에 이미지를 할당하는 콘텐츠 비의존적(content-agnostic) 할당 전략으로 이어진다. 우리는 콘텐츠 민감형(content-sensitive) 전략을 제안하여 이 문제를 해결하며, 실험적으로 이 전략이 더 우수한 성능을 이끈다는 것을 보인다. 우리는 전략들의 동작을 이론적으로 연구하여, 예산 제약 분류에 적합하기 위해 결정 지점이 만족해야 하는 조건을 도출한다. 우리는 실패 사례를 분석하여 향후 연구 방향에 대한 통찰을 제공한다.

arXiv:2607.13239v1cs.AI공통 태그 Model Selection, Combinatorial Optimization

교통 관리를 위한 비용 최적 파운데이션 모델 배포 포트폴리오

Cost-Optimal Foundation Model Deployment Portfolio for Transportation Management

파운데이션 모델(foundation model)에는 대규모 언어 모델(LLM)과 비전-언어 모델(VLM)이 포함되며, 이상 탐지, 사고 보고, 여행자 정보 제공과 같은 교통 관리 센터(TMC) 업무에 점점 더 많이 사용되고 있다. 여러 이러한 모델을 TMC 기능 전반에 배포하는 것은 포트폴리오 질문을 제기한다: 각 기능에 어떤 모델이, 어떤 배포 모드로, 그리고 어떤 공유 하드웨어 예산 하에서 제공되어야 하는가? 우리는 이를 파운데이션 모델 배포 포트폴리오(FMDP) 문제로 공식화한다. 이는 공유 GPU 용량에 대해 기능별 품질, 지연 시간, 안전성 제약을 만족하면서 총 소유 비용(TCO)을 최소화하는 혼합 정수 프로그램이다. 0-1 배낭 문제로의 환원을 통해 이 문제가 NP-난해함을 증명하고, 다항 시간 탐욕적 휴리스틱을 제안한다. 다섯 가지 TMC 기능과 19개의 후보 (모델, 모드) 쌍을 포함한 예시 사례 연구에서, FMDP는 4개 기능을 오픈소스 API로, 오픈소스 모델이 품질 하한을 충족하지 못하는 1개 기능을 폐쇄형 API로 라우팅하는 혼합 포트폴리오를 식별하여 월 $34(가장 저렴한 실행 가능한 전체 폐쇄형 API 기준선 대비 97% 절감)의 비용을 산출한다. 손익분기 분석에 따르면, 온프레미스 GPU 투자는 시간당 약 309회의 비전 쿼리 이상이거나 API 가격이 두 배로 오를 때만 합리적이 된다.

토론

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