6 ms·

Graph of Thoughts: Solving Elaborate Problems with Large Language Models

283 points by jonbaer 3y ago

Cloudly 3y ago
https://github.com/spcl/graph-of-thoughts https://github.com/spcl/graph-of-thoughts Code for the paper too
refulgentis 3y ago
Need more data. - Complex generalization with a simple unstated justification: last 'paper' like this was ToT, and a tree is a graph with constraints. - Framework is discussed cognitively, units of "thoughts" "scored". (AutoGPT redux, having the LLM eat its own output repetitively improves things but isn't a panacea) - Only sorting demonstrated "due to space constraints" -- unclear what that means, it seems much more likely it was self-enforced time constraints - Error rate is consistently 14%. - ~10x the cost for ~15% error rate in sorting instead of ~30% - GPT3.5
marcopicentini 3y ago
What are other use cases that could be made only by LLM ? Number sorting is faster using code.
- creer 3y ago
  I don't think efficiency is important at this point. Finding that it's possible "this way" opens the door for more work and more applications. (Which doesn't prevent others to already work on efficiency.)
- empath-nirvana 3y ago
  The point of using number sorting for this paper is that its A) difficult to impossible for an LLM to do in a single pass B) easy to verify the correctness. In general, the point isn't finding things that only an LLM can do, but find things that LLMs can do with decent results at lower cost than getting a human to do it.
  - deleted 3y ago
    [deleted]
  - jbay808 3y ago
    It is only difficult for a LLM to sort a list of numbers if the list is longer than half of the context window. (Source: I tested this myself[1]). The sorts are not error-free every time, but with sufficient training they become error-free the vast majority of the time, even for long lists. This is not especially surprising because transformers are capable of directly representing sorting programs.[2] [1] https://jbconsulting.substack.com/p/its-not-just-statistics-gpt-4-does https://jbconsulting.substack.com/p/its-not-just-statistics-... [2] https://arxiv.org/abs/2106.06981 https://arxiv.org/abs/2106.06981
    - empath-nirvana 3y ago
      Of course you can train a neural network to sort numbers, but I'm talking about a general LLM which hasn't been trained to sort numbers specifically. Training a GPT network to sort numbers is not what I would consider to be a Large Language Model.
firewolf34 3y ago
The more I read about ML, the more I begin to believe that - psychologically speaking - hierarchy (esp. graph structures, trees) are absolutely core to advanced information processing in general.
- blurbleblurble 3y ago
  This article is about how non-hierarchical graphs, those with cycles, are performing better than trees or chains.
  - theptip 3y ago
    I suspect that you'll still find strong hierarchy in an optimized/well-performing graph of thought. The human brain, for example, also has recurrence, but it's limited. It seems pretty intuitive that you'd get a "task / subtask" split for example, with feedback from the latter, but semantic content largely flowing from the former to the latter.
- brutusborn 3y ago
  I won’t pretend to understand it, but this reminds me of the idea of markov blankets when using the free energy principle to model congition. https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7955287/#:~:text=The%20free%2Denergy%20principle%20begins,state%20(Friston%2C%202020) https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7955287/#:~:tex....
- visarga 3y ago
  We got symbolic AI sneaked into the connectionist model by making a graph of thoughts. A graph can explicitly implement any algorithm or data structure. They could make it more efficient by implementing a kind of "hard attention". Each token should have access to a sparse subset of the whole input, so it would be like a node in a graph only having access to a few neighbours. Could solve the very large context issue. This can also be parallelised, running all thought nodes in parallel, of course each with a sparse view of the whole input making it much faster. For example when reading a long book, the model would spawn nodes for each person, location or event of interest, and they would track the source text as the action develops. A mental map of the book. That would surely help a model deal with many moving pieces of information. Or when solving a problem, the model could spawn a node to work on a subproblem, parametrised by the parent node with the right inputs. Then the node would report back with the answer and the parent continues. This would work with recursive calls. The new cpu is the LLM and the clock tick is 1 token.
