A new approach to deciding quasi-reducibility is proposed by introducing witnesses. Furthermore, an algorithm for constructingwitnessed test sets of left-linear rewrite systems has been designed.Compared with the standard test set approach presented by Kapur,Narendran and Zhang, the method proposed generates test sets of smallersize and therefore has more efficient applications.