cs.LGNov 14, 2026

Random Cut Forests, Games and Diffusion over Approximately Nested Anisotropic Local Geometry

Authors: Sudipto Guha

Abstract

Just as the data in a dynamic stream changes, questions asked of the stream also change in intent: what to hold constant, which counterfactuals to consider, and so forth. Energy-based learning has been celebrated for its uniform approach to losses and estimation, but interpretability remains challenging. Tree-based methods, on the other hand, offer high interpretability but often rely on bespoke, disjointed estimators. Neither paradigm readily supports changing questions on streaming data. In this paper we take a step towards combining energy, interpretability, and streaming. Random cut forests retain an evolving geometry of the data. We study this geometry as the basis for diffusion dynamics, prediction, explanation, and games. We show that several existing scores are escape probabilities of random walks on the trees. The induced affinity is realized exactly by a sparse electrical network on each tree, giving a single energy calculus, a Hamiltonian, maintained along one path per update. This connects an estimate, its supporting evidence, and the response to intervention through the same boxes, gaps, masses, and paths. Different questions correspond to different clamp decisions on the energy. Fixing observed values gives harmonic prediction with Gaussian uncertainty. Fixing a partition gives normalized cuts whose cost is attributed exactly to oriented faces. Releasing clamps gives coalition games, in which collusive displacement measures the field response. With noise, the same energy gives diffusion dynamics whose relaxation rates are read from the boxes. Axis-parallel cuts localize at a rate set by affine rather than ambient dimension, and this control passes to the averaged energy. Across a forest the boxes are only approximately nested; common reference observations align the trees. A rotating star with added noise illustrates the measurements.

Figures & tables

Explore similar work

May 1, 2026

Trees to Flows and Back: Unifying Decision Trees and Diffusion Models

Decision trees and diffusion models are ostensibly disparate model classes, one discrete and hierarchical, the other continuous and dynamic. This work unifies the two by establishing a crisp mathematical correspondence between hierarchical decision trees and diffusion processes in appropriate limiting regimes. Our unification reveals a shared optimization principle: Global Trajectory Score Matching (GTSM), for which gradient boosting (in an idealized version) is asymptotically optimal. We underscore the conceptual value of our work through two key practical instantiations: \treeflow, which achieves competitive generation quality on tabular data with higher fidelity and a 2\times computational speedup, and \dsmtree, a novel distillation method that transfers hierarchical decision logic into neural networks, matching teacher performance within 2% on many benchmarks.
May 29, 2026

Correcting Split Selection in Online Decision Trees via Anytime-Valid Inference

Bagging-based ensembles, most notably Adaptive Random Forests, are among the strongest performers for learning from data streams. A common denominator across these methods is their reliance on Hoeffding Trees as base learners, which grow decision trees incrementally by testing whether a candidate split is significantly better than its alternatives using concentration inequalities. Despite their empirical success, existing variants lack valid statistical guarantees. Current analyses rely on fixed-sample concentration bounds, while split decisions are made using data-dependent stopping rules, which invalidates their guarantees and can drive the probabilty of incorrect splits to one. We introduce a principled alternative based on anytime-valid inference. Our method provides: (i) anytime-valid control of false splits under arbitrary data streams, including non-stationary settings; (ii) finite commitment time under a predictive advantage; and (iii) under stationary i.i.d. data, risk is monotone decreasing and strictly improves at every split. Empirically, we evaluate both standalone trees and their use within Adaptive Random Forests on non-stationary streams. Our method improves performance while producing substantially smaller trees.
May 28, 2026

Reasoning with Sampling: Cutting at Decision Points

Frontier reasoning models are produced by post-training base language models with reinforcement learning. Recent work has challenged this by showing that sampling from a sharpened version of the base model's distribution, a so-called power distribution, elicits comparable reasoning without additional training, curated datasets, or verifiers. However, making this method practical requires efficiently sampling from the power distribution. A sampler needs to "mix" to the power distribution, which necessitates moving between modes of the target distribution; intuitively, e.g., trying different reasoning strategies. The samplers proposed in prior works repeatedly select a "cut" position in the current reasoning trace uniformly at random and resample the suffix from that position onward. However, reasoning traces typically contain a few consequential decisions (e.g., the choice of proof strategy or algorithm), and we observe that a uniformly chosen cut tends to rewrite local details rather than revisit decision points. We introduce an algorithm (Entropy-Cut Metropolis-Hastings) that uses the base model's next-token entropy as a proxy to identify key decision points and resample from those positions. We empirically verify that entropy jumps are a useful proxy for decision points and, in a stylized model of reasoning, prove that our method's mixing time scales with the number of decisions in a trace rather than with the number of tokens, which can be much larger. Across MATH500, HumanEval, GPQA Diamond, and AIME26, our method consistently improves over baselines and RL-trained models, including best-of-N at the same token budget.