Many problems in AI, e.g., inference in Bayes Nets, MPE, MAXSAT, #SAT, can be represented as a computation over a set of local functions. The sets of variables these local functions depend on form a graph, and many of these problems can be solved by performing dynamic programming on a tree decomposition of this graph. The well known Variable Elimination (VE) algorithm is one example of this approach. The locality of the functions also means that by instantiating only a treewidth number of variables the remaining reduced functions become disjoint; that is, the problem decomposes. This can be exploited in a divide and conquer style algorithms that can achieve the same worst case complexity as VE. In this talk, however, I will describe how a simple caching scheme can allow standard backtracking search to also exploit decomposition and to also achieve the same worst case bounds as these previous algorithms. Backtracking with caching also has some structural advantages over previous algorithms that allow it to display superior performance on some problems.