New York Times' Connections: A Case Study on NLP in Word Games — Shafik Quoraishee, NYT Games

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. If anyone's heard of Connections before or played Connections, or not, since some people might have.

So, again, a little bit about me: a game developer at the Times. I worked previously in media for most of my career, and 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.

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

We do have internal research and just need to clarify that separation. The results of this work are preliminary and subject to refinement, with additional experimentation. And the purpose of this work is investigatory, not authoritative. So it's mostly me trying to kind of look into the realm of AI problem solving in the game space through our games, and it's mostly like a fun exercise.

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.

So, um, for those of you who are not familiar with the game, Connections was launched by the New York Times in June of 2023 into beta and officially released in August of 2023 to the greater world. The game is edited by Wena Liu, who's an awesome editor at the Times that I work with on games, and she creates the puzzles for Connections.

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, the game mechanics and the programming, et cetera, are human-made now and forever, so all of our properties fall into that category.

So the game is on theright in case you have your mobile apps want to download it. So, how Connections works: each, so you have a daily puzzle, and each puzzle provides 16 words to be grouped. The visualization on theright is kind of demonstrating play.

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

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.

When you actually solve the game, the most obvious connections are within the yellow category. Green is the slightly less obvious connections, where you have to kind of stretch a little to think, but once you get those, it's kind of like, oh, okay, this is kind of obvious why how these things are related.

The blue category is trickier themes, where you have things like sayings, idiomatic, lexical, or trivia-based themes. And then purple is the infamous purple, for those of who think of the game as a difficult game, is the category that usually trips up most people from a perfect win, and that's because there's a concept of decoy slash overlap slash misleads that are associated with the purple category.

So why is it an interesting game via AI analysis and standards? So it can actually challenge AI's ability to abstractly reason. And now, at some point in time, we all believe that LLMs can do absolutely everything, and some people think that's true, but one thing that Connections has done throughout the course of its time period is actually challenged LLMs to actually have a 100% solve rate.

The game's intentional decoys tests whether AI can avoid overfitting or superficial similarities. Each solution requires clean and explainable, well-aligned with AI transparency. So, like, for example, if you want to figure out how AI reasoned through a game, this is an actual good, like, process because you do need some sort of reasoning and perhaps abstract reasoning to solve, like, the difficult or purple category, and you have to see how AI thinks about that.

There's fixed input solutions make it a reproducible and scalable test bed. 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.

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. This is sort of like an unfair comparison because this is the 4.0 model.

The higher models do give better reasoning, but that's not exactly, I'll go into that a little later if I get the time. And so how do humans solve Connections? There's the concept of system one versus system two thinking.

I'm guessing many people might be familiar with this concept. It came out in the '90s, and it's, so system one 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.

Your brain sort of makes that automatic judgment. System two, which is slow and deliberate thinking, is where you have, like, the sort of deep kind of reasoning which you need to perform, and that's where you're like, oh, I'm struggling.

I don't know if this belongs to one or two. Let me use my knowledge base. And then, in order to solve the games most effectively, most people use a high technology, where they've used both the fast intuitive thinking and then the slow deep thinking, and that's what 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 thought it looked obvious, but you messed up because it wasn't actually obvious. 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.

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

They're not by us, they're third-party benchmarks, but they do demonstrate progressive capability of LLMs to solve the game, but it's still not perfect, and as I mentioned before, there are caveats to that solvability. So there's, now I'm going into the, like, deeper part, and I'm going to see how far I get through the rest of this because this is where my AI analysis goes into play.

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

Then the mathematics or combinatorics of the Connections board indicate that after maybe if you get one categoryright 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, you could maybe do it.

I don't know. And then 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? So if you're like, screw it, I'm going to guess randomly, then you have a one in 35 percent chance, one in 35 chance of winning, or about a percent chance, and that means that, oh, okay, well, you're doing pretty good, I think.

Now the graph coloring problem, we're going to go into a little bit of CS. Who's familiar with the graph coloring problem? 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 theright, which is basically a bunch of nodes and edges. There's some number associated with the graph. Not going to get too deep into that, but I'm doing that chromatic number is important. And when you want to solve a graph coloring problem, you use algorithms that are popularly known, backtracking, greedy coloring.

And the graph coloring problem, just for interest, has applications in all kinds of areas outside of, you know, just computer science, scheduling, frequency assignment, wireless networks, and in Connections. So you can model Connections as a graph coloring, an augmented graph coloring problem.

