Many personalization systems keep a small model of how a user's wants depend on one another. For example, a traveller's budget drives whether they will accept a distant hotel, and that in turn drives whether transit access matters to them. Such a model can be written as a directed acyclic graph (a DAG, a network of arrows with no loops), learned from interaction logs by greedy score-based search that adds, deletes, or reverses one arrow at a time. When the user's preferences drift, the natural engineering move is to keep the current graph and let the same greedy search update it as new data arrives. We argue this move fails in a specific and predictable way. A drift that reverses a chain of dependencies cannot be reached by one-arrow edits without passing through graphs that score worse, so the warm-started search stays stuck on the old structure. The obvious fix is to restart from scratch on recent data only, but that throws away most of the evidence about the parts of the graph that did not change.
This note proposes to name that tradeoff between keeping data and getting trapped, and to escape it. The method detects which parts of the graph have stopped fitting recent data. It then runs an exact or lookahead search only over that neighbourhood, and keeps the rest of the graph, together with its full data history, frozen. If this works, a system can track a drifting preference structure with the statistical power of the long history and the escape ability of a fresh global search, at a small fraction of the cost of either.
Core Claim
Greedy structure learning under drift has two failure modes that no single greedy strategy avoids together. Warm-started search keeps its data but inherits the old graph's basin of attraction. Cold-restarted search escapes the basin but is starved of data. The first failure is well documented for stationary data. Improving Causal Discovery By Optimal Bayesian Network Learning shows a "precision-saturation" effect, in which more samples reinforce early greedy mistakes instead of correcting them. Permutation-based Causal Inference Algorithms with Interventions notes that searching directly over DAGs can break consistency even with infinite data. Our claim is that drift turns this phenomenon from an occasional pathology into the default. The old graph is a well-supported optimum of any score that still gives weight to old data, so a warm start sits at exactly the wrong local optimum.
We make two predictions that can be checked. First, the warm-started tracker's error after a drift should grow with the reversal length of the drift, meaning how many arrows along a path must flip together. It should not grow much with the raw number of changed arrows. Second, because typical preference drift is local (a few dependencies change), a search that is exact only on the changed region should dominate the whole error-versus-window-length curve traced by cold restarts.
Research Program
The tracked object is a DAG $G$ over preference variables with a decomposable score, meaning the total is a sum of per-variable "family" terms, one for each variable and its parents. We use a discounted version of the Bayesian Information Criterion (BIC, a fit score that penalizes extra arrows):
$$S_\gamma(G) = \sum_{j} s_\gamma\big(X_j, \mathrm{Pa}_G(X_j)\big),$$
where $X_j$ is the $j$-th preference variable, $\mathrm{Pa}_G(X_j)$ its parents in $G$, and $s_\gamma$ is the family BIC computed from sufficient statistics in which a sample from time $t$ gets weight $\gamma^{T-t}$ at current time $T$. This discounting is the same device Right Now, Wrong Then: Non-Stationary Direct Preference Optimization under Preference Drift applies to preference-pair losses. Here it is moved to the structure score, and it serves as a baseline ingredient rather than the contribution.
The method has three steps.
Detect. Decomposability allows a per-family check. Family $j$ is flagged when, on a short recent window, its current parent set is beaten by the best alternative parent set of bounded size by a likelihood-ratio margin $\tau$. Because this is a local test, it can fire on a family whose global score contribution looks fine.
Localize. The flagged region $R$ is the union of the Markov blankets of the flagged variables (each variable's parents, children, and children's other parents), estimated with the Max-Min Markov Blanket skeleton step. That step is borrowed from Triplet A* in Improving Causal Discovery By Optimal Bayesian Network Learning.
Re-search. Inside $R$ we solve the family-score maximization exactly with A* branch-and-bound, holding all arrows outside $R$ fixed and adding the acyclicity constraints they impose. Families inside $R$ are scored on recent-weighted data. Families outside $R$ keep their long-history statistics. When $R$ is too large for exact search (roughly above 20 variables), we fall back to Monte Carlo tree search over arrow edits restricted to $R$. This reuses the incremental cycle detection of CD-UCT from Tree search in DAG space with model-based reinforcement learning for causal discovery, which reports up to 13.25× faster cycle checks at 50 nodes.
The analytic part of the program is a short construction showing the first prediction. We will build a family of linear-Gaussian structures in which reversing a directed path of length $k$ yields a new optimum, and every single-arrow edit sequence from the old graph passes through graphs of lower discounted score, with the gap growing in $k$ for fixed $\gamma$. This formalizes the "horizon effect" the file attributes to BIC. It explains why warm-started greedy search, and also tempered variants such as Less Greedy Equivalence Search, which skips insertions that contradict conditional-independence tests, will not cross such barriers: skipping bad insertions does not create the multi-arrow moves needed.
Preference drift is the application regime, not the mechanism, and the choice matters for design. The file motivates it from several angles. AcCoRD: Evaluating User-Agent Collaboration Under Realistic User Preference Dynamics finds that "triggered" preferences, which appear only after the agent shows relevant items, are satisfied at rates as low as 0.09. In our terms these are new arrows that switch on mid-session. Breaking Feedback Loops in Recommender Systems with Causal Inference shows that recommendations act as interventions that reshape user responses, which is one source of the structural change we track. Evaluating Rule-based Programming and ReinforcementLearning for Personalising an Intelligent System observes that users revise their preferences on seeing outputs, and that they want transparent rule-like models. A sparse DAG is such a model.
Our work differs from the closest connecting papers in what it assumes. Causal Preference Elicitation learns DAGs with a human in the loop but assumes the expert's knowledge is static. Non-Stationary Structural Causal Bandits plans non-myopically over a time-unrolled graph but assumes that graph is known. We learn a graph that is itself changing.
Baselines
The naive reference point is warm-started GES with discounting: Greedy Equivalence Search continued from the previous graph on $\gamma$-weighted statistics, which is what a practitioner would deploy. It isolates the trap. The second baseline is cold-restart GES and LGES on a sliding window $W$, rerun at every checkpoint. It isolates data starvation. We sweep $W$ and report the whole curve, not one setting.
The strongest existing competitor is full-graph lookahead restart with CD-UCT from Tree search in DAG space with model-based reinforcement learning for causal discovery, run on discounted statistics at each checkpoint. It escapes local optima globally and reports beating greedy search and RL-BIC with up to 100× fewer score evaluations than RL-BIC. For small graphs we add global Triplet A* restarts as an exact upper reference. No reported result on Lacuna exists for any of these methods tracking structure under drift. The nearest reported numbers are stationary. LGES reports roughly 50% lower SHD (Structural Hamming Distance, the count of wrong, missing, or extra arrows) than GES at 150+ variables. CD-UCT reports no numeric SHD in the file.
All methods share the same data streams, the same score, the same $\gamma$ grid, and an equal budget of score evaluations per checkpoint. Hyperparameters ($\gamma$, $W$, $\tau$, MCTS iterations) are tuned on held-out drift schedules with the same number of trials each.
Two ablations isolate the key ingredient. Localized greedy keeps our detect-and-localize steps but runs greedy search inside $R$, testing whether exactness or lookahead matters. Oracle region hands the method the true changed families, bounding the cost of detection errors.
Beating the baselines means lower time-averaged SHD than every point on the cold-restart $W$ curve and lower than warm start, at a score-evaluation budget no larger than CD-UCT's. It also means matching CD-UCT's post-drift SHD at a fraction of its evaluations.
Why not just…?
Why not just restart from scratch on a recent window? This is the real threat. GES from an empty graph is not burdened by the old basin, and with enough recent data it may be enough. Our answer is a measurement, not an argument. If drift is local, cold restart pays for re-estimating unchanged families from a short window, and its SHD on those families should rise as $W$ shrinks. If the best-tuned $W$ matches our method on both changed and unchanged families, the proposal's core claim fails and we will report it as such.
Why not just discount old data more aggressively and keep warm-starting? Discounting reshapes the score but does not add moves. Our construction predicts that the barrier around the old graph persists for any $\gamma$ that keeps useful history. The experiment sweeps $\gamma$ and $k$ jointly. If some $\gamma$ lets warm start escape length-$k$ reversals without collapsing to cold-restart behaviour, the prediction is refuted. NS-DPO's own reliance on a pre-tuned $\gamma$ suggests no single value will serve both sudden and gradual drift.
Why not just run a global non-greedy search every step, such as CD-UCT, a continuous relaxation like Gradient-Based Neural DAG Learning, or exact integer programming as in Integer Programming Based Methods and Heuristics for Causal Graph Learning? These methods solve the trap but not the cost, and the file notes that exact integer programming and A* scale poorly beyond moderate sizes. Continuous methods retrain on stationary batches, and a warm-started gradient run may inherit the old basin just as greedy search does. We include CD-UCT restarts and a warm-started GraN-DAG run. We expect comparable accuracy to ours only at far larger per-checkpoint compute, and we will report the evaluation counts that settle this.
Proposed Experiments
The main testbed is synthetic Erdős–Rényi graphs with 20 to 150 variables, the family used by LGES and CD-UCT, carrying scheduled drifts of controlled type. The drift types are arrow additions, deletions, parent swaps, and path reversals of length $k \in \{1,\dots,5\}$, each applied suddenly or gradually. The discrete Bayesian networks Asia, Child, and Insurance receive the same injected changes to test discrete scores. On the 11-variable Sachs signaling network we build a semi-real stream by concatenating data segments with mechanism changes imposed on a few known edges, and we check the result against the observational-to-refined SHD scale that Causal Preference Elicitation reports there, about 14 edges gained with 40 queries.
For the preference application we build simulated users from AcCoRD-Travel's preference dimensions, about 11 per scenario. Each simulated user has a preference DAG, and triggered preferences are modelled as arrows that activate after exposure. We score the fraction of the user's current preferences that a recommender built on the tracked graph satisfies. The published reference is that frontier agents reach a perfect-outcome rate below 30% and triggered-preference satisfaction as low as 0.09, though those numbers come from LLM agents and are context rather than a head-to-head.
The metrics are SHD over time and its area under the curve, SHD split into changed and unchanged families, detection delay, and score evaluations and wall-clock time per checkpoint.
Three results would settle the claim. First, warm-start SHD after drift should rise with reversal length $k$ at a fixed number of changed arrows. If it tracks only the number of changed arrows, the trap mechanism is wrong. Second, our method should sit below the full cold-restart error-versus-$W$ curve, winning on unchanged families without losing on changed ones. Third, the localized-greedy ablation should fail on $k \ge 2$ reversals where the exact local search succeeds. That result would show that non-greedy search inside the flagged region, not localization alone, is the ingredient doing the work.
References
- Improving Causal Discovery By Optimal Bayesian Network Learning
- Permutation-based Causal Inference Algorithms with Interventions
- Right Now, Wrong Then: Non-Stationary Direct Preference Optimization under Preference Drift
- Tree Search in DAG Space with Model-based Reinforcement Learning for Causal Discovery
- Less Greedy Equivalence Search
- AcCoRD: Evaluating User-Agent Collaboration Under Realistic User Preference Dynamics
- Breaking Feedback Loops in Recommender Systems with Causal Inference
- Evaluating Rule-based Programming and ReinforcementLearning for Personalising an Intelligent System
- Causal Preference Elicitation
- Non-Stationary Structural Causal Bandits
- Gradient-Based Neural DAG Learning
- Integer Programming Based Methods and Heuristics for Causal Graph Learning