New York Times' Connections: A Case Study on NLP in Word Games

Talk transcript

1. 0:00

   [upbeat music] Uh, yes, AI and a case study on the New York Times Connections, which is, um, the team that I work on is our games team, and I work on our popular games.

2. 0:25

   Um, if anyone's, uh, heard of Connections before or played Connections, um, or not, [chuckles] since some people might have. So, um, again, a little bit about me, a game developer at The Times.

3. 0:36

   I worked previously in media for most of my career, um, and, uh, I have a background in machine learning, mobile development, and data science. So the majority of this talk is going to probably involve a little bit of all of those.

4. 0:50

   So caveats about what you're about to see, and I'll get through as much of it as I can because it's... some of it's a little bit dense. But this is my own independent research and experimentation.

5. 1:00

   Um, it's not based on our internal research. We do have internal research and just need to clarify that separation. Um, results of this work are preliminary and subject to refinement, uh, with additional experimentation.

6. 1:13

   And the purpose of this work is investigary-- investigatory, not authoritative. So it's mostly me trying to kind of look into the, uh, the realm of, uh, AI problem-solving in the game space through our games, and it's mostly, like, a fun exercise.

7. 1:29

   Um, there does exist third-party research in AI as it resolves-- as it relates to solving Connections and other games, but... And that's an inspiration here for this project, but the processes and everything that I'm describing here I did on my own, with my own research.

8. 1:43

   So, um, for those of you who are not familiar with the game, Connections was launched by The New York Times in, uh, June of 2023 into beta and officially released in August of 2023 to the greater world.

9. 1:56

   Uh, the game is edited by Wynn Alu, who's a, uh, awesome editor at The Times that I work with, um, on games, and she creates the puzzles for, uh, Connections.

10. 2:04

    Um, it quickly became one of The New York Times' most played games, second only to Wordle, with hundreds of millions of plays within its first year. And, um, just to mention, all the Connections puzzles and game itself, game, the game mechanics and the programming, et cetera, are human-made now and forever.

11. 2:21

    So, um, all of our properties fall into that category. So the game is on the right in case, um, you have your mobile apps, wanna download it. So how Connections works.

12. 2:30

    Uh, each-- So you have a daily puzzle, and a, each puzzle provides 16 words to be grouped. The visualization on the right is kinda demonstrating play. The goal is to form four groups of words for...

13. 2:41

    of four groups of four related words. Uh, each word belongs only to one group, no overlaps, and players can make up to four incorrect guesses before losing. So, um, as you can see that, uh, as the game finishes, this particular situation, the person has won the game.

14. 2:57

    So this is where the AI and data science and et cetera start to come into play. There's a difficulty structure to Connections. So people who play the game probably know that the easiest category is yellow, where yellow is, like, the most obvious.

15. 3:10

    When you actually solve the game, it-- the most obvious connections are within the yellow category. Uh, green is the slightly less obvious connections, where you have to kind of stretch a little to think.

16. 3:20

    But once you get those, it's kind of like, "Oh, okay, this is kind of obvious, um, why, how these things are related." Uh, the blue category is trickier themes, where you have things like sayings, um, idiomatic, lexical, or trivia-based themes.

17. 3:33

    And then purple is the infamous purple, for those of who you, uh, think of the game as a difficult game, [chuckles] uh, is the category that usually trips up most people from a perfect win, and that's because there's, uh, a concept of decoy slash overlap slash misleads that are associated with the purple category.

18. 3:51

    Um, so why is it an interesting game, uh, via, via AI analysis and standards? So it, uh, can actually challenge AI's ability to abstractly reason. And now, at some point in time, we all believed that LLMs can do absolutely everything, um, and some people think that's true.

19. 4:06

    But, uh, one thing that Connections has done throughout the course of its time period is actually challenge LLMs to, um, actually have a 100% solve rate. Um, the game's intentional decoys tests whether AI can over-- avoid overfitting or superficial similarities.

20. 4:22

    Um, each solution requires clean and explainable, well-aligned with AI transparency. So, like, for example, if you want to figure out how a AI reason through a game, this is a, an actual good, like, process because you do need some sort of reasoning and in pers- perhaps abstract reasoning to solve, like, the difficult or purple category, and you

21. 4:40

    have-- you get to see how AI thinks about that. Um, there's fixed input solutions make it a reproducible and scalable testbed. So one of the interesting things that I like about this game particularly is because it is a-- could be a potential benchmarking tool, and people have used it as such to test the capabilities of AI.

