The Trefftz method, endowing with polynomial type trial solutions of the high-dimensional heat conduction equation in an arbitrary simply-connected domain, is a cheap boundary-type meshless method to solve the high-dimensional backward heat conduction problem (BHCP), which is well-known a highly ill-posed problem. For solving the BHCP we develop a multiple/scale/direction polynomial Trefftz method (MSDPTM), of which the directions are uniformly distributed on a hyper-sphere and the scales are determined in advance by the collocation points on boundary. A post-conditioner for the resultant linear system is introduced by using the derived multiple-scale, and then use the conjugate gradient method (CGM) to solve the post-conditioned linear system, of which the expansion coefficients are determined fast. The MSDPTM can find the missing initial data very well, with several two- and three-dimensional numerical examples of the BHCP to evaluate the performance. Although under a very large relative noise from 30% to 80% with the maximum absolute noisy error being 2.17, the presented method still recovers the unknown initial temperature quite accurately. It is worthy to notice that the CPU time does not exceed two seconds for 2D examples and seven seconds for 3D examples. (C) 2015 Elsevier Ltd. All rights reserved.