As one of the nearest and most dormant supermassive black holes (SMBHs), M31* provides a rare but promising opportunity for studying the physics of black hole accretion and feedback at the quiescent state. Previous Karl G. Jansky Very Large Array (VLA) observations with an arcsec resolution have detected M31* as a compact radio source over centimeter wavelengths, but the steep radio spectrum suggests optically-thin synchrotron radiation from an outflow driven by a hot accretion flow onto the SMBH. Aiming to probe the putative radio outflow, we have conducted milli-arcsec-resolution very long baseline interferometric (VLBI) observations of M31* in 2016, primarily at 5 GHz and combining the Very Long Baseline Array, Tianma-65m and Shanghai-25m Radio Telescopes. Despite the unprecedented simultaneous resolution and sensitivity achieved, no significant (& 3) signal is detected at the putative position of M31* given an RMS level of 5.9 μJy beam−1, thus ruling out a point-like source with a peak flux density comparable to that ( 30 μJy beam−1) measured by the VLA observations taken in 2012. We disfavor the possibility that M31* has substantially faded since 2012, in view that a 2017 VLA observation successfully detected M31* at a historically-high peak flux density ( 75 μJy beam−1 at 6 GHz). Instead, the non-detection of the VLBI observations is best interpreted as the arcsec-scale core being resolved out at the milli-arcsec-scale, suggesting an intrinsic size of M31* at 5 GHz larger than 300 times the Schwarzschild radius. Such extended radio emission may originate from a hot wind driven by the weakly accreting SMBH.