🚀 Flawless LLM: Decoding on Graphs

#09

Written by: Jodie Jung

Series 1: RAG, but Better

Series 2: Better LLM? Think on Graph!

Series 3: KGARevion: Smarter Medical AI Agent

🚀 Flawless LLM: Decoding on Graphs - 4

How much easier would it be if we could avoid the need for apologies in the first place? This mindset of preventing mistakes from the start mirrors the approach researchers have taken with LLMs—ensuring accuracy from the outset rather than correcting errors later.

Enter DoG(Decoding on Graphs): a system specifically designed to ensure LLMs generate only accurate information by strictly adhering to the constraints of a Knowledge Graph(KG), avoiding anything that doesn’t exist within it.

Unlike systems that generate incorrect information and then fix it later, DoG imposes strong constraints to ensure only valid data from the KG is used. Its process works as follows:

It identifies key elements of the question.
It incorporates structural constraints from the KG to select only valid triplets.
Finally, it generates an accurate and reliable answer.

Intrigued? Let’s explore how it works in more detail! 🚀

The Key Lies in the Well-Formed Chain

LLMs have the ability to answer complex questions through step-by-step reasoning. Knowledge Graphs(KGs), with their structured representation of query elements and relationships, excel at providing logical reasoning paths. DoG(Decoding on Graphs) introduces a novel approach by tightly integrating LLM’s step-by-step reasoning capabilities with the structural information of KGs.

At the heart of DoG lies the concept of the “well-formed chain.” This refers to a logical sequence of triplets that leads from the query to the answer. A well-formed chain must meet two key conditions:

☝🏼 Every triplet in the chain must exist in the KG.
✌🏼 The head or tail of each triplet must have already been visited in the chain or be an element explicitly mentioned in the query.

Since all triplets must exist in the KG, there’s no risk of generating incorrect information during reasoning. Additionally, by focusing only on neighboring relationships of already-visited elements, the scope of exploration is significantly reduced. This makes the well-formed chain not only more accurate but also more efficient compared to traditional methods.

Why DoG Stands Out

There are two common methods for combining LLMs with KGs: subgraph retrieval and iterative prompting. However, both approaches have clear limitations.

Subgraph Retrieval

Extracts a small, relevant subgraph of the KG based on the query beforehand.
If the retrieved data is incomplete or inaccurate, the reasoning accuracy drops significantly.

Iterative Prompting

LLM independently performs step-by-step reasoning to incrementally generate an answer.
Struggles with complex multi-hop queries, leading to potential logical inconsistencies.
Prone to hallucinations, creating false or irrelevant information.

How DoG Solves These Issues

DoG overcomes the shortcomings of both methods, offering a more reliable and flexible approach.

When KGs are converted into linearized text input for LLMs, the structured information of the graph becomes unclear. This makes it difficult for the LLM to generate accurate reasoning paths. For instance, the connections between "Blue Hawaii → location → Hawaii" and "Hawaii → national flower → Hibiscus" might get lost when presented as plain text. The LLM cannot recognize that these relationships are interconnected.

DoG addresses this challenge through a novel technique called Graph-Aware Constrained Decoding. This method restricts the LLM’s decoding process based on KG’s structural constraints, ensuring only valid triplets are generated.

Ready to see how it works in action? Let’s dive into a visual breakdown! 🔎

An example workflow of DoG with beam size of 1. Source: (link)

First, an initial subgraph(b) is generated from the KG based on the key elements of the query and their connected triplets. During reasoning, DoG applies constraints to ensure that the LLM only considers relationships and elements connected to the current node.

For instance, if "Hawaii" is the current element, only relationships like "location" or "national flower," which are directly linked to "Hawaii," are considered valid outputs.

As reasoning progresses, the subgraph gradually expands(e), generating a well-formed chain that reflects the KG's network structure. Since DoG starts with valid triplets and only generates triplets previously visited or connected to them, the chances of errors are significantly reduced.

How Did DoG Perform?

Experimental results show that DoG outperforms traditional methods across key Knowledge Graph Question Answering (KGQA) datasets. Remarkably, DoG achieves high accuracy even in environments without additional training. As seen in the table below, DoG maintains stable performance regardless of beam size (bs=n).

Larger beam sizes increase the number of paths evaluated simultaneously, leading to greater computational complexity. However, DoG leverages Graph-Aware Constrained Decoding to efficiently limit all paths, ensuring consistent performance. This ability to handle even more complex queries with high accuracy is one of the key reasons DoG excels.

Performance comparison of different methods on the three KGQA benchmarks.

The best performance is highlighted in bold. Source: (link)

Of course, DoG has its limitations. If the KG lacks information or is incomplete, DoG cannot generate answers. Additionally, dynamically expanding subgraphs in large-scale KGs can still be computationally expensive.

Despite these challenges, DoG successfully combines the strengths of LLMs and KGs to create a new breed of intelligent systems. It holds particular promise in fields like healthcare, finance, and law, where complex, data-driven reasoning is essential for success.

DoG is a framework that combines the reasoning capabilities of LLMs with the structural information of KGs to generate reliable inference paths. By introducing innovative mechanisms like well-formed chains and graph-aware constrained decoding, DoG overcomes the limitations of traditional KGQA systems, setting a new standard for diverse applications.

At Datumo, we remain committed to exploring groundbreaking research and delivering valuable solutions in 2025 and beyond. Stay tuned! 🚀

Subscribe to our Newsletter 💌