PaperlayerView exact revision on arXiv

Source-linked AI summary

Can Language Models Solve Graph Problems in Natural Language?

Heng Wang, Shangbin Feng, Tianxing He, Zhaoxuan Tan, Xiaochuang Han, Yulia Tsvetkov

arXiv:2305.10037v3cs.CLcs.AI

TL;DR

The paper asks whether LLMs can explicitly solve graph algorithm problems expressed in natural language, beyond tasks with implicit graphical structure. It introduces and evaluates the NLGraph benchmark with prompting approaches, finding preliminary graph reasoning abilities but brittleness and diminishing benefits on complex problems; its proposed prompts yield gains of 3.07% to 16.85% across multiple tasks.

  • Problem

    Whether LLMs can explicitly process natural-language graph descriptions and perform structured graph operations remains underexplored despite their use in tasks with implicit graphical structures.

  • Method

    The paper constructs NLGraph, a 29,370-problem benchmark covering eight graph reasoning tasks with varied complexity, and evaluates LLMs and prompting techniques on it.

  • Results

    LLMs show preliminary graph reasoning abilities, while advanced prompting and in-context learning provide diminishing benefits on complex tasks and LLMs remain brittle to spurious correlations.

  • Takeaways & Limitations

    Build-a-Graph and Algorithmic Prompting improve performance by 3.07% to 16.85% across multiple tasks, but improving performance on the most complex graph problems remains open.

  • Takeaways & Limitations

    The proposed instruction-based prompting methods work to varying extents on easy problems but have only marginal effects on more complex graph reasoning problems.

Abstract

from arXiv · show

Large language models (LLMs) are increasingly adopted for a variety of tasks with implicit graphical structures, such as planning in robotics, multi-hop question answering or knowledge probing, structured commonsense reasoning, and more. While LLMs have advanced the state-of-the-art on these tasks with structure implications, whether LLMs could explicitly process textual descriptions of graphs and structures, map them to grounded conceptual spaces, and perform structured operations remains underexplored. To this end, we propose NLGraph (Natural Language Graph), a comprehensive benchmark of graph-based problem solving designed in natural language. NLGraph contains 29,370 problems, covering eight graph reasoning tasks with varying complexity from simple tasks such as connectivity and shortest path up to complex problems such as maximum flow and simulating graph neural networks. We evaluate LLMs (GPT-3/4) with various prompting approaches on the NLGraph benchmark and find that 1) language models do demonstrate preliminary graph reasoning abilities, 2) the benefit of advanced prompting and in-context learning diminishes on more complex graph problems, while 3) LLMs are also (un)surprisingly brittle in the face of spurious correlations in graph and problem settings. We then propose Build-a-Graph Prompting and Algorithmic Prompting, two instruction-based approaches to enhance LLMs in solving natural language graph problems. Build-a-Graph and Algorithmic prompting improve the performance of LLMs on NLGraph by 3.07% to 16.85% across multiple tasks and settings, while how to solve the most complicated graph reasoning tasks in our setup with language models remains an open research question. The NLGraph benchmark and evaluation code are available at https://github.com/Arthur-Heng/NLGraph.

1 Introduction

The paper investigates whether LLMs can explicitly solve graph algorithm problems described in natural language. It introduces NLGraph, evaluates prompting methods, and finds preliminary abilities alongside brittleness and diminishing gains on complex tasks.

  • Research question: The study addresses whether LLMs can explicitly process textual graph descriptions and perform graph algorithm operations, a question relevant to applications involving implicit graphs and structures.Motivating applications include robotics planning, theory-of-mind reasoning, structured commonsense reasoning, and multi-hop question answering.
  • Benchmark: NLGraph contains 29,370 natural-language problems spanning eight graph reasoning tasks from connectivity and shortest path to maximum flow and graph neural network simulation.The benchmark controls difficulty through graph size, sparsity, numeric range, and related factors, with easy, medium, and hard subsets.
  • Findings: LLMs perform 37.33% to 57.82% above the random baseline on simple tasks including connectivity, cycle, and shortest path.Chain-of-thought prompting can further improve performance while producing sound and accurate intermediate steps.
  • Findings: Advanced prompting methods improve simple graph reasoning but are mostly ineffective or counterproductive on complex problems such as topological sort and Hamilton path.The reported approaches include chain-of-thought, least-to-most, and self-consistency prompting.
  • Proposed methods: Build-a-Graph and Algorithmic Prompting improve performance by 3.07% to 16.85% across multiple tasks and settings.Build-a-Graph grounds textual graph descriptions in conceptual spaces, whereas Algorithmic Prompting revisits algorithmic steps before using examples.

2 The NLGraph Benchmark

