# Prioritizing Search Space Regions in the Low Autocorrelation Binary Sequences Problem

arXiv: https://arxiv.org/abs/2607.09688 · HTML: https://mlsanity.com/paper/2607.09688/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 50 references that are in the map.
- First posted on arXiv 17 Jun 2026.

## Builds on (most cited first, 11 of 11)

- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Low Autocorrelation Binary Sequences](https://mlsanity.com/paper/1512.02475/) (2015)
- [Low-Autocorrelation Binary Sequences: On Improved Merit Factors and Runtime Predictions to Achieve Them](https://mlsanity.com/paper/1406.5301/) (2014)
- [Improved Branch-and-Bound for Low Autocorrelation Binary Sequences](https://mlsanity.com/paper/1305.6187/) (2013)
- [On the Skew-Symmetric Binary Sequences and the Merit Factor Problem](https://mlsanity.com/paper/2106.03377/) (2021)
- [Parallel Self-Avoiding Walks for a Low-Autocorrelation Binary Sequences Problem](https://mlsanity.com/paper/2210.15962/) (2022)
- [Moments of Autocorrelation Demerit Factors of Binary Sequences](https://mlsanity.com/paper/2307.14281/) (2023)
- [Spreading Code Optimization for Low-Earth Orbit Satellites via Mixed-Integer Convex Programming](https://mlsanity.com/paper/2404.12629/) (2024)
- [Dual-Step Optimization for Binary Sequences with High Merit Factors](https://mlsanity.com/paper/2409.07222/) (2024)
- [Large-Scale GNSS Spreading Code Optimization](https://mlsanity.com/paper/2410.04653/) (2024)
- [New Improvements in Solving Large LABS Instances Using Massively Parallelizable Memetic Tabu Search](https://mlsanity.com/paper/2504.00987/) (2025)

## Abstract (arXiv)

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 ≤ L ≤ 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.