arXiv:2607.09688v1 cs.LG

Prioritizing Search Space Regions in the Low Autocorrelation Binary Sequences Problem

Blaž Pšeničnik, Borko Bošković, Jan Popić, Janez Brest

제출 2026-06-17

한국어 초록

낮은 자기상관 이진 수열 문제(LABS)는 통신, 신호 처리, 위성 항법 분야에서 중요한 응용을 갖는 어려운 조합 최적화 과제이다. 본 논문은 LABS 탐색 공간의 제한 클래스에 걸쳐 계산 노력을 적응적으로 배분하기 위해 Thompson 샘플링과 병렬 자기회피 보행(self-avoiding walk)을 결합한 하이브리드 탐색 프레임워크를 제안한다. 파티션을 다중 팔 밴딧(multi-armed bandit) 설정의 팔(arm)로 모델링함으로써, 제안된 방법은 덜 샘플링된 영역의 탐험(exploration)을 유지하면서도 경험적으로 더 높은 성능 지수(merit factor)를 산출하는 파티션 쪽으로 탐색 자원을 동적으로 전환한다. 이 접근법은 GPU 병렬 실행, 공유 사후 업데이트, 효율적인 이웃 평가, 그리고 사이클 방지를 위한 블룸 필터(Bloom filter)를 통해 추가로 가속된다. 또한 제약된 분할 비대칭 공간(partitioned skew-symmetric space)을 먼저 탐색한 후 비제약 공간에서 최적 후보를 정제하는 2단계 최적화 전략을 사용한다. 긴 이진 수열에 대한 실험 결과, 제안된 방법은 $450 \le L \le 527$ 범위의 35개 수열 길이와 $L=573$에 대해 이전에 알려진 최선의 결과를 개선하였다. 특히 $L=451$에서 성능 지수 8.0을 초과하는 새로운 최장 수열을 보고한다. 결과는 또한 Thompson 샘플링이 더 나은 관측 성능을 보이는 파티션을 효과적으로 우선시함을 보여주며, LABS 최적화에서 온라인 데이터 기반 자원 배분의 가치를 확인한다. 전반적으로 제안된 프레임워크는 고성능 성능 지수 최대화를 위한 확장 가능하고 효과적인 전략을 제공한다.

원문 초록

Low autocorrelation binary sequences problem (LABS) is a hard combinatorial optimization challenge with important applications in communications, signal processing, and satellite navigation. This paper proposes a hybrid search framework that combines Thompson sampling with parallel self-avoiding walks to adaptively allocate computational effort across restriction classes of the LABS search space. By modeling partitions as arms in a multi-armed bandit setting, the proposed method dynamically shifts search resources toward partitions that empirically produce higher merit factors while maintaining exploration of less-sampled regions. The approach is further accelerated through GPU-parallel execution, shared posterior updates, efficient neighborhood evaluation, and a Bloom filter for cycle prevention. In addition, we use a two-stage optimization strategy that first searches constrained partitioned skew-symmetric spaces and then refines the best candidates in the unrestricted space. Experiments on long binary sequences show that the proposed method improves the previously best-known results for 35 sequence lengths in the range $450 \le L \le 527$ and for $L=573$. In particular, we report a new longest sequence with merit factor exceeding $8.0$, obtained for $L=451$. The results also show that Thompson sampling effectively prioritizes partitions with better observed performance, confirming the value of online, data-driven resource allocation in LABS optimization. Overall, the proposed framework provides a scalable and effective strategy for high-performance merit factor maximization.

제출 이력

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

  1. arXiv:2607.09688v1제출 시각 미확인

함께 살펴볼 논문

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

arXiv:2610.10974v1cs.LG공통 태그 Multi-Armed Bandits, Combinatorial Optimization

오프-정책 평가를 위한 예산 제약 다중 소스 반사실적 주석 달기

Budgeted Multi-Source Counterfactual Annotation for Off-Policy Evaluation

