Same graph. Different answer.
Renaming a node leaves the answer unchanged. It can still change the text a model must read and keep track of.
New: triangle confirmation results → · Difficulty study
What we can prove
For these six tasks, a one-to-one change of node names preserves the correct answer, provided the query nodes, blocked nodes, edges and weights are carried along with the renaming.
The mathematical argument
Let π be a bijection on node identifiers. For a graph G and query q, the exact answer satisfies a(πG, πq) = a(G, q). Renaming pairs every path, walk, triangle and cut with exactly one corresponding object. It preserves adjacency, path lengths, weights and query constraints, so the requested count, optimum or reachability value is unchanged.
For an undirected simple graph with adjacency matrix A, the triangle count is tr(A³)/6. Renaming by a permutation matrix P gives A′ = PAPᵀ, and tr((A′)³) = tr(PA³Pᵀ) = tr(A³). Every triangle contributes six closed walks of length three.
This proves the task’s invariance. It does not prove that a text model implements an invariant algorithm. Our renaming check is a test of that behavior.
There is also a simple error bound. On paired completed numeric answers to the same uniquely answered question, let d be the fraction that disagree, and let e₁ and e₂ be the two error rates. Then d ≤ e₁ + e₂: whenever the answers differ, at least one is wrong. Thus their average error is at least d/2. Agreement alone proves nothing; both answers can be wrong. The bound describes observed answers, not a causal effect of renaming, and identical-prompt repeats provide a control for ordinary variation.
Triangle counting itself has a direct exact algorithm: enumerate all unordered triples and check their three edges, using O(n³) adjacency checks. A model’s failure on this task is not evidence that it faces an intractable graph problem; the unresolved question is how it represents and executes the computation from text.
What could explain the errors?
These are hypotheses and proposed tests, not conclusions about a model’s internals.
| Possible explanation | A useful test |
|---|---|
| Names change tokenization or make identifiers easier to confuse. | Vary label vocabulary and length; measure each model’s tokenization and test multiple random renamings. |
| The model loses track of edges, counts a triangle twice or makes an arithmetic error. | Check saved intermediate claims against exact edges and counts. In a separate diagnostic condition, request a verifiable certificate. |
| A structural shortcut depends on familiar or meaningful names. | Compare neutral names with role-correlated and role-reversed names while controlling order and token length. |
| The response needs more space than the cap allows. | Report completion and accuracy separately; use a predeclared budget sweep on fresh cases. |
| The answer changed through ordinary sampling variation. | Include several identical-prompt repeats alongside independent renamings on the same graphs. |
Claude’s four selected triangle errors finished normally, so hitting the output cap does not explain those four errors. We have not isolated the remaining causes.
Can we use chain of thought or mechanistic interpretability?
Saved explanations can identify checkable mistakes. They are not a faithful readout of internal computation: Turpin et al. (2023) show that explanations can omit factors that influence an answer.
API responses support behavioral analysis. A mechanistic claim needs access to internal activations and controlled interventions, such as changing an activation and testing whether a specific error changes. An open-weight model could support a separate study. A probe or an attention picture alone would not establish a cause.
What is missing from our coverage?
The difficulty study plans nine configurations, with full coverage for five. Grok, Kimi, Mistral and DeepSeek were represented in earlier work, but lack a matched evaluation on these 72 graphs. See the 21-model pilot and run history; their scores cannot fill the gaps here.
Useful candidates for a future matched study include Grok, Kimi, Mistral and DeepSeek. A small open-weight family such as Gemma would also help separate model scale from provider effects. This is a research shortlist, not a scheduled run.
More independent graphs and repeated controls matter as much as more families. We also need tokenization and edge-order controls, completion curves, and a separate tool-assisted baseline. Exact program solvers provide the answer reference; tool-assisted model scores would be reported separately.
How this relates to earlier work
NLGraph (Wang et al., 2023) already tested basic graph problems and found sensitivity to spurious correlations. Talk like a Graph (Fatemi et al., 2023) showed that graph encodings affect performance. Our contribution must be assessed against this work: paired renaming controls, exact answers and explicit completion accounting, rather than a claim that graph reasoning evaluation is new.
The fresh-graph test is complete
On 96 fresh graphs, Claude Sonnet 5.5 answered 83 original prompts correctly and 60 renamed prompts correctly: a 24-point drop in the predeclared paired comparison (exact McNemar p = 0.00043). None of the 576 study responses hit the completion limit.
The three unchanged-prompt repetitions averaged 86.1% accuracy; three neutral renamings averaged 66.7%. This exploratory repeat analysis supports the same direction. The result establishes a behavioral effect for this configuration and graph family, not its internal cause.
See the full results, controls and downloads →
The next diagnostic step is to separate label mapping, tokenization and enumeration errors with controlled interventions. No additional paid run is scheduled.