Pointer Networks Solve TSP in Milliseconds, But Quality Collapses at Scale
an2ancan · reddit · 2026-11-08
A deep-dive article (first in a series) on solving combinatorial optimization with ML, focusing on the classic Pointer Network trained via REINFORCE, which constructs near-optimal solutions to NP-hard problems (2D Euclidean TSP) in fractions of a millisecond.
- Benchmarked against Google OR-Tools (Guided Local Search, 10s timeout) across problem scales from N=20 to N=200.
- Key finding: while solutions come almost instantly, tour quality decays significantly as problem size grows.
- Root cause: the LSTM encoder imposes an artificial sequential order and recency bias on coordinate sets, fundamentally mismatching the permutation-invariant nature of geometric graphs.
More from Research
- Debate over METR's 2x speedup claim: does it lean on private information? — JacquesThibs · 2026-11-08
- Scaling May Be Superlinear: LessWrong Debate on Steepening AI Progress Curves — teortaxesTex · 2026-11-08
- Reviewers reward flaw-free work, users reward useful work — why peer review punishes innovation — wzenus · 2026-11-08
- Math community debates Glazer's proof and OpenAI's H10 paper: slop need not compound — littmath · 2026-11-08
- Stanford paper: more info helps some LLM trading agents, wrecks others — rohanpaul_ai · 2026-11-08
- Neel Nanda pushes back on LRH critique: one steering vector, four norms, four behaviors — NeelNanda5 · 2026-11-08