We present GFORS, a GPU-accelerated framework for large binary integer programs. It couples a first-order (PDHG-style) routine that guides the search in the continuous relaxation with a randomized, feasibility-aware sampling module that generates batched binary candidates. Both components are designed to run end-to-end on GPUs with minimal CPU–GPU synchronization. The framework establishes near-stationary-point guarantees for the first-order routine and probabilistic bounds on the feasibility and quality of sampled solutions, while not providing global optimality certificates. To improve sampling effectiveness, we introduce techniques such as total-unimodular reformulation, customized sampling design, and monotone relaxation. On classic benchmarks (set cover, knapsack, max cut, 3D assignment, facility location), baseline state-of-the-art exact solvers remain stronger on small–medium instances, while GFORS attains high-quality incumbents within seconds; on large instances, GFORS yields substantially shorter runtimes, with solution quality often comparable to—or better than—the baseline under the same time limit. These results suggest that GFORS can complement exact solvers by delivering scalable, GPU-native search when problem size and response time are the primary constraints.