We present a scalable, GPU-accelerated algorithmic framework for large binary integer programs that operates end-to-end with minimal synchronization overhead. The proposed method combines a first-order routine that guides search in the continuous relaxation with a randomized, feasibility-aware sampling module that generates batched binary candidates. We establish a residual convergence guarantee for the first-order component in the convex setting and a finite-horizon primal-dual residual estimate in the general nonconvex setting, together with probabilistic bounds on the feasibility and solution quality of sampled candidates, without providing global optimality certificates. A key modeling consideration under this framework concerns the treatment of equality constraints to enhance sampling effectiveness. We address this through total-unimodular reformulations and tailored sampling schemes designed to improve feasibility rates. We evaluate the framework on standard benchmark classes, including set cover, knapsack, max-cut, three-dimensional assignment, and facility location. On small- to medium-scale instances, state-of-the-art exact solvers remain stronger overall; nevertheless, our method produces high-quality incumbents within short runtimes. On larger instances, the proposed approach achieves substantially shorter runtimes while often delivering solution quality comparable to exact solvers under the same time limit. Overall, the framework complements exact methods by enabling scalable, parallel search in domains where problem size and response time are primary considerations.