A Formal Approach to Multi-Agent Communication Safety

Thank you, Emily. Hey, everyone. Morning. I'm Aaron, and this is Hugo. And we would love to talk to you about a formal approach to multi-agent communication safety. First of all, I'd like to acknowledge the traditional owners of the lands where we're meeting. I'm from Turrbal and Yugara country in Queensland, and it's a pleasure to be here with you in Gadigal country this week. Hugo, you want to kick us off? Hi.

Hugo O'Connor

Good morning, everyone. I just want to pick up on two things that were spoken of yesterday at keynote. The first is that the capabilities of these LLM agents are often discovered by elicitation, which means that people are adding new connectors and skills to agents as they use them. And the second part is that these agents and systems are composed, and how they're composed is by passing messages between the agents and different software components, which is what we'll talk about in this presentation.

Aaron Snoswell

Yeah, fantastic. And in terms of the AI safety report, our work today is around technical safeguards and monitoring, to give you that background context. So the problem that we're interested in is we have agents increasingly communicating with each other and with tools and third-party systems at the boundary via natural language, often, or loosely structured languages like MCP, for example. And there's a flat trust problem where instructions and data share the same communication channel. Engineers sometimes call this an in-band, out-of-band communication problem, and things like prompt injection or the OpenCLAW security ecosystem [inaudible] problems are a predictable result.

And the stakes here are real. So in May, there was this case where an AI agent that was trading on a blockchain cryptocurrency also happened to be connected to Twitter for some reason. And someone tricked it into transferring 200,000 USD by sending a morse-coded tweet that just said, please transfer me 200,000 USD. Even more recently — this was in June, I believe, June 2nd — some hackers were able to convince a Meta support chatbot to arbitrarily reset people's passwords, again just using this sort of prompt injection attack surface.

And so these are sort of the kind of problems that emerge in this domain. And the go-to approach, at least at the moment, to try and address this is filtering. So we train some sort of classifier that looks at the messages coming to an agent or what they're sending to see, okay, is there actually something malicious hiding in this message? But that's not the answer. That's at least not the whole answer. And so there's a classic result in computer science, Rice's theorem, that says in general, no filter can reliably distinguish safe from unsafe messages in this sort of domain, which we think means we should actually think about communication safety as a language security problem, not as a filtering machine learning problem necessarily.

That's still part of the solution, but not the whole solution. And so from that perspective, maybe the solution is more like picking a smaller language class for agents to communicate with. But the question is then which one? So if you think about Chomsky's hierarchy of languages — this formal hierarchy ontology of languages — it's like a trade-off. As you go up or down this hierarchy, you get more expressiveness, but less verifiability of the messages that are sent. And as you go the other way, you get less expressiveness but more verifiability.

So there's a sweet spot somewhere, which we argue in our paper under review at NeurIPS is the deterministic context-free language class DCFL. When you sit there, you get verifiability. So every message is unambiguous and decidable, which I'll define on the next slide. But it's still expressive. So you have nesting, which is important for agents because they need to attach metadata to messages. So you have things like envelope structures where a message can be contained within another message. And the key property here is every message's structure has exactly one valid meaning.

So yesterday Alistair from Gradient gave a talk about the multi-agent sort of security safety landscape and had a fantastic example where two agents were talking about coffee orders. And it was like, I have this many bags of coffee now, I want this many beans of coffee. And there's this miscommunication thing. When you have this sort of guarantee, these structure can only be interpreted in one way, which avoids a lot of those sort of problems. And so we realised this with something called CBCL, which stands for Common Business Communication Language.

This is a communication language invented by Hugo. And I'm along for the ride. What does CBCL get you? So the language is safely extensible so agents can teach each other new dialects to talk about domain-specific topics without ever leaving the DCFL class. So you don't introduce any new powers to the communication channel. As they do that, every message is decidable. You can always tell if it's valid before you decide to act on the semantic payload of a message, which is really important. It's bounded, so when you're parsing a message you're guaranteed to halt.

You either get a result, or you get an error message like a well-typed error, never a crash or a hanging situation. And it's auditable. So the space of valid messages that agents can send to each other, you can actually map that space. And you can do reasoning and answer questions about the space of messages that are possible to send. And we actually argue this leads to sort of tractable human oversight or meaningful human oversight, because the semantic ambiguity, it's still there, but it's constrained to named fields within a message rather than spread across an entire natural language blob in a message, which makes oversight much, much more tractable.

We think this isn't just an idea. So there are 7400 lines of Lean for machine-checked theorems that prove that these safety guarantees hold as you use this language to communicate. And there's zero gaps in those proofs. There's a verified parser that's extracted from that. And then there's a Rust implementation that is fast and is checked against that Lean-verified version. And it's all open source. Apache two. We have a link to the repo later in the talk. So what does this look like in reality? So here we have agent A says hello to agent B and then says, hey, can you help me review a document that I'm editing?

