technology

KGraphLang: Knowledge Graph Query Language for Reasoning LLMs

marchadfieldLeave a comment

KGraphLang is a knowledge graph query language designed for Ensemble Reasoning and Reasoning LLMs.

Reasoning LLMs are trained to split a request into steps and then consider and follow each step to complete the request, revising the steps as needed.  Ensemble Reasoning is a method of taking advantage of this step-wise reasoning process to execute steps directly during the reasoning process.  This dramatically improves the performance of A.I. Agents by eliminating the latency of switching between LLMs and tool calls.

More information about Ensemble Reasoning is available in the articles:

Why a new query language?

KGraphLang is designed to be simpler than query languages like SQL and graph query languages like SPARQL and OpenCypher.

By stripping the query language to just the essentials, we empower LLMs and fine-tuned SLMs to generate syntactically valid queries without ambiguity.

The loss of the more general and complex syntax of other query languages is made up for by defining domain specific predicates.

The KGraphLang specification defines predicates as relations between parameters.  An application of KGraphLang defines domain specific predicates such as friend(?X,?Y) which defines a friend relation between parameters ?X and ?Y.

By defining good predicates we can choose exactly what the LLM can access and hide any complexity inside the predicate implementations, keeping the LLM interface clean and minimalist.  This also allows direct control over what information the LLM can access as predicates act as the gateway to all data.

As an example, let’s consider a supply chain application.

Using KGraphLang, we can define predicates for supply chain cases such as:

  • Product Information: product(?Product, ?Supplier, ?ProductInfo)
  • Supplier Information: supplier(?Supplier, ?Product, ?SupplierInfo)
  • Shipping Routes: route(?Source, ?Destination, ?Route)
  • Weather Data and Predictions: weather(?Location, ?DateTime, ?Report)
  • Delivery Cost Prediction: cost(?Route, ?Product, ?Cost)
  • Performance Prediction: performance(?Supplier, ?Product, ?Route,
    ?Weather, ?Performance)

These predicates are implemented using queries to the underlying knowledge graph or via code, such as a weather service API.

The A.I. Agent, Porter, receives a report that the delivery of 500 controller motors that are critically needed in the manufacturing process of widgets for WidgetCo is delayed, and is given the task of finding an alternate source.

Porter can generate kgraphlang queries to lookup information using the predicates and find an alternate source of the controller motors that fit the needs of WidgetCo.  These queries are processed as they are generated, so the reasoning trajectory can change as information is retrieved in real time.

Thus, Porter can generate and execute a kgraphlang query such as:

?MinCost = min { ?C |
	?Supplier in ?Suppliers,
	route(?Supplier, WidgetCo, ?Route),
	cost(?Route, ControllerMotor, ?C)
}

during reasoning to determine the minimum delivery cost given a list of suppliers, and have this cost estimate affect the next steps of Porter’s reasoning.  The next step could be using the performance() predicate to estimate the likelihood of on-time delivery.  Porter can decide to switch to a different supplier if the cost and delivery estimate is not acceptable.  Much in the same way a Reasoning LLM can continue to reason on a math problem until a solution is found, a Reasoning LLM can continue to use kgraphlang queries until an acceptable solution is found, and the alternate source of controller motors is secured.

KGraphLang Predicates

Predicates define a relation between parameters. For knowledge graphs, these often are traversals on the knowledge graph.  For instance,

friend(?Person1, ?Person2)

could define a traversal on the graph from ?Person1 to ?Person2 along a relation or “edge” representing friendship.

These can be chained together, such as:

friend(?Person1, ?Person2), friend(?Person2, ?Person3)

which would follow a two-hop path from ?Person1 to ?Person3 along “friendship” relations.

The kgraphlang predicates can directly be implemented in code, or use an underlying data source.  For Ensemble Reasoning, the implementation uses KGraphService to implement predicates over a knowledge graph.

Besides traversing the knowledge graph, there are two other major types of predicates: Vector Similarity Predicates and String Hash Predicates.

