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

arXiv: https://arxiv.org/abs/2605.09542 · HTML: https://mlsanity.com/paper/2605.09542/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 32 references that are in the map.
- First posted on arXiv 10 May 2026.

## Builds on (most cited first, 11 of 11)

- [Lost in the Middle: How Language Models Use Long Contexts](https://mlsanity.com/paper/2307.03172/) (2023)
- [GPQA: A Graduate-Level Google-Proof Q&A Benchmark](https://mlsanity.com/paper/2311.12022/) (2023)
- [MMLU-Pro: A More Robust and Challenging Multi-Task Language Understanding Benchmark](https://mlsanity.com/paper/2406.01574/) (2024)
- [A Survey on Hallucination in Large Language Models: Principles, Taxonomy, Challenges, and Open Questions](https://mlsanity.com/paper/2311.05232/) (2023)
- [Faith and Fate: Limits of Transformers on Compositionality](https://mlsanity.com/paper/2305.18654/) (2023)
- [Is ChatGPT Good at Search? Investigating Large Language Models as Re-Ranking Agents](https://mlsanity.com/paper/2304.09542/) (2023)
- [Large Language Models are Effective Text Rankers with Pairwise Ranking Prompting](https://mlsanity.com/paper/2306.17563/) (2023)
- [Go for a Walk and Arrive at the Answer: Reasoning Over Paths in Knowledge Bases using Reinforcement Learning](https://mlsanity.com/paper/1711.05851/) (2017)
- [Neural Multi-Hop Reasoning With Logical Rules on Biomedical Knowledge Graphs](https://mlsanity.com/paper/2103.10367/) (2021)
- [Rewarding Explainability in Drug Repurposing with Knowledge Graphs](https://mlsanity.com/paper/2509.02276/) (2025)
- [Likert or Not: LLM Absolute Relevance Judgments on Fine-Grained Ordinal Scales](https://mlsanity.com/paper/2505.19334/) (2025)

## Built on by (most cited first, 1 of 1)

- [Repair Before Reinforce: Context-Augmented Knowledge Graph Reasoning for Multi-Hop Question Answering](https://mlsanity.com/paper/2609.12230/) (2026)

## Abstract (arXiv)

Extracting multi-step explanations from knowledge graphs poses a combinatorial challenge requiring both heuristic guidance (as candidates proliferate with depth) and credit assignment (as path quality emerges over extended sequences). Frontier LLMs, strong on knowledge/reasoning benchmarks, offer a compelling source of such heuristics, yet their knowledge comes sans guarantees and compositional performance degrades as chains lengthen. We thus present TESSERA, a 3-part neuro-symbolic framework that uses LLMs in a circumscribed role: for local discriminative judgement rather than autonomous multi-step generation; the knowledge graph then defines the hypothesis space enforcing hard structural constraints, and MCTS coordinates the long-horizon search with principled credit assignment via backpropagation. LLMs perform dual roles as a prior policy biasing exploration and a comparative state evaluator supplying reward signals. Evaluation on drug mechanism elucidation across two complementary knowledge graphs demonstrates fidelity to curated biology while surfacing coherent alternative mechanisms, with ablations confirming discriminative contribution from both LLM components. Beyond its current application, our framework offers a general paradigm for compositional reasoning over structured knowledge.