Strategic Planning and Rationalizing on Trees Make LLMs Better Debaters

🕒 Published (v1): 2026-01-01 · Source: ICLR · Venue: ICLR 2026 · link

Why this paper was selected

Tree-structured strategic planning significantly improves LLM agent competitive debate

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

TreeDebater is a competitive debate framework for LLMs that uses two complementary tree structures — a pre-debate Rehearsal Tree for argument strength estimation and an in-debate Debate Flow Tree for action selection — to address time-constrained, back-and-forth argumentation. It outperforms the state-of-the-art multi-agent debate system Agent4Debate by up to 3.5× in debate-level opinion shift win rate in human evaluation. The key insight is that tree-structured planning, analogous to how expert human debaters mentally rehearse and track argument flows, enables strategic time allocation that flat LLM generation cannot achieve.

Problem

Current LLMs generate fluent arguments but fail in competitive debate due to two structural gaps: (1) strict time limits require selective prioritization of debate actions (propose, reinforce, attack, rebut) rather than exhaustive argument coverage; (2) no objective reward signal exists — winning depends on audience persuasion via the evolving argument flow, making it impossible to plan toward a single final game state as in rule-based games. Existing systems like Agent4Debate do not model this dynamic interaction or time budget allocation.

Method

TreeDebater introduces two tree structures operated in two phases:

Rehearsal Tree \(T_r\) (pre-debate): Built top-down with LLM-generated candidate claims as roots. Each node \(x^l\) is an argument; children are potential counterarguments. Two LLaMA-3.2-3B reward models score attack impact \(r_a(x^l, x^{l-1})\) and support impact \(r_s(x^l, x^{l-2})\). A k-step strength score is computed bottom-up via a minimax recursion: $\(f_k(x^l) = f_0(x^l) - \gamma \cdot \max_{x^{l+1} \in \text{Child}(x^l)} f_{k-1}(x^{l+1})\)$ with decay \(\gamma = 0.8\). This models the worst-case utility assuming the opponent always chooses the most damaging counterargument. \(k\) is set to the number of remaining debate rounds, so strength scores are horizon-aware.

Debate Flow Tree \(T_d\) (in-debate): Updated after each opponent statement by extracting (action, claim, argument, target) tuples. Tracks node states (proposed/attacked) and visit counts. At each stage, candidate actions are filtered from the tree (e.g., rebut only leaf nodes of the opponent; propose only in opening). Arguments for each candidate action are retrieved from \(T_r\) via cosine similarity using Gemini-text-embedding-4 (threshold 0.8).

Simulated audience feedback: The current Debate Flow Tree is serialized as a tree-like string, then semantically matched against a curated human debate flow tree corpus. A retrieved human tree is fed to a simulated audience agent that critiques message clarity, engagement, evidence presentation, and persuasive elements. The writer revises the draft based on this feedback.

Speech Time Controller: Uses FastSpeech TTS to estimate actual speech duration. Binary search over word-count targets iterates until the estimated speech time falls within \([t_l, t_r]\) or a maximum revision limit is reached, bypassing LLMs' known inability to reliably follow word-count instructions.

Key Contributions

• Two-tree debate architecture: Rehearsal Tree for pre-debate argument strength estimation (minimax k-step scoring) and Debate Flow Tree for in-debate action tracking and candidate selection.
• LLaMA-3.2-3B reward models trained on the Kialo dataset for fine-grained attack/support scoring.
• Human debate flow tree corpus with semantic retrieval to ground simulated audience feedback in real human debate patterns.
• Speech time controller using FastSpeech + binary search to enforce hard time constraints that word budgets alone cannot achieve.
• Controlled stage-level (120 comparisons, 212 Prolific participants) and end-to-end Oxford-style debate-level human evaluation protocol.

Results

• Stage-level persuasiveness (head-to-head): TreeDebater wins in 11/12 stage comparisons; preferred 1.5× (Gemini backbone) and 2.5× (DeepSeek backbone) over Agent4Debate.
• Stage-level win with DeepSeek: +15.6% improvement in persuasiveness score.
• Debate-level opinion shift win: 3.5× higher than Agent4Debate with Gemini backbone; 1.3× higher with DeepSeek backbone.
• Debate-level improvement: +10% opinion shift win overall.
• Format/time validity: TreeDebater produces 100% format-valid and time-valid statements; Agent4Debate (Gemini) achieves only 77% format-valid debates and consistently exceeds time limits.
• Annotator agreement: 60.7% on stage-level pairwise judgments (reported as moderate consensus given debate subjectivity).

Limitations

• Human evaluation is conducted entirely in English with US-based Prolific participants; cross-lingual and cross-cultural generalizability is untested.
• The Rehearsal Tree is built before the debate and cannot incorporate opponent claims discovered only during the live debate; the tree is static once constructed.
• Reward models (\(r_a\), \(r_s\)) are trained on the Kialo dataset, which may not cover all debate domains or argument styles.
• The speech time controller adds latency via iterative TTS inference; computational cost of the full pipeline is not benchmarked.
• Evaluation is restricted to the simplified Oxford-style format (opening/rebuttal/closing); generalization to other debate formats is not assessed.
• Human evaluation sample sizes are small (4–7 motions for debate-level), which limits statistical power.

Relevance to Agentic AI / LLM Agents

TreeDebater is a direct instance of structured planning for LLM agents in adversarial, partially observable, interactive environments — a core open problem in agentic AI. The Rehearsal Tree's minimax strength scoring formalizes look-ahead planning without a ground-truth reward signal, connecting to the broader challenge of value estimation in open-ended agent tasks where no single terminal state defines success. The Debate Flow Tree exemplifies dynamic state tracking as an explicit agent memory, analogous to working memory modules in tool-augmented agents. The speech time controller addresses a real-world constraint satisfaction problem (action budgets) that arises whenever agents must operate under resource limits — generalizable to token budgets, API rate limits, or latency targets in deployed agentic systems. This work also demonstrates that retrieval-augmented self-improvement via a curated corpus (human debate trees) can substitute for online RL in domains where reward signals are sparse or subjective.