brutusborn 3y ago
This is fantastic. I’d love to see a system that uses an LLM to generate knowledge graphs from academic papers to make them machine readable. Some kind of prompt like “does paper P contain idea A and does it suggest that A is true.” Then you could automatically categorise citations by whether they agree/disagree with the cited paper. Sometimes I see papers with 2,000 citations and I wonder: how many of those are dis/agreeing with the paper.
- throwaway290 3y ago
  By that logic why don't you just directly ask the LLM on whether a citation agrees or not, you are already trusting it to be correct with that graph in the first place...
  - brutusborn 3y ago
    You are correct, I wrote that in a rush and mixed up examples in my head. I don’t think you need to trust the LLMs for this kind of thing to be very useful. The LLM could generate the KG with every node labelled as “autogenerated.” When you use the graph for research, you are still going to read the papers you are interested in so you can then update the relevant citation node with the label “human checked.” If a research group uses the same graph over time, the nodes will gradually become “trustworthy” (ie verified by humans). Maybe even get reviewers to update a papers graph during review and publish that for other groups to add to their graphs.
    - visarga 3y ago
      That's a great idea. It would be easier to know if anyone done what you want, get a better overview of the current knowledge.
    - throwaway290 3y ago
      Then why not just author knowledge as a graph in the first place, as humans?
      - 3y ago
creer 3y ago
I keep feeling that LLMs are one direction to address the thorny "common sense" issue of AI. Mountains of training text incorporate, probably, most common sense (and a lot of nonsense). It's beautiful to see so many ideas come out currently to make better use of the models. Including the fast progress made with image generation.
jstx1 3y ago
How well do these papers replicate? In some of experiments with GPT-4 I've seen chain-of-thought style prompting make answers noticeably worse than plainly asking a question once.
- rmbyrro 3y ago
  Really? Do you have any examples to share? I'd be surprised to see that in action.
knexer 3y ago
This is a really natural extension of CoT. I was experimenting for a month or two with a similar concept in a hobby project this past spring: https://github.com/knexer/llmtaskgraph https://github.com/knexer/llmtaskgraph . I'm really excited to see more people exploring in this direction! I was focusing more on an engineering perspective; modeling a complex LLM-and-code process as a dependency graph makes it easy to: - add tracing to continuously measure and monitor even post-deployment - perform reproducible experiments, a la time-rewinding debugging - speed up iteration on prompts by caching the parts of the program you aren't working on right now My test case was using GPT4 to implement the operators in a genetic algorithm, which tbh is a fascinating concept of its own. I drifted away after a while (curse that ADHD) but had a great time with the project in the meantime.
- petra 3y ago
  That's really interesting. Did using genetic algorithms enabled GPT4 to be truly creative ?
- llmsolutions 3y ago
  This is great, we've built eerily similar tooling for our internal projects. Unfortunately, in our experiments with OpenAI chat completions, the "reproducible" part has proven to just not be possible. There's nothing more frustrating than spending an hour debugging your chain, only to realize a binary classification prompt has decided to flip after hundreds of consistent executions!
  - knexer 3y ago
    Oh yeah, I empathize with that frustration! I've come to the conclusion that LLM applications require a fundamentally different approach to reliability than we're used to. Traditional programming is about composing abstractions to build more complex abstractions; because the low-level abstractions are so close to perfect, we can build these immense towers of abstractions and still have effective guarantees on their behavior. With LLMs, perfect abstractions are impossible, and composing them naively will exponentially magnify their imperfections. Instead, I think composing LLMs needs to be done in a way that degrades gracefully, with resilience to failure being a fundamental consideration. Biology has similar properties; complex biological systems (ecosystems, cells, etc) have feedback loops, redundancy, and most of all diversity. If we take a similar approach to building LLM apps, we'll end up with things like: - multiple different prompts used in parallel, with results joined e.g. with voting. A change in how one prompt behaves can thus only have a bounded effect on the system as a whole. - some way for an LLM to productively express 'this thing you're asking me to do is nonsense', with monitoring and continuous evaluation hooked up to that signal, and maybe runtime retry behavior as well. This can help with when you get into situations where prompt A gets an "I'm afraid I can't do that" response, and then you give that to prompt B as if it is a valid thing, and that cascades through the rest of the application. llmtaskgraph as a library is designed to make building, operating and maintaining systems with these sorts of features easier - without good observability, it's impossible to know if some feedback loop is doing its job, or which prompts in a pool are behaving well vs poorly, much less what effect they are having on the rest of the system. Sorry for the wall of text, I got a bit nerd-sniped. :)
