stat.MLSep 17, 2026

Complex Problem Solving in Large Language Models: A Statistical Control Survey and Diagnostic Framework

Authors: Jiazhang Cai, Tao Wang, Ruidong Zhang, Siyuan Li, Terry Ma, Luyang Fang, Haoran Lu, Huimin Cheng, 

Organizations: Department of Genetics and Genomic Science, Icahn School of Medicine at Mount Sinai, New York, NY, USA. · Department of Statistics, University of Georgia, Athens, GA, USA. · School of Computing, University of Georgia, Athens, GA, USA. · School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, USA. · 

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Complex problem solving (CPS) with large language models (LLMs) is often framed as a matter of stronger reasoning or longer generation. Yet early-step error amplification, prompt brittleness, and failures to revise incorrect commitments are difficult to explain by missing knowledge or expressive capacity alone. This survey interprets CPS as a sequential estimation-and-decision problem over a latent solution state. A controller maintains a belief about an unobserved solution trajectory, updates it as noisy intermediate evidence arrives, and decides whether to commit, verify, branch, roll back, or abstain to minimize expected loss. Reasoning supplies candidate transitions and interpretations, whereas process control shapes and evaluates those proposals and regulates subsequent transitions and observations. Within this framework, we organize existing methods around five components: explicit state representation, transition structuring, validation and constraint enforcement, search and rollback, and uncertainty management. We also interpret evaluation metrics according to the statistical quantities they estimate. The framework further yields a diagnostic hypothesis: interventions should be most effective when they target the error or uncertainty component implicated by an observed failure. We distinguish systematic, stochastic, and irreducible error together with epistemic and aleatoric uncertainty, and call this alignment problem-control fit and its failure control mismatch. For example, additional sampling may reduce sampling variability while leaving a shared systematic error unchanged. This perspective clarifies what current methods estimate and control, what remains uncontrolled, and why reliable validation, targeted recovery, calibrated uncertainty, and matched-budget evaluation are central open problems.

Figures & tables

Figure 1: Error propagation under contracting and expanding updates. Starting from the same early perturbation, a locally contracting update ( ∥Jt∥<1\lVert J_{t}\rVert<1 ) attenuates the error, whereas an expanding update ( ∥Jt∥>1\lVert J_{t}\rVert>1 ) amplifies it geometrically along the trajectory. The figure is an analytical schematic of the local stability interpretation in Equation ( 1 ), rather than an empirical trajectory
Failure signatureLikely implicated term (component)Candidate matched interventionLikely mismatch
Same wrong formulation across samplesFormulation bias (transition)Reformulate, replanSelf-consistency
Same arithmetic or factual slip across samplesComputation bias (validation)Executable check, program groundingLonger CoT
Answer varies, correct one recursVariance (search)Self-consistency, rerankingLonger single chain
Confident on ambiguous inputInput ambiguity / aleatoric uncertaintyClarify, abstain, or use selective predictionForce an answer
Early error contaminates the restState-estimate divergence (validation, state)Step validation, targeted rollbackResample whole trajectory
Early commitment forecloses pathsPosterior collapsed early (search)Branch, keep modesValidate one trajectory
Table 1: Problem–control fit as a diagnostic hypothesis, read through the error decomposition of ( 4 ). Each row pairs a characteristic failure signature with a plausibly implicated error component (and loop component), a candidate matched intervention, and an intervention likely to leave that signature unaddressed. The mapping is not unique or causally identified from the signature alone. Sampling-based aggregation primarily addresses sampling variability and may leave shared systematic errors or irreducible ambiguity unchanged.
Figure 2: The estimation-and-decision loop. Reasoning proposes candidate moves, while the selected control action shapes the next-state transition and the evidence that becomes available; the observation model then updates the belief, and the decision rule commits, verifies, branches, rolls back, or abstains under that belief. Decision-relevant uncertainty, not posterior spread alone, informs how aggressively the rule explores or commits. The five components of Section 2.4 are parts of this one loop, and distributing control across agents and internalizing it at training time are cross-cutting dimensions that reshape, but do not replace, it
MethodStateTrans.Search/Valid.Uncert.Multi-Train.
   rollback  agent 
