GPT-4 Doesn't Know It's Wrong: An Analysis of Iterative Prompting for Reasoning Problems

Over recent years, large language models such as GPT-3 and GPT-4 have demonstrated impressive linguistic abilities, sparking interest in their reasoning potential. Early hypotheses suggested that increasing model scale could lead to emergent reasoning skills, but subsequent studies revealed significant limitations, especially in logic, arithmetic, and planning tasks. Research by Kojima et al. (2022) and others questioned whether these models can truly understand and verify complex solutions. The community has explored prompting strategies, chain-of-thought reasoning, and self-critique, yet conclusive evidence of robust reasoning remains elusive. The challenge lies in the models’ internal verification capabilities, which are often weak or unreliable, especially for NP-hard problems like graph coloring, which require combinatorial reasoning and validation beyond pattern matching.

The core issue addressed is whether GPT-4 can effectively verify and improve its solutions in complex reasoning tasks, specifically graph coloring. Despite claims of emergent reasoning, empirical evidence suggests models struggle with internal validation, often passing incorrect solutions or failing to recognize correct ones. This limits the effectiveness of iterative prompting strategies that rely on self-critique. The problem is compounded by the models’ inability to distinguish between correct and incorrect solutions reliably, raising questions about their suitability for high-stakes applications requiring verifiable correctness.

This work introduces a comprehensive evaluation framework combining multiple feedback strategies, external formal verification, and top-k sampling to assess GPT-4’s reasoning and verification abilities. It innovates by systematically contrasting self-critique versus external validation, revealing that external verifiers significantly outperform self-assessment. The approach also demonstrates that success largely depends on chance, challenging assumptions about the emergent reasoning capabilities of LLMs. The integration of external correctness checks with probabilistic sampling offers a new paradigm for reliable reasoning systems, bridging neural models with formal verification techniques.

• �� Generate 100 random graph instances using Erdős–Rényi model, ensuring diversity and manageable complexity.
• �� Translate graphs into natural language prompts describing edges and coloring constraints.
• �� Implement multiple prompting strategies: direct solving, self-critique, external verifier with various feedback depths (fail, first error, all errors).
• �� Use GPT-4 API with temperature=0 for deterministic outputs, and apply top-k sampling (up to 15 answers) to increase chance of correct solutions.
• �� Integrate a formal external verifier that checks correctness by enumerating all violated constraints.
• �� Record success rates, analyze the impact of feedback content, and compare iterative versus non-iterative approaches.
• �� Conduct ablation studies to isolate effects of feedback richness and sampling size, ensuring robustness of conclusions.

The experimental setup involved 100 graph instances with nodes 10-17, edges averaging 24, generated via Erdős–Rényi. The models attempted to solve these directly, with iterative self-critique, and with external verification. Different feedback strategies were tested, including minimal (fail/pass), detailed (all errors), and model-generated feedback. Multiple sampling (up to 15 answers) was used to evaluate the chance of hitting correct solutions. Success rates, verification accuracy, and error types were systematically recorded. The experiments aimed to quantify the influence of feedback content, sampling size, and external verification on overall performance, providing a comprehensive assessment of GPT-4’s reasoning and validation capabilities.

GPT-4’s baseline success rate was only 16%. Self-critique strategies did not improve performance; they often worsened it due to the model’s inability to recognize correct solutions. External verification combined with top-k sampling increased success to nearly 40%, with minimal differences across feedback types. The model’s verification accuracy was extremely low, correctly identifying less than 10% of solutions. Multiple sampling approaches yielded similar improvements, indicating that success depends more on chance than genuine reasoning. These results highlight the current limitations of LLMs in internal validation and reasoning, emphasizing the necessity of external correctness checks.

Findings inform the design of AI systems requiring high reliability, such as automated scheduling, resource allocation, and decision-making in safety-critical domains. Integrating external formal verification modules with neural models can enhance correctness guarantees. The approach can be extended to other NP-hard problems, complex planning, and multi-modal reasoning tasks, fostering development of hybrid AI architectures that combine neural flexibility with symbolic rigor, ultimately improving trustworthiness and robustness in real-world applications.

The study focuses solely on graph coloring, limiting generalizability to other reasoning domains. The models’ verification weakness constrains the effectiveness of self-critique strategies. Feedback content has limited impact, indicating poor information utilization. Computational costs are high due to multiple sampling and external verification, affecting scalability. Future work should explore integrating formal reasoning modules, improving internal validation, and testing broader problem sets to enhance model reliability.