标题： 变压器可以在某些图中学习连接性，但不能在其他图中学习 显示英文标题

标题： Transformers Can Learn Connectivity in Some Graphs but Not Others

摘要： 推理能力对于确保基于Transformer的大语言模型（LLMs）的响应的真实性至关重要，而对传递关系的稳健推理在许多场景中至关重要，例如因果推断。 因此，研究Transformer在推断传递关系任务中的能力是至关重要的（例如，知道A导致B，B导致C，那么A导致C）。 推断传递关系的任务等同于有向图中的连通性任务（例如，知道从A到B有一条路径，从B到C有一条路径，那么从A到C有一条路径）。 过去的研究集中在Transformer是否能够从输入提示中提供的上下文示例中学习推断传递性。 然而，Transformer从训练示例中推断传递关系的能力以及扩展如何影响这种能力尚未被探索。 在本研究中，我们通过生成有向图来训练不同规模的Transformer模型，并评估它们在各种图大小下推断传递关系的能力，以回答这个问题。 我们的发现表明，Transformer能够在“网格状”有向图上学习连通性，其中每个节点可以嵌入到低维子空间中，并且可以从节点的嵌入中轻松推断出连通性。 我们发现底层网格图的维度是Transformer学习连通性任务能力的强预测因子，高维网格图比低维网格图更具挑战性。 此外，我们观察到，增加模型规模会导致对网格图上连通性的泛化能力不断提高。 然而，如果图不是网格图并且包含许多不连通的组件，Transformer在学习连通性任务时会遇到困难，尤其是当组件数量较大时。 显示英文摘要

摘要： Reasoning capability is essential to ensure the factual correctness of the responses of transformer-based Large Language Models (LLMs), and robust reasoning about transitive relations is instrumental in many settings, such as causal inference. Hence, it is essential to investigate the capability of transformers in the task of inferring transitive relations (e.g., knowing A causes B and B causes C, then A causes C). The task of inferring transitive relations is equivalent to the task of connectivity in directed graphs (e.g., knowing there is a path from A to B, and there is a path from B to C, then there is a path from A to C). Past research focused on whether transformers can learn to infer transitivity from in-context examples provided in the input prompt. However, transformers' capability to infer transitive relations from training examples and how scaling affects the ability is unexplored. In this study, we seek to answer this question by generating directed graphs to train transformer models of varying sizes and evaluate their ability to infer transitive relations for various graph sizes. Our findings suggest that transformers are capable of learning connectivity on "grid-like'' directed graphs where each node can be embedded in a low-dimensional subspace, and connectivity is easily inferable from the embeddings of the nodes. We find that the dimensionality of the underlying grid graph is a strong predictor of transformers' ability to learn the connectivity task, where higher-dimensional grid graphs pose a greater challenge than low-dimensional grid graphs. In addition, we observe that increasing the model scale leads to increasingly better generalization to infer connectivity over grid graphs. However, if the graph is not a grid graph and contains many disconnected components, transformers struggle to learn the connectivity task, especially when the number of components is large.