TsuGO: Probing Search Efficiency in LLM Reasoning via Go Life-and-Death Problems

TsuGO: Probing Search Efficiency in LLM Reasoning via Go Life-and-Death Problems

Abstract Summary

The paper introduces TsuGO, a process-level reasoning benchmark for evaluating Search Efficiency in LLM reasoning through Go life-and-death problems. The authors argue that existing evaluation methods fail to capture how models plan reasoning paths and allocate reasoning resources—that is, how they organize search. Prior process-level methods focus on coherence and redundancy of chain-of-thought (CoT), and most benchmark tasks have a single objective solvable by static capabilities such as derivation and tool use, leaving search organization unmeasured. TsuGO provides closed and verifiable solution spaces with an inherent adversarial structure, making candidate generation, response checking, branch comparison, and backtracking necessary parts of reasoning. By constraining the solution space, TsuGO disentangles domain knowledge from search organization, parses CoT into a structured search tree, and reports Search Efficiency together with Token Efficiency and other diagnostic metrics and visualizations. Experiments show that current LLMs remain far from stable tsumego solving: stronger models succeed by finding the correct candidate earlier and sustaining effort on productive branches, but most models still behave much closer to unguided search algorithms than to neural-guided KataGo. Longer CoT or higher Token Efficiency does not necessarily imply better search. The results identify search organization and reasoning-resource allocation as missing dimensions in LLM reasoning evaluation.

Introduction Summary

Chain-of-Thought (CoT) and extended thinking have become central to LLM reasoning, improving performance on mathematics, code generation, and scientific problem solving. This shift moves evaluation beyond final-answer correctness toward whether reasoning processes are effective and efficient. Existing evaluations mainly study the quality and efficiency of reasoning along a single trajectory. Traditional benchmarks such as GSM8K, MATH, and ARC focus on final-answer correctness, while recent process-level methods analyze reasoning traces themselves. CoTJudger measures necessary reasoning and structural redundancy from dependency graphs; ReEfBench maps traces into logical structures to analyze reasoning efficiency and behavioral patterns; and process-supervision or PRM-based methods evaluate intermediate steps through step-level feedback. These studies show whether a reasoning chain is correct, concise, and logically coherent, but mainly assume that effective reasoning follows a single derivation path.

Many challenging problems require more than static problem solving along a single derivation path: models must explore alternatives, identify promising directions, and allocate resources across competing paths. The authors call this capability Search Efficiency (SearchE): organizing reasoning search toward effective solutions across multiple possible trajectories. Compared with Token Efficiency, which reflects observable token cost, SearchE is more internal: it tracks how models move through the solution space and redistribute effort across branches, rather than only how much surface text they produce. Adversarial tasks naturally expose this ability because each decision must survive future responses, forcing comparison, verification, and revision. Branching is therefore not inherently redundant; effective reasoning depends on whether exploration is organized around valuable paths.

The paper introduces TsuGO, a benchmark based on Go life-and-death problems for evaluating SearchE in LLM reasoning. The name draws on tsumego (tsume-go), the Japanese term for Go life-and-death problems, and emphasizes how models choose where to go next. Tsumego offers a controlled adversarial environment with verifiable solution spaces, enabling analysis of both final answers and search over alternatives. The authors parse free-form CoT into process search trees and report SearchE, which measures whether resources target the correct branch, and TokenE, which normalizes accuracy by observable token cost. Experiments show that stronger models succeed by proposing the correct candidate earlier and sustaining effort on productive branches, establishing search organization as a dimension beyond outcome accuracy and token efficiency.

The contributions are threefold: (1) TsuGO, a process-level benchmark for evaluating Search Efficiency in controlled adversarial tasks with verifiable solution spaces; (2) a search-trace framework that converts free-form CoT into process search trees and diagnoses resource allocation with Search Efficiency and supporting trajectory/scale diagnostics; (3) demonstration that Search Efficiency aligns more closely with search organization than token-level efficiency, and that TsuGO remains far from saturated: even frontier LLMs lag far behind neural-guided KataGo, making search organization a key underdeveloped direction for LLM reasoning.

Related Work Summary

