Pointer Networks

We have the task — point at hull vertices. Before the fix, see exactly where the standard recipe breaks.

A 2014-era sequence-to-sequence model (read an input sequence with one network, write an output sequence with another) ends each step the same way: a softmax over a fixed list of output symbols decided before training. For translation that list is the German vocabulary — large, but it never changes from sentence to sentence.

Convex hull breaks that assumption. With 5 input points the answer must choose among 5 labels; with 50 points, 50 labels; with 500, five hundred. The size of the answer space is the input length, and it differs on every single example. A softmax sized once, up front, simply has no slot to point at the 137th input point if it only ever saw 50.

The blocker is the fixed output list. The fix lives in the decoder's final step — but first, the overall shape both models share.

Like ordinary seq2seq, a Pointer Network has two recurrent halves (the paper uses single-layer LSTMs — a kind of recurrent cell that carries memory across steps). The encoder reads the input points one by one, feeding in each point as its raw (x, y) coordinates, and leaves behind one hidden state ej per point. The decoder then writes the answer, producing one hidden state di per output step.

At every output step the decoder looks back over all the encoder states and scores each input position. In a plain attention model those scores would be turned into one blended summary. The whole twist — coming in Part B — is what the Pointer Network does with the scores instead.

We have the skeleton and the scores. Here is the fork in the road — the single design choice that separates the two models.

Both models start identically. At decoder step i they compute a relevance score uj for every input position j, then run softmax to turn those scores into weights aj that sum to 1. The split happens in what comes next.

"Point at the highest score" is the idea. Now do it for real, on our five points, one decoder step at a time.

We are at decoder step 1. The model has just started writing the fence and needs its first vertex — by the paper's convention, the hull point with the lowest index, which here is point 1. For each input position j the decoder produces a raw score uj (these are illustrative logits; the real ones come from the formula in Step 6). Then softmax turns the five scores into a probability over the five points, and the biggest probability is the pointer.

Why does the tallest score win so decisively? Because softmax turns differences into exponentials. Take just two of the scores — say point 1 at 3.2 versus point 2 at 1.1. The weight on point 1 is e3.2 / (e3.2 + e1.1), and a gap of 2.1 already pushes it to 89%. Drag the two scores and feel the lever:

You just produced pointers by hand. Here is the formula that produced the scores you used — and you will see you already did it.

The score uj for input position j at decoder step i is the paper's additive attention (a small learned network that compares two vectors): mix the encoder state ej with the decoder state di through two matrices, squash with tanh, and project to a single number with a vector v.

That is the entire pointer. The first line is the score you read off the bars in Step 5; the second line is the softmax you already ran by hand. Ci is the output at step i — an index into the input, not a token from a vocabulary.

One step gives one index. A convex hull is a list of indices — so we loop, and each choice conditions the next.

After step 1 points at point 1, the model feeds that choice back into the decoder, advances to d2, and scores all positions again — now biased to continue the fence counter-clockwise, so point 2 wins. Then point 3, then point 4. When the scores favour the stop marker ⇐, the sequence ends. The hull {⇒, 1, 2, 3, 4, ⇐} has been written entirely out of input indices.

We have a working loop. The quiet superpower is that the very same loop runs on inputs longer than anything it trained on.

Look back at the formula: it scores each input position with the same little network v⊤tanh(W1ej + W2di), then softmaxes over however many positions there are. Add a sixth point and the loop simply scores six. There is no fixed-size output layer to retrain — the output layer is the input.

So a model trained only on point sets of size 5 to 50 still produces sensible hulls at n = 100, 200, even 500 — far past anything it saw. That is strong evidence the network learned the geometry of "what makes a fence," not a lookup table keyed on length.

We understand the mechanism. Now the evidence: on convex hull at n = 50, all three approaches share the encoder — only the last step differs.

"Accuracy" here is strict: the predicted index sequence must match exactly. "Area" is gentler: how much of the true hull's area the predicted polygon covers. Watch the gap between a plain LSTM, an attention-blended LSTM, and the Pointer Network.

Generalization, in one row: train on point sets of size 5–50, test far beyond. Exact accuracy fades as expected — 92% at n = 5, 69.6% at 50, 50.3% at 100, 1.3% at 500 — yet area coverage stays above 99% the whole way. The fence keeps being nearly right long after naming every vertex in order becomes hard.

One task proved the idea. The paper's real flex is that nothing about the architecture is hull-specific.

Change only the training data — same encoder, same decoder, same pointer — and the network learns three different bits of computational geometry, purely from examples:

A fair caveat the paper is honest about: as a TSP solver it is not competitive with classical heuristics or later neural methods — its tours drift longer as n grows past the training range. The lasting contribution was never the benchmark numbers. It was the pointer abstraction.