VCSearch: Bridging the Gap Between Well-Defined and Ill-Defined Problems in Mathematical Reasoning

Shi-Yu Tian, Zhi Zhou, Kun-Yang Yu, Ming Yang, Lin-Han Jia, Lan-Zhe Guo, Yufeng Li

TL;DR

This paper introduces VCSEARCH, a novel framework that uses formal language and a variable-constraint search strategy to help Large Language Models (LLMs) better identify and reject ill-defined mathematical problems (those with missing or contradictory information). This approach significantly improves robustness in mathematical reasoning, achieving at least a 12% increase in identifying unsolvable problems across various LLMs.

What Problem Does This Paper Address?

Modern LLMs excel at mathematical reasoning, but current evaluations primarily focus on "well-defined" problems where all necessary information is provided. In real-world scenarios, however, mathematical problems are often "ill-defined," containing missing or contradictory conditions. This can lead LLMs to generate plausible but incorrect solutions instead of recognizing the problem's unsolvability, potentially reinforcing misconceptions. Existing benchmarks don't systematically evaluate this crucial aspect of robust reasoning. The authors address this gap by developing a new benchmark and a method to improve LLMs' ability to handle these challenging, real-world problems.

Methods

The core contribution is VCSEARCH (Variable-Constraint Search), a training-free framework designed to detect ill-defined problems. It leverages formal language (SMT-LIB) and a novel variable-constraint dynamic search mechanism. This mechanism iteratively decomposes complex problems into smaller, manageable variable-constraint pairs. The process involves:

  1. Preparation: Identifying constraints related to a specific "head" variable.
  2. Exploration: Using LLM knowledge to refine these constraints and discover new variables.
  3. Verification: Using an SMT solver to check the satisfiability and uniqueness of the generated model.

VCSEARCH also incorporates an Anchored Initialization step, using LLM reasoning to generate a preliminary model state, which helps overcome the "cold start" problem of the search process. The framework integrates with existing LLMs and formal solvers (like Z3) to enhance their reasoning and rejection capabilities.

Datasets

The authors introduce a new large-scale benchmark called Problems with Missing and Contradictory conditions (PMC), containing over 5,000 validated ill-defined mathematical problems. PMC is constructed by mutating problems from four common math datasets (GSM8k, SVAMP, AddSub, MultiArith) to create "Missing-type" and "Contra-type" problems. They also use these original datasets, along with Robustmath and GSM-IC, for evaluating well-defined problem-solving.

Key Insights and Ideas

  • The Trade-off: A significant challenge for LLMs is the inherent trade-off between solving well-defined problems accurately and rejecting ill-defined ones. Improving one often degrades the other.
  • Formal Language as a Bridge: Formal languages and SMT solvers can provide a robust mechanism for detecting unsolvable problems, but LLMs struggle to model complex problems accurately in formal language in a single pass.
  • Iterative Refinement is Key: VCSEARCH's iterative variable-constraint search allows for a more systematic and accurate modeling of complex problems, progressively improving the formal representation.
  • Real-World Relevance: Evaluating LLMs solely on well-defined problems misses a critical aspect of their practical utility. Robustness in handling ambiguity and contradictions is paramount.

Key Results

  • VCSEARCH improves the accuracy of identifying unsolvable problems by at least 12% across different LLMs.
  • The framework significantly outperforms traditional methods (like CoT and PAL) in rejecting ill-defined problems, with rejection rates improving by over 42% when combined with these methods.
  • VCSEARCH demonstrates strong robustness, maintaining consistent performance across models of varying sizes.
  • The method shows significant improvements in modeling capabilities, particularly for smaller base models, with an average accuracy improvement of 14.95% on well-defined problems compared to conventional few-shot approaches.

Limitations and Future Work

  • Time Consumption: VCSEARCH's iterative nature incurs higher computational overhead compared to baseline approaches, which might limit scalability for very large datasets or real-time scenarios. Future work could explore techniques for reducing this overhead, such as pruning or parallelization.
  • Formal Tool Limitations: The method's reliance on SMT solvers means it will reject tasks that cannot be adequately modeled with logical constraints. This can lead to overly conservative behavior, potentially rejecting some well-defined problems. Extending the framework with more flexible or hybrid reasoning mechanisms could address this.
  • Model Scale: While VCSEARCH mitigates performance degradation on smaller models, performance still generally correlates with model size.
  • Future Work: The authors suggest exploring techniques for reducing computational overhead and investigating more flexible reasoning mechanisms to alleviate the conservativeness of formal tools.

Summary updated

Abstract

Large language models (LLMs) have demonstrated impressive performance on reasoning tasks, including mathematical reasoning. However, the current evaluation mostly focuses on carefully constructed benchmarks and neglects the consideration of real-world reasoning problems that present missing or contradictory conditions, known as ill-defined problems. To further study this problem, we develop a large-scale benchmark called Problems with Missing and Contradictory conditions (PMC) containing over 5,000 validated ill-defined mathematical problems. Our preliminary experiments through PMC reveal two challenges about existing methods: (1) traditional methods exhibit a trade-off between solving accuracy and rejection capabilities, and (2) formal methods struggle with modeling complex problems. To address these challenges, We develop Variable-Constraint Search (VCSearch), a training-free framework that leverages formal language to detect ill-defined problems, where a variable-constraint pair search strategy is incorporated to improve the modeling capability of formal language. Extensive experiments demonstrate that VCSearch improves the accuracy of identifying unsolvable problems by at least 12% across different LLMs, thus achieving stronger robust mathematical reasoning ability.
BibTeX
@inproceedings{tian2025vcsearch,
  author = {Shi-Yu Tian and Zhi Zhou and Kun-Yang Yu and Ming Yang and Lin-Han Jia and Lan-Zhe Guo and Yufeng Li},
  title = {{VCSearch: Bridging the Gap Between Well-Defined and Ill-Defined Problems in Mathematical Reasoning}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2025},
  url = {https://openreview.net/forum?id=z8PyS02Twn},
}
Figure