Methods and apparatus for verifying spoken passwords and sentences with small decoder complexity requirements. A proposed method permits the verbal verification of a spoken password sentence without computationally extensive large-vocabulary decoding. A decoder preferably uses target baseforms (representing the original content to be verified) together with a special set of competing simplified baseforms that may be easily constructed using finite-state grammars (FSG).