Vector Similarity Predicates make use of vectors and vector search to find similar knowledge graph elements.  This is critical to support “Graph RAG” functionality ( https://microsoft.github.io/graphrag/).  A node representing a supplier in our earlier example could be similar to other suppliers if they supply similar products or are otherwise similar.

String Hash Predicates make use of string hashing and string hash searching to find text that is similar on a character by character basis.  This can be helpful to match names like “Jon Smith” would be very similar to “John Smyth”, or to find documents that contain overlapping language.

KGraphLang Syntax

KGraphLang supports a comprehensive syntax while maintaining simplicity to enable high quality LLM query generation.

The syntax includes:

  • Predicates implemented in code or via queries to an underlying data source
  • Predicate annotation with extra-logical values like @top_k(10) to control predicate output
  • Grouping and logical AND, OR, NOT
  • Comparisons: >, <, >=, <=, != 
  • Aggregation functions: collections, count, sum, average, max, min
  • Math functions
  • Data types: string, number, boolean, date, time, currency, geolocation, units, URIs
  • Complex data types for List, Map
  • Membership and Subset in Lists and Maps
  • Single and multi-line comments

Here’s an example:

?uri_prop = 'urn:uri_prop'^URI,
?name_prop = 'urn:name_prop'^URI,
?email_prop = 'urn:email_prop'^URI,

?prop_list = [ ?uri_prop, ?name_prop, ?email_prop ],

person_uri_list(?PersonList), 

?PersonEmailMapList = collection { 
    ?PersonMapRecord | 
    ?Pid in ?PersonList,
    get_person_map(?Pid, ?prop_list, ?PersonMapRecord)
}.

This retrieves a list of Person records, each of which having an id, name, and email address.

KGraphLang Implementation

The KGraphLang implementation evaluates kgraphlang queries based on a set of registered predicates.

The predicates are implemented either using an underlying data source or directly in code.  

Predicates implemented using KGraphService use an underlying knowledge graph implemented by a graph and vector database.  This means that, internally, the kgraphlang query is translated into a target query language such as OpenCypher, SPARQL, or GraphQL which is used with the implementing database.  So, predicates are a means of bundling complex queries into simple chunks the LLM can easily work with.

An example of a predicate directly implemented in code could be:

weather(?Location, ?DateTime, ?Report)

which could be implemented via an API call to a weather service to get an accurate weather report at the time the query is evaluated.

The KGraphLang implementation parses the query and then evaluates it, but there are cases when the parse can be used directly.  Parsing the kgraphlang query produces an AST (abstract syntax tree), which can be manipulated first and then later evaluated.  This is useful in cases of optimizing the query or replacing predicates with pre-cached values.

KGraphLang Fine-tuning

Reasoning LLMs such as R1-Distill-Llama are successful in producing valid KGraphLang queries using only prompting.  However, fine-tuning should improve generation and reduce the prompting needed for KGraphLang requests to only the predicate definitions for that request.  Also, fine-tuning SLMs should allow domain specific SLMs to produce valid KGraphLang queries with specific sets of predicates included in the training, making for a highly optimized query capability.

We’re in the process of collecting datasets to use for kgraphlang fine-tuning.

Source Code

All source code is open-source and available via GitHub.

KGraphLang is implemented in the repo:

https://github.com/vital-ai/kgraphlang

KGraphService is implemented in the repo:

https://github.com/vital-ai/kgraphservice

The Vital LLM Ensemble Reasoner, which uses KGraphLang is implemented in:

https://github.com/vital-ai/vital-llm-reasoner

The vLLM-based server running the Ensemble Reasoner is implemented in:

https://github.com/vital-ai/vital-llm-reasoner-server

Next steps

A follow-up article will present an implementation of KGraphLang predicates based on sample datasets to make it easy to run examples, and subsequent articles will explore deploying Ensemble Reasoning with kgraphlang.

If you are interested in utilizing kgraphlang as part of your Reasoning LLM and A.I. Agent implementations, please contact us at Vital.ai!

Agents and Ensemble Reasoning

marchadfield3 Comments

The recent release of open source reasoning models such as QwQ (Qwen) and Phi-4 (Microsoft) have opened up new possibilities in Agents to reason via a methodology that can be called: “Ensemble Reasoning“

Ensemble Reasoning brings together an ensemble of different A.I. components that can directly participate in reasoning via a collective process.

The release of Open AI’s o1 model kicked off this era by releasing a model specifically trained to generate reasoning steps.  Prior to this, techniques such as “ReAct” prompted models to generate reasoning steps, but o1 “baked in” this reasoning directly in the model.

Now with the release of open source reasoning models akin to o1, the A.I. developer community can experiment, develop, and deploy Agents based on ensemble reasoning, including components of their own design and choosing, creating a new category of A.I. software components: Ensemble Reasoners.

So what is different?

Today, Agents utilize tools, such as a web search or database query, to help accomplish tasks.  This occurs in a loop with an Agent using an LLM model to decide what to do next, such as selecting a tool, then the Agent uses the tool, and then the Agent provides the output of the tool back to the model to decide the next step.  This cycle repeats as long as needed to accomplish the task.  At each step, the model starts reasoning from scratch.

With Ensemble Reasoning, the model can utilize the ensemble directly during the reasoning process, short-circuiting the need to restart reasoning after each step.

This not only compresses the Agent “loop” to greatly speed up the process, but open source reasoning models also open up the “black box” of the model to enable integrating highly optimized ensemble members to improve the reasoning process in a human understandable way.

To a degree, Ensemble Reasoning is a generalization of the Mixture-of-Experts LLM algorithm (non-reasoning) which splits a large model into smaller “expert” modules such that only a portion of the model is active for a given request.   Reasoning models are specifically trained to produce reasoning steps as tokens (words) which can be sent to an ensemble “expert” to process.  These reasoning tokens can be read by humans directly to understand the reasoning process.  This is in contrast to Mixture-of-Experts where expert modules are enabled via the internal parameters of the model and cannot be directly understood.

When the reasoning steps are dynamically routed to the ensemble members to process, the results are then provided back to the reasoning model which then continues reasoning.

The key difference is that the model keeps inferencing while output from the ensemble members is fed into it to further the reasoning process.  By comparison, the current Agentic loop starts over for each iteration which introduces a large amount of overhead and latency.

So what are these Ensemble Reasoning members?

There is the reasoning model, which acts as the conductor of the ensemble and produces reasoning steps that can be processed by the ensemble members.

An ensemble member takes a reasoning step as input and produces output which is added into the reasoning, allowing the reasoning model to be aware of this information as it continues reasoning.

Examples of types of ensemble members include:

  • A separate LLM Model, trained for a specific task or usage scenario
  • Knowledge Graph Search
  • Web, Document, Database Search
  • Code Executor
  • Math Calculator, Constraint Solver, Formal Planner
  • Logical (Semantic) Reasoner, Rule Engine 
  • Machine Learning Prediction Model, Recommendation Model (Graph Neural Network)

Any “tool” currently used by an Agent could potentially become an ensemble member.  However, only tools which affect reasoning should be used in this way, and only tools which can operate efficiently to keep pace with reasoning.  Also, such tools should not affect the state of the Agent as reasoning is thinking about what to do and not actually doing it (yet).  Reasoning may “change its mind” many times before deciding on an action.

As a counter example, an API to send an SMS text message should not be an ensemble member as it changes the Agent’s state (message sent vs not sent) and cannot be retracted.

It’s helpful to make a distinction between ensemble member tools as “ensemble tools” or “internal tools” and tools that the Agent uses as “Agent tools” or “external tools” (as in, external to the model).

So what are some examples of how Ensemble Reasoning works?

Let’s consider an agent, named Haley, that we are going to ask to do certain tasks. These are simple illustrative examples whereas an Agent can have complex multi-step workflows and act autonomously.  Here’s how ensemble reasoning can affect the reasoning process for these tasks.

Planning a trip:

>> Haley, give me directions to get to the MoMA Museum.

The reasoning ensemble can use real-time traffic and transportation information to plan a route directly during the reasoning process and avoid the Agentic “loop” of having to have many LLM requests to check each routing option.  A constraint solver or planner could be leveraged for a complex route or one with multiple waypoints. 

Writing fiction:

>> Haley, give me some ideas of what should happen next in this Sci-Fi story I’m writing.

The reasoning ensemble can take advantage of reasoning to understand the plot and motivations of characters in the story and use an expert LLM trained in creative fiction writing to generate the text of the ideas.

Recommending a Movie to watch:

>> Haley, what movie should I watch out with my friends tonight?

The reasoning ensemble can take advantage of real-time movie schedules and a trained recommendation model (based on GNNs) to correlate recommendations with the available options.  Queries to a knowledge graph can provide information about the friends for their movie interests and locations to find a suitable theater for the group.

Shopping Recommendation:

>> Haley, what should I get my mom for her birthday?

The reasoning ensemble can query the knowledge graph to get information about my mother’s likes, use a recommendation model (based on GNNs) to get product recommendations, and check shipping options to confirm a gift will arrive in time.

Produce a financial report:

>> Haley, generate a financial report as a PDF based on projections for next quarter and email it to the finance team.

The reasoning ensemble can leverage document and database search to collect the requisite information, use prediction models to make financial projections, write and execute code to produce the sums needed for the report, and produce Agent tool calls for generating the report PDF and emailing it which the Agent can then execute.  So, this is an example of combining “ensemble tools” with “Agent tools”.

Counting things:

>> How many R’s in Strawberry?

This is a classic problem LLMs have, partly due to how text is encoded in tokens when provided to the LLM, so LLMs often give the wrong answer of “2” to this seemingly trivial request.

Reasoning models specifically spell this out as “s-t-r-a-w-b-e-r-r-y” during reasoning and then count the letters.  But, even so, mistakes are made.

I personally like the variant of this:

>> How many vowels are in this exact sentence?

When the reasoning model is told that the ensemble includes code execution and it should use this for any request which can be solved by coding, the QwQ model generates the code:

sentence = "how many vowels are in this exact sentence?"
vowels = "aeiouAEIOU"
count = 0
for char in sentence:
    if char in vowels:
        count += 1
print(count)

This code can be executed by the ensemble member Code Executor, which then gets the correct answer.  The LLM models in general are much better at producing code then trying to do anything directly quantitative, so ideally all such requests are routed to an ensemble member.

See below for a sample reasoning trace of the QwQ model working through a logic puzzle. This will give a sense of a reasoning model working through different options to find a solution.

What are the real benefits?

Ensemble Reasoning has some immediate benefits and opportunities including:

  • Dramatically speeding up the Agentic “loop” by pushing more processing directly into the model removing overhead and latency.
  • As the reasoning model generates reasoning steps, it only chooses expensive operations when necessary, decreasing the overall cost.
  • Mix and match LLM models into a Reasoning workflow.  Want to combine QwQ with LLama and Mistral? Sure! Want to use Open AI o1 as a reasoning “tool” within QwQ? Sure!
  • Enterprise guardrails integrated directly into the reasoning process to approve or deny reasoning steps as they occur.
  • Integrating sources of dynamic knowledge like Knowledge Graphs into the reasoning, exploring many more cases than would be possible with the Agentic loop.
  • Integrating prediction and recommendation models, such as Graph Neural Networks (GNNs), into reasoning for applications such as eCommerce personalization. 

More broadly, with reasoning models focusing on reasoning, other aspects of the LLM like knowledge retrieval can be “out-sourced” to the Ensemble, making for smaller reasoning models that are faster, cheaper to operate, and smarter with the Ensemble.

What needs to be implemented?

A Reasoning Ensemble first and foremost requires a reasoning model.  The Ensemble is directly integrated with the reasoning model, which means either the reasoning model is open source or the developer has full access to the model (via creating it or a commercial license).  Current open source reasoning models include QwQ and Phi-4, with others on the way.

The reasoning model runs within server software such as vLLM or llama.cpp (both open source).

Vital.ai is developing a Reasoning Ensemble framework to run within vLLM.  This will leverage the Vital AI Agent Ecosystem to provide ensemble tools like KGraphService, which is a Knowledge Graph service leveraging Vector and Graph queries.

What is next?

At Vital.ai we are developing Ensemble Reasoning as a core capability with implementations using the open-source Vital A.I. Agent Ecosystem.

The current open source reasoning models are impressive but still experimental in nature and we’re excited to use these in our Agent deployments as they mature.

We’re excited to work with clients interested in making Ensemble Reasoning part of their Agent strategy and implementations.  Please contact us (https://www.vital.ai) to discuss your current Agent initiatives and to learn about Ensemble Reasoning!

Fun thing to try

One thing I haven’t tried yet is directly streaming tokens between two models with the second model acting to critique the first.  One model critiquing another (or even self-critiquing) is a technique that has worked quite well to improve the final output of prior LLM models.  Having this criticism incorporated dynamically during reasoning would be a very interesting approach and may have excellent results.

Notes

  1. https://huggingface.co/Qwen/QwQ-32B-Preview
  2. https://qwenlm.github.io/blog/qwq-32b-preview/
  3. https://huggingface.co/microsoft/phi-4
  4. https://techcommunity.microsoft.com/blog/aiplatformblog/introducing-phi-4-microsoft%E2%80%99s-newest-small-language-model-specializing-in-comple/4357090
  5. https://venturebeat.com/ai/microsoft-makes-powerful-phi-4-model-fully-open-source-on-hugging-face/
  6. https://github.com/vllm-project/vllm
  7. https://github.com/ggerganov/llama.cpp
  8. https://github.com/vital-ai
  9. https://www.vital.ai/agent-ecosystem.html
  10. ReAct
    https://arxiv.org/abs/2210.03629
  11. https://github.com/langchain-ai/react-agent
  12. Large Language Models Cannot Self-Correct Reasoning Yet
    https://arxiv.org/abs/2310.01798
  13. CRITIC: Large Language Models Can Self-Correct with Tool-Interactive Critiquing
    https://arxiv.org/abs/2305.11738
  14. https://arbisoft.com/blogs/why-ll-ms-can-t-count-the-r-s-in-strawberry-and-what-it-teaches-us
  15. https://en.wikipedia.org/wiki/Graph_neural_network
  16. https://en.wikipedia.org/wiki/Autonomous_agent
  17. https://openai.com/o1/
  18. https://en.wikipedia.org/wiki/Knowledge_graph
  19. https://en.wikipedia.org/wiki/Semantic_reasoner

Sample QwQ Reasoning Trace

“Selena, Jennifer and Miley wear a blue dress, yellow dress, and green dress in an unknown order. It is known that:

1) If Selena wears blue, then Jennifer wears green.
2) If Selena wears yellow, then Miley wears green.
3) If Jennifer does not wear yellow, then Miley wears blue.

