# Unweighted Stochastic Local Search can be Effective for Random CSP Benchmarks

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Nov 2014.

## Built on by (most cited first, 1 of 1)

- [frb100-40 After Two Decades: An Optimality Certificate and a Preregistered Search Study](https://mlsanity.com/paper/2609.02804/) (2026)

## Abstract (arXiv)

We present ULSA, a novel stochastic local search algorithm for random binary constraint satisfaction problems (CSP). ULSA is many times faster than the prior state of the art on a widely-studied suite of random CSP benchmarks. Unlike the best previous methods for these benchmarks, ULSA is a simple unweighted method that does not require dynamic adaptation of weights or penalties. ULSA obtains new record best solutions satisfying 99 of 100 variables in the challenging frb100-40 benchmark instance.