Chain-of-Thought ( Wei et al., 2022b )✓      
Scratchpad ( Nye et al., 2021 )✓      
Tree-of-Thoughts ( Yao et al., 2023a )✓ ✓    
Least-to-Most ( Zhou et al., 2023a ) ✓     
PAL / PoT ( Gao et al., 2023 ; Chen et al., 2023b ) ✓ ✓   
Table 2: Representative LLM methods mapped onto the control components they implement. Most methods realize more than one component, which is why we organize the survey by component rather than by method.
Figure 3: The diagnostic as an error decomposition. Following ( 4 ), the error of a solved trajectory separates into a systematic component (bias, shared across sampled trajectories), a stochastic component (variance, sample-dependent), and an irreducible component (noise, aleatoric). The systematic component splits into a formulation bias, repaired at the transition by reformulation or replanning, and a computation bias, repaired at validation by an executable check. Sampling-based aggregation primarily targets sample-dependent variation; it may leave errors shared by the dominant trajectories and irreducible ambiguity unchanged, which is the control mismatch illustrated at the bottom
Published resultDominant componentReading under the decomposition
Self-consistency: GSM8K 56.5 ⁣→ ⁣74.456.5\!\rightarrow\!74.4 but CommonsenseQA 79.0 ⁣→ ⁣80.779.0\!\rightarrow\!80.7 (PaLM-540B) ( Wang et al., 2022 )Task-dependent benefit from samplingAggregation helps substantially more on GSM8K in this setting, but these two results alone do not identify which error component caused the difference.
GSM-HARD: chain-of-thought 23.123.1 vs program-aided 61.261.2 (Codex) ( Gao et al., 2023 )Executable computationDelegating arithmetic to an interpreter improves this large-number task; the comparison does not measure error correlation across samples.
Longer reasoning or more inference-time compute leaves accuracy flat or lower ( Chen et al., 2025 ; Wang et al., 2025 )Possible effort mismatchThe result is consistent with misallocated effort, but the cited studies do not isolate which control component should have received the budget.
Table 3: The diagnostic read against published results. Each row reports an existing finding, the failure component suggested by our framework, and why the intervention is consistent with that diagnosis. These studies do not causally identify the component itself. Numbers are quoted from the cited papers and are comparable within a row, not across rows.
Figure 4: Domain-dependent control requirements. Different problem domains place their primary control burden on different components: search- and planning-intensive domains on transition structuring and search, validation-heavy domains on executable checking, and uncertainty-dominated domains on estimation and abstention. In statistical terms, these regimes emphasize the proposal kernel and posterior search, the likelihood or observation model, and, when ambiguity is intrinsic, the irreducible aleatoric component, respectively. This domain-level view complements the failure-level diagnostic in Table 1
Figure 5: From implicit computation to explicit intermediate state. (a) In vanilla LLM generation, intermediate computation remains hidden, so no observable state is available between the problem and the final answer. (b) Chain-of-Thought prompting externalizes a single linear sequence of textual states, making the intermediate trajectory visible. (c) Scratchpad prompting strengthens this representation by explicitly storing intermediate values in a working memory that can be reused across later steps, yielding persistent working state. (d) Tree-of-Thoughts further generalizes explicit state into a branching structure, allowing multiple candidate states to coexist before commitment. Across this progression, explicit state capacity increases from implicit internal computation to visible, persistent, and branching intermediate state; however, these methods primarily enrich state representation rather than directly constraining how state transitions are updated
Figure 6: A spectrum of increasingly constrained transition mechanisms in intermediate reasoning. (a) Free-form language transitions rely on unconstrained natural language to move between intermediate steps. (b) Decomposition-based transitions introduce explicit plans, subgoals, or ordered subproblems to regulate how the reasoning process proceeds. (c) Program- and tool-grounded transitions further constrain intermediate updates by translating reasoning into executable code or tool-invocation steps. (d) Hybrid structured transitions combine natural language reasoning with executable programmatic steps, integrating the interpretability of textual explanation with the precision of symbolic execution
Figure 7: LLM Reasoning with Search, Rollback, and Iterative Correction. (a) Self-Consistency: Majority vote over sampled paths. (b) Tree Search: Systematic navigation with scoring and pruning. (c) Self-Refine: Iterative draft-critique-revise cycles. (d) Multi-Agent Debate: Interactive deliberation with critique and reflection to achieve consensus
Benchmark (model)Intrinsic self-correctionExternal verificationSource
GSM8K (GPT-4)95.5→89.095.5\to 89.095.5→97.595.5\to 97.5Huang et al. (2024b)
CommonsenseQA (GPT-3.5)75.8→41.875.8\to 41.875.8→89.775.8\to 89.7Huang et al. (2024b)
Graph colouring (GPT-4)16→216\to 216→3816\to 38Stechly et al. (2025)
Blocksworld (GPT-4)40→5540\to 5540→8740\to 87Stechly et al. (2025)
Code repair, APPS (GPT-4)33.333.3 (GPT-4 feedback)52.652.6 (human feedback)Olausson et al. (2024)
Table 4: Intrinsic self-correction versus external verification, reported as accuracy or task success (%). The intrinsic column shows performance after self-correction with no external signal; the external column shows performance when a sound verifier, an oracle stopping rule, or a stronger feedback source is available. Settings and metrics differ across papers, so entries are comparable within a row, not across rows.
Loop componentRepresentative evaluation signalStatistical quantity estimated
Explicit statetrace inspectability; state-recovery probessufficiency of the state statistic
Transition structuringstep-level validity; decomposition correctnessbias of the proposal kernel
Validationexecution accuracy ( Chen et al., 2021 ) ; prover pass rate ( Lightman et al., 2023 )risk under an executable loss; likelihood fit
Search / rollbackself-consistency ( Wang et al., 2022 ) ; recovery-after-error ratevariance / dispersion of the answer estimator
Uncertaintycalibration, ECE and Brier ( Kadavath et al., 2022 ) ; selective accuracyproper scoring; risk–coverage of the retained set
Cross-cuttingfaithfulness ( Lanham et al., 2023 ) ; efficiency (tokens, latency)causal sufficiency of the trace; cost per unit risk reduced
Table 5: Mapping common evaluation signals onto the loop component they probe and the statistical quantity each estimates.
Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

