LLMs for Game Theory: Entropy-Guided In-Context Learning and Adaptive CoT Reasoning

AI summary

Overview

• Research area: Natural Language Processing — specifically LLM reasoning, in-context learning, retrieval-augmented generation, and uncertainty estimation applied to sequential decision-making (game theory). Published under arXiv:2601.10775v2 [cs.CL] (11 Apr 2026), initially posted 2026-01-15.
• Technical level: Intermediate. The core intuition (spend more reasoning effort when the model is unsure) is accessible, but the paper includes formal notation for state spaces, autoencoder and contrastive losses, and token-level entropy.
• Scope (1 sentence): The paper proposes and evaluates a framework that couples entropy-guided context retrieval with adaptive chain-of-thought reasoning so that an LLM playing Tic-Tac-Toe expends more examples and more reasoning paths only when its token-level uncertainty is high.

What This Paper Is About

LLMs that perform well in single-step tasks still struggle in structured, sequential decision-making, where every move changes all future states and requires long-term planning. The authors ask whether an LLM can make better moves — without any task-specific fine-tuning — if the amount of retrieved context and the depth of its reasoning are both driven by how uncertain the model is at each turn. They test this on Tic-Tac-Toe against a deliberately suboptimal algorithmic opponent, using a Minimax table as the ground truth for move quality.

Key Contributions

1. Entropy-guided context retrieval. A retrieval size is computed dynamically as k = min(k_max, ⌈k₀ + α · H_q⌉), so confident outputs use a compact set of nearest-neighbour examples and uncertain outputs pull in more examples — bounded by the model's token budget L_max.
2. A structured retrieval representation for board states. Boards are flattened to vectors in R^9 and encoded into a latent space by an autoencoder, then reshaped with a contrastive objective that pulls boards sharing the same optimal move together and pushes apart boards with different optimal moves, with the combined loss L = L_rec + λ L_con.
3. Adaptive chain-of-thought with entropy thresholds. Five reasoning modes are defined (direct output, Multi-CoT, tree-based CoT, and an entropy-guided hybrid), where step-level entropy H_t^step (the average of token-level entropies over the generated tokens) is mapped through ordered thresholds 0 = H₀ < H₁ < … < H_m to a number of parallel branches n_t = min(n_j, |A(s_t)|).
4. An empirical validation of entropy as an uncertainty proxy. Across 500 randomly selected board states, token-level entropy correlates negatively with move optimality (Spearman ρ = −0.471, p < 10⁻³; Kendall τ = −0.346, p < 10⁻³).

Main Findings

• Context retrieval alone helps substantially. With no CoT and no additional context, the agent scores −11.6%; adding a fixed-size context lifts this to −5.2%, and entropy-guided context to −2.8%.
• The best absolute score comes from tree-based CoT with entropy-guided context: +9.8% over 100 games — but at 188 LLM queries per game on average.
• Entropy-guided CoT with entropy-guided context is nearly as good for a fraction of the cost: +9.5% at 48 queries per game, roughly one-fourth of the tree-based CoT query cost. Full model choice for all reported results is LLaMA-7B; each cell of Table 1 reports the average outcome per game S over 100 games plus the rounded average number of LLM queries per game.
• Larger reasoning trees pay off only in combination with retrieval. Tree-based CoT ranges from −2.7% (no additional context, 165 queries) to +4.5% (fixed-size context, 178 queries) to +9.8% (entropy-guided context, 188 queries).
• Multi-CoT improves monotonically with context quality: −7.5% → −1.2% → +4.8% as context goes from none, to fixed-size, to entropy-guided (24, 26, and 28 queries respectively).
• High entropy consistently signals riskier moves. The paper reports that high entropy arises from genuine uncertainty (true positive) or from multiple similarly optimal moves (false positive), with false positives mostly in early-game states — mitigated by not applying entropy-based branching on the first move.
• Performance is reported against a controlled suboptimal opponent. The opponent samples moves from a distribution P(i) over Minimax-ranked moves, parameterized by a skill level α = 0.95, which peaks at the move matching that skill and decays linearly toward both less optimal and overly optimal moves.
• The zero-shot claim rests on the absence of fine-tuning. The retrieval encoder is trained self-supervised and the LLM is never fine-tuned on the downstream task; reasoning is said to emerge purely from contextual conditioning.

Methodology in Plain English

The setup is a turn-based game loop. The board is represented as a 3×3 grid of values (0 empty, 1 for X, 2 for O) and flattened into a 9-dimensional vector. An autoencoder compresses this into a compact latent vector, and a contrastive term shapes that latent space so that boards with the same best move sit close together — which makes nearest-neighbour lookup by cosine similarity meaningful.

A vector database stores about 20% of all possible board states, chosen uniformly at random, each paired with its Minimax-optimal move. At each turn, the query board is embedded, the top-k most similar stored boards are retrieved, and k itself is set by the model's current uncertainty. The prompt given to the model contains the retrieved board/move examples, the current board, the list of empty positions, and which player is active; an example prompt is given in Appendix A, with moves in a simple (x, y) coordinate format.

