Two-level hierarchical decision-making problems, where a leader’s choice influences a follower’s action, arise across key business and public-sector domains, from market design and pricing to defense. These problems are typically modeled as bilevel programs and are known to be notoriously hard to solve at scale. In single-level combinatorial optimization, especially for challenging instances, local search methods are often used to obtain good-quality solutions when problem size limits the use of specialized solvers. Additionally, these methods also play a key role within state-of-the-art solvers to improve feasibility bounds. Their appeal lies in fast implementation and scalability; however, applying them to bilevel problems presents two key challenges: (i) the potentially large number of iterations required to terminate, and (ii) in each iteration, evaluating the leader’s objective function requires solving the follower’s problem, which may be hard by itself. We address the first challenge by extending approximate local optimality to the bilevel setting. This solution concept guarantees that no neighboring solution improves the leader’s objective function beyond some limit. To overcome the second challenge, we introduce the concept of weak local optimality, yet another generalization. Specifically, instead of computing the follower’s rational response, we evaluate the leader’s objective function using either a follower’s approximate solution, or simply a feasible decision. By combining these two concepts, we demonstrate that a (weak) approximate local optimal solution can be efficiently computed through a local search-based approach. Computational experiments demonstrate that the proposed method significantly reduces runtime compared to standard local search while maintaining comparable solution quality.