What is the color of the dress Selena is wearing?”

Let’s tackle this logic puzzle step by step. We have three girls: Selena, Jennifer, and Miley, each wearing a different colored dress: blue, yellow, and green. The problem gives us three conditions, and we need to figure out what color dress Selena is wearing based on these conditions.

First, let’s list out the conditions again for clarity:

1. If Selena wears blue, then Jennifer wears green.

2. If Selena wears yellow, then Miley wears green.

3. If Jennifer does not wear yellow, then Miley wears blue.

Our goal is to determine the color of Selena’s dress.

Since there are only three colors and three people, each wearing a different color, we can start by assuming each possible color for Selena and see which one fits all the conditions.

**Option 1: Selena wears blue.**

From condition 1: If Selena wears blue, then Jennifer wears green.

So, if Selena is blue, Jennifer is green.

Then, since there are only three colors and Selena has blue and Jennifer has green, Miley must have yellow.

Now, let’s check condition 2: If Selena wears yellow, then Miley wears green.

But in this case, Selena is wearing blue, not yellow, so this condition doesn’t directly apply.

Next, condition 3: If Jennifer does not wear yellow, then Miley wears blue.

In this scenario, Jennifer is wearing green, which is not yellow, so according to this condition, Miley should wear blue.

But wait, earlier we deduced that if Selena is blue and Jennifer is green, then Miley must be yellow.

