Does Tree-Depth, Not Graph Size, Set Where LLM Graph Reasoning Breaks?

When a language model works through a graph problem in text, such as finding the longest shortest path in a network, it gets steadily worse as the graph grows. On the GraphArena benchmark, GPT-4o's rate of producing invalid answers on graph diameter rises from roughly 16% at 5 nodes to over 80% at 30 nodes (GraphArena). The usual explanation is size: more nodes means more tokens and more places to slip. This note proposes a different, testable explanation taken from parameterized complexity, the part of algorithm theory that explains why some problems are only fast on structured inputs. Our hypothesis is that failures track tree-depth, a measure of how deeply a graph's dependencies nest, rather than node count. We then test whether splitting the model's work along a low-depth hierarchy moves the point where it breaks down.

Tree-depth has a simple definition. It is the smallest height of a rooted forest (an elimination forest) on the graph's nodes such that every edge connects a node to one of its ancestors. A path of $n$ nodes has tree-depth about $\log_2 n$. A $k\times k$ grid has tree-depth on the order of $k$. A clique has tree-depth $n$. Algorithm theory already uses this parameter to cut polynomial running times: On the Power of Tree-Depth for Fully Polynomial FPT Algorithms shows that problems like weighted matching and negative-cycle detection, which have cubic or quadratic lower bounds on general graphs, run in $O(d(m+n\log n))$ when given an elimination forest of depth $d$. Here $m$ is the number of edges and $n$ the number of nodes. Our bet is that the same parameter measures how hard a graph is for a model reasoning in context. It also tells us how to decompose the problem: the model handles one subtree at a time and keeps only the at most $d$ ancestor nodes in view.

Core Claim

The claim has two parts, and each can be falsified on its own. The first is diagnostic. Hold node count fixed and vary tree-depth, and the model's rate of invalid answers should move with $d$. Hold $d$ fixed and vary $n$, and it should move much less. Concretely, we fit a logistic model of per-instance failure,

$$\Pr[\text{fail}] = \sigma(\beta_0 + \beta_n \log n + \beta_d\, d + \beta_m \log m),$$

where $\sigma$ is the logistic function and $m$ the edge count. We predict that $\beta_d$ dominates, and that $d$ alone explains more held-out variance than $n$ and $m$ together. We include $m$ so that tree-depth is not just standing in for "more edges to read."

The second part is an intervention, which we call elimination-forest prompting. A classical heuristic computes an elimination forest; we use depth-first-search trees and minimum-degree elimination, since computing the optimal forest is NP-hard, as the tree-depth paper notes. The model then solves the task bottom-up. Each call sees one subtree's summary messages and the edges to its at most $d$ ancestors, and nothing else. For shortest distance, the summaries are distances to ancestors. For maximum independent set, they are best set sizes for each ancestor assignment, which is feasible only for small $d$. We predict that this keeps the failure rate roughly flat in $n$ at fixed $d$.

The idea extends divide-and-conquer prompting to the case where it currently fails. When Splitting Makes Stronger proves that splitting a task into sub-tasks and solving each in a clean context helps on hard, hallucination-prone tasks. It assumes the sub-tasks are nearly independent. Divide-and-Conquer CoT trains a director model with reinforcement learning to hand out parallel sub-tasks to worker models, but to cut latency rather than to handle coupled structure. Graphs with cycles violate the independence assumption. An elimination forest is the textbook way to make coupled sub-problems interact only through a small, explicit set of shared ancestors.

Relation to Prior Work

GraphArena motivates the work: it documents the wall but characterizes it only by node count. GraphThought supplies the strongest trained competitor. It fine-tunes an 8B model on reasoning traces distilled from classical algorithms and exact solvers, and matches Gurobi on hard maximum independent set with average solution size 12.570. It reasons sequentially over the whole graph and degrades on large graphs. We change the structure of inference rather than the training data, and the two approaches could be combined.

Three papers constrain the design. Beyond Code shows that plans a model writes for itself can hurt, with Step-wise Similarity to expert plans of only 5.16% for CodeGen-350M. Externally supplied plans raised Starcoderbase-1B's Pass@5 from 5.15% to 12.40%. We therefore compute the decomposition classically and do not ask the model to invent it. Can Large Language Models Always Solve Easy Problems if They Can Solve Harder Ones? warns that models fail inconsistently across difficulty, so we analyze matched instance families rather than aggregate accuracy. ReTreVal searches over reasoning branches with tool-based verification and backtracking. That tree is a search over interpretations, unrelated to the input's structure, and it costs about 2.3 times the tokens of Self-Refine. Our tree comes from the input, and its cost is fixed in advance.

