Reverse Engineering RL-Induced Traversal: Formalizing and Simulating Hierarchical Search in LLMs

Research Question: What formal computational principles underlie the procedural search improvements induced by RL in LLMs, and how do these relate to classic hierarchical search algorithms?

Hypothesis: RL tunes LLMs to approximate an efficient hierarchical search policy akin to breadth-first or depth-first search, but with model-specific biases and shortcuts.

Experiment Plan: Develop a formal model of hierarchical search (e.g., Markov Decision Process or tree search algorithm). Simulate various search strategies on the same hierarchies used in LLM experiments. Analyze LLM internal activations and output sequences during traversal tasks; fit these to the formal models. Identify where and how the LLM’s behavior deviates from “classic” search, and relate deviations to RL-induced changes.

References: ['Zhang, R., Kaniselvan, M., & Mireshghallah, N. (2025). Reinforcement Learning Improves Traversal of Hierarchical Knowledge in LLMs.', 'Li, D., Zhang, T., Huang, L., Wang, C., He, X., & Xue, H. (2024). KEHRL: Learning Knowledge-Enhanced Language Representations with Hierarchical Reinforcement Learning. International Conference on Language Resources and Evaluation.', 'Wang, D., Li, B., Song, B., Chen, C., & Yu, F. (2024). HSMH: A Hierarchical Sequence Multi-Hop Reasoning Model With Reinforcement Learning. IEEE Transactions on Knowledge and Data Engineering.']