Introduction
Dependency parsing—the task of identifying grammatical relationships between words—is a cornerstone of natural language processing. While deep learning has significantly advanced the state-of-the-art, most high-performing models rely on sequential architectures like LSTMs or transition-based systems. These models process tokens or actions one by one, creating a computational bottleneck that fails to fully leverage the parallel processing capabilities of modern GPUs.
This paper introduces Dilated Iterated Graph CNNs (DIG-CNNs), an architecture designed to be "parallel-first." By treating dependency parsing as a 2D image-processing task over a sentence's adjacency matrix, the authors enable efficient, end-to-end parallel parsing that remains competitive with top-tier sequential models.
Methodology
The core innovation of DIG-CNNs lies in the shift from 1D sequential processing to a 2D grid representation.
2D Representation and Convolutions
Instead of a 1D sequence, the sentence is represented as a $T \times T$ grid, where $T$ is the number of tokens. Each cell $(i, j)$ represents a potential dependency edge between a "head" word and a "dependent" word. This allows the model to treat the adjacency matrix like an image, applying convolutional filters to identify patterns and refine the entire structure simultaneously.
To capture long-range dependencies without a massive parameter overhead, the model employs dilated convolutions. These filters skip over tokens at set intervals, expanding the receptive field. Furthermore, the architecture uses Iterated Blocks, applying the same stack of convolutional layers multiple times to refine predictions iteratively. This process is guided by a parallel objective function that rewards accuracy after every block, mitigating vanishing gradient issues.
Experimental Setup
The model was evaluated on the English Penn TreeBank (PTB) using standard splits (Sections 2–21 for training, 22 for development, and 23 for testing). Original constituency trees were converted to dependencies using the Stanford dependency framework (v3.5), with POS tags provided by the Stanford left3words tagger.
Key Results
The DIG-CNN model achieved performance comparable to established graph-based parsers. While it did not surpass the absolute state-of-the-art BiLSTM-based models of the time, it demonstrated the viability of purely convolutional, parallel architectures for complex linguistic tasks.
As shown in the table above, the DIG-CNN achieved a UAS of 93.70 and an LAS of 91.72. When combined with the Eisner algorithm for post-processing, these scores improved to 94.03 and 92.00, respectively. While slightly lower than the scores reported by Dozat and Manning (2017), the DIG-CNN is significantly more amenable to GPU acceleration because it avoids the sequential bottleneck of LSTMs.
Discussion and Future Work
A key insight from this work is that competitive results can be achieved even with a relatively small receptive field (approximately 9 tokens of context), suggesting that iterative refinement can compensate for the lack of global sequential context provided by LSTMs.
However, the limited context window remains the primary drawback. Future research will focus on deeper architectures to incorporate broader sentence context and providing concrete wall-clock speed benchmarks to quantify the efficiency gains of this parallel approach in production environments.
Summary updated