This creates a contradiction because condition 3 says Miley should wear blue, but our earlier deduction says Miley is yellow.

Therefore, this option is invalid because it leads to a contradiction.

**Option 2: Selena wears yellow.**

From condition 2: If Selena wears yellow, then Miley wears green.

So, if Selena is yellow, Miley is green.

Then, since Selena has yellow and Miley has green, Jennifer must have blue.

Now, let’s check condition 1: If Selena wears blue, then Jennifer wears green.

But in this case, Selena is wearing yellow, so this condition doesn’t directly apply.

Next, condition 3: If Jennifer does not wear yellow, then Miley wears blue.

In this scenario, Jennifer is wearing blue, which is not yellow, so according to this condition, Miley should wear blue.

But earlier, from condition 2, we have Miley wearing green.

This is a contradiction.

Therefore, this option is also invalid.

**Option 3: Selena wears green.**

If Selena wears green, then we don’t have any direct conditions from the given statements.

Let’s see what we can deduce.

Since Selena is green, then Jennifer and Miley must be wearing blue and yellow, but we don’t know which one yet.

Now, look at condition 1: If Selena wears blue, then Jennifer wears green.

But Selena is green, not blue, so this condition doesn’t apply.

Condition 2: If Selena wears yellow, then Miley wears green.