MethodComponentMechanismWhat remains uncontrolled
Chain-of-ThoughtExplicit stateexternalizes a linear textual tracevalidity of the individual transitions
Tree-of-ThoughtsState, searchbranches over candidate states with backtrackingbranching and rollback are fixed, not feedback-driven
PAL / PoTTransition, validationoffloads computation to executable codecorrectness of the problem formulation
Self-Refine / ReflexionSearch, rollbackrevises a draft using self-generated feedbackreliability of the self-critique
Verifier-guided searchValidation, uncertaintyscores partial paths with a verifier and prunesverifier failures at scale
Multi-agentDistributed controlsplits roles across agents with cross-checkscorrelated errors across agents
Appendix
Table 6: A closer view of representative methods: the component each implements, the mechanism it uses, and what it leaves uncontrolled. This refines the checkmark mapping of Table 2 into the argument the survey makes about each pattern; evaluation signals for each component are collected separately in Table 5 .
More in this topic

LLM Reasoning

Large language model reasoning studies how models solve multi-step problems, verify intermediate steps, and use computation or tools reliably.

See all 931 papers

Explore similar work

CardsList
Apr 15, 2026

Empirical Evidence of Complexity-Induced Limits in Large Language Models on Finite Discrete State-Space Problems with Explicit Validity Constraints

Large Language Models (LLMs) are increasingly described as possessing strong reasoning capabilities, supported by high performance on mathematical, logical, and planning benchmarks. However, most existing evaluations rely on aggregate accuracy over fixed datasets, obscuring how reasoning behavior evolves as task complexity increases. In this work, we introduce a controlled benchmarking framework to systematically evaluate the robustness of reasoning in Large Reasoning Models (LRMs) under progressively increasing problem complexity. We construct a suite of nine classical reasoning tasks: Boolean Satisfiability, Cryptarithmetic, Graph Coloring, River Crossing, Tower of Hanoi, Water Jug, Checker Jumping, Sudoku, and Rubik's Cube, each parameterized to precisely control complexity while preserving underlying semantics. Using deterministic validators, we evaluate multiple open and proprietary LRMs across low, intermediate, and high complexity regimes, ensuring that only fully valid solutions are accepted. Our results reveal a consistent phase transition like behavior: models achieve high accuracy at low complexity but degrade sharply beyond task specific complexity thresholds. We formalize this phenomenon as reasoning collapse. Across tasks, we observe substantial accuracy declines, often exceeding 50%, accompanied by inconsistent reasoning traces, constraint violations, loss of state tracking, and confidently incorrect outputs. Increased reasoning length does not reliably improve correctness, and gains in one problem family do not generalize to others. These findings highlight the need for evaluation methodologies that move beyond static benchmarks and explicitly measure reasoning robustness under controlled complexity.

