We present SparseLUT, a novel training method for Lookup Table (LUT)-based Deep Neural Networks (DNNs) that eliminates the need for random seed optimization-a common requirement in existing LUT-DNN approaches (e.g., LogicNets, PolyLUT, PolyLUT-Add, and NeuraLUT) that rely on fixed sparsity masks. SparseLUT is a connectivity-centric training technique tailored for LUT-based DNNs, that leverages a non-greedy training strategy that prioritizes the pruning of less significant connections and strategically regrows alternative ones, resulting in efficient convergence to the target sparsity. Experimental results show consistent accuracy improvements across benchmarks, including up to a 2.13% increase on MNIST and a 0.94% improvement for Jet Substructure Classification compared to random sparsity. This is done without any hardware overhead and achieves state-of-the-art results for LUT-based DNNs (Code: https://github.com/bingleilou/SparseLUT).