LLM + RoboticsUnit 4 · Specialised architectures · Day 18

Pointer Networks

When the answer is "which of the inputs", don't predict from a fixed vocabulary. Use the attention weights themselves as the output.

AuthorsOriol Vinyals, Meire Fortunato, Navdeep Jaitly

Year / venue2015 · NIPS (NeurIPS)

Core ideaAttention as an output pointer

Study time3–4 h

Original: arXiv:1506.03134 · Code, notebook and exercises: 30u30 Day 18

Start here (no maths needed)

When the answer is "one of the things you were given", a Pointer Network simply points at it, instead of choosing from a fixed list of answers.

Think of it like this

Stick some pins in a board and stretch a rubber band around all of them. The band touches only the outer pins. Now say which pins it touches, in order around the outside. Your answer is just pointing: "this one, then this one, then that one". It works the same with 5 pins or 500. A Pointer Network answers the same way. It doesn't need a fixed list of possible answers, because the answers are always the inputs themselves.

How it works

The network looks at all the points and makes a note about each one.
At each step, it gives every point a score: how likely is this one to be next?
The scores become shares that add up to 100%. The point with the biggest share is its pick.
Points already used are crossed out, so it can't pick them again.
It repeats until it is done. Because it only ever points, the same network works for any number of points.

Why robots care

A delivery robot with eight stops has to choose the order to visit them. At each step it can point at the best next stop and cross off the ones it has done. Crossing off also works for safety: any spot that is blocked or unsafe can be crossed out before the robot chooses.

Try it

Put a handful of coins on a table. Pretend a rubber band is stretched around them. Go around the outside, pointing at each coin the band would touch, in order. You are doing the network's job.
In the demo further down, press Next step again and again. Bigger circles mean the network is pointing more strongly at that point, and hollow points are crossed out. Use Restart or New points to try again, and move the Number of points n slider to see that it still works with more points.

Words to know

Pointer: An answer that picks one of the inputs.
Convex hull: The outside shape you get by stretching a rubber band around all the points.
Mask: Crossing out choices that aren't allowed, like points already used.
Vocabulary: The list of answers a network can give. For a pointer, it is the inputs.
Travelling salesperson problem: Finding the shortest route that visits every stop once.

Going deeper: everything below is the full version, with some maths. On a first read, skim the headings and the "Why it matters for robotics" box, and come back for the rest later.

1. Summary

TL;DR

A seq2seq model ends in a softmax over a fixed vocabulary. That breaks when the output is a choice among the inputs: the convex hull of 10 points has indices up to 10, of 500 points up to 500. Pointer Networks (Ptr-Nets) keep the attention score from Day 15 but stop there. The softmax over input positions is the output distribution. The output vocabulary grows and shrinks with the input, so one model can run on any number of points. The authors trained Ptr-Nets on examples alone to produce convex hulls, Delaunay triangulations and short travelling-salesman tours.

Encoder: an LSTM reads the input points, giving one state per point.
Decoder: an LSTM; at each step its state is compared with every encoder state, and the softmax picks a point.
Convex hull: 72.6% exact accuracy at n = 50 versus 38.9% for an LSTM with attention and 1.9% for a plain LSTM.
Generalisation: trained on 5–50 points, the same model covered 99.2% of the true hull's area at n = 500, although exact accuracy fell to 1.3%.
TSP: near-optimal for small n. For n = 50, trained on a weak heuristic's tours, it beat that heuristic (6.42 vs 6.46 tour length).

2. The core idea

Encoder states e_1 … e_n, decoder state d_i at output step i:

Attention (Day 15):   u_j^i = vᵀ tanh(W_1 e_j + W_2 d_i)
                      a^i   = softmax(u^i)
                      d'_i  = Σ_j a_j^i e_j       → feed to a fixed-vocabulary softmax

Pointer:              u_j^i = vᵀ tanh(W_1 e_j + W_2 d_i)     j = 1 … n
                      p(C_i | C_1 … C_{i−1}, P) = softmax(u^i)

u_j^i scores input j for output step i. Same additive form as Bahdanau attention.
W_1, W_2, v are the only pointer parameters, and none of their shapes depend on n. That's why the model runs on any input size.
softmax(u^i) has exactly n entries. Picking its argmax means "output input number j".
C_i is the index chosen at step i, P the input point set. Training is plain maximum likelihood on example index sequences; decoding uses beam search.
Models were single-layer LSTMs with 256 or 512 units, trained on points sampled uniformly from the unit square.

3. Deep dive