NLGraph is a natural-language benchmark that generates graph problems across eight tasks and controls their complexity through graph structure, task-specific edits, and difficulty subsets. It evaluates solutions with exact, validity, and partial-credit metrics.

  • Graph generation: Randomly generated base graphs vary in node count and edge probability to control structural complexity, with directedness determined by the task.Task-specific graph edits and other difficulty factors are added after base-graph generation.
  • Task design: The benchmark asks models to solve natural-language formulations of graph tasks, including valid topological orderings, shortest paths, matchings, Hamilton paths, and message passing.An external program checks correctness for several generated solutions, including topological sorts, matchings, Hamilton paths, and graph-neural-network embeddings.
  • Difficulty control: Each task includes difficulty-controlled subsets, with easy, medium, and hard variants for simpler tasks and easy and hard variants for advanced tasks.Difficulty is adjusted using graph size, sparsity, and other task-specific factors.
  • Benchmark statistics: The standard and extended benchmark versions contain 5,902 and 29,370 problems, respectively.Table 1 reports benchmark statistics and difficulty specifications for the task subsets.
  • Evaluation: Evaluation uses accuracy or exact match by default, with additional partial-credit metrics for shortest path, maximum flow, and graph neural network tasks.Shortest-path partial credit is based on the rank of the predicted valid path, while graph-neural-network partial credit measures correct node embeddings and relative error.

3 Experimental Settings

The experiments evaluate language models on NLGraph using prompting baselines ranging from zero-shot to self-consistency. They compare these approaches against randomized task-specific baselines and test multiple model settings.

  • Experimental goals: The study evaluates whether language models solve graph algorithm problems in natural language and whether prompting approaches improve graph reasoning.The evaluation is conducted on the NLGraph benchmark.
  • Prompting baselines: Baselines include zero-shot, few-shot, chain-of-thought, zero-shot chain-of-thought, least-to-most, and self-consistency prompting.These approaches are applied across graph reasoning tasks in NLGraph.
  • Random baseline: The RANDOM baseline samples task-appropriate answers, enabling comparison between prompting methods and chance-like behavior.For true/false tasks its expected accuracy is 50%; for shortest path it selects a random valid path, and for maximum flow it samples a value within the permitted range.
  • Models and settings: TEXT-DAVINCI-003 is the default model, with GPT-3.5-TURBO, CODE-DAVINCI-002, and GPT-4 evaluated additionally.Most baselines use temperature τ = 0, while self-consistency samples five chain-of-thought responses at τ = 0.7.

4 Results

LLMs show preliminary graph reasoning abilities on simple tasks, but prompting benefits diminish on complex problems, where models are vulnerable to spurious correlations and invalid intermediate reasoning.

  • Advanced prompting: FEW-SHOT prompting outperforms COT+SC on both easy and hard maximum flow subsets, suggesting difficulty generating valid intermediate steps.COT, LTM, and self-consistency are mostly ineffective on topological sort.
  • Advanced prompting: Chain-of-thought and self-consistency improve simple graph reasoning, including graph neural network simulation, but can be ineffective or counterproductive on complex tasks.The mixed prompting effects appear across simple tasks, graph neural network simulation, topological sort, and maximum flow.
  • In-context learning: Zero-shot prompting consistently outperforms other techniques on Hamilton path, while in-context learning and advanced prompting have mostly marginal effects on bipartite matching.Few-shot learning underperforms zero-shot learning by 1.00% to 10.48% on Hamilton path and bipartite graph matching.
  • In-context learning: Increasing the number of Hamilton path exemplars does not improve performance, which remains below zero-shot prompting in both difficulty settings.These results suggest that in-context learning can be counterproductive for complex structured reasoning.
  • Spurious correlations: Connectivity performance drops by more than 40% on chain and clique special cases, indicating vulnerability to spurious correlations in problem settings.The special cases invert the usual relationship between node degree, mention frequency, and connectivity.

5 Making Language Models Better Graph Reasoners

The paper proposes two instruction-based prompting techniques that ground graph descriptions and revisit relevant algorithms. They improve performance on easier tasks, but complex graph reasoning remains unresolved.

  • Methods: Build-a-Graph prompting asks LLMs to construct nodes and edges first, encouraging conceptual grounding before solving the graph problem.The instruction is appended after the graph description to support an implicit mental sketchpad.
  • Methods: Algorithmic prompting supplies the relevant algorithm before in-context examples, encouraging LLMs to revisit and recite task-specific solution steps.For shortest path, the prompt provides a Depth-First Search algorithm description.
  • Evaluation: The two approaches are evaluated together with chain-of-thought prompting on three representative NLGraph tasks spanning different difficulties.Figure 5 illustrates the prompting designs and their generated instructions.
  • Results: 3.07% to 16.85% performance gains occur on the easier cycle and shortest path tasks with the proposed instructions.The gains are reported across the two tasks.
  • Results: The instructions are largely ineffective on the more complex Hamilton path task, leaving complex graph reasoning an open research question.The benchmark can support evaluation of future instructions and solutions for improving graph reasoning.

