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

Researchers introduce TESSERA, a neuro-symbolic framework that combines Large Language Models with Monte Carlo Tree Search to extract multi-step explanations from knowledge graphs, specifically for drug-disease mechanism discovery. The system uses LLMs for local judgments rather than autonomous generation, enforcing structural constraints through knowledge graphs while employing MCTS for principled credit assignment across extended reasoning chains.

TESSERA addresses a fundamental challenge in AI reasoning: generating reliable, multi-step explanations from complex structured data without succumbing to hallucination or compositional degradation. The framework represents a pragmatic approach to neuro-symbolic AI that respects the complementary strengths of neural and symbolic systems. Rather than relying on LLMs for end-to-end generation—where errors compound across chains—TESSERA constrains them to local discriminative tasks where they excel, while delegating global search coordination to principled MCTS algorithms with formal credit assignment properties. This architectural choice directly addresses known LLM limitations in maintaining consistency over extended reasoning sequences.

The work builds on a growing recognition that frontier language models require structural scaffolding to produce reliable outputs in knowledge-intensive domains. Drug mechanism elucidation is particularly suited for this approach, as biomedical knowledge graphs provide extensive structured evidence and the consequences of explanation errors carry real stakes. The dual role of LLMs—as exploration priors and reward evaluators—leverages their pattern recognition capabilities without demanding infallible autonomous reasoning.

Beyond pharmaceutical applications, TESSERA's framework offers broader implications for AI systems requiring compositional reasoning over structured knowledge. The approach demonstrates viability for knowledge graph traversal problems spanning biology, materials science, and other empirically grounded domains. For the AI industry, this work reinforces the trend toward hybrid architectures that view LLMs as components within larger reasoning systems rather than standalone solutions. The emphasis on fidelity to curated biology suggests commercial applications in drug discovery pipelines where explainability and accuracy are non-negotiable.

• →TESSERA combines LLMs with Monte Carlo Tree Search to extract multi-step mechanistic explanations while enforcing knowledge graph constraints and principled credit assignment.
• →The framework restricts LLMs to local discriminative judgments rather than autonomous multi-step generation, mitigating hallucination risks in extended reasoning chains.
• →Dual LLM roles—prior policy for exploration and state evaluator for rewards—enable efficient search over combinatorially large hypothesis spaces in biomedical knowledge graphs.
• →Evaluation on drug mechanism elucidation demonstrates both fidelity to curated biology and discovery of coherent alternative mechanisms, with ablations confirming both LLM components contribute meaningfully.
• →The approach generalizes beyond drug discovery to any domain requiring compositional reasoning over structured knowledge with formal guarantees.