In this contribution we study the propagation constant of interconnects subject to line edge roughness by means of an efficient stochastic framework. By employing the stochastic testing method, we succeed in limiting the number of calls to the full-wave electromagnetic field solver at the core of the system. Additionally, the computationally burdensome solution of the eigenvalue problem is eased by reducing its order through projection on an appropriate basis. The resulting two-step acceleration leads to an effective approach to assess the effect of line edge roughness on the characteristics of interconnects. The novel framework is applied to a rough rectangular waveguide and a microstrip.