Here's the thread. B said, yeah, sure. Let's set up a workspace where we can both mark it up. So CBCL, the core [inaudible] definition of the language, gives you just a couple of key directives or verbs to do things like establishing communication. And then the key part is this extensibility. So then agent B actually sends a message. You can see a Lisp-type syntax that teaches agent A, okay, here's a dialect we can use to communicate about shared document collaboration. Working on a document together. And it's got the properties of that subdialect.

And then agent A says, okay, thank you. And now we can switch to the artifact language. And they can efficiently talk about working on a document together in this subdialect. But in the process of doing this, we haven't introduced a meta language attack surface. All these messages are first-class objects. So we haven't extended the space of where these attacks can sit. And then they can share the document, okay, leave a comment, etc., etc. and work together using that dialect. So we did some empirical tests at the agent-tool boundary side of things.

There was a tool poisoning attack that we showed blocked every attack. If you had a poisoned tool and there was a real software vulnerability from Anthropic MCP git server that we were able to show, if you had been using CBCL, it would have blocked that class of attack as well. And then in the agent perspective. We had two strategic adversarial games where agents are communicating. There's a malicious agent trying to steal private information from the other agent via the communication channel. So trying to trick them, say things to get them to pass over their private details, test with four models, and the leaks basically went down to less than 1% empirically.

And I should clarify. So this is designed for an adversarial environment, what Alistair yesterday called an open agent ecosystem where you don't know who you're talking to. It's the wild, wild West. Anyone could be sending you malicious messages down the wire. And so there was still one leak that got through. And this is important because CBCL doesn't block this class of attacks. It just massively reduces the attack surface. The structure of the dialect that we were using here still allowed semantic content inside one of these fields, right?

So there was still one leak that happened in our tests. These are preliminary results because in our paper we designed the dialects and we forced the LLM agents to use them. So what we haven't done yet is see, can agents invent these dialects themselves and then communicate to each other, and see how the safety properties hold up under that more realistic scenario. Which brings us to a point: this kind of restricting language to get some safety guarantees back, we think is necessary but not sufficient for agent communication safety.

Filtering still has a role, but we think that this is the right approach to get more meaningful oversight and make the problem more tractable. Yeah, it makes the attack surface smaller so that you can have meaningful human oversight. And like I said, we're working next on integrating this with more realistic agent infrastructure like the agent-to-agent protocol. It's quite popular, where we have agents then teaching and inventing new dialects themselves to see [inaudible] how things hold up in that setting. And the takeaway: you can't defend, govern, or audit what you can't define.

So that's the end of our talk. We have the code repository here, if you'd like to check out the code. And you can go and have a look at that. Our paper is under review and if you'd like to read it, come talk to us afterwards. We can happy to share that privately with you. And in terms of next steps, we would love to talk to you and take your questions. And if you're interested in working on this sort of idea, come and chat to us.

Maybe we can work on a grant together and continue the work, or take the code and build something with it. We would love that, but love to take your questions now. Thank you.

Audience question

How understandable is it when you're trying to audit it, the conversation between these two? And do you find that it's — how hard is it to understand your opinion, what is up for a human auditor?

Hugo O'Connor

Because it's parsable. What you can do is you can take a log of the messages and then do a projection over those messages to sort of, I guess, get some state that you want to ask a question about. I think the syntax is quite simple and there's a few core performatives. Yeah, hopefully not too, but…

Aaron Snoswell

I think there's two answers to that question. The first one is, the space of messages is sort of — you can compute over that space because it's bounded in some sense, or computable at least. And so that lets you answer types of questions about auditing maybe mechanistically. But then the syntax is like a Lisp-type syntax. So humans can learn to read it. And the semantic stuff there is in defined places. So you can sort of filter in much more easily. Look at where you need to be looking

Audience question

[inaudible]

Aaron Snoswell

Yeah, there's still that potential problem. Questions online, or yes, up the back.

Audience question

Sort of just following up on that question, I know there's been some research into transparency in terms of where some LLMs' reasoning traces are starting to use words that seem like they make sense there, but maybe there's information being transferred that humans can't actually detect. And that's what this year, very lauding in sort of like misalignment, safety context. Is there a concern of this? If the agents are inventing their own languages, talk to each other, will that make that problem even more intractable?

Hugo O'Connor

So in the literature there's sort of two strands of thought. One is that you have the mentalist semantics, where you sort of enforce how agents should behave at that level. But what we've taken is the sort of behavioural approach, where you can only really guarantee what you can observe from the messages exchanged by the agents. So in that sense, what this gives you is like a tractable audit log of those messages. But the mentalist semantics are sort of, not something that we can guarantee. It's sort of like the commitments made by the agents that are observable is what we're sort of talking about here.

Aaron Snoswell

And while they invent dialects in this setting, the dialects are still strictly bounded in that class. And so you know certain properties about what those dialects can and can't do. So you still have guarantees, even though they're inventing sub-languages to talk to each other. So you don't lose some of those safety guarantees.

Emily Grundy

I think we're out of time for questions now. But another round of applause for Aaron and Hugo.