Why a fixed vocabulary fails here

A seq2seq baseline needs a separate output class for "point 1", "point 2", and so on. It must be trained and tested at the same n, and it has to learn what "point 7" means from scratch. A pointer instead compares content: "which of these encoder states fits what I need next?" The Ptr-Net trained on mixed sizes 5–50 reached 92.0% hull accuracy at n = 5 and 87.0% at n = 10, against 87.7% and 29.9% for LSTMs trained specifically at those sizes.

Decoding a convex hull, step by step

Interactive: pointing at the next hull point

The output vocabulary is the input points. At each step, circle size shows the pointer distribution over all n points. Hollow points are masked (already used). Scores here come from a hand-written gift-wrapping rule (score falls with the number of points on the wrong side of the edge), standing in for what a trained Ptr-Net computes with vᵀtanh(W₁e + W₂d). The mechanics are the real ones: one softmax over the inputs, masking, and a vocabulary of size n.

Number of points n:

Step

–

Vocabulary size

–

P(chosen point)

–

Hull points so far

–

Two practical details from the paper. First, the output order is fixed by convention for training: for TSP, every training tour starts at the first city. Day 16 shows why such conventions matter. Second, nothing in the bare model stops it pointing at the same city twice, so for TSP the authors restricted beam search to valid tours. For n > 20, at least 10% of instances produced no valid tour otherwise. Masking already-chosen inputs, as in the demo, is the now-standard fix.

Results and limits

TSP, exact training data (Held-Karp): tour length 2.12 at n = 5 (optimal 2.12) and 2.88 at n = 10 (optimal 2.87).
TSP generalisation: trained on 5–20 cities, results were near perfect at n = 25 and good at 30, but broke down from 40 up (7.66 vs 5.79 for Christofides at n = 50).
Delaunay triangulation: 80.7% exact at n = 5, 22.6% at n = 10. Harder structure, weaker results.
Later work (for example attention-based models trained with reinforcement learning) pushed learned routing much further, but the pointer output head stayed.

4. Why it matters for robotics

"Grasp that one" is a pointer. Given N detected objects or N candidate grasp poses, a policy can score each and softmax over them, instead of regressing coordinates. It works for any number of objects, and the output is always a valid candidate.
Task ordering and routing. Visiting inspection points, picking orders in a warehouse, or ordering welds is TSP-like. Pointer-style decoders with masking are a common learned heuristic for these, usually checked against or combined with classical solvers.
Masking encodes constraints. Already picked, unreachable, or in collision: set those scores to −∞ and the policy can't choose them. It's a simple way to put hard safety and feasibility rules around a learned selector.
Be honest about scale. The paper's TSP results degrade past the training range. For real fleets, classical solvers and heuristics remain the baseline to beat.

5. How to study it

Read sections 2 (models) and 4 (results) of the paper. Compare equation 3 with Bahdanau's alignment model from Day 15.
In the 30u30 Day 18 folder, read implementation.py (it uses sorting as the task) and run train_minimal.py. Plot pointer distributions with visualization.py.
Do the exercises: pointer attention, masking, convex hull, TSP cost, greedy decoding.
Test size generalisation yourself: train on n ≤ 10, evaluate at n = 20 and 40, and plot accuracy versus n.
Stretch: replace the LSTM encoder with a Transformer encoder without positional encodings, so the input is treated as a set.

6. Self-check

What is the one change from Bahdanau attention to a pointer?

The attention distribution over inputs is used directly as the output distribution, instead of being used to mix encoder states into a context vector.

Why can one Ptr-Net handle any number of inputs?

Its parameters (W_1, W_2, v) act per input, and the softmax simply has one entry per input. Nothing is sized to a fixed n.

On the hull task at n = 500, why is accuracy 1.3% but area coverage 99.2%?

Accuracy needs every hull point exactly right. With 500 points a single near-collinear mistake fails the example, while the polygon produced still covers almost all the true hull.

How do you stop a pointer network from visiting a city twice?

Mask already-chosen inputs by setting their scores to −∞ before the softmax, or restrict beam search to valid outputs, as the paper did for TSP.

Why did a Ptr-Net trained on A1's tours beat A1?

It learned a smoothed general rule from many examples rather than reproducing each tour's specific mistakes. It's evidence the model isn't just memorising, but the gain was small (6.42 vs 6.46).

7. Further reading

The original paper (arXiv; published at NIPS 2015)
30u30 Day 18: implementation, notebook, cheatsheet, exercises
Next: Day 19, A Simple Neural Network Module for Relational Reasoning