Abstract M-Modes for graphical models is the problem of fifinding top M label confifigurations of highest probability in their local neighborhoods. The state-ofthe-art method for solving M-Modes is a dynamic programming algorithm which computes global modes by fifirst computing local modes of each subgraph and then search through all their consistent combinations. A drawback of the algorithm is that most of its time is wasted on computing local modes that are never used in global modes. This paper introduces new algorithms that directly search the space of consistent local modes in fifinding the global modes, which is enabled by a novel search operator designed to search a subgraph of variables at each time. As a result, the search algorithms only need to generate and verify a small number of local modes and can hence lead to signifificant improvement in effificiency and scalability