We consider the small sample composite hypothesis testing problem, where the number of samples n is smaller than the size of the alphabet m. A suitable model for analysis is the high-dimensional model in which both n and m tend to infinity, and n = o(m). We propose a new performance criterion based on large deviation analysis, which generalizes the classical error exponent applicable for large sample problems (in which m = O(n)). The results are: (i) The best achievable probability of error Pe decays as −log(P e ) = (n2/m)(1 + o(1))J for some J > 0, shown by upper and lower bounds. (ii) A coincidence-based test has non-zero generalized error exponent J, and is optimal in the generalized error exponent of missed detection. (iii) The widely-used Pearson's chi-square test has a zero generalized error exponent. (iv) The contributions (i)-(iii) are established under the assumption that the null hypothesis is uniform. For the non-uniform case, we propose a new test with nonzero generalized error exponent.