오프-정책(off-policy) 평가(OPE)는 기록된 데이터로부터 타깃 정책의 가치를 추정하지만, 행동 정책의 제한된 커버리지로 인해 높은 분산의 가중치 재조정이나 보상(reward) 모델(model) 외삽이 불가피할 수 있습니다. 반사실적(counterfactual) 주석(annotation)은 관측되지 않은 행동에 대한 증거를 추가할 수 있지만, 도메인 전문가나 대규모 언어 모델(LLM)을 포함한 실제 소스는 비용이 많이 들거나 편향되거나 노이즈가 있을 수 있습니다. 본 연구에서는 맥락적 밴딧(contextual-bandit) OPE를 위해 이러한 주석을 예산 제약 하에서 획득하는 문제를 연구합니다. 소스별 비용과 오류 프로필이 주어졌을 때, 주석 계획에 의존하는 추정량 분산 성분을 최소화하도록 맥락-행동 쌍과 주석 소스에 대한 정수 할당 문제를 정형화합니다. 또한 첫 번째 주석 임계값과 국소적 주석 가치 영역을 통해 주석이 언제 유용한지 규명합니다. 결합된 다중 소스 문제에 대해, 목적 함수를 단조적으로 개선하는 동적 계획법 서브루틴 기반의 주화-최소화(majorization-minimization) 알고리즘을 개발합니다. 합성 임상 및 LLM 주석 기반 교육 밴딧 실험에서 본 할당 방법은 주석이 없는 경우 대비 고정 프로필 평균 제곱 오차(MSE)를 각각 20.58% 및 10.77% 감소시킴을 보여줍니다.

arXiv:2610.11007v1cs.AI공통 태그 Multi-Armed Bandits, Combinatorial Optimization

LLM 에이전트를 위한 상시 로드 컨텍스트 큐레이션: 중도절단 피드백을 갖는 용량 제한 구색 모델

Curating Always-Loaded Context for LLM Agents: A Capacitated Assortment Model with Censored Feedback

모든 세션이 시작될 때, 대규모 언어 모델(LLM) 에이전트는 $\texttt{AGENTS.md}$와 같은 고정된 컨텍스트 파일을 로드합니다. 파일에 로드된 각 토큰은 세션의 후속 라운드마다 반복해서 비용이 청구되며, 이러한 파일은 크기가 커질수록 성능을 저하시킬 수 있습니다. 그러나 실제로는 사람 또는 자동화된 큐레이터가 대개 내용을 덧붙이는(append) 방식으로 이러한 파일의 크기를 늘립니다. 본 연구에서는 컨텍스트 큐레이션을 용량 제한 구색 문제(capacitated assortment problem)로 정식화합니다. 지시문은 유한한 어텐션 용량 내에서 토큰을 소모하며, 지시문을 추가하더라도 다른 지시문의 준수율이 결코 높아지지 않는 반면 유지되는 지시문은 세션당 설정 비용(setup cost)을 발생시킵니다. 본 논문에서는 사용 가능한 후보 지시문의 수와 관계없이 최적 파일 크기의 상한을 증명하며, 단독 가치가 양수인 모든 지시문을 단순히 덧붙이는 방식이 최적의 부분 집합을 선택하는 것에 비해 순가치(net value) 측면에서 임의로 크게 악화될 수 있음을 증명합니다. 또한 토큰 예산은 토큰 가격이 과소평가되었을 때의 손실을 제한합니다. 이어 과거 세션으로부터 무엇을 학습할 수 있는지, 그리고 이 정보가 지시문의 추가 또는 제거 결정을 어떻게 이끌 수 있는지 살펴봅니다. 피드백은 본질적으로 중도절단(censored)되어 있습니다. 로드된 지시문의 이점과 위해는 관찰 가능한 반면, 누락된 지시문은 그 부재가 위해를 초래할 때만 피드백을 생성합니다. 이러한 환경에서 에이전트가 무시한 지시문을 삭제하는 것은 유용한 지시문까지 필연적으로 제거할 수 있음을 보입니다. 또한 지시문을 추가하기 전에 수집해야 하는 근거의 양을 특성화합니다. 아울러 인간 검토자가 기간당 제한된 수의 수정 사항만 검토할 수 있을 때의 후회(regret) 한계를 제시합니다. 실증 실험을 통해서도 실제 컨텍스트 파일에서 추출한 무관한 규칙들이 언어 모델의 준수율을 낮춘다는 점을 추가로 보입니다.