The paper reviews three areas of related work. First, reasoning evaluation benchmarks: early benchmarks mainly evaluate final-answer accuracy (GSM8K, MATH, ARC, BIG-Bench), while recent studies analyze intermediate reasoning traces (ROSCOE, ReCEval, CoTJudger, ReEfBench, ProcessBench, PRMBench, process reward modeling). These methods mainly evaluate the quality of a single reasoning trajectory. Second, search-based reasoning: recent work improves LLM reasoning by introducing explicit search procedures (Tree-of-Thought, Graph-of-Thoughts, RAP, LATS, AlphaZero-like search, Stream of Search, LE-MCTS). These methods show that structured search can improve reasoning when supplied as an external procedure, but leave open whether LLMs can organize search within their own reasoning traces. Third, adversarial reasoning environments: AlphaGo and AlphaGo Zero demonstrate the importance of tree search for decision making in games; recent LLM studies on chess, Othello, and Go investigate state tracking, move prediction, and strategic reasoning. These works mainly evaluate task performance or state understanding. TsuGO uses Go life-and-death problems differently: as a controlled environment for analyzing how models explore, verify, and organize reasoning search.

TsuGO Benchmark Summary

The paper explains why tsumego is suitable: adversarial solution spaces are large and dynamic; each candidate move changes the space of possible replies, and a line remains valid only if it survives the opponent's strongest response. Tsumego provides this structure in a compact and verifiable form: relevant moves are local, variations can be checked against reference solutions and engine analysis, and positions can be rendered as coordinates, matrices, or images. The authors use tsumego not to test Go strength, but as a closed adversarial environment where the difficulty of Go-style search comes from dynamically changing branches and the need to separate domain knowledge from search organization.

Data curation: Problems are curated from public tsumego materials, classical collections, and traceable source records, including texts such as Xuanxuan Qijing and Go Life-and-Death Dictionary. TsuGO keeps only normalized board states, candidate points, reference solution trees, and provenance records; each problem is stored in SGF and converted to JSON with a 19×19 matrix, coordinates, side to play, and solution tree. Problems satisfy three criteria: Locality (relevant stones occupy a bounded region), First-move determinacy (correct first moves are unique or finite and not ko-dependent), and Verifiability (ground-truth solutions are expert-checked and cross-validated by a Go engine). Each position is rendered as Symbolic coordinates, Grid matrices, Symbolic+Grid, Visual images, and Symbolic+Visual.

Dataset overview: The curated pool contains 1,500 problems in five input forms; the main evaluation uses 600 problems, sampled as 200 problems from each of three evaluated difficulty tiers. Difficulty tiers combine human-rank bands, main-line depth, and plausible wrong candidates. The paper evaluates each problem under two candidate-space conditions: K=4, where the model selects from four first moves including the correct one, and K=None, where it must generate, compare, and justify a move from the board. This separates candidate discrimination from independent search organization across symbolic, grid, and visual modalities. The paper also tests rotation, reflection, color inversion, coordinate relabeling, and candidate-order permutation as robustness controls.

Search-Trace Analysis Framework Summary

Trace source: TsuGO uses each model's observable reasoning output to reconstruct search organization, using full CoT or reasoning content when available. For closed-source models that expose only compressed summaries, those summaries are analyzed as observable artifacts rather than complete internal computation.

Process Search Tree: Each output is parsed into a process search tree T = (V, E, τ), where V is the node set, E the directed edges, and τ a strictly increasing timestamp. The root r is the initial board state; action nodes a are proposed or simulated moves with side(a) and pos(a); evaluation nodes j are terminal judgments with polarity(j) ∈ win, lose, undetermined. The root's action children form the first-level candidates C = c1,..., cm. For candidate c, subtree(c) measures allocated resources and maximum root-to-leaf distance measures reading depth. Cross-candidate timestamp transitions are search jumps; jumps to previously visited candidates are backtracking.

Extraction pipeline: The paper builds a domain prior dictionary from open-ended answers with four step types: candidate exploration, variation reading, position evaluation, and backtracking. An LLM-based extractor identifies action and evaluation nodes, classifies edges from temporal and semantic context, and closes branches with win/lose/undetermined judgments. Structural validation enforces well-formed trees. The extraction is validated on 300 sampled problems with two human experts assisted by KataGo; Gemini-2.5-Pro reaches 93–98% agreement.

Metrics: TsuGO reports answer accuracy as first-move hit rate. SearchE aggregates wrong-branch waste (SWR), first-hit behavior (SFH), and correct-candidate search rank (SCR): SearchE = 100 · (0.5(1 − SWR) + 0.3 SFH + 0.2(1 − SCR)). TokenE measures accuracy relative to observable thinking-token cost: TokenE = 100 · A/(A + ITT/1000), with A = 100 · Acc. The paper also reports trajectory metrics (Trajectory Max Depth, Trajectory Max Fan-out, Trajectory Node Count) and scale metrics (Inference Total Tokens, Inference Per Node).

