coarse-graining a point cloud with a kd-tree?

As my loyal reader knows, I am interested in fast-multipole method and whether it could be used to improve or speed machine-learning methods on graphs or spatial point clouds. Over the last months, I have learned about lots of limitations of FMMs, some of which we discuss here. I'm still interested! But when I last spoke with Leslie Greengard (Flatiron) he indicated that he felt like if you want to take FMMs scale up to very clustered data in high dimensions, maybe you have to think of truly adaptive trees (not the fixed tree of an FMM), like perhaps kd-trees. Today Soledad villar (JHU) and I discussed this idea. The question is: What could be proved about such an approach, or are there such approaches where you could get things like accuracy guarantees? The FMM has the beautiful property that you can compute the precision of your approximation, and dial up the order to get better precision.