Again, Selena is green, not yellow, so this doesn’t apply.

Condition 3: If Jennifer does not wear yellow, then Miley wears blue.

In this scenario, since Selena is green, Jennifer could be blue or yellow.

If Jennifer is yellow, then condition 3 doesn’t apply because Jennifer is wearing yellow.

If Jennifer is blue, then condition 3 says Miley wears blue, but that’s impossible because Jennifer is already wearing blue, and each person has a different color.

Therefore, if Selena is green and Jennifer is blue, it leads to Miley also wearing blue, which is a contradiction.

So, if Selena is green, Jennifer cannot be blue; she must be yellow.

Therefore, Jennifer is yellow, and Miley is blue.

Let’s check if this fits all conditions.

Condition 1: If Selena wears blue, then Jennifer wears green.

Selena is green, not blue, so doesn’t apply.

Condition 2: If Selena wears yellow, then Miley wears green.

Selena is green, not yellow, so doesn’t apply.

Condition 3: If Jennifer does not wear yellow, then Miley wears blue.

Jennifer is yellow, so this condition doesn’t apply because she is wearing yellow.

Therefore, there are no contradictions in this scenario.

So, Selena is wearing green.

Wait a minute, but the problem asks for the color of Selena’s dress, and according to this, it’s green.

But in the initial options, both Selena wearing blue and yellow led to contradictions, so the only remaining option is green.