arXiv:2610.03296v1cs.AI공통 태그 Multi-Armed Bandits, 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:2609.26978v1stat.ML공통 태그 Stochastic Optimization, Combinatorial Optimization

다중 스케일 행렬 가중치를 통한 온라인 역 선형 최적화의 정밀 후회 상한

Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights

고정된 알려지지 않은 선형 효용(utility)을 갖는 온라인 역 선형 최적화를 연구한다. 각 라운드에서 환경(environment)은 컴팩트 행동 집합을 제시하고, 학습자(learner)는 그 집합에서 행동(action)을 추천하며, 환경은 동일한 집합 위에서 효용을 최대화하는 행동을 반환한다. 효용 벡터와 행동이 $d$차원 유클리드 단위 구(unit ball) 안에 있을 때, 시간 지평(time horizon)을 알 필요 없이 모든 시간 지평에 대해 기대 후회(regret)---최적 행동 대비 누적 효용 부족분---가 $O(\sqrt d)$인 무작위 알고리즘을 제시한다. $d$에 대한 의존성은 $T\ge d$인 지평에 대한 알려진 $\Omega(\sqrt d)$ 하한에 의해 상수 배수까지 최적이다. 우리 알고리즘은 기하학적으로 간격을 둔 스케일에서 다항식 특징(feature) 공간上的 행렬 곱셈 가중(matrix multiplicative weights)을 유지한다. 선형 프로그램(linear program)을 풀어 추천 분포를 선택하고, 이용 가능한 행동과 피드백 행동을 비교하여 점수 행렬을 갱신한다. 유리수 oracle 출력과 피드백 행동 하에서, 선형 최적화 oracle에 상대적으로 계산 가능한 구현이 $O(\sqrt d)$ 후회 상한을 유지한다. 차원, 지평, 입력 길이에 대해 다항 시간 실행 복잡도로 동일한 rate를 달성할 수 있는지는 열려 있다.

arXiv:2609.28263v1cs.LG공통 태그 Stochastic Optimization, Combinatorial Optimization

재해결 없이 온라인 선형 계획을 위한 자원 적응형 확률적 경사하강법

Resource-Adaptive Stochastic Gradient Descent for Online Linear Programming without Re-solving

대규모 언어 모델(LLM) 추론과 검색 서비스의 확대는 온라인 선형 계획 문제의 규모를 키우며, 계산적으로 효율적인 알고리즘을 요구한다. 본 연구는 확률적 온라인 선형 계획을 위한 자원 적응형 확률적 경사하강법(RASGD)을 제안한다. 이 알고리즘은 요청 하나와 현재 재고(inventory)만으로 자원 가격을 갱신하며, 자원 m개에 대해 도착(arrival)마다 O(m) 연산과 메모리만 필요하고 LP나 표본 평균 최적화(sample-average optimization)는 사용하지 않는다. 핵심은 재해결(re-solving)에서 쓰이는 현재 자원 가격 책정 로직을 1차 SGD 갱신으로 표현하는 것이다. 각 도착마다 이중 목적(dual objective)의 잔여 재고 허용량(allowance)을 갱신하고, 스텝 크기(stepsize)는 초기에는 학습을 위해 작아지다가 이후에는 재고 조정 속도에 맞추어 커진다. 표준 비퇴화(non-degeneracy) 조건 하에서 알고리즘은 모든 표본 경로(sample path)에서 실행 가능(feasible)하며, 실현된 분수적 후견 최적(realized fractional hindsight optimum) 대비 O(\log T) 기대 후회(expected regret)를 달성한다. 이는 분포를 알고 계산 제약이 없는 정책에 대한 하한과 일치한다. 분석은 변화하는 자원 수준에서 최적 가격을 추적하지 않고, 고정 참조 가격 주변의 곡률(curvature)을 재고 안정성(inventory stability)으로 전환한다. 수치 실험에서 RASGD는 도착마다 LP 재해결과 견줄 만한 후회를 달성하고, 시험한 1차 기준선(first-order baselines)보다 나으면서 1차 방법의 계산 효율은 유지한다. 이 결과는 RASGD가 대규모 OLP에서 높은 할당 품질을 계산 효율적으로 달성하는 접근임을 보여준다.

