Edges have no order — yet a prompt must list them one by one. We show that hidden choice quietly changes what an LLM understands, and how to order it well.
Take a benzene ring. List its bonds in ring order and you see it instantly; shuffle them and you have to reassemble it in your head. LLMs are no different — yet edge order is a choice every graph prompt makes silently.
This is the graph from the paper. Pick a strategy: the traversal replays on the graph while the edge list the LLM reads is rebuilt — random scatters the hub, ordered strategies surface the structure first.
Edges in arbitrary order — the model must reconstruct the structure with no hints.
We serialize a graph to an edge list, permute that list by a chosen strategy, wrap it in the task prompt with zero-shot CoT, and measure accuracy — without ever telling the model an order was applied.
"(i, j) means node i and node j are connected." A plain edge list.
Apply BFS / DFS / PageRank / PPR — or random as the baseline.
Append the task question and "let's think step by step." Order is never disclosed.
Score across 6 graph tasks × 6 mainstream LLMs.
Same eight-node graph throughout. Pick a task and watch what the question actually asks the model to trace — from a single local hop to a global tour. The harder the trace, the more the edge order matters.
Is there a path between two nodes?
Across the six tasks and six models, ordered descriptions top the random baseline — and the gains grow with task difficulty. The smallest effect is on the easiest, most local tasks; the largest on global, structure-tracing ones.
Probability-based orders generally beat traversal-based BFS/DFS, with the biggest node-classification gains.
Connectivity & cycle are robust; shortest path, Hamilton path and topological sort move the most with order.
Zero-shot, few-shot or CoT — the ordering benefit persists in every prompting regime.
We added two probe orders — Shortest-path and Longest-path. The shortest order (highest overlap with the answer path) wins; the longest (lowest overlap) loses, sometimes dropping below random. But overlap isn't the whole story: DFS overlaps the answer more than BFS, yet BFS still wins — so a structure-aware order genuinely improves the model's understanding, not just its luck.
Why does it help? The paper's hypothesis: positional encodings can't fully capture an unordered edge set, so attention gives undue priority to some positions over others — and a scattered description becomes hard to follow. Reordering the edges so the structure reads coherently works with that bias instead of against it.
In a random order, the structural edges scatter across positions — some land where attention is low, so the structure is easy to miss.
The fix is free: reorder the edges before you ask. And the right order is task-shaped — connectivity wants a local view, a Hamiltonian path wants a global one — so the best strategy follows the task, not a single rule.
@inproceedings{ge2025graphdo,
title = {Can Graph Descriptive Order Affect Solving Graph Problems with LLMs?},
author = {Yuyao Ge and Shenghua Liu and Baolong Bi and Yiwei Wang and
Lingrui Mei and Wenjie Feng and Lizhe Chen and Xueqi Cheng},
booktitle = {Proceedings of the 63rd Annual Meeting of the Association for
Computational Linguistics (ACL)},
year = {2025},
url = {https://aclanthology.org/2025.acl-long.321/}
}