However, let’s double-check to make sure there are no hidden contradictions.

If Selena is green, Jennifer is yellow, and Miley is blue, does this satisfy all conditions?

Condition 1: If Selena wears blue, then Jennifer wears green.

Selena is not wearing blue, so no issue.

Condition 2: If Selena wears yellow, then Miley wears green.

Selena is not wearing yellow, so no issue.

Condition 3: If Jennifer does not wear yellow, then Miley wears blue.

Jennifer is wearing yellow, so this condition doesn’t apply.

Everything seems to check out.

Therefore, Selena is wearing the green dress.

**Final Answer**

green

Reasoning, LLMs, Neuro-Symbolic AI, and Defeasible Logic (with Python Example)

marchadfieldLeave a comment

I recently had the above interaction with ChatGPT (GPT-4).

I asked:

There is a standard 3 color traffic light that is displaying a color. The color is not green or blue. What color or colors could it be?

And got the response:

If a standard 3-color traffic light is displaying a color that is not green or blue, then it could only be displaying red. Standard traffic lights consist of red, yellow (amber), and green colors, and since blue is not a color in standard traffic lights, if it’s not displaying green, it must be red.

So, a wrong answer, and somewhat nonsensical as it had the correct information (yellow and red) a few words earlier in the same sentence, and yet then concluded the wrong answer, red.

This response was a bit of the luck of the draw. I asked the same question later in the day and got the correct response of “yellow and red”. And, there are techniques of prompting such as “Chain of Thought” that trigger LLMs to generate a response in a more stepwise fashion, leading to more accurate and reliable results. However, for such a simple case we should not have to carefully construct a prompt or hope to be lucky.

If you forgive the LLM by it being “tricked” by the prompt mentioning “blue” then you are removing one of the main use-cases of LLMs: “RAG” (retrieval augmented generation) applications. These applications perform a query of various data sources to collect potentially relevant information and then depend on the LLM to sort through it to pick out the relevant information from unstructured and messy query results to use as supporting information when generating a response. RAG Applications couldn’t work without the LLM being able to separate out and ignore irrelevant facts like a Traffic Light is not displaying blue, or pink, or purple.

By contrast, using classic symbolic artificial intelligence, with a reasoning logic language like prolog, we could define a “TrafficLight” and infer the possible colors in a couple lines of code, with no ambiguity.

Of course symbolic artificial intelligence has its own limitations, including brittleness and an inability to scale well, which is why we’ve moved on to machine learning and generative models like LLMs.

But, we should not have to give up what was good about the symbolist approach to use the new developments of artificial intelligence.

There are efforts underway to combine the symbolist approach with the newer forms of artificial intelligence. There are various names for this effort, but a popular one is Neuro-Symbolic AI.

Let’s say we are creating an application to recommend movies. A symbolist approach might define a relationship:

EnjoysGenre(Person, Genre)

and use that relationship to define facts like:

EnjoysGenre(john, scifi)

and then a further relationship could be defined by composing relationships:

LikeMovie(Person, Movie) :- EnjoysGenre(Person, Genre), HasGenre(Movie, Genre)

