Research map / Large language models / Agents, code and math
Teaching Transformers to Solve Combinatorial Problems through Efficient Trial & Error
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.
Trains a vanilla GPT-2-style causal Transformer to solve Sudoku (and 1-in-3 SAT) via DFS trial-and-error transcripts with multi-target loss, then optimizes guess selection as a contextual Min-Sum Set Cover problem.
Problem
LLMs and neural solvers struggle with combinatorial NP problems such as Sudoku, SAT and TSP; prior neural Sudoku solvers use custom architectures or single-pass prediction without error recovery, and imitation-learning transcripts cannot represent mistakes.
Approach
Train a standard causal Transformer on DFS trial-and-error transcripts (rule application, informed guessing, backtracking) with action-level 3-digit tokens and a multi-target cross-entropy loss; then, for depth-1 non-adaptive guessing, train the guess node with a loss L1 = (sum of backdoor probabilities)^-1 derived from Min-Sum Set Cover, trained only on successful trajectories.
Key results
- Trial-and-error Transformer reaches 98.9% board accuracy on random Sudoku and 99.4% on RRN test, versus 92.6% for retrained Recurrent Transformer on Random.
- Depth-1 guessing with the L1 loss solves 99.8% of random Sudoku boards, with median 1.5 guesses versus 2.2 for cross-entropy and 2.3 for the upper-bound oracle.
- Frontier LLMs (GPT-4o, Gemini, o3-mini, DeepSeek-R1) achieve 0.00% board accuracy on Sudoku across three encodings.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use trial-and-error search with informed guessing and backtracking instead of direct rule-based imitation | Causal Transformer Trial & Error · Kaggle unfiltered | board accuracy: 67.16% -> 98.90% | Helped |
| Use trial-and-error search with informed guessing and backtracking instead of direct rule-based imitation | Causal Transformer Trial & Error · Kaggle filtered | board accuracy: 87.18% -> 99.50% | Helped |
| Use trial-and-error search with informed guessing and backtracking instead of direct rule-based imitation | Causal Transformer Trial & Error · RRN | board accuracy: 94.80% -> 99.40% | Helped |
| Train RRN on Random instead of RRN data | RRN · Random | board accuracy: 79.30% -> 92.40% | Helped |
| Use L1 expected-trials loss instead of L2 multiple-target Cross-Entropy (ablation) | Depth-1 guessing policy · Sudoku, Random | guesses to solution (median): 2.2 -> 1.5 guesses | Helped |
| Use L2 multiple-target Cross-Entropy rather than the upper-bound oracle ordering | Depth-1 guessing policy · Sudoku, Random | guesses to solution (median): 2.3 -> 2.2 guesses | No clear effect |
| Replace triplet tokenization with compact action-level encoding (ablation) | Causal Transformer rule-learning setup · Sudoku rule-logic training | rule-logic accuracy | Helped |
| Use multi-target loss instead of single-target loss (ablation) | Causal Transformer rule-learning setup · Sudoku rule-logic training | rule-logic accuracy | Helped |
| Train only on successful trajectories, excluding incorrect guess tokens (ablation) | Depth-1 guessing policy · Sudoku, Random | guesses to solution | Helped |
Surprising findings
- Frontier reasoning LLMs achieve 0% board accuracy on Sudoku despite long inference times.
- Training only on successful trajectories (excluding incorrect guess tokens) outperforms imitation learning that includes wrong guesses.
Limitations
- Depth-1 non-adaptive guessing only; multi-level policies not optimized.
- Results shown primarily for Sudoku and 1-in-3 SAT; generality to TSP and other NP problems not empirically demonstrated.
- Baselines reproduced by the authors; MDM results taken from the original paper with unreleased code.
Experimental setup
Datasets: Random Sudoku generator (SudokuPy) Kaggle Sudoku (unfiltered 3M) Kaggle filtered 1.9M RRN Sudoku dataset 1-in-3 SAT random instances
Benchmarks: Random Sudoku 100K test Kaggle unfiltered Kaggle filtered RRN test set 1-in-3 SAT
Metrics: board accuracy cell accuracy rule-logic accuracy time (sec/puzzle) median number of guesses
Baselines: RRN Recurrent Transformer Causal Transformer MDM GPT-4o Gemini-1.5 Pro o3-mini DeepSeek-R1
Builds on: Causal Transformer (Sudoku imitation of human strategies) minGPT DPLL Min-Sum Set Cover
Closest papers by meaning
- Causal language modeling can elicit search and reasoning capabilities on logic puzzles (NeurIPS 2024 · similarity 0.91)
- Self-Guiding Exploration for Combinatorial Problems (NeurIPS 2024 · similarity 0.87)
- Learning How to Cube (NeurIPS 2026 · similarity 0.87)
- GOAL: A Generalist Combinatorial Optimization Agent Learner (ICLR 2025 · similarity 0.87)
- Self-Verifying Reflection Helps Transformers with CoT Reasoning (NeurIPS 2025 · similarity 0.86)
- DART-Math: Difficulty-Aware Rejection Tuning for Mathematical Problem-Solving (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.