LLM-Guided Monte Carlo Tree Search over Knowledge Graphs: Composing Mechanistic Explanations for Drug–Disease Pairs

1 Introduction

Computational scientific discovery has engaged researchers for over half a century [Simon, 1966], often viewed as a heuristic search problem akin to planning or game-playing, but with the attendant expectation that its outputs constitute not merely predictions but explanations, expressed in formalisms amenable to inspection, challenge, and communication [Langley, 2024]. Systems medicine exemplifies this: in drug repurposing, for instance, a putative statistical association between a drug and a disease is far more compelling when accompanied by a mechanistic account of how the intervention propagates, through biological intermediates, to produce its therapeutic effect.

Knowledge graphs, as explicit symbolic representations of domain knowledge, offer a natural substrate for such explanations [Sosa and Altman, 2022; d'Aquin, 2025]. Extracting these, however, poses a combinatorial challenge as candidates proliferate with depth, precluding exhaustive enumeration. The problem is thus well framed as heuristic search, with background knowledge guiding exploration towards promising candidates [Langley, 2024].

Frontier large language models, strong on biomedical knowledge and reasoning benchmarks [Phan et al., 2025; Wang et al., 2024; Rein et al., 2023], present a compelling source of such guidance. Yet LLMs exhibit a kind of approximate omniscience: broad coverage of domain knowledge, but without guarantees of correctness [Kambhampati, 2023; Kambhampati et al., 2024], subject to hallucinations and confabulations [Huang et al., 2025]. Empirically, compositional performance degrades systematically as task complexity increases: models succeed at single / few-step judgements but fail to compose them reliably as errors compound [Dziri et al., 2023]. Together, these recommend a circumscribed role: LLMs as sources of local discriminative judgement, not autonomous generators of extended reasoning chains.

Assembling these local judgements into a multi-step explanation requires credit assignment: determining which early choices contribute to eventual explanation quality. Monte Carlo Tree Search provides a principled framework for this, accumulating evidence across trajectories and backpropagating credit over extended sequences. This yields a threepillar framework, where the knowledge graph defines the hypothesis space and enforces hard structural constraints, the LLM provides soft, local semantic judgement, and MCTS coordinates long-horizon search. We refer to this framework as TESSERA (Tree-search for Explanation Synthesis via Semantic Evaluation and Ranked Actions). 1

Our contributions include: (i) a neuro-symbolic framework coupling MCTS with LLM-derived heuristics for extracting mechanistic explanations from biomedical knowledge graphs; (ii) a listwise prior policy (for exploration bias) that scales to large action sets through batched evaluation, exploiting LLMs' strength at relative judgement while avoiding long-context degradation; (iii) a comparative state evaluator (for reward signal) that scores partial paths against a depth-bound competitor set, using token-level probabilities for uncertainty-aware estimates and conditioning on accepted paths to assess marginal contribution; and (iv) evaluation on two complementary substrates: DrugMechDB (allowing deterministic evaluation against curated ground-truth), and the Multi-scale Interactome (enabling high-branching search, but without ground-truth, motivating an LLM-as-judge protocol, which we control and validate for reliability).

1 Code and supplementary material available at https://github. com/RishabhJakhar/tessera.

2 RelatedWork

We situate our work relative to two strands of prior research: (i) Post-hoc attribution, with methods such as Kelpie [Rossi et al., 2022], adversarial explanations [Betz et al., 2022], and GNNExplainer [Ying et al., 2019], produces saliencystyle explanations that highlight influential inputs (triples, subgraphs, or feature subsets), but often lack key explanation desiderata (e.g., coherence, parsimony); an inadequacy emphasised in broader critiques of attribution [Chou et al., 2022] and carried over to link-prediction explainability [Nunes et al., 2025]. (ii) Path-based reasoning explains predictions through multi-hop traversals that serve as interpretable traces. The dominant paradigm casts traversal as RL-based sequential decision-making: MINERVA [Das et al., 2018] rewards terminal arrival alone, with subsequent work progressively shaping rewards towards explanatory virtues with metapath compliance (PoLo; [Liu et al., 2021]), phenotype associations (CoCo; [Stork et al., 2023]), and degree-based specificity heuristics (REx; [Nunes et al., 2025]). REx goes furthest, explicitly invoking explanatory qualities-fidelity, relevance, simplicity-yet still relies on structural proxies optimised through fixed-length rollouts (typically 3-4 hops). Outside RL, methods like DrugCORpath [Song et al., 2025] incorporate LLM-derived embeddings of precomputed paths with subsequent clustering and classification, but remain constrained to certain metapaths at fixed, short lengths (2-3 hops). Our approach differs by replacing the hand-crafted proxies with a direct semantic evaluation via LLMs, and embedding this signal within a search algorithm (rather than policy rollouts), enabling variable depth over longer horizons. We view these as complementary: proxy rewards and policy rollouts offer efficiency; semantic evaluation and combinatorial search offer richer assessment and longer horizons, but at attendant cost.

3 Methodology

3.1 Problem Setting

Given a graph G as substrate, we formulate the problem as one of extracting an explanatory subgraph g(d, z) that accounts for the therapeutic effect of a drug d on a target disease z. We perform a lookahead search on G: starting from d and conditioned on z, the search traverses nodes and relations to uncover plausible mechanistic pathways.

The substrate is a directed, typed, multi-relational knowledge graph G=(V,R, E), where V are entity nodes, R relation types, and E⊆V×R×V the set of typed edges.

A search state s∈S is encoded as s=(u, H, z), where u∈V is the current node in G, H∈E ∗ is the ordered path traversed to reach u, and z∈V is the target node. V (H) denotes the nodes appearing along H. For any given search, z remains fixed. Since states are path-dependent, visiting the same graph node via different paths corresponds to distinct search states. The legal actions at state s, A(s), form a subset of the outgoing edges of u and are determined in two stages. The first is a filtering on the top-k neighbours ranked by a personalised PageRank score pprz(v), with a one-hot personalisation vector encoding the target disease z:

The second is an augmentation to k, ensuring adequate representation of key node types: for a designated set T ⊆V and target proportion λ∈(0, 1], if nodes in T comprise less than proportion λ of the targets in Ak(s), additional actions with v∈T are injected from the ranked tail, up to an augmentation budget τ . Writing A+τ (s) for the resulting set of injected actions, the final action set is

Since an action represents the tuple (r, v), the transition function is deterministic: executing (r, v) in s=(u,H, z) yields afterstate s′=(v,H++(u, r, v), z).

3.2 Search Algorithm

We use Monte Carlo Tree Search (MCTS), guided by an LLM-based prior policy πLLM(·|s) to bias exploration towards high-probability actions and a comparative, path-aware state evaluation v(sL) to assign leaf values.

The search tree consists of states s as nodes, with outgoing edges (s,a) for all a∈A(s). Each edge stores statistics: visit count N(s,a), cumulative action value W(s,a), mean action value Q(s,a), and a prior probability P(s, a):=πLLM(a|s). Search starts at root s0=(d,∅,z), and evolves under a preset simulation budget T. Each simulation cycles through 4 phases:

Selection. Starting at the root s0, the tree is traversed until a leaf sL is reached. At each step t<L, an action at is chosen to maximise Q(st, a)+U(st, a) using PUCT [Rosin, 2011; Silver et al., 2017], with

We formulate the exploration coefficient cpuct=δ(d) · ϕ(N) to be depth and visit-count dependent, where

Here d is the depth and N the total visit-count of the parent state st. δ(d) decays and hence tempers exploration as depth increases, while ϕ(N) provides an early-visit exploration bonus that vanishes as st gets more visits.

Evaluation. On reaching sL=(u,H, z), we check for terminal states: if u=z (target state), the corresponding path history is admitted to the explanation set Hexp(s0), incoming edge (sL-1, aL-1) is closed and v(sL) is set to 0. If A(sL)=∅, i.e. a dead-end, again edge (sL-1, aL-1) is closed with v(sL)=0. For non-terminal states (excluding root s0), a scalar value v(sL)∈[-1, 1] is obtained from the LLMbased state evaluator (section 3.4).

Backpropagation. A backward pass is made for steps t≤L with updates: N(st, at)←N(st, at)+1, W(st, at)←W(st, at)+v(sL), and Q(st, at)← W(st,at) N(st,at) .

Expansion. Leaf sL is expanded unconditionally. Expansion is atomic over (i) materialising all successors in A(sL), and (ii) assigning priors P(sL,a)=πLLM(a|sL).

Upon search termination, subgraph g(d, z) is constructed as the edge union of all paths in Hexp(s0).

3.3 Prior Policy

We estimate πLLM(·|s) by pairing an LLM with a listwise sorting procedure. The design draws upon ranking algorithms in information retrieval and in particular, adapts the multipivot, n-ary quicksort of [Godfrey et al., 2025] for action scoring on graphs.

Four considerations shape the method: (i) as |A(s)| typically exceeds the quality cap for a single LLM pass, we use batched evaluations, with a batch size W≪|A(s)|, to avoid long-context degradation (e.g. position bias [Liu et al., 2024]), (ii) considering LLMs are stronger at relative than absolute judgements [Sun et al., 2023; Qin et al., 2024], we perform n-ary listwise comparisons, which batching naturally enables by presenting sets of actions jointly, (iii) to maximise throughput given LLM latency, batches are scored concurrently, with quicksort requiring only a light-weight final aggregation to scale batch-level judgements to a global distribution over A(s), and (iv) since MCTS is most sensitive to ordering of the top actions, the procedure progressively truncates the action set, concentrating computation on the distribution head. The full procedure is formalised in Algorithm 1 (Suppl. S3). We outline the key steps below:

Batch construction. The quicksort procedure runs over m passes, truncating the working action set AT over a linear schedule from T1=|A(s)| to Tm=W. In each pass, we select k=⌊W/2⌋ quantile-spaced pivots from AT using bootstrap scores βT 2 ; batches are then formed by adjoining this shared pivot set P (size k) to disjoint chunks of non-pivots (size ≤W-k).

LLMevaluation. Each batch B∈B is sent concurrently for LLM evaluation, with context including the parent leaf state s=(u,H, z), rubric Rprior, and for every action a=(r, v)∈B, the predicate r and node v attributes (identifier, type, label, and description). The model returns a rank πB(a) and score sB(a) per action, and on the final pass (i.e. for the top-W actions) a free-text justification to support interpretability 3 . A within-batch z-score standardisation yields ˜ sB(a).

Cross-batch aggregation & global order. Within each ordered batch, we identify the left and/or right pivot for every non-pivot. To obtain a transitive global order, we use the shared pivots as anchors: each pivot's rank and score are averaged across batches to form an anchor score S(p)=(-¯π(p), ¯ s(p)). We then extend S(·) to non-pivots by interpolating between their neighbouring pivots. Having established S(a) for every action, the final ordering is obtained by sorting lexicographically on (S(a), sB(a), β(a)).

2 for m=1, βT are the PageRank scores pprz (·), for m≥2 these are replaced with the batch-standardised LLM scores ˜ s(a).

3 Full prior policy prompt (template and example) in Suppl. S2.

Prior over actions. Given the final ordering, each action is assigned a utility that blends its normalised rank with its batch-standardised LLM score. We then map these utilities to probabilities via a temperature-controlled softmax.

3.4 State Evaluation

We perform a comparative evaluation of non-terminal leaves: each candidate is (i) assessed jointly with a small set of competing paths C(sL), and (ii) scored for its marginal contribution relative to the current explanation set Hexp.

Formally, consider the evaluation of a leaf state sL=(u,H,z) under root s0. Let L(s0) be the set of all active search states under s0, and Hs the root-to-s path, whose length |Hs| gives the depth of state s.

We aim to estimate the state value v(sL)∈[-1, 1] using an LLM-based evaluator by scoring its path history HsL against a depth-bound competitor set C(sL). Competitors are selected from a filtered pool F∆(sL), containing only states within a depth window ∆ ∈ N0 of sL :

C(sL) is then constructed as {sL} ∪ Top -k≺(F∆(sL)), where the ordering ≺ is lexicographic (descending) on two search-tree statistics:

Here N and P are per-edge visit counts and priors, and ε>0 is a small numerical clamp. If fewer than k competitors exist, all are included; if none exist, C(sL) = {sL}.

Each state s∈C(sL) is presented to the model through its path history H, with the prompt conditioned on the current explanation set Hexp(s0)={H:∃s=(z,H, z)}. The model evaluates each state using a predefined ordinal rubric Rstate-eval={ρmin<. . .<ρmax}⊂Z of integer labels. 4 Instead of using the output label directly, we obtain a continuous, uncertainty-aware score by taking a softmax over the rubric, using the model's token-level log-probabilities ℓ(ρi|s), to get a categorical probability distribution p(ρi|s). The resulting expected score, ∑i p(ρi|s) ρi, is normalised to get v(s) :

Non-LLM baseline (PPR-eval). As a deterministic baseline, we replace the LLM evaluator with a value computed from the target-conditioned PageRank scores pprz(·). Since pprz is not on the [-1, 1] scale used in PUCT backups, we apply a global rank calibration:

4 Full state-eval prompt (template and example) in Suppl. S4.

4 Experimental Setup

4.1 Substrate Graphs

DrugMechDB (DMDB). A merged supergraph of expertcurated per-indication mechanisms from DrugMechDB [Gonzalez-Cavazos et al., 2023], allowing evaluation against ground-truth mechanisms, thus decoupling algorithmic performance from substrate completeness. The resulting graph (5,128 nodes; 10,064 edges) spans multiple levels of biological organisation (molecular activities, pathways, anatomical structures, phenotypes) but offers only a small per-step action set (out-degree mean=2; p90=4; max=224) and minimal strong connectivity (largest strongly connected component (SCC) covering just 1% of nodes).

Multi-scale Interactome (MSI). To complement the above and probe performance under high-branching search, we evaluate on a large-scale biological knowledge graph adapted from the Multiscale Interactome [Ruiz et al., 2021] (adaptation details in Suppl. S5). The graph (29,698 nodes; 921,953 edges) encompasses 17,527 proteins, 9,798 biological functions, 1,550 drugs, and 821 diseases. Its dense proteinprotein interaction core and GO function hierarchy yield a much larger action space (out degree mean=31, p90=75, max=2,299). Moreover, the largest SCC spans 92% of nodes, indicating extensive bidirectional reachability and, as search states are path-dependent, a high path multiplicity, making search more challenging.

4.2 Language Models and Evaluation Set

For state evaluation during search, we experiment with SOTA non-reasoning models, GPT-4.1, DEEPSEEK-V3.1, and QWEN3-235B, on the premise that decomposition of search into local discriminative judgements at least partially obviates the need for reasoning models. The prior policy uses GPT-4.1 throughout; priors are cached per search state, enabling reuse across runs varying only the state-eval model. Model identifiers, inference settings, and algorithm hyperparameters are provided in Supplement S1.

Due to the computational costs associated with LLM inference (see Supplement S10 for a per-search LLM-call bound), we limit our evaluation to a representative sample of 15 drugdisease pairs. To ensure diversity across pharmacological and pathophysiological contexts, pairs were sampled across 12 MeSH disease categories and 9 ATC therapeutic classes, and further stratified by DMDB reference graph size (node/edge count). Full details in Supplement S6.

4.3 Evaluation Protocol

With DrugMechDB as substrate

The predicted subgraphs are compared deterministically against their curated (gold) counterparts along 4 axes (formal definitions in Suppl. S7).

Node Set Agreement (NSA). Set overlap between the curated and predicted nodes; order agnostic.

Edge Set Agreement (ESA@h). Edge agreement with hhop tolerance. A predicted edge (u→v) counts for precision if the curated graph connects (u⇝v) within ≤ h hops (i.e. shortcuts allowed). Conversely, a curated edge is covered

(counts for recall) if the prediction connects (u⇝v) within ≤ h hops (i.e. detours allowed). ESA@1 reduces to strict edge overlap.

Transitive-Closure Agreement (TCA). Path independent reachability among curated nodes. Let C⋆ and Cp be the transitive closures of the curated and predicted graphs over the curated node set V⋆ (i.e., C⋆,Cp ⊆ V⋆ × V⋆). Precision is the fraction of pairs in Cp that also lie in C⋆; recall is the fraction of pairs in C⋆ that also lie in Cp (predicted paths may traverse any, including non-curated, nodes). Captures agreement of the overall connectivity structure.

Exact Path Agreement (EPA). Overlap of exact drug to disease paths, evaluated only at path lengths present in the curated subgraph. EPA-IV (in-vocabulary) scores only those predicted paths that stay entirely within curated nodes, making precision more lenient to off-mechanism nodes and isolating verbatim fidelity to the curated narrative. EPA-OW (open-world) scores all predicted paths, yielding stricter precision and emphasizing parsimony by penalizing paths that route through non-curated nodes.

With the Multi-scale Interactome as substrate

In absence of ground-truth mechanisms to compare against, we implement a rubric-based LLM-as-judge protocol, using large language models augmented with expert-curated reference knowledge to score the predicted subgraphs. Each subgraph is judged on 5 dimensions-Biological Plausibility, Mechanistic Coherence, Contextual Specificity, Completeness, Conciseness-with each dimension rated on a 1-5 ordinal scale. As reference, we use the mechanism-of-action entries from DrugBank [Knox et al., 2024] and mechanism graphs from DrugMechDB to ground assessments (prompt and rubric in Suppl. S8).

To control for scoring variability, we employ a 3×3 design: (i) as LLMs can exhibit sensitivity to the presentation-order of graph elements, each judge evaluates 3 different serialisations (permutations) of the same graph, varying only in node/edge ordering; (ii) as different LLMs can exhibit different scoring behaviours, each subgraph is independently scored by 3 judges (GPT-4.1, DEEPSEEK-V3.1, QWEN3-235B). For each individual judgement, we extract the model's token probabilities over the five ordinal scale values k∈{1, . . ., 5}, renormalise them, and compute a probability-weighted expected rating E[s]= ∑k k p(k), yielding a continuous score in [1, 5]. The reported scores (per subgraph, dimension) are the mean of these expected ratings across all 9 permutation-judge combinations.

5 Results and Discussion

5.1 Evaluation on DrugMechDB

Aggregate performance

Table 1 reports scores pooled across state-eval LLMs. Nodelevel agreement is strong (NSA Micro P/R = 0.71/0.83). At edge level, ESA@1 (no hop slack) yields Micro P/R = 0.44/0.64. Allowing for a 1-hop tolerance (ESA@2) raises precision (0.44 to 0.50), while recall remains flat, indicating more 1-hop shortcuts than detours in the predicted subgraphs (examined further below). To investigate whether the modest precision at both h={1, 2} reflects outright spurious edges or plausible but uncurated mediators, a valid possibility given DMDB mechanisms are not exhaustive, we evaluated ESA while restricting edges to curated nodes only, which raised Micro P to 0.86 at h=1 and 0.99 at h=2, confirming the low rate of false positives (spurious edges) among curated nodes. Comparing reachability between curated node pairs in both graphs, TCA shows Micro P/R = 0.99/0.66, i.e. nearly all reachability claims made by the algorithm are valid, with the predictions missing about 34% of node pairs reachable in gold (primarily due to missing nodes). Finally, comparing complete drug→disease paths, EPA-IV has a Micro P of 0.84, implying the algorithm's traversal of curated nodes by and large follows gold paths. On the other hand, the significant drop in precision from EPA-IV to EPA-OW (0.84 to 0.27) underscores that predicted paths frequently incorporate nodes outside the curated mechanism.

Path-length and mediator analysis

Figure 1 decomposes the structural agreement. A. (PathLength Alignment) shows 73.1% of mass on the diagonal (matched hops) and 91.6% within |∆h|≤1. When not matched, paths tend to compress (above diagonal (shortcut) = 25.8%) rather than expand (detour = 1.1%), reinforcing why ESA precision improves with h=2 while recall stays flat; B. (Mediator Overlap) shows that for pairs requiring at least one mediator (h≥2 hops), predicted paths share on average 61.5% of their mediators with the corresponding gold paths (Jaccard overlap); the remainder includes substitutions involving both curated and uncurated nodes; C. (Mediation via Gold Nodes) shows that 74.1% of all predicted mediators are curated nodes, thus most mediation mass flows through curated biology even if exact routes differ.

The comparisons above show the algorithm largely identifies and connects the correct endpoints (high NSA/TCA), often via slightly shorter routes (Panel A) that nonetheless pass through curated biology (Panel C). It also shows good fidelity to curated paths (high EPA-IV precision) but can lack parsimony, proposing paths that traverse uncurated mediators (low EPA-OW precision). While understandable, given the search uses pre-trained LLMs with no task-specific supervision to match DMDB exactly, it does raise the question of whether these uncurated proposals constitute valid alternatives.

Qualitative analysis

We examined 15 subgraphs (GPT-4.1 state-eval) and identified recurring divergence patterns that nonetheless preserved biological coherence; per-pair annotations in Suppl. S9. Two dominant patterns appeared: (1) mechanistic elaboration, where predictions added upstream signaling pathways or regulatory detail (12/15 pairs; e.g., IL-1-mediated signaling pathway, adenylate cyclase-GPCR signaling, smooth mus- Figure 2: Predicted vs. Curated explanatory subgraph for Benazepril→Hypertensive Disorder. Legend: Common;

Curated only; Predicted only.

cle contraction), and (2) phenotype insertion, where predictions introduced explicit phenotypic states between biological processes and disease endpoints (9/15 pairs; e.g., Hypertension before Hypertensive disorder, joint swelling before Rheumatoid arthritis). Less frequent patterns included insertion/omission of chemical mediators (5/15; e.g., Dopamine, Aldosterone, Calcium) and addition/omission of anatomical/cellular context (4/15; e.g., lymphoid system, Leukocyte). In all cases, direction of effect and endpoint alignment were maintained. Figure 2 illustrates this on a representative pair, Benazepril-Hypertensive Disorder, which otherwise shows poor performance on exact path metrics (EPA-(IV & OW)=0). Both graphs share the canonical ACE inhibitor pharmacology (Benazepril → Benazeprilat → inhibits ACE → ↓Angiotensin II). The curated graph then routes through renal sodium absorption and water retention; the prediction instead captures an upstream regulator in the same axis, aldosterone secretion. The prediction also inserts an explicit phenotypic intermediate (Hypertension).

5.2 Evaluation on the Multi-scale Interactome

Following the LLM-as-judge protocol, let smg,d be the mean expected score across the 3x3 serialisation-judge combinations, for subgraph g, dimension d, and state evaluation model m∈ {GPT-4.1, DEEPSEEK-V3.1, QWEN3-235B}.

Reliability. To assess the reliability of the scoring process, we estimated intra- and inter-rater agreement using twoway mixed-effects, absolute-agreement, intraclass correlations (ICC) [Koo and Li, 2016]. Within-model agreement across the 3 serialisations was extremely high, ICC(3,3) = 0.989 (DEEPSEEK-V3.1), 0.987 (QWEN3-235B), and 0.981 (GPT-4.1), indicating practical invariance to permutation order. Likewise, agreement among the 3 judge LLMs, pooled across the 5 dimensions, was excellent: ICC(3,3)=0.946, 95% CI 0.93-0.96, justifying the use of smg,d as a reliable input.

Score distributions. Figure 3 shows the score distributions; included are two baselines that substitute the LLM-based state evaluation with PPR-eval. Baseline-1 retains the LLM prior; Baseline-2 pairs PPR-eval with a uniform prior over legal actions. Across the three LLM-based state-eval variants, Contextual Specificity was uniformly highest (medians spanning 4.23-4.51), followed by Biological Plausibility (3.723.87), Mechanistic Coherence (3.70-3.84), and Completeness (3.64-3.71); Conciseness was scored the lowest (2.34-2.47).

GPT-4.1 exhibited the tightest dispersion (IQR between 0.220.42); QWEN3-235B and DEEPSEEK-V3.1 showed wider spread (IQR between 0.54-1.10). While both baselines scored lower across all dimensions, Baseline-2 collapsed markedly, i.e. the exploration bias induced by the LLM-informed priors largely offsets PPR-eval; absent this, search tends to degenerate and disperse across the target-proximal space.

Cross-model comparison. We compute the difference between dimension-averaged scores, per drug-disease pair, for each state-eval model pair ∆g(m1, m2) = 1 5 ∑d (sm1 g,d -sm2 g,d ), and report (Table 2) the median (signed and absolute) and fraction of subgraphs scored within δ=1/4 and 1/2 of a scale point. Additionally, we measure rank concordance across subgraphs using Kendall's τb. Looking at the results, signed medians are near-zero; absolute medians span 0.13-0.16, small relative to the 1-5 rubric scale. Agreement within-δ further underscores the tight clustering, with DEEPSEEK-V3.1 accounting for most outliers. Rank concordance is also strong (τb=0.60-0.79), implying the models largely agree on which drug-disease pairs are easier or harder to explain, in part due to topological constraints of the shared substrate.

Structural convergence vs. Mechanistic pluralism. The patterns above imply strong cross-model agreement in the scored outcomes. For insight into the extent to which this reflects structural convergence versus distinct but equally defensible mechanisms, Figure 4 relates the absolute score difference (|∆g|) to structural divergence (edge-level Jaccard distance). We see a substantial structural spread (edgedistance IQRs between 0.37-0.41 across model pairs), pointing to significant mechanistic pluralism between the models, and, in turn, to the discriminative influence of the stateeval function on the search. Taking a per-quadrant view, using |∆g|=0.5 (half a scale step) and edge-distance =0.5 as thresholds, mass concentrates comparably between Q11 (40.0%, convergent mechanisms) and Q12 (49.0%, plural mechanisms). Notably, Q21 (structural convergence, score divergence) is empty across pairs, consistent with the high ICC values and a reliable subgraph evaluation methodology.

5.3 Ablation Study: Prior Policy

To assess the influence of the prior policy, we conduct an ablation on MSI, replacing πLLM(·|s) utilising GPT-4.1 with a uniform distribution over legal actions. Figure 5 shows, for each dimension d and state-eval model m, the mean of score differences ∆smg,d=sm,LLM g,d -sm,Uniform g,d across drug-disease pairs. Overall, the LLM-derived priors yield higher scores across rubric dimensions and state-eval models. The largest gains are on Conciseness, followed by Mechanistic Coherence, and smallest on Contextual Specificity, the latter indicative of both priors, bound by the same PPR-filtered neighbourhood, exploring similar regions of the substrate; larger differences in conciseness and coherence thus appear to reflect how paths are assembled within this overlapping region.

To examine this, we compute four structural metrics per subgraph: drug→disease path count (npath), mean path length (ℓpath), fraction of paths consisting solely of protein-protein interactions (fPPI-only), and ratio of biological-process to protein nodes (rBP:Prot). Table 3 reports averages across drugdisease pairs and state-eval models. To situate the analysis in the substrate's topology, consider that MSI is proteindominated: protein-protein interactions comprise 84% of all edges, and proteins outnumber biological-process nodes 17,527 to 9,798, predisposing any under-discriminative policy to proliferate protein-heavy subgraphs. The search under a uniform prior manifests this bias clearly, admitting on average 2.5× more paths per subgraph, that are substantially more protein-dominated ( ¯ fPPI-only: 0.39 vs. 0.13) and markedly less process-enriched (¯ rBP:Prot: 0.29 vs. 0.64). In contrast, πLLM biases search onto a smaller set of longer, process-mediated routes, suppressing many shorter, redundant, protein-only chains. Taken together with the score deltas in Figure 5, this partially explains why explanations become simultaneously more complete and more concise, and why mechanistic coherence improves despite the increase in average path length.

6 Conclusion

Extracting multi-step explanations from knowledge graphs requires heuristic guidance to manage combinatorial explosion and credit assignment to evaluate extended sequences. To address these, we present TESSERA, a neuro-symbolic decomposition wherein the knowledge graph bounds the hypothesis space, LLMs supply local semantic judgement, and MCTS coordinates search with principled backpropagation. Evaluation on drug mechanism elucidation demonstrates the approach recovers established biology while surfacing coherent alternatives. The decomposition applies broadly to compositional reasoning over structured knowledge.

A note on limitations. Our evaluation spanned 15 drugdisease pairs; while stratified for diversity, broader validation is needed. Additionally, a systematic hyperparameter optimisation remains non-trivial and unexplored given LLM inference costs and sparse ground-truth signal; current settings reflect manual tuning from pilot experiments.

Acknowledgments

This work was supported by the GENIUS Lab (Generative Enhanced Next-Generation Intelligent Understanding Systems), a collaboration between Delft University of Technology, Maastricht University, DSM-Firmenich, and KickstartAI, and by the NWO Long-Term Programme ROBUST, initiated by the Innovation Center for Artificial Intelligence (ICAI). We thank Dennis Soemers for helpful discussions on Monte Carlo Tree Search.