with this new relation then able to “predict” enjoying a movie if that movie happens to be in the genre that you like, such as:

LikeMovie(john, starwars) :- EnjoysGenre(john, scifi), HasGenre(starwars, scifi)

Neuro-Symbolic AI extends the symbolic model by learning to perform predictive tasks such as:

  • Predict instances of relations such as LikeMovie based on training with known examples. In the context of Knowledge Graphs this is known as Knowledge Graph Completion as it fills in a Knowledge Graph with predicted relationships based on existing relationships.
  • Assign weights to components of rules which would learn how much influence “Genre” should have in the relation LikeMovie compared to other components.
  • Generate new kinds of relations which could then factor into other relations, and so on, recursively. For instance, ReleaseYear or MovieCountryOfOrigin could be learned to be relations of interest and factor into relations such as LikeMovie. ForeignFilm could be learned to be the relation between MovieCountryOfOrigin and the logical NOT of PersonCountryOfOrigin and be included as a factor in LikeMovie (i.e. a foreign film to you is a film from any other country but your own country of origin). We could ask the model to come up with a relationship for DateNightMovies which it could learn to be a composition of the partners’ preferences and perhaps something more light-hearted, influenced by previous DateNights.

These tasks may use classic feature driven machine learning models and recommendation systems or may use newer techniques taking advantage of deep learning, embeddings, and transformer models. Some examples of the latter include Graph Neural Networks (see PyG), Probabilistic Soft Logic, and Logic Tensor Networks.

One aim of using Neuro-Symbolic AI vs machine learning is to make the reasoning explainable. The output can include a trace of its reasoning why it thinks you should watch the movie “Miller’s Crossing” based on the genre, director, being similar to a movie you watched and liked recently, and so forth whereas machine learning is more of a black box without much explanation possible.

Future LLMs may have Neuro-Symbolic AI modules as components, similar to how Mixture-of-Expert models combine multiple component models into one melded LLM.

Currently such Neuro-Symbolic models can be used in combination with an existing LLM, taking advantage of such techniques as “function calling”. In function calling, the LLM composes a request to an external resource (a “function”) and that function returns some information that can help the LLM complete its task. So, as example, if the LLM can generate a function call in the form of a query like:

LikeMovie(john, ?Movie)

Then the Neuro-Symbolic AI Model can take over and do the reasoning to generate ?Movie results for john, and then the LLM can use those results to complete its task. This is essentially just another “RAG” query to get contextual information to complete a task.

If we used our LLM to generate logical statements from the prompt, something like:

traffic_light(green, false)

And then used a function calling to “run” those logical statements within a logical reasoner (Neuro-Symbolic or just symbolic), we can use the LLM for what it is good at and use the reasoner for what it is good at to come to our answer.

One aspect of our simple Traffic Light question is that it rests on a finite enumerated list: green, yellow, and red. Our reasoning system must use a process of elimination. If we know that the traffic light is not green and not red, then reasoning can infer that it is yellow, even without that fact explicitly stated. This is easily accomplished in a symbolic system, but as with our example at the start, LLMs can struggle with this.

One important feature of symbolic systems that I have not seen replicated in a Neuro-Symbolic context as of yet is Defeasible Reasoning. Defeasible Reasoning allows certain knowledge to “defeat” other knowledge as part of a reasoning process. This allows new knowledge to override old knowledge, more specific knowledge to override more general knowledge, and knowledge of a higher rank to override less ranked knowledge.

Defeasible Reasoning solves the problem of an inference system coming into conflict by having rules that generate conflicting conclusions. Consider a rule such as: 

All Birds Fly

which classifies all instances of the Bird class into a CanFly class. Now consider adding a rule such as:

Penguins Can Not Fly

which classifies all instances of the Penguin class into the CanNotFly class.

Now we have Penguins that are classified as both CanFly (as Birds) and CanNotFly (as Penguins) creating a logical contradiction, which, for a logical inference system, is very bad. Having A and not A both be true simultaneously grinds everything to a halt.

Defeasible Reasoning solves this by having the more specific rule for Penguins defeat the more general rule for all Birds.

Another example of this is the so-called “Nixon Diamond” problem because by one path of reasoning U.S. President Nixon was a pacifist as a Quaker (Society of Friends) and by another path of reasoning was a non-pacifist based on his Republican policies of the Vietnamese War. Defeasible Reasoning provides a tie-breaker between the pacifist and non-pacifist conclusion to avoid a logical contradiction when determining Nixon’s classification for Pacifism.

