💻 computer science

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

This paper introduces TsuGO, a novel benchmark using Go life-and-death problems to evaluate LLM reasoning by measuring search efficiency and resource allocation, revealing that current models often rely on unguided search patterns rather than effective strategic planning despite longer chains of thought.

Original authors: Shunwen Bai, Ziping Ma, Chaoyang Zhang, Yarong Wang, Jiale Liu, Zhen Qin, Qingpei Guo

Published 2026-08-14

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Shunwen Bai, Ziping Ma, Chaoyang Zhang, Yarong Wang, Jiale Liu, Zhen Qin, Qingpei Guo

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are watching a grandmaster chess player solve a puzzle. In the past, we only cared if they picked the winning move at the very end. If they got it right, we cheered; if they got it wrong, we moved on. But recently, scientists studying Artificial Intelligence (AI) realized that just looking at the final answer isn't enough. They started looking at the "Chain of Thought"—the messy, step-by-step chatter the AI says out loud while it thinks. They wanted to know: Is the AI actually thinking, or is it just guessing and hoping to get lucky?

However, there's a catch. Most of these AI tests are like math problems where there's only one straight line to the answer. The AI just needs to follow the rules. But real thinking often involves exploring dead ends, backtracking, and trying different paths before finding the right one. It's about searching. The big question is: When an AI faces a problem with many possible paths, does it know how to organize its search efficiently, or does it just wander around aimlessly, wasting energy? This is the mystery researchers are trying to solve.

Enter TsuGO, a new experiment designed to peek inside the AI's brain while it plays a very specific game: Go life-and-death problems (known as tsumego). Think of these not as a full game of Go, but as a tiny, intense puzzle where a group of stones is trapped, and the player must find the one specific move to save them or kill the opponent. It's a closed world with a clear winner and loser, making it the perfect training ground to see how an AI organizes its thoughts.

The researchers built a system to turn the AI's free-flowing thoughts into a "search tree." Imagine the AI's mind as a tree growing in a garden. The trunk is the starting board. Every time the AI considers a new move, a branch grows. If that move leads to a win, the branch stays green; if it leads to a loss, it turns red. The goal isn't just to see if the AI found the green branch at the end, but to watch how it grew the tree. Did it waste time growing huge, useless branches? Did it find the right path quickly? Or did it keep circling back to the same wrong ideas?

The results are a bit of a reality check for the world of AI. The study found that even the smartest, most powerful AI models today are still far from being master searchers. When the researchers gave the AI a list of four possible moves to choose from, the better models did okay. But when they took away the list and asked the AI to find the move from scratch, many of them stumbled. They often acted like a person wandering through a dark forest with a flashlight, checking every bush randomly, rather than a detective who knows exactly where to look.

Here is the surprising part: The researchers discovered that writing more text doesn't mean the AI is thinking better. Some models produced huge, long explanations (using thousands of words) but still failed to find the right move. Others were shorter but got it right. The paper introduces a new way to measure this called "Search Efficiency." It turns out that the best models aren't the ones that talk the most; they are the ones that stop wasting time on dead-end branches and stick to the promising ones.

The study also compared these AI models to a specialized computer program called KataGo, which is designed specifically to play Go. Even the strongest AI models lagged far behind this specialized program. It suggests that while AI is getting very good at talking and following instructions, it still struggles with the internal "planning" required to navigate complex, adversarial situations where it has to predict an opponent's next move and adjust its strategy on the fly.

In short, TsuGO reveals that the next big leap for AI isn't just about making models bigger or having them talk longer. It's about teaching them how to organize their search, how to know when to give up on a bad idea, and how to focus their energy on the paths that actually matter. Until they master this, they might be able to solve a math problem, but they'll still get lost in a forest of possibilities.

Technical Summary: TsuGO

Problem Statement

Current evaluation of Large Language Model (LLM) reasoning has shifted from final-answer accuracy to process-level assessment. However, existing process-level methods primarily analyze the coherence, redundancy, and logical flow of a single Chain-of-Thought (CoT) trajectory. They largely fail to capture Search Efficiency: how models plan reasoning paths, organize search across multiple possibilities, and allocate reasoning resources (effort) among competing branches.

Most benchmarks (e.g., GSM8K, MATH) rely on static capabilities like derivation or tool use with a single objective, leaving the organization of search unmeasured. In complex, adversarial environments where models must explore alternatives, identify promising directions, and backtrack, current evaluations cannot distinguish between effective search organization and unguided, redundant exploration.

Methodology

1. The TsuGO Benchmark

The authors introduce TsuGO, a process-level benchmark based on Go life-and-death problems (tsumego). These problems were selected because they provide:

Closed and Verifiable Solution Spaces: Solutions are finite and can be rigorously checked against expert annotations and Go engines (e.g., KataGo).
Inherent Adversarial Structure: A candidate move is only valid if it survives the opponent's strongest response, forcing the model to perform candidate generation, variation reading, branch comparison, and backtracking.
Disentanglement of Knowledge and Search: By constraining the solution space, TsuGO separates domain knowledge (Go rules) from the organization of the search process itself.

Dataset Construction:

Curated from 1,500 verified tsumego problems (ranging from 15K to 7D difficulty).
Normalized into five modalities: Symbolic coordinates, Grid matrices, Visual images, and combinations thereof.
Evaluated under two conditions:
- K=4 (Bounded): The model selects the best move from four provided candidates (one correct, three distractors).
- K=None (Open): The model must generate, compare, and justify a move from the full board without candidate hints.

2. Process Search-Tree Framework

To evaluate search organization, TsuGO parses free-form CoT outputs into a structured Process Search Tree ( $T = (V, E, \tau)$ ):

Nodes: Root (initial state), Action nodes (proposed moves), and Evaluation nodes (terminal judgments: win/lose/undetermined).
Extraction: An LLM-based extractor identifies atomic steps (candidate exploration, variation reading, position evaluation, backtracking) and constructs the tree while preserving temporal order.
Validation: Structural validation ensures well-formed trees, merging duplicate actions and handling ambiguous branches.

3. Metrics

The benchmark introduces Search Efficiency (SearchE) alongside traditional Token Efficiency (TokenE):

SearchE: A composite score aggregating three signals:
- Search Waste Ratio (SWR): Fraction of resources spent on wrong branches.
- Search First Hit (SFH): Whether the correct candidate branch is explored first.
- Search Correct Rank (SCR): The rank of the correct candidate in the search order.
- Formula: $SearchE = 100 \cdot (0.5(1-SWR) + 0.3 \cdot SFH + 0.2(1-SCR))$ .
TokenE: Accuracy normalized by observable token cost ($A / (A + ITT/1000)$).
Diagnostics: Includes trajectory metrics (Max Depth, Fan-out, Node Count) and scale metrics (Total Tokens).

Key Results

Experiments were conducted on 600 problems across various state-of-the-art LLMs (including Kimi-K2.5, Qwen3-VL, DeepSeek-R1, GLM-4.6V, and Gemini models) and non-LLM baselines (MCTS/UCT and KataGo).

LLMs Lag Behind Guided Search: Even the strongest LLMs remain far from stable tsumego solving. While they outperform unguided MCTS in some settings, they are significantly weaker than neural-guided KataGo.
Search Organization is the Bottleneck:
- K=4 vs. K=None: Performance drops significantly when moving from bounded (K=4) to open (K=None) search. Strong models succeed by finding the correct candidate earlier and sustaining effort on productive branches, but many models behave closer to unguided search algorithms than to neural-guided ones.
- Token Efficiency $\neq$ Search Efficiency: Longer CoT or higher Token Efficiency does not necessarily imply better search. Some models produce long, token-efficient traces that are structurally diffuse and fail to allocate resources to the correct branch.
SearchE Correlates Better with Accuracy: SearchE aligns more consistently with task success than TokenE. TokenE is dispersed because low token cost does not guarantee effective search, whereas SearchE directly measures how resources are allocated toward the solution.
Failure Modes: Analysis reveals that failures are often due to search-resource allocation issues rather than a lack of domain knowledge. Models frequently:
- Fail to enter the correct local branch.
- Accept weak local lines as decisive.
- Drift in coordinate/state maintenance during multi-step lines.
- Prematurely terminate or abandon viable forcing branches.

Significance and Claims

The paper claims that Search Efficiency and Reasoning-Resource Allocation are missing dimensions in current LLM reasoning evaluation.

Beyond Outcome Accuracy: TsuGO demonstrates that evaluating only the final answer or the coherence of a single trajectory is insufficient for understanding how models solve complex, adversarial problems.
Diagnostic Value: By converting free-form traces into process search trees, TsuGO provides diagnostic feedback on where reasoning effort is spent, identifying bottlenecks in candidate generation, branch comparison, and backtracking.
Future Direction: The results suggest that future improvements in LLM reasoning require training frameworks that explicitly supervise search organization (e.g., branch prioritization, opponent-response verification, and state maintenance) rather than just final answers or fluent rationales.

The authors conclude that TsuGO is not yet saturated; even frontier models exhibit significant gaps in search organization compared to specialized search algorithms, highlighting a critical area for future research in autonomous reasoning.