Abstract: For the past twenty years, Tensor Network States (TNS) have been widely used to model the low energy sector of local Hamiltonians. Their success in doing so has led to the wide-held mantra that TNS of low bond dimension are the `only physical states' of natural condensed matter systems. However, given our experimental limitations to interact with such systems, it is not clear how this conjecture translates into any observable effect. In this Letter we give a first step in this direction by identifying particular operational features pertaining to all Matrix Product States (MPS), the class of TNS used to model non-critical one-dimensional spin chains. By exploiting two surprising structural constraints of MPS, we show how to systematically derive `bond dimension witnesses', or k-local operators whose expectation value allows us to lower bound the bond dimension of the underlying quantum state. We extend some of these results to the ansatz of Projected Entangled Pairs States (PEPS). As a bonus, we use our insight on the structure of MPS to derive some limitations on the use of MPS and PEPS for ground state energy computations.