Oriol Vinyals, Meire Fortunato, Navdeep Jaitly
5 min
We introduce a new neural architecture to learn the conditional probability of an output sequence with elements that are discrete tokens corresponding to positions in an input sequence. Such problems cannot be trivially addressed by existent approaches such as sequence-to-sequence and Neural Turing Machines, because the number of target classes in each step of the output depends on the length of the input, which is variable. Problems such as sorting variable sized sequences, and various combinatorial optimization problems belong to this class. Our model solves the problem of variable size output dictionaries using a recently proposed mechanism of neural attention. It differs from the previous attention attempts in that, instead of using attention to blend hidden units of an encoder to a context vector at each decoder step, it uses attention as a pointer to select a member of the input sequence as the output. We call this architecture a Pointer Net (Ptr-Net). We show Ptr-Nets can be used to learn approximate solutions to three challenging geometric problems -- finding planar convex hulls, computing Delaunay triangulations, and the planar Travelling Salesman Problem -- using training examples alone. Ptr-Nets not only improve over sequence-to-sequence with input attention, but also allow us to generalize to variable size output dictionaries. We show that the learnt models generalize beyond the maximum lengths they were trained on. We hope our results on these tasks will encourage a broader exploration of neural learning for discrete problems.
The authors address a fundamental limitation in existing sequence-to-sequence neural networks: the inability to handle problems where the size of the output dictionary depends on the length of the input sequence. Standard models require a fixed output vocabulary, making them unsuitable for combinatorial optimization tasks where the output must consist of specific elements from the input set (e.g., selecting points to form a convex hull).
The researchers introduce the Pointer Network (Ptr-Net), a modification of the standard neural attention mechanism. In traditional attention models, the network uses attention to "blend" hidden states of the encoder into a context vector. In contrast, the Ptr-Net uses the attention mechanism as a pointer to select specific indices from the input sequence.
By outputting a probability distribution over the input positions rather than a fixed vocabulary, the Ptr-Net can handle inputs of varying lengths and produce outputs that are inherently tied to the input elements. This architecture allows the model to learn to "point" to the correct input at each step of the decoding process.
The authors tested the Ptr-Net on three challenging geometric and combinatorial problems:
The results show that Ptr-Nets significantly outperform standard sequence-to-sequence models and provide a viable, data-driven approach to solving computationally difficult problems without requiring hand-coded algorithms.
This work is significant because it bridges the gap between deep learning and classical algorithmic problem-solving. By demonstrating that neural networks can learn to solve combinatorial optimization problems directly from data, the authors open the door for using machine learning to address complex, intractable problems where traditional algorithmic solutions might be difficult to design or computationally expensive to execute.
Sam: That's a critical limitation the authors acknowledge. The model doesn't inherently understand the rules of the task — like the fact that you can't revisit a city. It just learns to point. For problems where that matters, researchers have to add a separate checking step to ensure the output is actually valid.
Alex: Like a student who understands the shape of a problem but still needs someone to check for basic errors. So what problems did they actually test this on?
Sam: They focused on three geometric challenges. The first is the "convex hull" — imagine stretching a rubber band around a set of nails on a board; the band snaps into the tightest shape that contains all the nails. The second is "Delaunay triangulation," which is about dividing a flat space into triangles in the most balanced way possible. And the third is the Travelling Salesman Problem — the classic challenge of finding the shortest path that visits every city exactly once.
Alex: The Travelling Salesman Problem is famously difficult. Did the model actually solve it, or just get close?
Sam: It found approximate solutions. For smaller sets of cities, it performed well. But the more notable finding is that the model could generalise to larger numbers of cities than it was ever shown during training — it learned a rule it could then apply at a scale it hadn't encountered before.
Alex: That's the part that surprises me. How can it handle fifty cities if it was only trained on twenty?
Sam: It's because the model learns relative relationships rather than absolute values. It doesn't learn "go to city number three." It learns something closer to "go to whichever city is nearest to where I am right now." By learning the logic of the *relationship* between points, it can scale up without needing to be retrained from scratch.
Alex: So it's learning the concept of proximity, not just memorising a map. That's a meaningful shift from how these models usually work.
Sam: It is. And when you zoom out, the implications are significant. This kind of architecture could evolve toward what some researchers call "Neural Algorithmic Reasoning" — where neural networks learn to execute complex logical steps by pointing to relevant variables, rather than simply predicting the next word in a sequence.
Alex: A much more flexible way to build systems that reason.
Sam: Exactly. By decoupling the output from a fixed vocabulary, we move closer to systems that can handle the dynamic, unpredictable nature of real-world problems. The research suggests that even with relatively simple, data-driven methods, we can begin to approximate solutions to problems that were once thought to require hand-coded algorithms.
Alex: So the shift is from "memorise the answer" to "learn how to point to the right solution." That's a notably elegant way to approach a difficult class of problems.
Sam: And a more honest framing of what these systems are actually doing. It doesn't resolve the inherent complexity of these problems — but it provides a flexible, scalable tool that can adapt to different inputs in a way that previous architectures simply couldn't manage.
Alex: Thanks for walking through the logic behind Pointer Networks. It's been a clear look at how researchers are teaching machines to reason about structure and relationships — and where that line of thinking might lead.
Sam: Thanks for listening to ResearchPod.