6 Related Work

Prior work studies LLMs in few-shot arithmetic, mathematical, logical, commonsense, and algorithmic reasoning settings. NLGraph extends this evaluation focus to explicit graph reasoning in natural language.

  • LLMs have been applied to implicit graph tasks including structured planning, commonsense planning, and theory-of-mind reasoning.
  • Few-shot reasoning research evaluates LLMs on arithmetic, mathematical proof, logical, and commonsense reasoning tasks.
  • Related work also explores evaluating and augmenting the algorithmic reasoning abilities of large language models.

7 Conclusion

The paper introduces NLGraph to evaluate whether LLMs can solve explicit graph algorithm problems in natural language across tasks of varying complexity. Results show preliminary abilities, brittleness and diminishing prompting benefits on complex tasks, while the proposed prompts improve performance; stronger complex-task solutions remain open.

  • NLGraph contains 29,370 natural-language problems spanning eight graph reasoning tasks with varying complexity.
  • LLMs show preliminary graph reasoning abilities, but advanced prompting and in-context learning may help less on complex tasks and remain brittle to spurious correlations.
  • Build-a-Graph and Algorithmic Prompting are simple instruction-based approaches that produce notable gains across multiple tasks.
  • The benchmark connects explicit graph reasoning with applications involving implicit graphical structures and structural reasoning.
  • Evaluating fine-tuning on graph-based chain-of-thought reasoning is identified as a direction for future work.

B Limitations

The paper identifies limitations in benchmark coverage, evaluated models, evaluation scale, and prompting effectiveness on complex graph problems.

  • The benchmark includes eight graph reasoning tasks but omits other algorithms such as Eulerian path, minimum spanning tree, and cut-edge.
  • Only four black-box LLMs are evaluated, leaving graph reasoning in other open-source LLMs for future work.
  • The experiments use 5,902 standard-benchmark problems because of monetary costs, while an extended version contains five times more problems.
  • The proposed instruction-based methods work variably on easy problems but have marginal effects on more complex graph reasoning problems.

D Analysis

Additional analyses show that instruction wording, graph descriptions, path length, exemplar difficulty, and scoring choices affect measured performance. These results highlight sensitivity to problem presentation and uncertainty in some apparent gains.

  • Instruction variants: Replacing instructions with dots tests whether gains arise from natural-language content or increased computation.
  • Graph definition variants: Changing nodes, edges, and weights into cities, roads, and distances improves easy-subset performance but reduces hard-subset performance.
  • Graph definition variants: Table 9 reports shortest-path performance after graph descriptions are changed to cities, roads, and distances.
  • Problem scale: Shortest-path accuracy steadily drops as the number of nodes on the optimal path increases.
  • In-context exemplars: Cycle-task performance drops when in-context exemplars become more difficult, indicating difficulty learning from those exemplars.
  • Partial credit: On hard maximum-flow subsets, chain-of-thought has the highest partial-credit performance, but its combination with self-consistency drops significantly.

E.1 CODE-DAVINCI-002 Results

CODE-DAVINCI-002 is evaluated on cycle, shortest path, and Hamilton path, with findings broadly matching TEXT-DAVINCI-003: preliminary reasoning on easy tasks but limited gains from advanced prompting on complex problems.

  • CODE-DAVINCI-002 is evaluated on cycle, shortest path, and Hamilton path.
  • Language models act as preliminary graph reasoners on easy tasks, while in-context learning and advanced prompting provide limited benefit on more complex problems.
  • COT and COT+SC results are omitted because CODE-DAVINCI-002 generates too many tokens before reaching the final answer.

E.2 OPT Results

The paper fine-tunes OPT-2.7B using generated zero-shot solutions from NLGraph training problems and evaluates it on a 1,000-problem test set. Additional qualitative evaluation examines GPT-3.5-TURBO and GPT-4 across representative cases, finding GPT-4 stronger but not robust.

  • OPT-2.7B fine-tuning: OPT-2.7B is fine-tuned on nine text corpora built from 4,902 NLGraph training problems and evaluated on 1,000 test problems.The corpora are organized by task plus one corpus concatenating all task text.
  • Qualitative evaluation: Qualitative analysis evaluates GPT-3.5-TURBO and GPT-4 on 19 representative problems spanning the eight tasks.The results are reported in Tables 11–15.
  • Qualitative evaluation: GPT-4 demonstrates better graph reasoning abilities than GPT-3.5-TURBO but remains far from a robust reasoner for graph-based problems.
Loading 2305.10037v3…