Research map / Learning theory and algorithms / Combinatorial and search optimization

Rethinking Deep Thinking: Stable Learning of Algorithms using Lipschitz Constraints

NeurIPS 2024 · Learning theory and algorithms › Combinatorial and search optimization · approach: Constrained neural network optimization · 1 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Stabilizes Deep Thinking recurrent networks by constraining the recurrent block to be approximately K-Lipschitz (K<1) via spectral normalization, guaranteeing convergence to a unique fixed point and enabling much smaller models that extrapolate better, including on TSP.

Problem

Deep Thinking (DT) style recurrent convolutional networks that learn iterative algorithms are unstable to train, overparameterized, and lack guarantees that iteration converges to a solution, which hurts extrapolation to larger problems at inference time.

Approach

Engineer the recurrent function to be approximately Lipschitz with constant less than but close to 1, using spectral normalization of convolutions, split recall convolutions, and parametric residual interpolation, so Banach fixed-point theorem guarantees convergence; combined with ELU, batch norm, and recall bias.

Key results

• On prefix sums (512-bit test), DTR reaches >90% accuracy in only 2 of 30 training runs while DTL fails to exceed 90% in only 2 of 30 runs, with DTL using w=32 models.
• DTL solves the same problems with, in some cases, three orders of magnitude fewer parameters, per the paper's claim.
• On TSP, DTL with M=120 at n=30 achieves mean tour length 6.02 (symmetric) and 7.7 (asymmetric), versus random tours 15.0 and NN 3.50, BNN 2.72, i.e. worse than nearest-neighbour heuristics but well better than random.

Measured effects reported in the paper

Surprising findings

• Adding bias terms made DT-style models very unstable, while the dead-cell problem worsened without bias.
• Attempting to train DTL on 9x9 mazes often led to trivial solutions that did not extrapolate, so 17x17 training was used instead.

Limitations

• Performance on TSP is far from state-of-the-art and worse than nearest-neighbour heuristics.
• Model still fails to learn in some cases; the convolutional locality means long-range dependencies must be captured through iteration.
• Problems studied are relatively simple, and the learned algorithms are not well understood.

Experimental setup

Datasets: EasyToHard prefix sums EasyToHard mazes EasyToHard chess puzzles randomly generated TSP instances (symmetric and asymmetric)

Benchmarks: EasyToHard prefix sums (512-bit test) EasyToHard mazes (33x33 extrapolation) EasyToHard chess puzzles random symmetric and asymmetric TSP (n=15, n=30)

Metrics: exact-solution accuracy mean tour length

Baselines: DT with recall (DTR) Random tours Nearest neighbor (NN) Best nearest neighbor (BNN)

Builds on: Deep Thinking networks DT with recall (DTR) spectral normalization incremental progress training Banach fixed-point theorem

Closest papers by meaning

• Rethinking Thinking Tokens: LLMs as Improvement Operators (ICML 2026 · similarity 0.83)
• Transformers Provably Solve Parity Efficiently with Chain of Thought (ICLR 2025 · similarity 0.83)
• Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalization (NeurIPS 2025 · similarity 0.83)
• One-Layer Transformers Provably Learn In-Context K-Nearest Neighbor Prediction with Chain-of-Thought (NeurIPS 2026 · similarity 0.83)
• Break the Block: Dynamic-size Reasoning Blocks for Diffusion Large Language Models via Monotonic Entropy Descent with Reinforcement Learning (ICML 2026 · similarity 0.83)
• Making Slow Thinking Faster: Compressing LLM Chain-of-Thought via Step Entropy (ICLR 2026 · similarity 0.83)