Realizing quantum speedup for practically relevant, computationally hard problems is a central challenge in quantum information science. I will present experimental investigations of quantum algorithms for solving the Maximum Independent Set problem using Rydberg atom arrays with up to 289 qubits in two spatial dimensions. I will outline how we use a hardware-efficient encoding associated with Rydberg blockade, realize closed-loop optimization to test several variational algorithms, and apply them to systematically explore a class of graphs with programmable connectivity. Next, I will discuss the results of benchmarking the quantum algorithm's performance against classical simulated annealing and explain graph properties that control the problem hardness.  Finally, I will explain our observations of a superlinear quantum speedup on the hardest graphs in finding exact solutions in the deep circuit regime and analyze its origins.