sorokod 3y ago
For the kind of synergy I demand, only the hypergraph of thought ( HoT ) will do.
- groceryheist 3y ago
  Intractable. Only the simplical complex of thought provides the optimal balance of expressiveness and constraint.
  - sorokod 3y ago
    Well ok, maybe only for distilling the essence of whole networks of thoughts
zalyalov 3y ago
Weird that they claim to use arbitrary graphs, while in reality it's a weird subclass of DAGs with one-vertex loops kind of allowed, except they don't really make sense to be represented as loops.
obeavs 3y ago
Cool to see it going this way. Over the last two years, we've been busy reinventing contracts and financial models as the dependency graphs that they are to provide a deterministic, intermediate representation of this information in finance. Still not sold that it'll fly in finance without that sort of observable, intermediate representation.
- darkteflon 3y ago
  Could you elaborate a little on the work you’re doing with contracts?
mountainriver 3y ago
Would love to see it compared to RAP rather than just ToT, MCTS is SOTA in RL task planning
deleted 3y ago
[deleted]
billgeller06 3y ago
I think the paper "Algorithm of Thoughts: Enhancing Exploration of Ideas in Large Language Models" (AoT) is big competitor with this paper. It shows that we can get similar results to Tree of Thoughts just by using a single query. AoT seems to be even surpassing ToT in some of the experiments.

283 points by jonbaer 3y ago

https://github.com/spcl/graph-of-thoughts https://github.com/spcl/graph-of-thoughts Code for the paper too

Need more data. - Complex generalization with a simple unstated justification: last 'paper' like this was ToT, and a tree is a graph with constraints. - Framework is discussed cognitively, units of "thoughts" "scored". (AutoGPT redux, having the LLM eat its own output repetitively improves things but isn't a panacea) - Only sorting demonstrated "due to space constraints" -- unclear what that means, it seems much more likely it was self-enforced time constraints - Error rate is consistently 14%. - ~10x the cost for ~15% error rate in sorting instead of ~30% - GPT3.5

marcopicentini 3y ago

What are other use cases that could be made only by LLM ? Number sorting is faster using code.

creer 3y ago
I don't think efficiency is important at this point. Finding that it's possible "this way" opens the door for more work and more applications. (Which doesn't prevent others to already work on efficiency.)
empath-nirvana 3y ago
The point of using number sorting for this paper is that its A) difficult to impossible for an LLM to do in a single pass B) easy to verify the correctness. In general, the point isn't finding things that only an LLM can do, but find things that LLMs can do with decent results at lower cost than getting a human to do it.
- deleted 3y ago
  [deleted]
- jbay808 3y ago
  It is only difficult for a LLM to sort a list of numbers if the list is longer than half of the context window. (Source: I tested this myself[1]). The sorts are not error-free every time, but with sufficient training they become error-free the vast majority of the time, even for long lists. This is not especially surprising because transformers are capable of directly representing sorting programs.[2] [1] https://jbconsulting.substack.com/p/its-not-just-statistics-gpt-4-does https://jbconsulting.substack.com/p/its-not-just-statistics-... [2] https://arxiv.org/abs/2106.06981 https://arxiv.org/abs/2106.06981
  - empath-nirvana 3y ago
    Of course you can train a neural network to sort numbers, but I'm talking about a general LLM which hasn't been trained to sort numbers specifically. Training a GPT network to sort numbers is not what I would consider to be a Large Language Model.

