New hybrid AI framework solves 35 binary sequence optimization records

The Low Autocorrelation Binary Sequences (LABS) problem is a notoriously hard combinatorial optimization challenge with critical applications in communications, signal processing, and satellite navigation. In a new arXiv preprint, authors Blaž Pšeničnik, Borko Bošković, Jan Popić, and Janez Brest introduce a hybrid search framework that dramatically advances state-of-the-art results. Their approach models partitions of the search space as arms in a multi-armed bandit, using Thompson sampling to dynamically allocate computational effort toward regions that empirically yield higher merit factors. This is combined with parallel self-avoiding walks, GPU-parallel execution, shared posterior updates, efficient neighborhood evaluation, and a Bloom filter to prevent cycles. A two-stage strategy first searches constrained partitioned skew-symmetric spaces, then refines the best candidates in 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. Notably, they report a new longest sequence with a merit factor exceeding 8.0, obtained for L=451. The results confirm that Thompson sampling effectively prioritizes partitions with better observed performance, validating online, data-driven resource allocation for LABS optimization. This scalable framework offers a powerful approach for high-performance merit factor maximization and could influence other hard optimization problems in signal design and cryptography.