So in this case, based on ranking of rules or by supporting evidence, the path through the Republican policies “defeats” the Quaker pacifism causing Nixon to be classified as non-pacifist.

One inference engine that implements Defeasible Reasoning is the open-source Ergo Engine (https://github.com/ErgoAI/ErgoEngine). Ergo is based on frame logic making it a cross-over between a logic language and an object oriented language (via “frames” in place of objects). Besides defeasible reasoning it has other advanced features including a convenient way of expressing negative knowledge, as we’ll see in the example below.

Ergo has a python interface, and an example using python is in the repo:
https://github.com/vital-ai/vital-logic-python

:- use_argumentation_theory.
////////////////////////////////////////////////////
// defeasible reasoning example
Human::Thing.
Mortal::Thing.
Immortal::Thing.
Undead::Thing.
MagicUser::Human.
Mortality::AbstractThing.
Mortal:Mortality.
Immortal:Mortality.
Undead:Mortality.
@{default} \neg ?P:Immortal :- ?P:Human.
@{default} ?P:Mortal :- ?P:Human.
@{magical} ?X:Immortal :- ?X:MagicUser.
@{magical} \neg ?X:Mortal :- ?X:MagicUser.
\overrides({magical},default).
// Instance Data
Socrates:Human.
Merlin:Human.
Merlin:MagicUser.
// Rules
mortality(?Human, ?Mortal) :- ?Human:Human,
    ?Human:?Mortal, ?Mortal:Mortality.

Above is a screenshot from PyCharm for the vital-logic-python project and some example rules from the “test_rules.ergo” file in the project.

The classic example from Logic 101 is:

The inference from the premises “all men are mortal” and “Socrates is a man” to the conclusion “Socrates is mortal” is deductively valid.

https://en.wikipedia.org/wiki/Deductive_reasoning

The example Ergo rules above extend this Logic 101 classic to define Defeasible Rules for the class Human as being Mortal but the class Magic User as being Immortal with magical rules overriding (defeating) the default ones. We define two instances of Human, Socrates and Merlin, with Merlin being a Magic User. The rule mortality(?Human, ?Mortality) allows listing out the humans and how they classify as mortal or immortal, with the results being:

?Human = Socrates, ?Mortality = Mortal
?Human = Merlin, ?Mortality = Immortal

The rule:

\neg ?P:Immortal :- ?P:Human.

is an example of a negative rule, encoding negative information, where Humans are not classified as Immortal, unless some rule can “defeat” this.

The result of the query mortality(?Human, ?Mortality) changes for Merlin when the fact:

Merlin:MagicUser.

is added into the database. This is an example of non-monotonic reasoning as the conclusion Merlin is mortal is retracted and a new inference is added for Merlin is immortal when the fact is added. The inference engine must keep track of what conclusions to remove and which to add when facts and rules change. Being able to handle changing facts and conclusions as knowledge changes is a critical component of an AI application.

The repo contains sample python code like:

   for row in pyergo_query('?C::Thing@logic, Merlin:?C@logic.'):
        print("row", row[0])

which runs a query that uses the reasoning rules to generate results, and prints them out. So, integrating python and Ergo is pretty simple. The above prints out the classes assigned to Merlin that are also subclasses of Thing within the database called “logic”.

There is also some sample code for the Traffic Light case mentioned at the start represented as symbolic rules.

Given the python interface, it is straightforward to combine Ergo queries with python code for LLMs, using LLM libraries such as LangChain to access models like OpenAI’s GPT-4 and Anthropic’s Claude. With the function call approach mentioned above, Python can be used to integrate symbolic reasoning with LLMs. If you are a developer, hope you give it a try! We’ll have some examples of using Neuro Symbolic AI using PyG for Graph Neural Networks coming along too. These examples can be used with Agents in the Vital AI Agent Ecosystem and with Agents deployed on Chat.ai.

To learn more about the Agent Ecosystem, check out: https://www.vital.ai/agent-ecosystem.html

To learn more about deploying agents on Chat.ai check out: https://chat.ai/developers.html

If you are interested in Vital.ai helping your organization build and deploy agents, please contact us: https://www.vital.ai/about.html#contact