firewolf34 3y ago

The more I read about ML, the more I begin to believe that - psychologically speaking - hierarchy (esp. graph structures, trees) are absolutely core to advanced information processing in general.

blurbleblurble 3y ago
This article is about how non-hierarchical graphs, those with cycles, are performing better than trees or chains.
- theptip 3y ago
  I suspect that you'll still find strong hierarchy in an optimized/well-performing graph of thought. The human brain, for example, also has recurrence, but it's limited. It seems pretty intuitive that you'd get a "task / subtask" split for example, with feedback from the latter, but semantic content largely flowing from the former to the latter.
brutusborn 3y ago
I won’t pretend to understand it, but this reminds me of the idea of markov blankets when using the free energy principle to model congition. https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7955287/#:~:text=The%20free%2Denergy%20principle%20begins,state%20(Friston%2C%202020) https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7955287/#:~:tex....
visarga 3y ago
We got symbolic AI sneaked into the connectionist model by making a graph of thoughts. A graph can explicitly implement any algorithm or data structure. They could make it more efficient by implementing a kind of "hard attention". Each token should have access to a sparse subset of the whole input, so it would be like a node in a graph only having access to a few neighbours. Could solve the very large context issue. This can also be parallelised, running all thought nodes in parallel, of course each with a sparse view of the whole input making it much faster. For example when reading a long book, the model would spawn nodes for each person, location or event of interest, and they would track the source text as the action develops. A mental map of the book. That would surely help a model deal with many moving pieces of information. Or when solving a problem, the model could spawn a node to work on a subproblem, parametrised by the parent node with the right inputs. Then the node would report back with the answer and the parent continues. This would work with recursive calls. The new cpu is the LLM and the clock tick is 1 token.

brutusborn 3y ago

This is fantastic. I’d love to see a system that uses an LLM to generate knowledge graphs from academic papers to make them machine readable. Some kind of prompt like “does paper P contain idea A and does it suggest that A is true.” Then you could automatically categorise citations by whether they agree/disagree with the cited paper. Sometimes I see papers with 2,000 citations and I wonder: how many of those are dis/agreeing with the paper.

throwaway290 3y ago
By that logic why don't you just directly ask the LLM on whether a citation agrees or not, you are already trusting it to be correct with that graph in the first place...
- brutusborn 3y ago
  You are correct, I wrote that in a rush and mixed up examples in my head. I don’t think you need to trust the LLMs for this kind of thing to be very useful. The LLM could generate the KG with every node labelled as “autogenerated.” When you use the graph for research, you are still going to read the papers you are interested in so you can then update the relevant citation node with the label “human checked.” If a research group uses the same graph over time, the nodes will gradually become “trustworthy” (ie verified by humans). Maybe even get reviewers to update a papers graph during review and publish that for other groups to add to their graphs.
  - visarga 3y ago
    That's a great idea. It would be easier to know if anyone done what you want, get a better overview of the current knowledge.
  - throwaway290 3y ago
    Then why not just author knowledge as a graph in the first place, as humans?
    - 3y ago

creer 3y ago

I keep feeling that LLMs are one direction to address the thorny "common sense" issue of AI. Mountains of training text incorporate, probably, most common sense (and a lot of nonsense). It's beautiful to see so many ideas come out currently to make better use of the models. Including the fast progress made with image generation.

jstx1 3y ago

How well do these papers replicate? In some of experiments with GPT-4 I've seen chain-of-thought style prompting make answers noticeably worse than plainly asking a question once.

rmbyrro 3y ago
Really? Do you have any examples to share? I'd be surprised to see that in action.

knexer 3y ago

