K-Level Reasoning: Establishing Higher Order Beliefs in Large Language Models for Strategic Reasoning (2025)

Abstract: Strategic reasoning is a complex yet essential capability for intelligent agents. It requires Large Language Model (LLM) agents to adapt their strategies dynamically in multi-agent environments. Unlike static reasoning tasks, success in these contexts depends on anticipating other agents’ beliefs and actions while continuously adjusting strategies to achieve individual goals. LLMs and LLM agents often struggle with strategic reasoning due to the absence of a reasoning framework that enables them to dynamically infer others’ perspectives and adapt to changing environments. Inspired by the Level-K framework from game theory and behavioral economics, which extends reasoning from simple reactions to structured strategic depth, we propose a novel framework: “K-Level Reasoning with Large Language Models (K-R).” This framework employs recursive mechanisms to enable LLMs to achieve varying levels of strategic depth, allowing agents to form higher order beliefs—beliefs about others’ beliefs. We validate this framework through rigorous testing on four testbeds: two classical game theory problems and two social intelligence tasks. The results demonstrate the advantages of K-R in strategic reasoning. Our work presents the first recursive implementation of strategic depth in large language models (LLMs). It establishes a foundation for future research into theory of mind and strategic reasoning in LLMs.

## introduction strategic reasoning-decision-making in multiparticipant environments-presents unique challenges for large language models (llms) and llm agents @xcite . in these settings, * work was done when interning at microsoft research asia. † corresponding author. ## experiments: game theory to fairly compare the strategic reasoning capabilities of llms, we first adopt two widely used game theory settings. these controlled, well-defined game theory problems provide a robust assessment of llms' performance, with detailed setups outlined in appendix b. ## experiments: social intelligence we then evaluate k-r in two social intelligence benchmarks to assess its performance in more openended realistic scenarios. compared to the abstract and theoretical settings of game theory, these scenarios involve richer contextual backgrounds and complicated goal pursuits, which better demonstrate the value of llm-based agents in practical applications, such as in chatbots and strategic decision making. the agent who secures more utility upon reaching an agreement wins the game, and we calculated the win rate to assess the performance of different agents. ## batter nash equilibrium approximation with k-level reasoning to assess the impact of k-level reasoning on nash equilibrium, we conducted experiments testing the performance of llms at different k-levels in the prisoner's dilemma. the prisoner's dilemma is a classic concept in game theory that illustrates a paradoxical situation in which individuals acting in their own self-interest lead to a suboptimal outcome for everyone involved. it's often used to study decision-making in situations involving cooperation and competition. from ## conclusion this paper represents a significant stride in understanding and enhancing the strategic reasoning capabilities of llms. we propose "k-level reasoning with llms." this innovative approach leverages recursive mechanisms to achieve varying thinking level within llms, enabling them to engage in deeper strategic thinking. through extensive experiments, we validate the advantage offered by this method. it establishes a foundation for future research into theory of mind and strategic reasoning in llms.