22. 4:57

    And since the puzzles are the same and playable, you can repeat this process. And this is just me entering the puzzle in ChatGPT, and ChatGPT giving the wrong solution.

23. 5:07

    This is sort of, like, um, unfair comparison 'cause this is the 4o model. The higher models do give better reasoning, but that's not exactly... Uh, I'll go into that a little later if I get the time.

24. 5:17

    Um, [clears throat] and so how do humans solve Connections? Uh, there's the concept of System 1 versus System 2 thinking. Uh, I'm guessing, uh, uh, many people might be familiar with this concept.

25. 5:27

    It, uh, came out in, uh, the nin- the '90s. And, um, it's-- So System 1 thinking is when you're trying to intuit relationships very fast. When you see two things that are obviously part of the same category, you don't have to think so much.

26. 5:41

    Your, your brain sort of makes that automatic judgment. Um, System 2, which is slow and deliberate thinking, is where you have, like, s- the sort of deep kind of reasoning which you need to perform.

27. 5:52

    And that's where you're like, "Oh, I'm struggling. I don't know if this belongs to 1 or 2. Let me use my knowledge base." Um, and then in order to solve the game's, uh- And most effectively, most people use a hybrid strategy where they've used both their fast intuitive thinking and then the slow deep thinking, and that's what

28. 6:09

    takes a lot of time in the actual playing of the game. And then you can suffer from canonical failures like System One failures. You, you thought it looked obvious, but you messed up because it wasn't actually obvious.

29. 6:19

    Stuff belonged to a different category. Or System Two thinking where you're like, "Oh, I thought too deeply about this," but it was actually the obvious one. And so, you know, you overthought that one.

30. 6:28

    So that's one of the fun parts of the game if you think that's fun. [chuckles] Um, so Connections studies and benchmarks do exist. There are several benchmarks, uh, for solving Connections with the l- later models that are come out-- that have come out.

31. 6:42

    They're not by us, they're third-party benchmarks, but they do demonstrate progressive capability of LLMs to, uh, solve the game, but it's still not perfect. And as I mentioned before, there are caveats to that solvability.

32. 6:53

    So [sighs] there's... Now I'm going into the, like, deeper part, and I'm gonna see how far I get through the rest of this because this is where my AI analysis goes into play.

33. 7:01

    So, um, if-- this is some mathematics. This is your chances of winning the game if you're guessing randomly, right? If you use no intuition whatsoever. So, um, if you're totally randomly guessing, you have, uh, if you have the complete initial board, you have about a zero percent chance of winning.

34. 7:18

    Then the mathematics or combinatorics of the Connections board, uh, indicate that after maybe if you get one category right and you still need to randomly guess through the next three, you have about a one in five thousand-- one in six thousand chance of winning, which is tiny, but it's, you know, uh, you could maybe do it.

35. 7:33

    I don't know. And then, um, most people get stuck on the third and fourth category where it's like, "Oh, I don't know. Like, I got two, and now all these words, how do they relate to each other?"

36. 7:42

    So if you're like, "Screw it, I'm gonna guess randomly," uh, then you have a one in thirty-five ch-percent chance-- uh, one in thirty-five chance of winning or about two percent chance.

37. 7:49

    And that means that, oh, okay, well, you're doing pretty good, I think. [chuckles] Um, now the graph coloring problem, we're gonna go into a little bit of CS. Uh, who's familiar with the graph coloring problem?

38. 8:00

    Okay, great. We have CS people here. Yes. So graph coloring involves assigning colors to vertices of a graph. The graph is the structure on the right, which is basically a bunch of nodes and edges.

39. 8:10

    Um, there's some number associated with the graph. Not gonna get too deep into that. But that I'm doing that chromatic number is important. Um, and when you want to solve a graph coloring problem, you use algorithms that are popularly known, backtracking, greedy coloring.

40. 8:25

    And the graph coloring problem, just for interest, has, um, applications in all kinds of areas outside of, um, you know, just computer science, scheduling, frequency assignment, uh, wireless networks, and in Connections.

41. 8:37

    But you can model Connections as a graph coloring, an augmented graph coloring problem. So this is a Connection solver that I built on the right that a bunch of puzzles and attempts to organize them into graph coloring, um, groups.

42. 8:49

    So each of the words, sixteen words in Connections, can be a vertex in this graph. The four hidden categories that we already went over, they're color-coded. And the goal is to color each word node with one of the four categories such that all four words belong to a specific category receive the same color.