Experiments Summary

Setup: The paper evaluates open reasoning, open non-reasoning, and proprietary models on 600 sampled problems, with 200 per difficulty tier, under K=4 candidate selection and K=None generation. Evaluated LLMs cover Moonshot AI Kimi-K2.5, Alibaba Qwen3-VL, MiniMax-M2.5, DeepSeek-R1/V3.2, Zhipu AI GLM-4.6V, and Google Gemini models. Accuracy is averaged over available modalities, while process metrics use Symbolic input. The paper uses Smargo MCTS/UCT and KataGo as non-LLM references with 200 playouts or visits per problem.

Main results: Current LLMs are still far from stable TsuGO solving. Even under K=4 Easy, the strongest open model, Kimi-K2.5, reaches only 52.0 accuracy; Gemini-3.1-Pro reaches 80.0 but falls to 19.0 on K=None Hard. Model classes show a clear but non-absolute ordering: Gemini models lead on easy settings but lose advantage with difficulty, while open reasoning models generally outperform weaker non-reasoning models in open search. The drop from K=4 to K=None exposes the open-search bottleneck. Difficulty trends show that candidate constraints can mask open-search failures. Treemaps reveal focused and diffuse search: under K=None, Kimi-K2.5 and Gemini-3.1-Pro concentrate on fewer candidates and push them toward verification, while GLM-4.6V and MCTS spread resources across shallow wrong branches.

Insight: Failure is a failure of search-resource allocation. In the open setting, the correct move is often absent or displaced by shallow checks of other branches. SearchE is a stronger process signal than TokenE: Figure 5 shows tighter clustering around accuracy for SearchE than TokenE, indicating stronger alignment with task success. LLMs lie between blind and guided search: MCTS reaches mid-tier LLM accuracy under K=4 but drops to single digits without candidates, while KataGo remains much stronger under the same visit budget.

Further analysis: Dynamics of resource allocation show that MCTS and KataGo both form early branch preferences and plateau, but KataGo converges faster and more strongly. LLM CoT is more scattered and volatile, indicating weaker concentration than explicit search. The paper also tests Logos, a Go LLM trained on KataGo game trajectories, but it often continues whole-game play or plays elsewhere instead of resolving the local life-and-death point, making its outputs unsuitable for reasoning-trace analysis.

Bad-case analysis: Manual inspection of failed open-setting traces identifies failures in candidate-generation knowledge, coordinate grounding, visual perception, board-state maintenance, adversarial verification, instruction following, reasoning loops, and branch management. These cases indicate a combined bottleneck in candidate generation, local state tracking, adversarial verification, and branch control, rather than resource allocation alone.

Conclusion Summary

The paper presents TsuGO, a process-level benchmark for evaluating Search Efficiency in LLM reasoning. Instead of testing Go-playing strength, it uses life-and-death problems as closed, verifiable, adversarial search spaces; K-Search controls the solution space, and process trees expose resource allocation. Experiments show that current LLMs remain far from stable tsumego solving: stronger models find the correct candidate earlier and sustain productive effort, while failures omit, delay, or abandon the key move, often compounded by state-perception and tactical errors. Search Efficiency is a more effective process signal than token cost alone because it measures how models allocate resources during search. With Token Efficiency as a cost reference, it identifies candidate generation, branch comparison, verification, and backtracking as core search-control bottlenecks. Overall, TsuGO turns free-form traces into diagnostic feedback and remains far from saturated, suggesting future work on Search-Efficiency-sensitive training data and planning frameworks.

Based on the paper, here are the specific improvements I can make to AI systems:

• Improvement: Add a module that tracks how reasoning tokens are distributed across candidate branches in real-time, not just total token count.

• Capability: The system can detect when it is wasting resources on shallow, unproductive branches and dynamically reallocate effort toward the most promising candidate, mimicking how stronger models like Kimi-K2.5 concentrate on fewer candidates and push them toward verification.

• Improvement: Implement a mechanism that scores and ranks candidate solutions at the first decision point, using domain priors to identify the correct move earlier.

• Capability: The system can avoid the common failure mode where the correct move is absent or delayed; it will generate and prioritize the correct candidate within the first few reasoning steps, improving accuracy on open-ended search tasks.

