The existing derivations of fast RLS adaptive filters are dependent on the shift structure in the input regression vectors. This structure arises when a tapped-delay line (FIR) filter is used as a modeling filter. In this paper, we show, unlike what original derivations may suggest that fast fixed-order RLS adaptive algorithms are not limited to FIR filter structures. We show that fast recursions in both explicit and array forms exist for more general data structures, such as orthononnally-based models. One of the benefits of working with an orthonormal basis is that fewer parameters can be used to model long impulse responses.