arXiv:2609.23180v1quant-ph공통 태그 Stochastic Optimization, Combinatorial Optimization

잡음이 있는 QAOA 최적화를 위한 적응형 차분 진화 및 다중 시작 탐색

Adaptive Differential Evolution and Multistart Search for Noisy QAOA Optimization

우리는 $N=12$, $p=3$, $D=6$ 조건에서 네 가지 비용 해밀토니안(cost-Hamiltonian) 계열에 걸쳐 고정된 저심도(low-depth) 양자 근사 최적화 알고리즘(Quantum Approximate Optimization Algorithm, QAOA) 앤자츠(ansatz)에 대한 고전적 최적화를 벤치마크한다. 10개의 옵티마이저를 10,000회 및 30,000회의 함수 평가(function evaluations, FEs)라는 공통 상한 하에서 25회의 독립 실행에 걸쳐 비교하며, 먼저 정확한 상태벡터(statevector) 목적함수로, 이후 두 가지 수준의 가산 관측 잡음(observation noise)을 적용하여 비교한다. 정확한 목적함수에서는 다중 시작(multistart) BFGS와 다중 시작 CMA-ES가 우세하다. 잡음이 있는 피드백 하에서는 적응형 개체군(population) 기반 방법들이 더 경쟁력을 갖게 되지만, 그 순위는 성능을 방문한 최적의 정확한 지점으로 측정하는지 아니면 잡음이 있는 관측값으로부터 선택된 지점으로 측정하는지에 따라 달라진다. 각 계열별로 사전 선별된 세 가지 인스턴스 전체에 대한 표적 확장 실험은 이러한 국면 전환(regime change)을 확인해주는 동시에, 명명된 적응형 차분 진화(adaptive-DE) 우승자들이 인스턴스에 따라 달라짐을 보여준다: 동일 인스턴스 요약에서 jSO-lite는 저잡음 오라클 탐색을, iL-SHADE는 고잡음 오라클 탐색을, L-SRTDE는 고잡음 선택 해(solution)를 각각 주도한다. 부트스트랩(bootstrap) 분석은 무시할 수 없는 수준의 고잡음 탐색-선택 격차(search-selection gap)를 정량화하며, 소급적 고정 예산 검증 프록시(retrospective fixed-budget verification proxy)는 최종 재평가를 위해 소량의 측정 예산을 남겨두는 것이 30,000 FEs에서 열 가지 방법 모두에 걸쳐 선택된 해의 품질을 향상시킴을 보여준다. 추가적인 구조 인식(structure-aware) 연구는 나아가 이러한 조건에서 QAOA의 교차 심도 제한(cross-depth restriction)과 연속적 분지 정제(continuous basin refinement)가 단독 몬테카를로 트리 탐색(Monte Carlo tree-search) 선택보다 더 유용함을 보여준다. 전반적으로 옵티마이저 선택은 지형 구조(landscape structure), 관측 잡음, 그리고 최종 지점 식별(final-point identification)에 공동으로 의존한다.

토론

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