43. 9:06

    And then edge is the strength of the connection that it's thought of to exist between words. So that is basically how related they are is the edge. So the reason why that's important is because that creates the search space for an algorithm or an AI to actually, you know, play the game effectively, um, or solve the game

44. 9:23

    effectively. Without that, it's falling into the random range of gra-- of sorting words, and it becomes much more difficult. So we have this idea of semantic similarity. It's not enough.

45. 9:34

    I, I wish-- I, I renamed it semantic similarity is not all you need, uh, if you get the transformer joke. Um, so [chuckles] this is like... It's hard to see here, but there's a tree of word relationships between different words.

46. 9:45

    For example, a-anagrams are related, uh, could be a, a, a type of category called orthography of words. So, um, you know, that could be an entire category. Morphology, meaning things like that have the same s-, uh, suffix, uh, like something like kingdom, fiefdom, or connectedness, um, is things like that.

47. 10:04

    Then you have other semantic relationships that are not so obvious, which are could be things like encyclopedic relationships, like for example, Globe, Mirror, Post, and Sun are all part of the newspaper category.

48. 10:14

    And then you have things like associative relationships, things that are red or things that are green, right? Strawberry, rose, Mars, et cetera. And so again, um, the most-- I just going back to this, polysemy, things that can, like for example, what a mole can be, an animal, [REDACTED:physical_attribute], spy, or unit, uh, that is where the Connections actually,

49. 10:33

    just for interest's sake, is the most complicated for most AIs and people because that's the, the polysemy multiple meaning section is where on a base level, people get tripped up.

50. 10:43

    The-- any intelligence can get tripped up. So you have this concept of relational alignment. So relational alignment is if you can create a metric that associates two words together, you can have a relational alignment score.

51. 10:55

    So there's different metrics that are a-associated with relational alignment, and so I created this heat map simulation on the right, which can pick different metrics and show how, based on the metric calculations, which I'm not showing here, that these two things are-- that these, um, two words from a large category are related.

52. 11:12

    Now, um, the build-- story I'm building up is that relational alignment between puzzles, uh, can help you determine on a computational way whether a puzzle is easy or whether it's hard.

53. 11:23

    So this is example from an easy puzzle years ago that was, uh, done versus a hard puzzle, and this is like, um, people have described this as the solve rate is nineteen percent for the hard puzzle, but like seventy something for the easier puzzle.

54. 11:37

    And you can see that there's a, a rough overarching coherence or relational alignment score differential between easy and hard. So that differential lets you understand there's a computational process which you can apply.

55. 11:49

    So you can see that time-variant relational alignment scores can go across categories and time. So puzzles are easy, puzzles are hard, and you see some sort of time-variant metric, which, you know, you can, you can com-- you can compute this, and you can draw a graph over time.

56. 12:03

    I'm not sure what happened here on 12/12. I think... Oh, we had a broken puzzle that day, so it was zero. Um, [chuckles] but the idea is that you can see that there could be patterns established from this, um, alignment score that you compute.

57. 12:15

    Now, i-if it was that easy, that would be great, but it's not actually that easy because as we have multiple different semantic relationships, we have multiple relational alignment scores.

58. 12:24

    So basically, uh, two words can be related in multiple ways, and they can have different scores across different categories. So some can be semantically or morphologically more strongly related than they are, um, for example, um, categorically or encyclopedically related.

59. 12:39

    But, uh, the idea is that you can create sort of this radar chart, which lets you kind of map out, uh, some sort of diagram or surface which you can analyze to see how the, uh, semantic space of the word across different categories looks.

60. 12:52

    That means you have yet another dimension to analyze how your AI can analyze how, um, to solve a puzzle, or your AI, or solver, or you yourself, if you want to think about, like, this stuff deep- more deeply using your, um, reasoning.

61. 13:06

    So multidimensional re- uh, relational a-alignment distribution was part of the things that I was kinda looking at. So I basically... A-another component of the system I built was the semantic distribution evaluation framework, where I'm taking a bunch of our puzzles, and then I'm building this category- categorical distribution over time, where you can see on the lower right.

62. 13:25

    It's hard maybe to see a little bit, but there's the different categories like hypernymy, um, morphology, orthography, things I talked about, and the distribution of categories for, um, the Connections puzzles over time.

63. 13:37

    And so you can see I'm counting, like, which categories over the days fall into which, um, of these buckets with these dots on this right, and I can build a sort of like histogram or count of this association.

64. 13:47

    And so you can look at trends, and then you can use that data, uh, that trend data. So now here is where it gets a little bit more involved.

