Scaling Inference-Time Computation via Opponent Simulation: Enabling Online Strategic Adaptation in Repeated Negotiation

1. Problem Statement

The paper addresses a critical limitation in current Large Language Model (LLM) agents: their inability to effectively adapt to unknown or dynamic opponents in repeated strategic interactions (e.g., negotiations).

• The Gap: While LLMs excel in stationary, single-agent tasks (like math or coding), they struggle in multi-agent settings where opponents vary over time.
• Limitations of Existing Approaches:
  • Offline Training/Fine-tuning: Methods like self-play or RL often converge to static, conservative policies (e.g., Minimax) that are robust against worst-case adversaries but fail to exploit cooperative opportunities or adapt to specific opponent behaviors.
  • Gradient-based Online Adaptation: Traditional online learning requires parameter updates, which are data-hungry, introduce high latency, and are impractical for real-time test-time adaptation.
• Core Question: Can LLMs achieve online strategic adaptation in repeated negotiations by scaling inference-time computation (using more compute at test time) rather than updating model parameters?

2. Methodology: BoN-oppo-simulation

The authors propose a framework called BoN-oppo-simulation, which embeds the principles of Smooth Fictitious Play (sFP) into LLM inference. Instead of updating weights, the method allocates extra compute tokens to simulate future interactions and refine decisions dynamically.

The framework consists of two decoupled modules:

A. Step 1: In-Context Opponent Modeling (Belief Formation)

To handle the intractability of tracking frequencies in a continuous natural language space, the authors use an auxiliary LLM ($\pi^{oppo}_2$) to model the opponent.

• Mechanism: The opponent model takes the full history of interactions ($C_{t-1}$) and the current partial trajectory as input.
• Prompting Strategy:
  1. Strategic Summarization: The model explicitly reflects on past interactions to summarize the opponent's high-level behavioral patterns (e.g., "aggressive," "fair," "tit-for-tat").
  2. Optimism (OFU): To handle uncertainty, the model is biased to predict outcomes favorable to the acting agent (Agent 1) when uncertain, acting as an exploration mechanism.
• Goal: To create a time-averaged belief about the opponent's policy without fine-tuning.

B. Step 2: Best-of-$N$ with Opponent Simulation (Best Response)

Instead of standard Best-of-$N$ (BoN) sampling, the authors introduce Strategic Brainstorming and Simulation.

• Strategic Brainstorming: The base agent ($\pi^{base}_1$) first generates $N$ diverse high-level strategies (e.g., "Cunning," "Fairness," "Tit-for-Tat") and then generates specific candidate actions based on these strategies. This ensures broader exploration of the strategy space compared to i.i.d. sampling.
• Opponent Simulation: For each candidate action, the agent simulates the entire future trajectory of the negotiation.
  • The agent plays its candidate move.
  • The Opponent Model ($\pi^{oppo}_2$) predicts the opponent's response.
  • The agent's base policy predicts its subsequent moves.
  • This roll-out continues until the episode ends to estimate the expected reward ($\hat{r}$).
• Selection: The agent selects the candidate action that yields the highest simulated reward.

Theoretical Insight: The paper proves that the error in the final policy scales linearly with the error in the opponent model. It also draws a parallel to Policy Iteration, where the inference-time simulation acts as a policy evaluation step, and the selection acts as policy improvement, all without parameter updates.

3. Key Contributions

1. Problem Formalization: The authors demonstrate theoretically and empirically that no single static policy dominates in repeated negotiation games against diverse opponents. They show that standard LLMs fail to self-improve through simple context accumulation alone.
2. Novel Framework (BoN-oppo-simulation): They introduce a principled method to scale inference-time computation by combining in-context opponent modeling with trajectory simulation. This allows the agent to "think ahead" against a simulated version of the opponent.
3. Strategic Brainstorming: They propose a structured generation process that separates high-level strategy formulation from action generation, significantly increasing the semantic diversity of candidate actions.
4. Empirical Validation: Extensive experiments show that this method enables significant self-improvement over repeated episodes, outperforming baselines that rely on parameter updates or simple prompting.

4. Experimental Results

The method was evaluated on two negotiation benchmarks: Buyer-Seller and Resource Exchange games.

• Performance Gains:
  • BoN-oppo consistently outperformed baselines (Zero-shot, Thinking, BoN-eval, BoN-simulation without opponent modeling) across different model families (Gemini, Claude, Qwen, Llama).
  • In the Buyer-Seller game, the method achieved the highest average rewards, particularly in later episodes, demonstrating effective online adaptation.
  • Robustness: The method maintained performance even when the opponent's private constraints (budget/cost) were randomized every episode, proving it adapts to behavioral policies rather than memorizing static values.
• Comparison with SOTA: The method outperformed specialized adaptive baselines (e.g., AI Feedback, Experience Reflection, Private Information Prediction) that rely solely on input-level prompting.
• Social Welfare: In cooperative settings, pairs of agents both using BoN-oppo achieved the highest social welfare, suggesting the method helps agents converge to more efficient equilibria.
• Efficiency: The generation and simulation steps can be fully parallelized, minimizing wall-clock latency despite the increased token usage.

5. Significance and Implications

• Paradigm Shift: The paper validates that scaling inference-time compute is a viable and powerful alternative to parameter updates for enabling strategic reasoning in LLMs.
• Generalizability: The approach is model-agnostic and works across different LLM architectures, suggesting a general path for improving multi-agent decision-making.
• Theoretical Bridge: It successfully bridges classical game theory (Fictitious Play) with modern LLM capabilities (In-Context Learning and Chain-of-Thought), providing a rigorous framework for online learning in non-stationary environments.
• Practical Application: This offers a solution for deploying LLM agents in dynamic real-world scenarios (e.g., automated trading, diplomatic negotiations, supply chain management) where opponents are unknown and strategies must evolve in real-time.

In conclusion, the paper demonstrates that by investing compute power into simulating opponents and brainstorming diverse strategies at test time, LLMs can overcome the limitations of static policies and achieve robust, adaptive strategic behavior in repeated interactions.