We consider bilevel programs that involve a leader, who first commits to a mixed-integer decision, and a follower, who observes this decision and then responds rationally by solving a linear program (LP). Standard approaches often reformulate these bilevel optimization problems as single-level mixed-integer programs by exploiting the follower’s LP optimality conditions. These reformulations introduce either complementarity or quadratic constraints, which become increasingly numerous and burdensome as the number of constraints in the follower’s problem grows. This growth is arguably the main computational bottleneck for solving these problems at scale. Accordingly, we propose a dimensionality-reduction approach that projects the follower’s constraints into a compressed representation of smaller size. Building on this representation, we develop a surrogate duality theory, from which we derive a feasibility-based lower bound and a surrogate-dual upper bound on the leader’s optimal objective function value. We also demonstrate the existence of a family of projections that ensures provable approximation guarantees. Rather than searching for those projections, we employ linear sketching techniques, offering probabilistic approximation guarantees and highlighting trade-offs between dimensionality reduction and approximation quality. Finally, our preliminary numerical experiments illustrate the computational promise of dimensionality reduction techniques in bilevel programming.