65. 13:54

    Um, the graph co- uh, coloring approximation is a search space reduction, uh, process, but then you get to the, uh, more complicated idea of graph clustering. Once you add the semantic relationships into the actual, uh, formulation, um, you actually start to build multidimensional or hypergraphs.

66. 14:10

    And this is just a three-dimensional hypergraph, but if you have multiple semantic relationships, you actually have multidimensional hypergraphs. And this is kind of just a demonstration of how the hypergraph converges in three dimensions, meaning that if you have all these semantic relationships, you're going to have these, uh, intercluster strengths between, uh, different nodes and different categories.

67. 14:30

    But you also have the intracluster strength, which shows you how strong the relationships are within the clusters that form due to the algorithm you're using. That's important because the graph-- this graph gives you more dimensionality, and again, well, is a more computational way of using AI to solve this, uh, problem, or any, again, solver to solve the

68. 14:48

    problem. Um, so how do you build these semantic graphs? You can use different ty-types of, uh, lexical databases or lexical, um, constructors. For example, WordNet, ConceptNet, and other word embeddings can be used to construct these relationships.

69. 15:02

    And so this is a, a flat example of a 2D graph of one puzzle, where you see relationships between, like, different words. Like, for example, two words co-occur together.

70. 15:11

    A mouse hunts a cat. A dog is related to a cat. A cat is capable of play. A cat is used for pet. And you can see the complex dimensionality of these conceptual semantic graphs as derived from WordNet, ConceptNet, and word embeddings allows you even more space.

71. 15:26

    So we're increasing the intelligence here. You see, I'm not just doing a reasoning model or dumbly put it into an LLM. I'm actually trying to increase this, uh, intelligence space, like, procedurally so that you can have a trackable and explainable way.

72. 15:39

    You know, explainable AI, that's what I'm all about. This is part of that. [chuckles] So, um, to get to the actual model which does that, anyone familiar with graph neural networks?

73. 15:49

    Okay, so if you've used GNNs, uh, before, that, that, that's the primary... Since this is a geometric problem in multi-space, you... Well, I-- The primary pro-- uh, solver that I'm using is a, uh, is a graph convolutional neural network, which allows you to kind of create, take in a graph as an input, and then s-put like candidate

74. 16:08

    subgraphs that could be solutions as outputs. This is one part of the problem. It's part of a two-part problem where I'm using the graph, the reinforcement learning system. So once we have the graph neural network that's actually outputting candidate graphs, you have edge weights and node weights that are being optimized, and then you find out which graph,

75. 16:26

    like, fits into the candidate solutions. Then you can track the actual structure of the graph, which is just cluster morphology or, like, how the graph looks. The next visualization, this is the system diagram.

76. 16:37

    I'm not gonna go into it. It's a lot. But, um, I'll just say it's the combination of a learning agents with, uh, a graph, uh, s- a graph-based system for, um, actually with the graph neural network for kind of isolating how, what candidate graphs you have.

77. 16:52

    And so this is... I'm almost out of time, but I'll just say that this is kind of like how the visualization looks in three-space. Once your, um, semantic graphs are, uh...

78. 17:03

    Once your semantic graphs are constructed, your graph candidates and the reinforcement learning system is kind of the appropriate way to kind of navigate these subclusters. And you can't actually see the cluster points here because the visualization wasn't super great, but the actual output is kind of like, "Okay, now this, it c- this traversal is allowed to exist."

79. 17:21

    So again, um, after all this stuff, the solvability rate from before to after for a short, a small subset of hard puzzle, puzzles increases somewhat reasonably. But now, again, this is a work in progress, and I tried this against a few puzzles before and after.

80. 17:36

    And now the idea is to extend this and, like, make it more involved for even more puzzles, and then get to game development. So why do all this? Or, well, our LLMs are great at a bunch of stuff, but, you know, they o- can often make, you know, their own mistakes.

81. 17:49

    LLMs are often are trained on internet data, and the puzzle solutions are available on the internet, so who knows if they're just pulling the solutions from the internet. That's one thing that bothered me about, uh, LLM solving these problems.

82. 17:59

    And so... And that's... LLM solutions are still a black box. And so, um, the idea is to connect this to the ARC-AGI benchmark, um, and that kind of thing.

83. 18:09

    So it, you know, that, that benchmark has a parti-- like a, yeah, uh, uh, a solvability, uh, association. And so we have some next steps, and this is pretty much the end of my presentation.

84. 18:20

    I ran a few seconds over. But yeah, if you're interested, talk to me later. All right. [upbeat music]