"Tree-of-Thoughts" as an alternative to "Chain-of-Thoughts"

Abstract

Introducing the "Tree-of-Thoughts" approach, which enhances the precision of the current state of affairs in the ChatGPT Chain-of-thoughts setting. We outline the methodology for retrieving past context in dialogues, which is crucial for prompt engineering in ChatGPT.

Background

One popular method for enhancing the accuracy of ChatGPT responses is through "Chain-of-Thoughts." This technique utilizes the organized flow of questions and answers to direct ChatGPT towards the most appropriate response.

LangChain, an open-source software, has gained popularity for its successful automation of repetitive tasks associated with "Chain-of-thoughts" prompt creation. This design principle has significantly influenced LangChain's development, with emphasis placed on compositionality in its structural design and software engineering approach. As a result, LangChain enables straightforward web service development, allowing for the orchestration of various third-party LLM services and domain tools through its backend services.

When considering possible solutions for a real-world scenario, it's crucial to remember that this tool is intended for incorporation into web services that prioritize particular domains. To adequately tackle the problem at hand, we must concentrate on the issue itself. Regarding expert perspectives on the challenges of LLM, Gobus Greyling articulated the following difficulties: "a small or unintended change to an upstream prompt, can lead to unexpected outputs and unpredictable results further downstream."

Our Problem

In reality, events don't always unfold in a linear or chronological order. Whether engaging in self-dialogue or conversing with others, it's essential to connect the discussion to the current state of affairs in the world. But how do we convey this present situation to ChatGPT, so that its predictions are relevant to us? This is a crucial question to consider if we seek ChatGPT's assistance.

Our Approach-- Tree-of-Thoughts

Our objective is to utilize formalism to model our current state of affairs. To achieve this, we need to establish a representation of what constitutes the "current" situation, along with the accompanying rules or laws to guide us in retrieving the relevant prompt context to transmit to ChatGPT for prediction.

What is the vocabulary that describes dialogue

(You can copy paste the code to https://coq.vercel.app/scratchpad.html for learning and verification. )

(For those who want to skip to the essential part, feel free to do so. This section is mainly for the sake of completeness.)

First, we define concept "state".

Require Import String.
Inductive state :=?
? | format_1(u:utterance)| format_2(e:event) | format_3(s:string)
with utterance:=
with event :=
start | good| bad | end'.        

What does the above code read?

• A "state" is something that have three different formats: it may be an utterance, or event, or string.
• An "utterance" is something we haven't got any concrete case yet. And that's totally fine, we can add more as we know. And now, with the definition, it reads "utterance" is something like the examples in an Empty_Set.
• An "event" is something that looks like examples in the set { start, good, bad, end' }.

Note that the definition here focuses on the set of individuals or objects that satisfy a particular concept or term, rather than on the inherent definition itself.

Building a model for a dialogue

Here is our expanded formal definitions:

Require Import String.
Inductive state :=?
? | format_1(u:utterance)| format_2(e:event) | format_3(s:string)
with utterance:=
with event :=
identified_as_man| identified_as_woman | identified_as_others | start | good| bad | end'.


Definition state1(e: event): state. constructor 2. auto. Defined. Coercion state1: event>->state.
Definition state2(e: utterance): state. constructor 1. auto. Defined. Coercion state2: utterance>->state.
Definition state3(e: string): state. constructor 3. auto. Defined. Coercion state3: string>->state.
Open Scope string.

Inductive dialog: state->Prop:=
?| a0_(_:dialog "i need go shopping")
? ? ? : dialog start?
?| a1_(_:dialog identified_as_man
? ? ? ? +dialog identified_as_woman
? ? ? ? +dialog identified_as_others) : dialog "i need go shopping"
?| a2_(_:dialog "good answer for man")
? ? ? : dialog identified_as_man
?| a3_(_:dialog good)
? ? ? : dialog "good answer for man"
?| a4_: dialog good
?.        

The term "dialog on state" refers to a conversation that occurs entirely after a specific state. For instance, if we consider the phrase "dialog start," it indicates a conversation that commences from the "start" state. On the other hand, the phrase "dialog 'I need to go shopping'" implies that all conversations that take place after the statement "I need to go shopping" are included.

How to retrieve the past context in a dialog

In order for ChatGPT to make predictions, a preceding context is necessary. This context can either consist of desired outcomes as few-shot learning examples or be inputted as a prompt for auto-completion. In either case, access to the "past" is required.

It is trivial to retrieve the past context from dialog X to dialog Y using proof techniques.

To illustrate, the statement labeled "goal", "dialog identified_as_man -> dialog start", will retrieve the dialogue sequence that occurs between the "dialog start" and "dialog identified_as_man."

Goal dialog identified_as_man -> dialog start.?
? intro. pose (dialog start).?
? ?constructor.? pose (dialog "i need go shopping").
? ?constructor. left. left. trivial. Qed.???        

The proof state right before "trivial" is

1 subgoal
H : dialog identified_as_man
P := dialog start : Prop
P0 := dialog "i need go shopping" : Prop
______________________________________(1/1)
dialog identified_as_man
        

Furthermore, the information related to the context of "dialog identified_as_man" from the point of "dialog start" is recorded in the "Prop" types located in the premises (above the line).

More Discussions on Tree-Based Dialog Design

The Inductive dialog type is readily able to show in a graph visualization to visualize the conversational design.

Moreover, it has formal representations, making the management of properties easy. For example, we want to verify the maximal length of dialog does not exceed certain length, we can just define a theorem like this:

Definition length(s:state)(d: dialog s): nat. Admitted. 
Definition L:= 10.
Theorem length_within_thre: forall p: dialog start, length p < L.        

Conclusion

By utilizing formalism to represent dialogue, we can effectively retrieve a context based on an utterance. This approach allows ChatGPT to acquire essential prompt contexts and generate predictions that are more contextualized.

The utilization of formalism provides a natural solution to handle the "mult-world interpretation" or "tree-of-thoughts" issue. By representing constraints using universal quantifiers (among others), we can efficiently explore the potential worlds through proof search. This method allows us to address the problem of multiple possible interpretations or thoughts, which can arise in complex dialogues.