Built on

Goldberg, A. V., and Harrelson, C. (2005, January). Computing the shortest path: A search meets graph theory. In SODA (Vol. 5, pp. 156-165)
2005
Earlier work this paper cites.
Hinton, Geoffrey E. and Osindero, Simon and Teh, Yee Whye: A Fast Learning Algorithm for Deep Belief Nets. Neural Computation 18
2006
Earlier work this paper cites.
Bengio, Yoshua and LeCun, Yann: Scaling Learning Algorithms Towards AI. In: Large Scale Kernel Machines. MIT Press (2007)
2007
Earlier work this paper cites.
Goodfellow, Ian and Bengio, Yoshua and Courville, Aaron: Deep learning, vol. 1. MIT Press (2016)
2016
Earlier work this paper cites.
Chen, Z., Chen, L., Villar, S., and Bruna, J. (2020). Can graph neural networks count substructures?. Advances in neural information processing systems, 33, 10383-10395
2020
Earlier work this paper cites.
Adhikari, Ashutosh and Yuan, Xingdi and others: Learning dynamic belief graphs to generalize on text-based games. Advances in Neural Information Processing Systems 33
2020
Earlier work this paper cites.
Brown, Tom and Mann, Benjamin and others: Language models are few-shot learners. Advances in neural information processing systems 33
2020
Earlier work this paper cites.
Wei, Jason and Wang, Xuezhi and others: Chain-of-thought prompting elicits reasoning in large language models. Advances in Neural Information Processing Systems 35
2022
Earlier work this paper cites.
Jin, B., Liu, G., Han, C., Jiang, M., Ji, H., & Han, J. (2023). Large language models on graphs: A comprehensive survey. arXiv preprint arXiv:2312.02783
Original
2023
Earlier work this paper cites.
Liu, C., and Wu, B. (2023). Evaluating large language models on graphs: Performance insights and comparative analysis. arXiv preprint arXiv:2308.11224
Original
2023
Earlier work this paper cites.

Similar

Fatemi, B., Halcrow, J., and Perozzi, B. (2023). Talk like a graph: Encoding graphs for large language models. arXiv preprint arXiv:2310.04560
Original
2023
Cited alongside, same era.
White, Jules and Fu, Quchen and Hays, Sam and others: A prompt pattern catalog to enhance prompt engineering with ChatGPT. arXiv preprint arXiv:2302.11382 (2023)
Original
2023
Cited alongside, same era.
Choudhary, Nurendra and Reddy, Chandan K: Complex Logical Reasoning over Knowledge Graphs using Large Language Models. arXiv preprint arXiv:2305.01157 (2023)
Original
2023
Cited alongside, same era.
Zelikman, Eric and Huang, Qian and others: Parsel: A (de-)compositional framework for algorithmic reasoning with language models. Advances in Neural Information Processing Systems (Spotlight) (2023)
2023
Cited alongside, same era.

Then

OpenAI: GPT-4 Technical Report. arXiv:2303.08774 (2023)
Original
2023
Later among the works it cites.
Qiao, Shuofei and Ou, Yixin and others: Reasoning with language model prompting: A survey. Association for Computational Linguistics (2023)
2023
Later among the works it cites.
Chai, Ziwei and Zhang, Tianjie and others: Graphllm: Boosting graph reasoning ability of large language model. arXiv preprint arXiv:2310.05845 (2023)
Original
2023
Later among the works it cites.
Saba, Walid S: Stochastic LLMs do not Understand Language: Towards Symbolic, Explainable and Ontologically Based LLMs. In: International Conference on Conceptual Modeling, pp. 3–19. Springer (2023)
2023
Later among the works it cites.
Wang, Xuezhi and Wei, Jason and others: Self-consistency improves chain of thought reasoning in language models. International Conference on Learning Representations (poster) (2023)

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…

2024

Can LLMs perform structured graph reasoning?

Agrawal, Palaash, Vasania, Shavak, Tan, Cheston

Understand

Pretrained Large Language Models (LLMs) have demonstrated various reasoning capabilities through language-based prompts alone, particularly in unstructured task settings (tasks purely based on language semantics).

However, LLMs often struggle with structured tasks, because of the inherent incompatibility of input representation.
Reducing structured tasks to uni-dimensional language semantics often renders the problem trivial.
Keeping the trade-off between LLM compatibility and structure complexity in mind, we design various graph reasoning tasks as a proxy to semi-structured tasks in this paper, in order to test the ability to navigate through representations beyond plain text in various LLMs.

Built on

