We have developed a theoretical framework that provides observational constraints on the early Universe galaxy-halo connection by combining measurements of the ultraviolet luminosity function (UVLF) and galaxy clustering via the two-point correlation function (2PCF). We implemented this framework in the FRESCO and CONGRESS JWST NIRCam/grism surveys by measuring the 2PCF of spectroscopically selected samples of Hα and [O III] emitters at 3.8 < z < 9 in 124 arcmin² in GOODS-North and GOODS-South. By fitting the 2PCF and UVLF at 3.8 < z < 9, we inferred that the Hα and [O III] samples at ⟨z⟩∼4.3, 5.4, and 7.3 reside in halos of masses of log(M_h/M_⊙) = 11.5, 11.2, and 11.0, respectively, while their galaxy bias increases with redshift with values of b_g = 4.0, 5.0, and 7.6. These halos, however, do not represent extreme overdense environments at these epochs. Our framework constrains the instantaneous star formation efficiency (SFE), defined as the ratio of the star formation rate over the baryonic accretion rate as a function of halo mass. We find that the SFE rises with halo mass, peaks at ∼20% at M_h ∼ 3 × 10¹¹ M_⊙, and declines at higher halo masses. The SFE-M_h shows only a mild evolution with redshift with tentative indications that low-mass halos decrease but the high-mass halos increase in efficiency with redshift. The scatter in the M_UV − M_h relation, quantified by σ_UV, implies modest stochasticity in the UV luminosities of ∼0.7 magand is relatively constant with redshift. Extrapolating our model to z > 9 showed that a constant SFE-M_h fixed at z = 8 cannot reproduce the observed UVLF, and neither a high maximum SFE nor a high stochasticity alone can explain the high abundances of luminous galaxies seen by JWST. Extending the analysis of the UVLF and 2PCF to z > 9 as measured from wider surveys will be crucial to breaking the degeneracies between different physical mechanisms that can explain the high abundance of bright galaxies.