Md. Fahad Ullah Utsho, Mohd. Ruhul Ameen, Akif Islam +2

Department of Information and Communication Engineering, University of Rajshahi, Bangladesh · College of Engineering and Computer Sciences, Marshall University, Huntington, WV, USA · Department of Computer Science and Engineering, University of Rajshahi, Bangladesh

LLM EvaluationLarge Reasoning ModelsReasoning Consistency in Language ModelsConstraint Satisfaction
AskPDF
Sep 3, 2026

It's the Problem, Not the Path: Budget and Difficulty Confounds in LLM Reasoning Trajectories

Reasoning traces of large language models are widely read as containing "breakthrough" moments and early-legible fates. Both readings rest on measurements missing a counterfactual control at the level of the claim; we supply both controls. First, a restart-controlled truncation probe separates when a solution fits the continuation budget from when a prefix carries value that fresh computation cannot buy, comparing per-anchor continuation solve rates against from-scratch restart curves at matched total generated-token budget. Applied to 178 problem-model cells (89 MATH problems x two small open models, an outcome-blind but difficulty-targeted cohort), exactly 1 of 178 cells survives as prefix-limited; restart dose-response separates a compute-starved model from a capability-limited one; and wherever the matched budget lies inside the restart grid, continuing the model's own prefix beats restarting (9 of 9) -- predominantly compute compression rather than expanded reachability. Second, a pre-registered, difficulty-controlled test finds no detectable outcome information in early-window internal signals beyond a problem-difficulty baseline, and two generation-free analyses of public corpora show why this control is needed: a trace-blind difficulty proxy reaches AUROC 0.873 on 192K DeepSeek-R1 generations -- inside the published probe range -- and a closely matched reconstruction of the closest published early-window positive recovers a comparable pooled result (0.849) while within problem it is statistically indistinguishable from chance at all ten anchors (0.496 at t=4); a post-hoc within-targeted probe finds only a small average residual, concentrated in three low-failure problems. High pooled probe AUROCs cannot by themselves establish within-attempt information; a question-only baseline or within-problem evaluation is required.

Yigit Utku Bulut

Johannes Kepler University Linz

LLM EvaluationLanguage Model ProbingLLM Reasoning
AskPDF
Feb 21, 2026

Think2^{2}: Grounded Metacognitive Reasoning in Large Language Models

Large Language Models (LLMs) demonstrate strong reasoning performance, yet their ability to reliably monitor, diagnose, and correct their own errors remains limited. We introduce a psychologically grounded metacognitive framework that operationalizes Ann Brown's regulatory cycle (Planning, Monitoring, and Evaluation) as a structured prompting architecture, and study its integration within a lightweight dual-process MetaController for adaptive effort allocation. Across diverse reasoning and diagnostic benchmarks (GSM8K, CRUXEval, MBPP, AIME, CorrectBench, and TruthfulQA) using Llama-3 and Qwen-3 (8B), explicit regulatory structuring substantially improves error diagnosis and yields a threefold increase in successful self-correction. Blinded human evaluations over 580 query pairs show an 84% aggregate preference for trustworthiness and metacognitive self-awareness over standard and Chain-of-Thought baselines. Grounding LLM reasoning in established cognitive theory offers a principled path toward more transparent and diagnostically robust AI systems.

Abraham Paul Elenjical, Vivek Hruday Kavuri, Vasudeva Varma

IIIT Hyderabad

Language Model Self-AssessmentMetacognition in Language ModelsLLM Self-CorrectionLLM ReliabilityAdaptive Computation
AskPDF