This is a really natural extension of CoT. I was experimenting for a month or two with a similar concept in a hobby project this past spring: https://github.com/knexer/llmtaskgraph https://github.com/knexer/llmtaskgraph . I'm really excited to see more people exploring in this direction! I was focusing more on an engineering perspective; modeling a complex LLM-and-code process as a dependency graph makes it easy to: - add tracing to continuously measure and monitor even post-deployment - perform reproducible experiments, a la time-rewinding debugging - speed up iteration on prompts by caching the parts of the program you aren't working on right now My test case was using GPT4 to implement the operators in a genetic algorithm, which tbh is a fascinating concept of its own. I drifted away after a while (curse that ADHD) but had a great time with the project in the meantime.

petra 3y ago
That's really interesting. Did using genetic algorithms enabled GPT4 to be truly creative ?
llmsolutions 3y ago
This is great, we've built eerily similar tooling for our internal projects. Unfortunately, in our experiments with OpenAI chat completions, the "reproducible" part has proven to just not be possible. There's nothing more frustrating than spending an hour debugging your chain, only to realize a binary classification prompt has decided to flip after hundreds of consistent executions!
- knexer 3y ago
  Oh yeah, I empathize with that frustration! I've come to the conclusion that LLM applications require a fundamentally different approach to reliability than we're used to. Traditional programming is about composing abstractions to build more complex abstractions; because the low-level abstractions are so close to perfect, we can build these immense towers of abstractions and still have effective guarantees on their behavior. With LLMs, perfect abstractions are impossible, and composing them naively will exponentially magnify their imperfections. Instead, I think composing LLMs needs to be done in a way that degrades gracefully, with resilience to failure being a fundamental consideration. Biology has similar properties; complex biological systems (ecosystems, cells, etc) have feedback loops, redundancy, and most of all diversity. If we take a similar approach to building LLM apps, we'll end up with things like: - multiple different prompts used in parallel, with results joined e.g. with voting. A change in how one prompt behaves can thus only have a bounded effect on the system as a whole. - some way for an LLM to productively express 'this thing you're asking me to do is nonsense', with monitoring and continuous evaluation hooked up to that signal, and maybe runtime retry behavior as well. This can help with when you get into situations where prompt A gets an "I'm afraid I can't do that" response, and then you give that to prompt B as if it is a valid thing, and that cascades through the rest of the application. llmtaskgraph as a library is designed to make building, operating and maintaining systems with these sorts of features easier - without good observability, it's impossible to know if some feedback loop is doing its job, or which prompts in a pool are behaving well vs poorly, much less what effect they are having on the rest of the system. Sorry for the wall of text, I got a bit nerd-sniped. :)

sorokod 3y ago

For the kind of synergy I demand, only the hypergraph of thought ( HoT ) will do.

groceryheist 3y ago
Intractable. Only the simplical complex of thought provides the optimal balance of expressiveness and constraint.
- sorokod 3y ago
  Well ok, maybe only for distilling the essence of whole networks of thoughts

zalyalov 3y ago

Weird that they claim to use arbitrary graphs, while in reality it's a weird subclass of DAGs with one-vertex loops kind of allowed, except they don't really make sense to be represented as loops.

obeavs 3y ago

Cool to see it going this way. Over the last two years, we've been busy reinventing contracts and financial models as the dependency graphs that they are to provide a deterministic, intermediate representation of this information in finance. Still not sold that it'll fly in finance without that sort of observable, intermediate representation.

darkteflon 3y ago
Could you elaborate a little on the work you’re doing with contracts?

mountainriver 3y ago

Would love to see it compared to RAP rather than just ToT, MCTS is SOTA in RL task planning

deleted 3y ago

[deleted]

billgeller06 3y ago

I think the paper "Algorithm of Thoughts: Enhancing Exploration of Ideas in Large Language Models" (AoT) is big competitor with this paper. It shows that we can get similar results to Tree of Thoughts just by using a single query. AoT seems to be even surpassing ToT in some of the experiments.