• Improvement: Add a self-checking subroutine that explicitly tests each proposed branch against the strongest possible counter-response (e.g., opponent's best reply in a game, or a critical edge case in a proof).

• Capability: The system can close branches with win/lose/undetermined judgments, preventing premature acceptance of invalid lines and reducing errors from missing adversarial replies—a key bottleneck identified in the bad-case analysis.

• Improvement: Implement a threshold-based backtracking mechanism that detects when a branch has consumed excessive resources without yielding a decisive result, and automatically jumps back to a previously visited, more promising candidate.

• Capability: The system can avoid reasoning loops and dead-end exploration, improving search efficiency by reducing wrong-branch waste (SWR) and increasing the likelihood of finding the correct solution within a fixed token budget.

• Improvement: Add a controller that limits fan-out (number of concurrent candidates) and enforces minimum reading depth per branch before switching.

• Capability: The system can avoid the diffuse, shallow exploration pattern seen in weaker models (e.g., GLM-4.6V and MCTS); it will sustain effort on productive branches long enough to verify them, rather than spreading resources thinly across many unverified options.

• Improvement: Train a lightweight classifier that separates domain-specific knowledge (e.g., recognizing a Go life-and-death pattern) from search organization (e.g., comparing branches, backtracking), based on the paper's finding that these are distinct bottlenecks.

• Capability: The system can identify when failures are due to missing domain knowledge versus poor search strategy, allowing targeted improvements (e.g., injecting relevant facts or adjusting search heuristics) without retraining the entire reasoning pipeline.

• Improvement: Integrate SearchE (0.5*(1-SWR) + 0.3SFH + 0.2(1-SCR)) as a real-time optimization target, alongside TokenE, to balance accuracy with token cost.

• Capability: The system can produce more concise reasoning traces that still achieve high accuracy, avoiding the pitfall where longer CoT or higher token efficiency does not correlate with better search—it will explicitly optimize for finding the correct branch early and verifying it deeply, rather than generating verbose but unfocused reasoning.

• Improvement: Train the search-organization module on multiple input formats (symbolic, grid, visual) to ensure it generalizes beyond a single representation.

• Capability: The system can maintain consistent search efficiency across different problem presentations (e.g., coordinates vs. images), reducing errors from coordinate grounding or visual perception that currently compound search failures.

• Improvement: Implement a meta-controller that assesses problem difficulty (based on main-line depth and plausible wrong candidates) and adjusts search strategy accordingly—e.g., using more aggressive backtracking on hard problems, or tighter branch limits on easy ones.

• Capability: The system can avoid the performance cliff seen in models like Gemini-3.1-Pro (80.0 on easy K=4, 19.0 on hard K=None) by scaling search effort appropriately, maintaining robustness across difficulty tiers.

• Improvement: Add a post-hoc analysis tool that parses the system's own CoT into a process search tree and reports SearchE, SWR, SFH, and SCR metrics after each task.

• Capability: The system can self-assess its search organization, identify specific weaknesses (e.g., late first-hit, high wrong-branch waste), and adjust its reasoning strategy on subsequent tasks—enabling continuous improvement without external feedback.

Overall, the improved AI system can: solve open-ended, adversarial reasoning problems (like tsumego, but also applicable to theorem proving, strategic planning, and code debugging) by organizing its search more like neural-guided KataGo—finding the correct candidate early, verifying it deeply against counterexamples, and efficiently backtracking—while using fewer tokens and providing interpretable diagnostics of its own search process.

The evaluation of LLM reasoning is moving from final-answer accuracy to process-level assessment, yet existing methods still fail to capture how models plan reasoning paths and allocate reasoning resources--that is, how they organize search. Prior process-level methods focus on the coherence and redundancy of chain-of-thought (CoT), and most benchmark tasks have a single objective solvable by static capabilities such as derivation and tool use, leaving search organization unmeasured. We introduce TsuGO, a process-level reasoning benchmark for evaluating Search Efficiency in LLM reasoning through Go life-and-death problems. These problems provide closed and verifiable solution spaces with an inherent adversarial structure, making candidate generation, response checking, branch comparison, and backtracking necessary parts of reasoning rather than incidental trace patterns. By constraining the solution space, TsuGO disentangles domain knowledge from search organization, parses CoT into a structured search tree, and reports Search Efficiency together with Token Efficiency and other diagnostic metrics and visualizations. Experiments show that current LLMs remain far from stable tsumego solving: stronger models succeed by finding the correct candidate earlier and sustaining effort on productive branches, but most models still behave much closer to unguided search algorithms than to neural-guided KataGo. Longer CoT or higher Token Efficiency does not necessarily imply better search. Our results identify search organization and reasoning-resource allocation as missing dimensions in LLM reasoning evaluation.