The architecture of many complex systems is well described by multiplex interaction networks, and their dynamics is often the result of several intertwined processes taking place at different levels. However only in a few cases can such multi-layered architecture be empirically observed, as one usually only has experimental access to such structure from an aggregated projection. A fundamental question is thus to determine whether the hidden underlying architecture of complex systems is better modelled as a single interaction layer or results from the aggregation and interplay of multiple layers. Here we show that, by only using local information provided by a random walker navigating the aggregated network, it is possible to decide in a robust way if the underlying structure is a multiplex and, in the latter case, to determine the most probable number of layers. The proposed methodology detects and estimates the optimal architecture capable of reproducing observable non- Markovian dynamics taking place on networks, with applications ranging from human or animal mobility to electronic transport or molecular motors. Furthermore, the mathematical theory extends above and beyond detection of physical layers in networked complex systems, as it provides a general solution for the optimal decomposition of complex dynamics in a Markov switching combination of simple (diffusive) dynamics.