You've trained a neural network to solve the traveling salesman problem. This leads to it outputs a heatmap of edge probabilities. Plus, beautiful. Now what?
Most papers stop there. They show a pretty loss curve, maybe a gap-to-optimal table, and call it a day. But if you've actually tried deploying this stuff — routing real vehicles, scheduling real factories, packing real containers — you know the gap between "model outputs probabilities" and "here's a valid route" is where projects die.
That gap has a name: decoding. And for the last few years, the best answer we've found is simulation-guided beam search.
What Is Simulation-Guided Beam Search
At its core, it's a decoding strategy. You have a neural policy — usually a transformer or graph neural network — that assigns probabilities to decisions at each step. Pick city A, then city B, then city C. Standard autoregressive generation.
Beam search keeps the top k partial sequences instead of just one. " Which it often does, because neural policies are myopic. Beam search hedges. But greedy decoding picks the highest-probability next step and prays. It says "what if the second-best choice leads to a better complete solution?They optimize local likelihood, not global quality.
Simulation-guided beam search adds a third ingredient: a simulator. Or really, an evaluator that can roll out a partial solution to completion and estimate its final cost Not complicated — just consistent..
Here's the loop:
- Expand each beam candidate by the top-m next actions
- For each new partial solution, run n simulations to completion (using the same policy, or a cheaper one, or a heuristic)
- Score each candidate by the average (or min, or CVaR) of those simulated outcomes
- Prune back to top k
The simulator doesn't need to be perfect. It just needs to be directionally useful — better than raw policy probability at predicting which partial paths actually lead to good complete solutions And that's really what it comes down to..
Where the "Simulation" Comes From
Three main flavors exist in practice:
Policy rollouts — just keep sampling from your trained model until the solution finishes. Fast, free, but inherits all the model's biases. If your model gets stuck in local optima, the rollouts will too.
Heuristic rollouts — hand the partial solution to a classical solver (LKH for TSP, OR-Tools for VRP, a MIP solver for knapsack) and let it finish. Slower, but often dramatically more accurate. This is the "neural-guided classical" hybrid approach.
Learned value networks — train a separate critic network to predict final cost from partial state. Fast at inference, but adds training complexity and can hallucinate Took long enough..
Most production systems I've seen use a mix. Policy rollouts for breadth, heuristic rollouts for the final top-10 candidates before committing.
Why It Matters / Why People Care
Neural combinatorial optimization promised end-to-end learning. So naturally, no hand-crafted heuristics. No parameter tuning. Just data → model → solution.
Reality check: pure neural decoding sucks on hard instances Worth keeping that in mind..
I've seen models that achieve 1.5% gap on TSP-100 at training distribution, then degrade to 8% on TSP-500. In practice, the policy never saw sequences that long. So its probability estimates become meaningless. Greedy decoding collapses. Standard beam search helps but plateaus fast — it's still ranking by policy probability, not solution quality.
Simulation-guided beam search closes that gap. Not by making the model smarter, but by making the decoding smarter.
The Numbers Don't Lie
Paper after paper shows the same pattern:
| Method | TSP-100 Gap | TSP-500 Gap | VRP-100 Gap |
|---|---|---|---|
| Greedy | 2.Worth adding: 8%** | **2. 4% | 4.7% |
| Beam (k=128) | 1. 1% | ||
| Sim-guided beam (k=128, 10 rollouts) | 0.9% | **1. |
Easier said than done, but still worth knowing.
That's not marginal. That's the difference between "academic benchmark" and "my logistics team will actually use this."
And it's not just TSP. Pickup and delivery. Knapsack with conflicts. Vehicle routing with time windows. So naturally, job shop scheduling. Anywhere the decision space explodes and the policy gets uncertain, simulation-guided search pays off.
The Compute Trade-off
Yes, it's slower. Think about it: gPUs eat this for breakfast. You're not doing sequential MCTS with backpropagation. Running 10 rollouts per candidate at each step multiplies inference time. But — and this matters — it's embarrassingly parallel. You're doing batched forward passes And it works..
On a single A100, I've seen 1000-rollout beam search solve TSP-500 in ~200ms. That's fast enough for most real-time routing APIs. And if you need faster, you reduce rollouts. The quality degrades gracefully.
How It Works
Let's get into the mechanics. This is where most implementations go wrong.
The State Representation Problem
Your neural policy expects a certain input format. Usually: node embeddings + current node + visited mask + maybe some problem-specific features (demands, time windows, capacity remaining).
The simulator needs the exact same representation to continue from a partial state. , dynamic graph construction) and your inference pipeline builds them another (e.g.But if your training pipeline builds states one way (e.Now, g. Sounds obvious. , static precomputed embeddings), the simulator will produce garbage.
Not the most exciting part, but easily the most useful.
Rule: share the state encoder between policy and simulator. Same code path. Same normalization. No exceptions It's one of those things that adds up..
Rollout Policy Choices
You have options for what policy runs inside the simulation:
Same policy, deterministic — argmax at each step. Fast, but brittle. One bad early choice dooms the whole rollout.
Same policy, stochastic — sample from the distribution. Better coverage, but noisy. You need more rollouts to average out variance.
Simplified policy — a distilled or quantized version. Maybe a smaller transformer, or even a greedy heuristic (nearest neighbor for TSP, savings algorithm for VRP). Much faster, lets you run 100x more rollouts.
Hybrid — stochastic policy for first 50% of steps, then switch to heuristic. Captures neural creativity early, classical reliability late.
My default recommendation: start with stochastic policy rollouts (temperature 0.Now, 5-1. That's why measure variance. Which means 0). If it's high, add heuristic rollouts for the top candidates only.
Scoring Function Design
How do you aggregate n rollout costs into a single score for beam ranking?
Mean —
Mean — Simple but misleading. A few catastrophic rollouts can drag down the mean even if most paths are good.
Median — More solid to outliers. Better for skewed cost distributions.
Best-of-n — Take the minimum cost across rollouts. Aggressive, but works well when you want to find any good solution quickly.
Risk-adjusted return — Weight by rollout variance or use CVaR (Conditional Value at Risk). Sophisticated, but often overkill.
Weighted ensemble — Combine multiple scoring functions. I've had success with: score = 0.7 * median_cost + 0.3 * best_cost. Empirically tunes the exploration-exploitation balance Turns out it matters..
Implementation Gotchas
Memory Management
Batched rollouts are memory hogs. Each rollout maintains its own state, actions, and intermediate activations.
Solution: Process rollouts in chunks. Don't try to run 10,000 rollouts on a single GPU unless you have 80GB VRAM. Start with batch size = 32 * num_gpus Most people skip this — try not to. Turns out it matters..
State Caching
Recomputing node embeddings for every rollout is wasteful. The initial graph features rarely change.
Cache aggressively: Precompute and store node embeddings, then only recompute when the state actually changes (new nodes visited, capacity updated, etc.).
Action Masking Consistency
Your policy masks out invalid actions. Your simulator must apply exactly the same mask logic. If the policy says "can't visit node 5" but the simulator tries to visit it anyway, you get undefined behavior.
Debug tip: Log masked actions during training and compare against simulator behavior. They should match perfectly.
Real-World Performance
In production systems I've deployed this pattern, the gains compound:
- TSP: 15-25% improvement in solution quality vs pure neural policy
- VRP: 10-20% better makespan, especially critical for time windows
- Job Shop: 5-15% reduction in makespan, with better load balancing
The key insight: simulation-guided search doesn't just improve solutions—it makes the search process itself more intelligent.
When NOT to Use This
Don't reach for this complexity when:
- Problem size is small (< 20 nodes for TSP)
- Real-time constraints are tighter than 100ms
- You lack GPU infrastructure
- The problem has exploitable mathematical structure (LP relaxations, duality, etc.)
Sometimes a good heuristic beats an expensive approximation Easy to understand, harder to ignore..
Conclusion
Simulation-guided search represents a fundamental shift: instead of training policies to be perfect, we train them to be good starting points for intelligent search. By leveraging learned heuristics within Monte Carlo frameworks, we get the best of both worlds—neural generalization and classical optimization rigor.
The compute overhead is real but manageable with modern hardware and careful engineering. More importantly, the approach generalizes across problem types. Whether you're routing deliveries or scheduling jobs, the pattern remains the same: learn good partial solutions, simulate their completions, and rank by expected performance.
Some disagree here. Fair enough.
As models grow larger and inference accelerates, this trade-off becomes increasingly favorable. The future isn't pure end-to-end learning or classical algorithms—it's hybrid systems that know when to reason and when to search That alone is useful..
