Reliable Reasoning with Large Language Models via Preference-Based Maximum Satisfiability

• URL: http://arxiv.org/abs/2605.29687v1
• Date: Thu, 28 May 2026 09:51:33 GMT
• Title: Reliable Reasoning with Large Language Models via Preference-Based Maximum Satisfiability
• Abstract summary: Large Language Models (LLMs) excel at understanding natural language but struggle with optimisation tasks involving user-defined preferences.<n>We propose a hybrid reasoning approach in which LLMs externalise reasoning through code generation.<n>Our results demonstrate that LLM-driven code generation combined with preference-based MaxSAT enables solver-verifiable optimisation.
• Score: 19.16962344736341
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Large Language Models (LLMs) excel at understanding natural language but struggle with optimisation tasks involving multiple constraints and user-defined preferences, which commonly arise in domains such as robotics. We propose a hybrid reasoning approach in which LLMs externalise reasoning through code generation. Given a natural language problem description, an LLM generates Python code that encodes user-defined constraints and preferences as a preference-based Maximum Satisfiability (MaxSAT) problem, which is then solved by an exact MaxSAT solver. To ensure correctness, solutions returned by the model-generated code are independently verified for feasibility and optimality against a canonical MaxSAT encoding, allowing for different encodings and multiple optimal solutions. We evaluate our approach using both open-source and closed-access LLMs on three families of preference-based reasoning tasks, and compare it against direct-answer, chain-of-thought, and program-of-thought baselines using the same models. While these baselines rarely produce feasible solutions, the MaxSAT-based pipeline achieves substantially higher acceptance rates, in some cases exceeding 80%. Our results demonstrate that LLM-driven code generation combined with preference-based MaxSAT enables solver-verifiable optimisation with respect to generated encodings, and substantially improves correctness under independently verified reference semantics.

Related papers

• MaxSAT-Based Feedback for Guiding Vision-Language Models in Sudoku [9.132725363009044]
  Vision--Language Models (VLMs) have recently demonstrated promising performance on structured visual reasoning tasks.<n>We propose a neuro-symbolic approach that integrates formal constraint reasoning into the VLM solving process.
  arXiv  Detail & Related papers  (2026-07-14T12:39:05Z)
• Generating Robust Portfolios of Optimization Models using Large Language Models [27.600634702684733]
  We develop a novel way to generate and evaluate optimization models.<n>We provide theoretical guarantees showing that the portfolio is well-aligned with human preferences.<n>We demonstrate strong performance across range optimization modeling tasks.
  arXiv  Detail & Related papers  (2026-05-26T13:30:43Z)
• Formalize, Don't Optimize: The Heuristic Trap in LLM-Generated Combinatorial Solvers [52.23061619664667]
  Large Language Models (LLMs) struggle to solve complex problems through direct reasoning, so recent neuro-symbolic systems increasingly use them to synthesize executable solvers.<n>We introduce CP-SynC-XL, a benchmark of 100 problems (4,577 instances), and evaluate three solver--construction paradigms: native algorithmic search (Python), constraint modeling through a Python solver API (Python + OR-Tools), and declarative constraint modeling.
  arXiv  Detail & Related papers  (2026-05-12T17:15:45Z)
• Execution-Verified Reinforcement Learning for Optimization Modeling [49.171122807323634]
  Execution-verified learning framework treats a mathematical programming solver as a deterministic, interactive verifier.<n>Experiments on NL4OPT, MAMO, IndustryOR, and OptiBench across Gurobi, OR-Tools, and COPT show that EVOM matches or outperforms process-supervised SFT.
  arXiv  Detail & Related papers  (2026-04-01T03:39:11Z)
• Multi-Objective Hierarchical Optimization with Large Language Models [41.41567058185742]
  Large Language Models (LLMs) are not the off-the-shelf choice to drive multi-objective optimization yet.<n>In this paper, we close this gap by leveraging LLMs as surrogate models and candidate samplers inside a structured hierarchical search strategy.
  arXiv  Detail & Related papers  (2026-01-20T12:10:13Z)
• LLMize: A Framework for Large Language Model-Based Numerical Optimization [0.0]
  Large language models (LLMs) have recently shown strong reasoning capabilities beyond traditional language tasks.<n>This paper presents LLMize, an open-source Python framework that enables LLM-driven optimization.
  arXiv  Detail & Related papers  (2025-12-30T20:05:30Z)
• Toward a Trustworthy Optimization Modeling Agent via Verifiable Synthetic Data Generation [11.988926173584154]
  We present a framework for training trustworthy large language model (LLM) agents via a synthetic data generation pipeline.<n> OptiTrust is a modular LLM agent that performs multi-language translation from natural language to solver-ready code.<n>Our agent achieves state-of-the-art performance on standard benchmarks.
  arXiv  Detail & Related papers  (2025-08-05T05:54:20Z)
• Self-ensemble: Mitigating Confidence Mis-calibration for Large Language Models [67.62810111789338]
  Large Language Models exhibit a confidence distortion problem on multi-choice question-answering.<n>We propose Self-ensemble to solve this problem.<n> Experimental results on three LLMs and datasets demonstrate that Self-ensemble comprehensively addresses the confidence distortion problem.
  arXiv  Detail & Related papers  (2025-06-02T17:59:29Z)
• Latent Preference Coding: Aligning Large Language Models via Discrete Latent Codes [54.93980123979578]
  We introduce Latent Preference Coding (LPC), a novel framework that models the implicit factors as well as their combinations behind holistic preferences.<n>LPC seamlessly integrates with various offline alignment algorithms, automatically inferring the underlying factors and their importance from data.
  arXiv  Detail & Related papers  (2025-05-08T06:59:06Z)
• Syntactic and Semantic Control of Large Language Models via Sequential Monte Carlo [90.78001821963008]
  A wide range of LM applications require generating text that conforms to syntactic or semantic constraints.<n>We develop an architecture for controlled LM generation based on sequential Monte Carlo (SMC)<n>Our system builds on the framework of Lew et al. (2023) and integrates with its language model probabilistic programming language.
  arXiv  Detail & Related papers  (2025-04-17T17:49:40Z)
• LLaMA-Berry: Pairwise Optimization for O1-like Olympiad-Level Mathematical Reasoning [56.273799410256075]
  The framework combines Monte Carlo Tree Search (MCTS) with iterative Self-Refine to optimize the reasoning path. The framework has been tested on general and advanced benchmarks, showing superior performance in terms of search efficiency and problem-solving capability.
  arXiv  Detail & Related papers  (2024-10-03T18:12:29Z)
• Solving General Natural-Language-Description Optimization Problems with Large Language Models [34.50671063271608]
  We propose a novel framework called OptLLM that augments LLMs with external solvers. OptLLM accepts user queries in natural language, convert them into mathematical formulations and programming codes, and calls the solvers to calculate the results. Some features of OptLLM framework have been available for trial since June 2023.
  arXiv  Detail & Related papers  (2024-07-09T07:11:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.