Knowledge Augmented Complex Problem Solving with Large Language Models: A Survey
A survey unifies CoT, RAG, and verifiers for complex LLM problem solving, but reports no new benchmark metrics.
Key Findings
Methodology
The survey decomposes complex problem solving into multi-step reasoning, domain-knowledge integration, and result verification. It reviews Chain-of-Thought (CoT), multi-path inference and inference scaling; RAG, GraphRAG, knowledge graphs and human interaction; and verification through LLM-as-a-judge, symbolic reasoning tools, and experimental validation.
Key Results
- Because this is a survey rather than a new-model paper, it reports no unified accuracy on GSM8K, MATH, or HumanEval and no percentage improvement. Its synthesis of prior work is that increasing the number of CoT paths generally raises the chance of finding a correct solution, while search space and inference cost grow with reasoning depth.
- GPT-o1 and DeepSeek-R1 are discussed as representative reasoning-scaled systems. RAG, GraphRAG, and knowledge graphs are identified as useful for long-tail knowledge in scientific discovery, theorem proving, and data science. The paper does not provide a controlled head-to-head benchmark among these systems.
- Verifiers are needed both to filter synthetic training traces and to select among multiple inference candidates. They may be LLM judges, symbolic tools, or experimental systems. Open-ended scientific and data-mining tasks remain difficult because they lack unique, predefined answers.
Significance
The paper distinguishes “reasoning well” from “solving real problems reliably.” Mathematical reasoning and competitive programming are relatively favorable because goals are explicit and outputs are easy to check. Software engineering requires repository-level understanding and efficiency; data science requires distribution-sensitive evaluation; scientific research involves open-ended goals. This framing gives researchers and practitioners a common vocabulary for designing and auditing agentic LLM systems.
Technical Contribution
Its contribution is a formal synthesis rather than a new algorithm. It defines a problem Π(X,Y,P), goal set G={Y∈Y|P(Y;X)}, feasible traces X→O1→…→Oκ→Y, and an algorithm quintuple A=(X,Y,O,δ,σ0). This separates cognition-guided human solving from computer-assisted state transitions and places planning, retrieval, tool use, and verification within one state-space perspective.
Novelty
Unlike surveys focused primarily on CoT or reasoning models, this work treats multi-step reasoning, knowledge augmentation, and verification as jointly necessary for real-world complex solving. It spans software engineering, mathematics, data science, and scientific research. Its novelty is therefore cross-domain integration and formal framing, not a new objective, dataset, theorem, or performance guarantee.
Limitations
- There is no unified benchmark, dataset protocol, metric aggregation, or meta-analysis, so the relative gains of CoT, RAG, GraphRAG, and different verifiers cannot be quantified from this paper.
- The supplied manuscript contains bibliographic inconsistencies: the text is an arXiv:2505.03418v1 survey from 2025, while the citation block displays a 2018 JACM publication template. Readers should treat the arXiv version as authoritative.
Future Work
Future research should build reproducible cross-domain benchmarks evaluating trace correctness, knowledge faithfulness, tool execution, cost, and downstream utility. Promising directions include verifiable long-horizon planning, retrieval and memory for long-tail knowledge, formal theorem proving, executable code and experiment loops, and human-LLM collaboration for scientific tasks whose objectives must be jointly defined.
AI Executive Summary
Complex problem solving is not merely producing a longer answer. It requires selecting a valid sequence of intermediate states from an input X to an output Y satisfying a predicate P(Y;X). The paper argues that real-world tasks are harder than benchmark mathematics because their goals may be ambiguous, their knowledge requirements long-tailed, and their solutions difficult to verify.
Its central synthesis has three parts. Chain-of-Thought (CoT) expands multi-step plans and benefits from multiple sampled paths; RAG, GraphRAG, and knowledge graphs supply external domain knowledge; and LLM judges, symbolic tools, or experiments verify candidates. More paths can improve solution discovery, but search and inference costs rise. GPT-o1 and DeepSeek-R1 illustrate the promise of this scaling-based reasoning paradigm.
The paper introduces no new model and reports no new accuracy, dataset comparison, or ablation. Its value is conceptual: reliable systems must close the loop among planning, retrieval, execution, and verification. Code agents must understand repositories; data agents must respect distributions; theorem provers need rigor; research agents need humans to define goals. The next frontier is not only stronger reasoning, but traceable, testable, and reproducible reasoning.
Deep Analysis
Background
LLMs have evolved from text generators into systems that plan, write code, and invoke external tools. CoT, Self-Consistency, program-aided reasoning, GPT-o1, and DeepSeek-R1 have strengthened performance on mathematics and competitive coding. Yet those tasks have explicit goals and convenient checks. Software engineering, data modeling, and research additionally require long-tail knowledge, repository or dataset context, open-ended objectives, and multi-level evaluation—dimensions often underrepresented in reasoning-focused surveys.
Core Problem
The target is a valid solution trace, not merely a plausible final response. Bottlenecks include exponentially expanding search as steps increase, error propagation from early decisions, poor retention of long-tail knowledge, and the absence of unique ground truth. In data science, several models may be defensible on the same dataset; in research, even the definition of success may evolve during investigation.
Innovation
- ��A three-part lens: multi-step reasoning, domain knowledge, and verification.
- ��Two solving paradigms: direct LLM solving versus LLM orchestration of conventional computation.
- ��Formal definitions for problems, traces, goal predicates, and state transitions.
- ��Cross-domain analysis covering repository context and efficiency in software, data scarcity and rigor in mathematics, distribution uncertainty in data science, and human collaboration in research.
Methodology
- ��Planning: CoT generates intermediate steps; multi-path sampling exploits inference scaling, with a verifier selecting candidates.
- ��Knowledge: RAG retrieves documents; GraphRAG and knowledge graphs organize relations; experts can provide missing knowledge.
- ��Execution: the LLM writes and runs code or invokes search, calculators, and specialized software.
- ��Verification: synthetic training traces are filtered; inference candidates are checked by LLM judges, symbolic reasoning tools, or experiments.
- ��Iteration: feedback updates the plan, retrieved evidence, and intermediate states, forming an agentic loop.
Experiments
This is a 28-page survey and conceptual review, not a new empirical algorithm paper. It provides no unified protocol, hyperparameters, training or test datasets, ablation tables, or new results on GSM8K, MATH, HumanEval, or SWE-bench. GPT-o1, DeepSeek-R1, RAG, and GraphRAG are literature examples rather than baselines evaluated under identical conditions. Consequently, its claims are synthesis-level rather than statistically comparative.
Results
The strongest conclusions are directional. More CoT paths generally improve the chance of discovering a correct solution but increase computation. External knowledge is particularly important for scientific discovery, theorem proving, and data science. Verification supports both training-data selection and inference-time candidate choice. Clearly specified tasks benefit most; open-ended tasks remain limited by goal definition and evaluation.
Applications
Software agents can generate, debug, and modify repository-scale code when paired with documentation, tests, static analysis, and sandboxed execution. Data agents can assist preprocessing, feature engineering, modeling, and visualization, provided distribution and leakage checks are performed. Mathematics can combine theorem libraries with formal checkers. Research agents can search literature, propose hypotheses, and design experiments, while humans retain scientific authority.
Limitations & Outlook
Without a common benchmark, the survey cannot determine which retriever, reasoning strategy, or verifier is best. Retrieval may return stale or incorrect evidence; models may produce plausible but non-executable plans; and verifiers can fail too. Long CoT, repeated tool calls, and experimental loops are expensive. Progress requires cross-domain evaluation, provenance tracking, formal checking, cost-quality analysis, robust recovery from verifier errors, and stronger human oversight.
Plain Language Accessible to non-experts
Imagine a large kitchen receiving a difficult custom order. A weak cook may confidently serve a dish after glancing at the request. A reliable kitchen first writes a recipe: understand the customer, inspect ingredients, prepare them, choose the cooking method, cook, taste, and revise. CoT is like the recipe’s ordered steps; trying several recipes increases the chance of success but consumes more time.
The cook cannot remember every recipe in the world. RAG is a trustworthy cookbook brought into the kitchen, while GraphRAG is a map linking ingredients, techniques, allergies, and outcomes. If exact arithmetic is needed, the kitchen uses a scale or calculator instead of guessing.
Taste-testing is essential. An LLM judge is another cook checking the result, a symbolic tool is a precise measuring device, and a real experiment is letting the customer try the dish. A math exercise has a clear answer, but research or data analysis may have several good dishes and no single judge. The paper’s message is simple: dependable AI must plan, look things up, use tools, test its work, and improve from feedback.
ELI14 Explained like you're 14
Picture an insanely difficult open-world game. A normal chatbot might say, “The treasure is on the mountain.” A complex-solving AI must plan the route, collect keys, avoid traps, defeat guards, and confirm that the treasure is real. An LLM is a clever teammate: it can suggest moves and write a mini-program, but it may also confidently call a dead end the best path.
Chain-of-Thought is the teammate saying, “First find the map, then get the key, then open the gate.” Trying several routes usually helps, but it costs more game time and computer power. GPT-o1 and DeepSeek-R1 show what happens when models spend more effort reasoning.
When the game map changes, old memory is not enough. RAG is like checking a live walkthrough; GraphRAG is a connected map of characters, places, and quests. For calculations, the teammate can ask a computer to run code rather than guess.
Then comes the crucial check: another teammate reviews the answer, a rule-based tool verifies it, or you actually run the program. School math is easy to mark; scientific research is like exploring a map with no walkthrough, where players must even agree on the mission. Future AI therefore needs more than clever talk—it needs plans that can be checked, replayed, and corrected!
Glossary
Chain-of-Thought
A method that exposes or uses a sequence of intermediate reasoning steps. It can enlarge the search for solutions but can also propagate an early mistake.
Reviewed as the main technique for multi-step reasoning.
Retrieval-Augmented Generation
A system retrieves relevant external documents before generation. Retrieved evidence supplements missing, long-tail, or outdated model knowledge.
Applied to scientific discovery, theorem proving, and data science.
GraphRAG
A retrieval approach that organizes evidence through entities, relations, and graph structure. It is useful when relationships matter more than isolated passages.
Presented as a knowledge-augmentation strategy.
LLM-as-a-judge
One language model evaluates another model’s answer or reasoning against criteria. It is flexible but can reproduce model bias and overlook subtle errors.
Listed as an inference-time verification method.
Verifier
A component that checks whether a candidate solution or step satisfies correctness conditions. It may be an LLM, symbolic program, or experimental system.
Used for synthetic-data filtering and candidate selection.
Solution trace
The complete sequence from an input state through intermediate states to a goal result. The paper writes it as X→O1→…→Oκ→Y.
Central to the formal definition of problem solving.
Open Questions Unanswered questions from this research
- 1 How can one benchmark jointly measure trace correctness, evidence faithfulness, tool reliability, cost, and practical utility across mathematics, code, data science, and research? The survey identifies the need but supplies no common answer.
- 2 How should an agent detect and recover when its retriever, planner, and verifier fail together? This is especially unresolved for scientific tasks without a unique answer or fixed success criterion.
Applications
Immediate Applications
Repository-scale coding assistant
Engineering teams can connect an LLM to repositories, documentation, tests, and static analyzers. RAG supplies project context, CoT plans edits, and sandboxed execution tests them. Access control, reproducible builds, and human review remain prerequisites.
Auditable data-analysis assistant
Analysts can provide data dictionaries and historical solutions so an agent proposes preprocessing, features, models, and visualizations, then runs experiments. Saving code, data versions, metrics, and evidence is essential to prevent fluent but invalid conclusions.
Long-term Vision
Human-LLM research partner
A future agent could continuously search literature, build knowledge graphs, propose hypotheses, design experiments, and analyze results. Deployment requires provenance, repeatable experiments, safety constraints, and researchers’ final control over goals and conclusions.
Abstract
Problem-solving has been a fundamental driver of human progress in numerous domains. With advancements in artificial intelligence, Large Language Models (LLMs) have emerged as powerful tools capable of tackling complex problems across diverse domains. Unlike traditional computational systems, LLMs combine raw computational power with an approximation of human reasoning, allowing them to generate solutions, make inferences, and even leverage external computational tools. However, applying LLMs to real-world problem-solving presents significant challenges, including multi-step reasoning, domain knowledge integration, and result verification. This survey explores the capabilities and limitations of LLMs in complex problem-solving, examining techniques including Chain-of-Thought (CoT) reasoning, knowledge augmentation, and various LLM-based and tool-based verification techniques. Additionally, we highlight domain-specific challenges in various domains, such as software engineering, mathematical reasoning and proving, data analysis and modeling, and scientific research. The paper further discusses the fundamental limitations of the current LLM solutions and the future directions of LLM-based complex problems solving from the perspective of multi-step reasoning, domain knowledge integration and result verification.