Research Program

We will build instance families in which $n$ and $d$ vary independently. Paths and balanced binary trees give $d\approx\log n$. Grids and "caterpillar-of-cliques" graphs let $d$ grow at chosen rates. Sparse random graphs with planted separators fill in the middle. Edge counts are matched within each family where possible.

The tasks come from GraphArena's polynomial-time set (shortest distance and diameter) plus negative-cycle detection from the tree-depth paper. Maximum independent set serves as an NP-hard control where tree-depth-based dynamic programming is exact but exponential in $d$. We will reuse GraphArena's three-stage scoring: answer extraction, feasibility (an infeasible answer counts as a hallucination), and optimality. We will also re-score GraphArena's real graphs, drawn from DBLP, social, DBpedia, flight and molecule networks, with heuristic tree-depth upper bounds. That tells us whether the relationship holds on real rather than synthetic structure.

Molecular graphs from PubChemQC have small tree-depth. Social graphs do not. That gives a natural contrast within the published benchmark.

Baselines

The naive reference is direct answering with chain-of-thought on the full graph, using the same models GraphArena evaluates. Its reported hallucination rate on diameter, 16% at 5 nodes rising to over 80% at 30 (GraphArena), is the curve we expect to reproduce and then flatten. Plain divide-and-conquer prompting in the style of When Splitting Makes Stronger is the closest prompting competitor. On their long-multiplication task they report 76.92 F1 against 69.41 for Tree-of-Thoughts. We run it with a balanced but structure-blind split of the nodes, so it receives the same number of calls and tokens as our method.

The strongest trained competitor is GraphThought-style fine-tuning. Its reported result is solution size 12.570 on hard maximum independent set, which ties Gurobi. We will compare on the same graph sizes it was evaluated on and on larger ones, and we will apply elimination-forest prompting to the same 8B base model so that model scale is matched.

The strongest practical competitor is having the model write and run code, which GraphArena reports partly buffers hallucination. For its exact rates, no reported result found on Lacuna. We run it with the same model and a fixed number of retries.

The key ablation keeps the call structure and token budget of elimination-forest prompting but swaps in a bad forest. One version uses a random rooted forest of equal height that is not a valid elimination forest, so some edges cross between branches. Another uses a valid forest deliberately inflated to depth $2d$. Beating it means structure, not merely splitting, produces the gain. A second ablation hands the model the valid forest but asks it to reason over the whole graph in one context. That separates "knowing the structure" from "isolating contexts."

Beating a baseline means one of two things. The first is a statistically lower infeasibility rate at matched token budget on graphs larger than 30 nodes. The second is a failure curve that is flat in $n$ at fixed $d$ where the baseline's curve rises.

Why not just…?

Why not just have the model write code? For textbook tasks like shortest distance, code calling a graph library will probably beat any text-reasoning method, and we will report that. The proposal is not a claim that models should solve diameter in prose. It is a claim about what governs in-context reasoning failure, and about a decomposition that applies when code is not a clean fit. That includes graphs described implicitly in natural language, or steps that need judgment the model cannot hand to a library. We will also measure whether the correctness of generated code depends on $d$. If it does not, that bounds where our result matters.

Why not just use a stronger reasoning model with a longer chain of thought? More tokens do not remove the fact that everything stays in one context, and GraphArena's wall appears in frontier models. The diagnostic experiment settles this directly. If a long-reasoning model's failures stop depending on $d$, the hypothesis is wrong for that model class, and we will say so.

Why not just fine-tune, as GraphThought does? Fine-tuning is a real threat on small graphs. The open question is behavior beyond the training sizes, where GraphThought reports degradation. We test fine-tuned and prompted variants on the same model at sizes beyond training, and also test them combined. The combination is the likely best system, not a rival.

Why not just use verified tree search like ReTreVal? Verification catches errors after the fact at roughly twice the token cost. Our method tries to keep each context small enough that errors are rarer to begin with. We compare at an equal token budget. If search with verification matches us there, the decomposition adds nothing beyond compute.

Decisive Checks

The work stands or falls on two results. First, on matched synthetic families, $d$ must predict held-out failure better than $n$ and $m$ together. If it does not, the diagnostic claim fails and the intervention has no rationale. Second, elimination-forest prompting must beat the invalid-forest ablation at equal token budget, with the gap widening as $n$ grows at fixed $d$. If a structure-blind split performs as well, the benefit comes from shorter contexts, not from complexity theory. That would be a useful negative result for anyone hoping to import structural parameters into prompting.