I will present a new algorithm to compute the interlace polynomial using tree decompositions. This algorithm is not based on MSOL, but computes the interlace polynomial directly. The running time is 2^O(k^2)*n, where n is the number of vertices of the input graph G and k is the width of a tree decomposition of G.