<p>Traditional attribute reduction methods for finding all reductions in consistent decision systems (DSs) primarily rely on discernibility matrix, but suffer from high computational complexity due to exhaustive searches over the attribute power set. To address this inefficiency, this paper presents a novel attribute reduction method based on matroid theory, which accelerates the reduction process of consistent DSs. The method mainly includes two stages: in stage one, a matroid is first generated based on consistent DS, with which a dependency space is then constructed; while in stage two, an attribute reduction algorithm of the consistent DS is developed based on the generated dependency space. In the proposed attribute reduction algorithm, seeking all the reductions of a consistent DS based on the discernibility matrix and normal form can be translated into seeking all the bases of the matroid generated from the given consistent DS, which results in the higher efficiency of the proposed attribute reduction algorithm. The numerical experiments conducted on the given datasets verified the efficiency of the proposed algorithms.</p>