Reasoning depth is also uncertainty-driven. The model can answer directly, sample several independent reasoning chains and take a majority vote on the first move (Multi-CoT), expand a tree over candidate moves and opponent replies, or use the paper's entropy-guided hybrid — branching into multiple paths only when step-level entropy crosses a threshold, then keeping only the top-k branches scored by average path entropy. All experiments use LLaMA-7B for the reported numbers (Gemma 3 270M was used for initial testing), with temperature 0.1, top_p = 1.0, top_k = 0, beam search 2, at most 10 generated tokens per move, and a fixed random seed of 42. The parallel CoT configuration uses n = 3 sequences, up to 3 branches per turn, and at most k = 10 retained paths. Initial tests ran on a single NVIDIA GeForce RTX 4050 with 6 GB VRAM and an Intel i7-12700H CPU with 16 GB RAM; final LLaMA-7B evaluations ran on an NVIDIA GeForce RTX 4060 Ti with 16 GB VRAM on Ubuntu 24.04 LTS. The implementation used Python with transformers, bitsandbytes, torch, and langchain. The 15 configurations (3 context types × 5 CoT strategies) were each run for 100 games.

Why This Matters

• Impact on research: The paper argues that evaluating only final answers hides reasoning errors, and that a fully solvable game like Tic-Tac-Toe gives an objective optimal-move reference, sidestepping the well-documented inconsistency of CoT evaluation benchmarks. It also provides evidence for token-level entropy as a usable uncertainty signal in sequential tasks.
• Real-world applications (as suggested by the framework's generality):
  • Sequential decision support where each action changes future options (planning, scheduling, resource allocation).
  • Retrieval-augmented assistants that must decide how much external evidence to pull in per query rather than always using a fixed context.
  • Cost-aware agentic systems that need to cap the number of model calls per task.
  • Interactive environments with a well-defined notion of an optimal action, where move quality can be scored automatically.
• Industry relevance: The performance–cost trade-off is the headline for practitioners — the paper reports achieving +9.5% at 48 queries per game versus +9.8% at 188 queries per game, a near-equivalent outcome for roughly one-fourth of the query budget. Systems that bill or throttle on inference calls can use uncertainty as a routing signal to decide when extra reasoning is actually needed.

Future Directions

• Scale beyond Tic-Tac-Toe. The authors point to Connect Four or Go as tests of scalability and robustness under higher-dimensional state representations and longer reasoning sequences.
• Test with stronger base models. Since LLaMA-7B has limited reasoning capacity, the question is whether entropy-guided mechanisms still add value when the base model already reasons well (they name GPT-5 and Gemini 2.5 as examples of stronger models).
• Improve the uncertainty signal. Token-level entropy assumes linguistic uncertainty maps onto decision uncertainty; alternative estimators such as ensemble variance or mutual information might be more reliable, especially where uncertainty comes from ambiguity rather than missing knowledge.
• Address retrieval data assumptions and reasoning quality. The retrieval database is built from the full game tree and may not transfer to incomplete or biased data, where retrieval redundancy or conflicting examples could hurt consistency. Evaluation also stays quantitative (win/loss and query count) without judging the logical soundness or interpretability of the reasoning traces; the paper also flags partially observable tasks and dynamically updating the entropy thresholds H_j based on previously observed entropy distributions as open directions.

Target Audience

Researchers and practitioners working on LLM reasoning, chain-of-thought, retrieval-augmented generation, and test-time compute allocation. It is also relevant to engineers building agentic or decision-making systems who care about the query-cost/quality trade-off, and to students looking for a small, fully controllable testbed — the paper notes that a fully solvable game makes statistical validation of the strategy unnecessary because the Minimax table gives a complete move ranking. Readers wanting a rigorous formal theory should note the paper states it does not introduce a completely new formal theoretical method; it relies empirically on entropy as a proxy for uncertainty. The reproducibility checklist states that all experiments used no datasets (optimal moves are precomputed via Minimax) and that code will be publicly released upon publication.

Authors’ abstract

We propose a novel LLM-based framework for reasoning in discrete, game-theoretic tasks, illustrated with \emph{Tic-Tac-Toe}. The method integrates in-context learning with entropy-guided chain-of-thought (CoT) reasoning and adaptive context retrieval. The model dynamically adjusts both the number of retrieved examples and reasoning paths according to token-level uncertainty: concise reasoning with minimal context is used when uncertainty is low, whereas higher uncertainty triggers expanded multi-path CoT exploration. Experimental evaluation against a sub-optimal algorithmic opponent shows that entropy-aware adaptive reasoning substantially improves decision quality, increasing the average game outcome from \(-11.6\%\) with the baseline LLM to \(+9.5\%\) with entropy-guided adaptive reasoning over 100 games (win = +1, tie = 0, loss = -1), while maintaining a relatively low number of LLM queries per game. Statistical validation confirms that the improvement is significant, and correlation analysis reveals a negative association between token-level entropy and move optimality. These findings demonstrate that uncertainty-guided adaptive reasoning effectively enhances LLM performance in sequential decision-making environments.