# Neural Learning of One-of-Many Solutions for Combinatorial Problems in Structured Output Spaces

arXiv: https://arxiv.org/abs/2008.11990 · HTML: https://mlsanity.com/paper/2008.11990/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Aug 2020.

## Built on by (most cited first, 14 of 14)

- [Competition-Level Code Generation with AlphaCode](https://mlsanity.com/paper/2203.07814/) (2022)
- [Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxation](https://mlsanity.com/paper/2207.05984/) (2022)
- [Unsupervised Learning for Combinatorial Optimization Needs Meta-Learning](https://mlsanity.com/paper/2301.03116/) (2023)
- [Pointwise Mutual Information Based Metric and Decoding Strategy for Faithful Generation in Document Grounded Dialogs](https://mlsanity.com/paper/2305.12191/) (2023)
- [Conditional set generation using Seq2seq models](https://mlsanity.com/paper/2205.12485/) (2022)
- [A Solver-Free Framework for Scalable Learning in Neural ILP Architectures](https://mlsanity.com/paper/2210.09082/) (2022)
- [Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods](https://mlsanity.com/paper/2310.05309/) (2023)
- [End-to-End Neuro-Symbolic Architecture for Image-to-Image Reasoning Tasks](https://mlsanity.com/paper/2106.03121/) (2021)
- [Scalable Coupling of Deep Learning with Logical Reasoning](https://mlsanity.com/paper/2305.07617/) (2023)
- [Neural Models for Output-Space Invariance in Combinatorial Problems](https://mlsanity.com/paper/2202.03229/) (2022)
- [Selective Self-Rehearsal: A Fine-Tuning Approach to Improve Generalization in Large Language Models](https://mlsanity.com/paper/2409.04787/) (2024)
- [Scaling Neuro-symbolic Problem Solving: Solver-Free Learning of Constraints and Objectives](https://mlsanity.com/paper/2508.20978/) (2025)
- [Multi-Attractor GNNs: Set-Valued Expressivity Beyond Unique Equilibria](https://mlsanity.com/paper/2609.35274/) (2026)
- [Tiny Recursive Message Passing](https://mlsanity.com/paper/2610.18649/) (2026)

## Abstract (arXiv)

Recent research has proposed neural architectures for solving combinatorial problems in structured output spaces. In many such problems, there may exist multiple solutions for a given input, e.g. a partially filled Sudoku puzzle may have many completions satisfying all constraints. Further, we are often interested in finding any one of the possible solutions, without any preference between them. Existing approaches completely ignore this solution multiplicity. In this paper, we argue that being oblivious to the presence of multiple solutions can severely hamper their training ability. Our contribution is two fold. First, we formally define the task of learning one-of-many solutions for combinatorial problems in structured output spaces, which is applicable for solving several problems of interest such as N-Queens, and Sudoku. Second, we present a generic learning framework that adapts an existing prediction network for a combinatorial problem to handle solution multiplicity. Our framework uses a selection module, whose goal is to dynamically determine, for every input, the solution that is most effective for training the network parameters in any given learning iteration. We propose an RL based approach to jointly train the selection module with the prediction network. Experiments on three different domains, and using two different prediction networks, demonstrate that our framework significantly improves the accuracy in our setting, obtaining up to 21 pt gain over the baselines.