Source-linked AI summary
Beyond LLMs: Advancing the Landscape of Complex Reasoning
Jennifer Chu-Carroll, Andrew Beck, Greg Burnham, David OS Melville, David Nachman, A. Erdem Özcan, David Ferrucci
TL;DR
LLMs can produce unsatisfactory results on constraint satisfaction and optimization problems, while developer-friendly platforms for building such solutions remain lacking. EC AI uses a precise symbolic reasoning engine with LLM-powered tools for specifying application logic and supporting user interaction. The EC AI systems, with LLM-support for user interaction, achieved 100% performance in all dimensions, significantly outperforming GPT-4, whose valid solutions were mostly suboptimal and invalid-solution recognition or rectification was poor.
Problem
LLMs can produce unsatisfactory results on constraint satisfaction and optimization problems, while developer-friendly platforms for building such solutions remain lacking.
Source: Conclusions · p. 14Method
EC AI uses a precise symbolic reasoning engine with LLM-powered tools for specifying application logic and supporting user interaction.
Source: Brief Introduction to the EC AI Platform · p. 7, Conclusions · p. 14Results
The EC AI systems, with LLM-support for user interaction, achieved 100% performance in all dimensions, significantly outperforming GPT-4, whose valid solutions were mostly suboptimal and invalid-solution recognition or rectification was poor.
Source: Conclusions · p. 15Takeaways & Limitations
EC AI provides a platform for developing business applications that involve constraint satisfaction and optimization.
Source: Conclusions · p. 14
Abstract
from arXiv · showhide
Since the advent of Large Language Models a few years ago, they have often been considered the de facto solution for many AI problems. However, in addition to the many deficiencies of LLMs that prevent them from broad industry adoption, such as reliability, cost, and speed, there is a whole class of common real world problems that Large Language Models perform poorly on, namely, constraint satisfaction and optimization problems. These problems are ubiquitous and current solutions are highly specialized and expensive to implement. At Elemental Cognition, we developed our EC AI platform which takes a neuro-symbolic approach to solving constraint satisfaction and optimization problems. The platform employs, at its core, a precise and high performance logical reasoning engine, and leverages LLMs for knowledge acquisition and user interaction. This platform supports developers in specifying application logic in natural and concise language while generating application user interfaces to interact with users effectively. We evaluated LLMs against systems built on the EC AI platform in three domains and found the EC AI systems to significantly outperform LLMs on constructing valid and optimal solutions, on validating proposed solutions, and on repairing invalid solutions.
LLMs and Reasoning
LLMs can produce coherent but ungrounded or self-contradictory outputs, prompting questions about their reliability on reasoning tasks. EC AI combines a symbolic reasoning engine with LLM-enabled knowledge acquisition and user interaction.
LLMs and Reasoning
- GPT-4's 16×16 Sudoku grid violated stated constraints, and its Spelling Bee response included an invalid word and claimed infinitely many solutions.The cited Sudoku figure shows GPT-4's response; its explanation claimed a column contained every number once despite duplicates and omissions.Source: LLMs and Reasoning · p. 3, Figure 1 · p. 3, Figure 2 · p. 4
- GPT-4 failed to recognize constraint violations in its outputs, while the paper views prompt engineering as an insufficient long-term solution.The authors acknowledge that prompting may improve performance to some extent.Source: LLMs and Reasoning · p. 4
- The proposed alternative combines LLMs with symbolic reasoning to produce reliable, provably correct solutions to constraint satisfaction and optimization problems.The paper compares this hybrid approach with LLMs on real-world applications.Source: LLMs and Reasoning · p. 4
A Neuro-Symbolic Approach to Solving Reasoning Problems
- The EC AI platform uses a symbolic reasoning engine for inference and multi-objective optimization, while Cogent expresses rules, constraints, and objectives in constrained English.Cogent specifications are compiled into logical forms that the reasoning engine can consume.Source: Brief Introduction to the EC AI Platform · pp. 5–6
- LLMs assist developers in turning instructions into Cogent specifications and support user interaction through generated natural-language and structured interfaces.The core symbolic engine with LLM-enabled interfaces for knowledge acquisition and user interaction is called the “LLM Sandwich.”Source: Brief Introduction to the EC AI Platform · pp. 6–7
Sample Complex Reasoning Problems
Constraint satisfaction and optimization recur in practical applications, where specialized tools or manual work are common. The paper describes EC AI systems for workforce, travel, and degree planning.
Sample Complex Reasoning Problems
- Many real-world applications need constraint satisfaction or optimization, but are often handled with specialized engines by expert developers or manually.The paper identifies workforce, travel, and degree planning among its application areas.Source: Sample Complex Reasoning Problems · p. 7
Workforce Planning
- Workforce planning assigns limited resources to tasks over time while meeting requirements; EC has a project-planning prototype that assigns employees to projects.The prototype is not yet an end-to-end application.Source: Workforce Planning · p. 7
Complex Travel Planning
- Round-the-World travel planning must satisfy route, city, and fare constraints, and EC deployed a conversational system that optimizes routes and identifies violated constraints when no itinerary works.The paper notes that most such itineraries were still booked through human travel agents as of 2020.Source: Complex Travel Planning · pp. 7–8
Degree Planning
- Degree planning constructs or validates course plans against degree requirements, prerequisites, and offerings; EC's deployed system also supports plan modification and course recommendations.The system uses students' transcripts and codified degree requirements and course dependencies.Source: Degree Planning · p. 8
Evaluation Criteria
The paper evaluates whether systems can construct optimal plans, validate proposed plans, and repair invalid ones. It focuses on those three capabilities, while reliability and explanations receive less systematic assessment.
Evaluation Criteria
- A capable planning system should construct optimal plans, validate plans against constraints, repair invalid plans, explain answers, and respond consistently to repeated inputs.Optimal construction includes probing for missing information; repair includes identifying violated constraints and modifying the plan.Source: Evaluation Criteria · pp. 8–9
- The evaluation focuses on construction, validation, and repair; answer reliability was not systematically tested, and explanations were assessed informally.The authors report that EC AI outputs were consistent anecdotally and that its reasoning engine can produce reasoning graphs and identify violated constraints.Source: Evaluation Criteria · p. 9
- The authors expect EC AI to outperform GPT-4 because its staged approach uses specialized technologies, including a symbolic reasoner built for constraint satisfaction and optimization.They contrast this with LLMs' monolithic black-box approach.Source: Evaluation Criteria · p. 9
Experimental Setup
The study compares three EC AI systems with GPT-4 on plan construction and repair across workforce, travel, and degree planning. Test data include real-user data where possible and examples of varying complexity.
Systems and Baselines
- The comparison pairs EC AI systems for project planning, Round-the-World travel, and degree planning with GPT-4 instances given the relevant business rules.The travel task was restricted to city ordering, and degree planning to Business degrees across eight majors.Source: Systems and Baselines · pp. 9–10
- For construction, systems received user requirements and optimization criteria; for repair, they received invalid plans and were asked to make minimal valid changes.Construction outputs were judged optimal, valid, or invalid.Source: Systems and Baselines · p. 10
Evaluation Data
- Test data came from deployed systems where possible and varied in complexity; Projecto used 87 instances derived from 20 projects and 10 employees.Unsolvable Projecto instances were filtered out.Source: Evaluation Data · p. 10
- The travel test set used 137 itineraries, degree-planning construction used 40 instances, and repair sets contained 47 Projecto, 20 travel, and 36 degree examples.Travel requests varied cities after extracting home cities from logged itineraries; degree instances removed one to five semesters from valid transcripts.Source: Evaluation Data · p. 10
Evaluation Results
The EC AI systems produced valid and optimal solutions on all three tasks, and achieved 100% performance on plan validation and repair. The evaluation judged constructed plans by validity and optimality and tested whether invalid plans could be recognized and repaired.
Evaluation Results
- Plan construction was judged on whether plans were valid and whether a better plan existed under the stated optimality criteria.The criteria could include the time needed to complete all projects.Source: Evaluation Results · p. 11
- 100% of the time, EC AI systems produced valid and optimal solutions across all three tasks.The systems combine application rules modeled in Cogent with a precise, deterministic logic-based reasoning engine.Source: Evaluation Results · p. 11
- 100% on all three tasks was reported for EC AI plan validation and repair.The tests measured whether invalid plans were correctly classified and, when classified invalid, modified to become valid.Source: Evaluation Results · p. 11, Table 2 · p. 12
Results Analysis
GPT-4’s construction and repair performance varied by application: it struggled on workforce and degree planning, while travel planning was a relative outlier. The travel evaluation did not include the more complex booking stage involving dates and flights.
Results Analysis
- 10% of GPT-4’s degree-planning solutions were valid when all test cases were considered, though valid plans were always optimal.For workforce planning, GPT-4 approached 50% validity only when the simplest scenarios, including two-project cases, were included, and all generated plans were suboptimal.Source: Results Analysis · p. 12
- GPT-4 produced valid travel itineraries for most test cases, but its performance dropped substantially when optimality was measured by travel distance.The authors suggest that visiting cities on one continent before moving to another often yielded a valid itinerary.Source: Results Analysis · p. 12
- 75% of travel test examples were correctly identified as invalid by GPT-4, which repaired roughly half of those it recognized.In workforce planning, GPT-4 practically failed at both identifying invalid plans and repairing them; in degree planning it identified fewer than half as invalid and repaired very few.Source: Results Analysis · p. 12
- 84% of travel test cases were valid with instructions to group cities by continent, versus 77% with the RTW fare rules.The more complex booking stage—selecting dates and flights—was not evaluated because providing real-time flight data to the LLM was difficult.Source: Results Analysis · p. 12
Discussions
The discussion attributes EC AI’s results to separating knowledge capture from reasoning execution, using precise specifications and a symbolic reasoning engine. It also notes higher development costs and limitations of monolithic LLM approaches.
Discussions
- EC AI’s performance is attributed to separating knowledge capture from reasoning execution, unlike LLMs’ end-to-end framework.The paper reports that EC AI systems significantly outperformed GPT-4 in plan construction, validation, and repair.Source: Discussions · p. 13
- Cogent is declarative and designed to capture complex knowledge in independently readable, unambiguous statements.An LLM-powered assistant helps developers translate natural-language instructions into Cogent, which a compiler checks for inconsistencies and errors.Source: Discussions · p. 13
- The symbolic reasoning engine deterministically generates outputs and explanations that link results to captured specifications.Diagnostic and validation tools support users in understanding system behavior and refining specifications.Source: Discussions · p. 13
- EC AI requires higher development cost than prompting an LLM, while tooling is intended to reduce application-building effort.The tools include an author assistant for Cogent specifications and configurable zero-shot dialogue for querying or modifying an application solution.Source: Discussions · p. 13
- The authors argue that token-by-token LLM processing prevents systematic composition of complex prompts and offers no guaranteed incremental progress through trial and error.They acknowledge that LLMs are improving, but contend that the current monolithic end-to-end statistical approach has fundamental limitations for these reasoning problems.Source: Discussions · p. 14
Conclusions
The paper concludes that LLMs perform poorly on constraint satisfaction and optimization problems, while developer-friendly platforms for building solutions remain lacking. It presents EC AI’s symbolic-reasoning architecture and reports stronger performance than GPT-4 across three applications.
Conclusions
- Constraint satisfaction and optimization problems are common in real-world applications, but effective, developer-friendly platforms for building solutions remain lacking.Source: Conclusions · p. 14
- The EC AI platform uses a symbolic reasoning engine with LLM-powered tools for capturing application rules and supporting user interaction.Cogent specifications are compiled into logical forms for the reasoning engine, and LLMs support development of an interactive interface through automatically generated APIs.Source: Conclusions · p. 14
- The evaluation tested construction, validation, and correction of plans in three applications built with EC AI.The systems were assessed on constructing plans from inputs and optimization criteria, checking plans against constraints, and rectifying invalid plans.Source: Conclusions · p. 14
- In the applications evaluated, EC AI systems with LLM support for user interaction achieved 100% performance in all dimensions, significantly outperforming GPT-4, which produced some valid solutions.The vast majority of GPT-4’s valid solutions were suboptimal, and it performed poorly in recognizing or rectifying invalid solutions.Source: Conclusions · p. 15