Goldberg, A. V., and Harrelson, C. (2005, January). Computing the shortest path: A search meets graph theory. In SODA (Vol. 5, pp. 156-165)
2005
Earlier work this paper cites.
Hinton, Geoffrey E. and Osindero, Simon and Teh, Yee Whye: A Fast Learning Algorithm for Deep Belief Nets. Neural Computation 18
2006
Earlier work this paper cites.
Bengio, Yoshua and LeCun, Yann: Scaling Learning Algorithms Towards AI. In: Large Scale Kernel Machines. MIT Press (2007)
2007
Earlier work this paper cites.
Goodfellow, Ian and Bengio, Yoshua and Courville, Aaron: Deep learning, vol. 1. MIT Press (2016)
2016
Earlier work this paper cites.
Chen, Z., Chen, L., Villar, S., and Bruna, J. (2020). Can graph neural networks count substructures?. Advances in neural information processing systems, 33, 10383-10395
2020
Earlier work this paper cites.
Adhikari, Ashutosh and Yuan, Xingdi and others: Learning dynamic belief graphs to generalize on text-based games. Advances in Neural Information Processing Systems 33
2020
Earlier work this paper cites.
Brown, Tom and Mann, Benjamin and others: Language models are few-shot learners. Advances in neural information processing systems 33
2020
Earlier work this paper cites.
Wei, Jason and Wang, Xuezhi and others: Chain-of-thought prompting elicits reasoning in large language models. Advances in Neural Information Processing Systems 35
2022
Earlier work this paper cites.
Jin, B., Liu, G., Han, C., Jiang, M., Ji, H., & Han, J. (2023). Large language models on graphs: A comprehensive survey. arXiv preprint arXiv:2312.02783
Original
2023
Earlier work this paper cites.
Liu, C., and Wu, B. (2023). Evaluating large language models on graphs: Performance insights and comparative analysis. arXiv preprint arXiv:2308.11224
Original
2023
Earlier work this paper cites.

Similar

Fatemi, B., Halcrow, J., and Perozzi, B. (2023). Talk like a graph: Encoding graphs for large language models. arXiv preprint arXiv:2310.04560
Original
2023
Cited alongside, same era.
White, Jules and Fu, Quchen and Hays, Sam and others: A prompt pattern catalog to enhance prompt engineering with ChatGPT. arXiv preprint arXiv:2302.11382 (2023)
Original
2023
Cited alongside, same era.
Choudhary, Nurendra and Reddy, Chandan K: Complex Logical Reasoning over Knowledge Graphs using Large Language Models. arXiv preprint arXiv:2305.01157 (2023)
Original
2023
Cited alongside, same era.
Zelikman, Eric and Huang, Qian and others: Parsel: A (de-)compositional framework for algorithmic reasoning with language models. Advances in Neural Information Processing Systems (Spotlight) (2023)
2023
Cited alongside, same era.

Then

OpenAI: GPT-4 Technical Report. arXiv:2303.08774 (2023)
Original
2023
Later among the works it cites.
Qiao, Shuofei and Ou, Yixin and others: Reasoning with language model prompting: A survey. Association for Computational Linguistics (2023)
2023
Later among the works it cites.
Chai, Ziwei and Zhang, Tianjie and others: Graphllm: Boosting graph reasoning ability of large language model. arXiv preprint arXiv:2310.05845 (2023)
Original
2023
Later among the works it cites.
Saba, Walid S: Stochastic LLMs do not Understand Language: Towards Symbolic, Explainable and Ontologically Based LLMs. In: International Conference on Conceptual Modeling, pp. 3–19. Springer (2023)
2023
Later among the works it cites.
Wang, Xuezhi and Wei, Jason and others: Self-consistency improves chain of thought reasoning in language models. International Conference on Learning Representations (poster) (2023)

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Shridhar, Kumar and Stolfo, Alessandro and others: Distilling multi-step reasoning capabilities of large language models into smaller models via semantic decompositions. Association for Computational Linguistics (2023)

2023

Cited alongside, same era.

Yuan, Zheng and Yuan, Hongyi and others: Scaling relationship on learning mathematical reasoning with large language models. arXiv preprint arXiv:2308.01825 (2023)

Original

2023

Cited alongside, same era.

Wang, Heng and Feng, Shangbin and others: Can Language Models Solve Graph Problems in Natural Language?. Advances in Neural Information Processing Systems (Spotlight) (2023)

2023

Cited alongside, same era.

Touvron, Hugo and Martin, Louis and others: Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.09288 (2023)

Original

2023

Cited alongside, same era.

Anil, Rohan and Dai, Andrew M and others: Palm 2 technical report. arXiv preprint arXiv:2305.10403 (2023)

Original

2023

Cited alongside, same era.

2023

Later among the works it cites.

Zhang, Z., Wang, X., Zhang, Z., Li, H., Qin, Y., Wu, S., and Zhu, W. . LLM4DyG: Can Large Language Models Solve Problems on Dynamic Graphs?. Association for Computing Machinery (2024)

2024

Closest in time.

Bian, Ning and Han, Xianpei and others: ChatGPT is a knowledgeable but inexperienced solver: An investigation of commonsense problem in large language models. Proceedings of the 2024 Joint International Conference on Computational Linguistics, Language Resources and Evaluation (LREC-COLING 2024)

2024

Closest in time.

Wu, Sean and Koo, Michael and others: A Comparative Study of Open-Source Large Language Models: GPT-4 and Claude 2: Multiple-Choice Test Taking in Nephrology. NEJM AI (2024)

2024

Closest in time.

Creswell, Antonia and Shanahan, Murray: Faithful reasoning using large language models. International Conference on Learning Representations (poster) (2024)

2024

Closest in time.