UC Irvine

Large language models (LLMs) exhibit impressive fluency and surface-level reasoning skills, yet they continue to struggle with deep, verifiable, and logically structured reasoning. Despite strong empirical performance on natural language benchmarks, LLM reasoning can be improved: models sometimes generate plausible but incorrect solutions, fail under increased compositional complexity, and lack transparent, step-by-step justification. A key challenge is that current reasoning benchmarks are static, passive, and non-generative, restricting research to solving predefined problems rather than developing mechanisms for creating and improving reasoning tasks themselves.This dissertation introduces a unified paradigm of Generative Problem Solving (GPS), reframing reasoning from the traditional objective of solving fixed tasks to a generative process of creating, solving, and verifying problems. We argue that enabling AI systems to generate structured reasoning tasks is an essential step toward overcoming LLM limitations and advancing beyond pattern imitation toward true deductive reasoning.The first contribution, GPS-Reasoning, is a symbolic problem-generation framework grounded in First-Order Logic (FOL). It systematically synthesizes valid, interpretable, and difficulty-controlled reasoning tasks using template-driven Abstract Syntax Trees (AST), model-first satisfiability planning, and symbolic verification via Vampire. Unlike static benchmarks such as FOLIO and LogicNLI, GPS-Reasoning supports scalable curriculum generation, reverse inference trace construction, and fine-grained control over logical complexity. By coupling synthetic generation with symbolic verification, it produces provably correct reasoning problems with explicit inference chains, enabling rigorous evaluation that can be understood by humans.The second contribution, Influence-Preserving Graph Synthesis (IPGS), addresses generative dataset construction under dynamic influence diffusion settings. Traditional Influence Maximization (IM) research assumes static networks, while real-world networks evolve over time and influence dominance shifts. IPGS constructs dynamic graph datasets that preserve expected influence of initial seeds through stratified Reverse Influence Sampling (RIS), incremental RR-set regrow strategies, and deterministic structural reinforcement. Experimental results demonstrate unbiased estimation, bounded influence drift under Hoarding concentration behavior, and near-optimal seed retention with minimal intervention across BA and ER network families.Together, these contributions establish a generative foundation that bridges modern LLM-based reasoning with classic symbolic AI. Classic AI provides formal logic, exact semantics, and verifiable inference; LLMs provide generative scalability, expressiveness, and abstraction. GPS unifies these strengths to enable AI systems that are transparent, controllable, and trustworthy. We believe that generative problem solving represents a step beyond passive benchmark solving toward AI that actively constructs knowledge, reasons over structure, and improves through generation.By integrating symbolic reasoning structure with scalable generative mechanisms, this dissertation contributes a path toward robust and interpretable reasoning systems, advancing the long-standing goal of combining the rigor of classic AI with the power of modern neural models.