So this is a connection solver that I built on theright that's a bunch of puzzles and attempts to organize them into graph coloring groups. So each of the words, 16 words in Connections, can be a vertex in this graph.

There are 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.

And then the edge is the strength of the connection that is 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 or solve the game effectively.

Without that, it's falling into the random range of sorting words, and it becomes much more difficult. So we have this idea of semantic similarity. It's not enough. I wish I renamed it semantic similarity is not all you need if you get the transformer joke.

So this is like, it's hard to see here, but there's a tree of word relationships between different words. For example, anagrams are related, could be a type of category calledorthography of words. So, you know, that could be an entire category.

Morphology, meaning things like that have the same suffix, like something like kingdom, fiefdom, or connectedness, things like that. Then you have other semantic relationships that are not so obvious, which could be things like encyclopedic relationships, like, for example, globe, mirror, post, and sun are all part of the newspaper category.

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, the most, I just, going back to this, polysomy, things that can, like, for example, what a mole can be, an animal birthmark spy or unit, that is where the Connections actually, just for interest's sake, is the most complicated for most AIs and people because that's the polysomy multiple meaning section is where, on a base level, people get tripped up.

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. So there's different metrics that are associated with relational alignment, and so I created this heat map simulation on theright, 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 two words from a large category are related.

Now, the story I'm building up is that relational alignment between puzzles can help you determine in a computational way whether a puzzle is easy or whether it's hard. So this is, for example, from an easy puzzle years ago that was done versus a hard puzzle.

And this is like, people have described this as the solve rate is 19 percent for the hard puzzle, but like 70 something for the easier puzzle. And you can see that there's 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. 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 compute this and you can draw a graph over time.

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

Now, 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. So basically, 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, for example, categorically or encyclopedically related. But the idea is that you can create sort of this radar chart, which lets you kind of map out some sort of diagram or surface which you can analyze to see how the semantic space of the word across different categories looks.

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

So multi-dimensional relational alignment distribution was part of the things that I was kind of looking at. So I basically, 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 categorical distribution over time, where you can see on the lowerright, it's hard maybe to see a little bit, but there's the different categories like hyponymy, morphology,orthography, things I talked about, and the distribution of categories for the Connections puzzles over time.

And so you can see I'm counting, like, which categories over the days fall into which of these buckets with these dots on thisright, and I can build a sort of, like, histogram or count of this association. And so you can look at trends, and then you can use that data, that trend data.

So now it gets a little bit more involved. The graph coloring approximation is a search space reduction process, but then you get to the more complicated idea of graph clustering. Once you add the semantic relationships into the actual formulation, you actually start to build multi-dimensional or hypergraphs.

And this is just a three-dimensional hypergraph, but if you have multiple semantic relationships, you actually have multi-dimensional 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 intercluster strengths between different nodes and different categories, but you also have the intra-cluster 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 this graph gives you more dimensionality and, again, is a more computational way of using AI to solve this problem, or any, again, solver to solve the problem. So how do you build these semantic graphs? You can use different types of lexical databases or lexical constructors.

For example, WordNet, ConceptNet, and other word embeddings can be used to construct these relationships. And so this is 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.

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.

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

You know, explainable AI, that's what I'm all about. This is part of that. So to get to the actual model which does that, anyone familiar with graph neural networks? Okay, so if you've used GNNs before, that's the primary since it's a geometric problem in multi-space.

You, well, the primary solver that I'm using is a graph convolutional neural network, which allows you to kind of create, take in the graph as an input, and then put, like, candidate 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 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, like, fits into the candidate solutions.

Then you can track the actual structure of the graph, which is cluster morphology or, like, how the graph looks. The next visualization, this is the system diagram. I'm not going to go into it. It's a lot, but I'll just say it's the combination of a learning agent with a graph-based system for actually with the graph neural network for kind of isolating what candidate graphs you have.

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 semantic graphs are, 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 traversal is allowed to exist. So again, after all this stuff, the solvability rate from before to after for a short, a small subset of hard puzzles increases somewhat reasonably.

But now, again, this is a work in progress, and I tried this against a few puzzles before and after. Another 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? Well, our LLMs are great at a bunch of stuff, but, you know, they can often make, you know, their own mistakes. LLMs 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 LLMs solving these problems. And so, and that's, LLM solutions are still a black box. And so the idea is to connect this to the ARC AGI benchmark and that kind of thing.

So, you know, that benchmark has a, like, a, yeah, a solvability association. And so we have some next steps, and this is pretty much the end of my presentation. I ran a few seconds over, but, yeah, if you're interested, talk to me later.