SourceTalk like a Graph: Encoding Graphs for Large Language Models
On ER graphs, 53.96% of edge-existence queries have no edge and 81.96% of cycle-check queries have a cycle, yet PaLM 62B scores below the majority baseline on both tasks. When graph structure is varied, the effect is dramatic: cycle check accuracy is 91.7% on complete graphs (which always have cycles) but only 5.9% on path graphs (which never have cycles) under zero-shot prompting. Similarly, edge existence accuracy is 60.9% on path graphs (few edges) but 19.8% on complete graphs (all edges present). The authors attribute this to the LLM having a strong prior towards graphs having cycles and a prior that two nodes are more likely to be disconnected.