COMPASS: Ordered Clustered Routing at 100K Scale

What it claims

The summary guesses this is about mixture-of-experts or serving-system routing. The abstract says otherwise: COMPASS solves the Ordered Clustered Traveling Salesman Problem (OCTSP) — physical/logistics routing where you must visit clusters of nodes in a prescribed order. This is a combinatorial optimization paper, not an ML-serving paper. It claims to scale to 100K synthetic nodes and 28.5K real e-commerce nodes, the latter described as the largest reported routing solution over asymmetric distances — 9x beyond established ATSP benchmarks.

How it works

COMPASS combines search with "learning-accelerated routing" by orchestrating parallel sub-solvers. The stated design points:

• It exploits cluster structure so exact solutions cost time exponential in cluster size rather than instance size — the lever that makes 100K-node instances tractable.
• It has no quality ceiling: solutions keep improving as you give it more compute (anytime behavior).
• Optimizing each cluster independently is the naive baseline it rejects, because that misses non-local dependencies between clusters.
• It consumes general distance matrices, not just coordinates — so it handles asymmetric distances (ATSP), unlike common large-scale solvers limited to coordinate inputs.

Evidence

The abstract states COMPASS "consistently outperforms alternative methods" but names no competitor, metric, or gap. The concrete scale claims are the 100K synthetic and 28.5K real asymmetric e-commerce instances, and the 9x-beyond-ATSP-benchmark framing. No solution-quality numbers, runtimes, or baseline figures appear in the fetched text.

Limits

• Abstract only — no method detail beyond the sketch above, no tables, no named baselines, no quantified results. The "outperforms" and "9x" claims are unverified from this page.
• Asymmetric-distance support and general distance-matrix input are the differentiators to check against your alternative; whether the learned component transfers across distance distributions is not addressed here.
• If you came expecting MoE/retrieval routing, this is the wrong paper — the "routing" here is TSP-family logistics optimization.
• The exact-solution guarantee is bounded by cluster size; instances with large clusters lose the exponential advantage, though the abstract does not quantify where that breaks.

Read the PDF before adopting: the actionable question — how much better and at what compute — is exactly what this page does not answer.