# FEDSTR (fdstr): Money-In AI-Out
A Decentralized Marketplace for Federated Learning and LLM Training on the
NOSTR Protocol

Konstantinos E. Nikolakakis
<EMAIL_ADDRESS>George Chantzialexiou
<EMAIL_ADDRESS>Dionysis Kalogerias
<EMAIL_ADDRESS>
###### Abstract

The NOSTR is a communication protocol for the social web, based on the w3c
websockets standard. Although it is still in its infancy, it is well known as
a social media protocol, thousands of trusted users and multiple user
interfaces, offering a unique experience and enormous capabilities. To name a
few, the NOSTR applications include but are not limited to direct messaging,
file sharing, audio/video streaming, collaborative writing, blogging and data
processing through distributed AI directories. In this work, we propose an
approach that builds upon the existing protocol structure with end goal a
decentralized marketplace for federated learning and LLM training. In this
proposed design there are two parties: on one side there are customers who
provide a dataset that they want to use for training an AI model. On the other
side, there are service providers, who receive (parts of) the dataset, train
the AI model, and for a payment as an exchange, they return the optimized AI
model. The decentralized and censorship resistant features of the NOSTR enable
the possibility of designing a fair and open marketplace for training AI
models and LLMs.

##  1 Introduction

The NOSTR (nstr) - Notes and Other Stuff Transmitted by Relays [1] is an open
protocol that enables censorship-resistant communication. In fact, it is
resilient and does not rely on any trusted central servers. The communication
over the NOSTR is tamperproof since it relies on cryptographic keys and
signatures. The first successful application of the NOSTR protocol is the
decentralized social media with at least $150000$ known trusted users [2]. The
NOSTR has several common structural properties with the competitive open
protocol Bluesky [3, 4]. Bluesky and the NOSTR both aim to solve the problem
of decentralized social media, under partial consistency trade-offs [5, 6, CAP
Theorem]. Herein, we focus on the NOSTR protocol because it is the most
flexible and safest of the protocols in terms of developer control and future
development.

In parallel with the NOSTR protocol development, distributed AI training has
attracted major attention the last few years, with the Language Model
breakthroughs leading the progress. By combining recent advanced tools and
breakthroughs from open communication protocols [1], bitcoin payments [7] and
distributed optimization algorithms [8], we propose a system design that
enables open marketplaces for training AI models. Specifically, the NOSTR has
already built-in protocol flow for payments through the lightning network [7],
as well as communication flows for a distributed data processing system, which
makes it the state of the art protocol for designing a decentralized market
for distributed computation and AI directories. Such a network system can
mitigate privacy issues, security risks and potentially minimize operational
costs of machine learning and language models training by leveraging the
structure and capabilities of the NOSTR protocol. We begin by discussing some
fundamental aspects of the NOSTR, and the core protocol application designed
specifically for the social web.

A prominent challenge for social web applications is that of designing
decentralized social networks through peer-to-peer architectures.
Additionally, web 3.0 and blockchain implementations will either fail to scale
or they will be highly centralized. Tokenized web 3.0 approaches introduce
unnecessarily highly counter-party economic risk. Although decentralized
payment systems require both blockchain and Proof-of-Work [9, 10] (or smart
contracts) for asynchronous distributed consensus under faulty processes, it
becomes more and more clear that other applications including decentralized
social media and marketplaces for computational resources work securely and
efficiently without blockchain or global consensus. In contrast, with peer-to-
peer networks, web 3.0 and blockchain applications, the NOSTR protocol works
efficiently as a social media protocol, because it does not require a majority
of nodes of the network to share a common database of the data history. As a
consequence, it is also economically efficient since it does not require any
form of tokens and it does not hide any counter party risk. In summary, the
NOSTR offers a censorship-resistance, open, public network structure, as a
well as a digital IDs (DIDs) solution through cryptography and a novel
protocol implementation [11].

At the core of the NOSTR, there are two main structural components: clients
and relays. For social media applications, users run clients to participate in
the network and interact/communicate with other users, through the user
interface of the client application. This includes, but it is not limited to
retrieving posts from other users, posting notes, accessing profiles of other
users, re-posts, likes or even sending payments through the lightning network
[7]. To guarantee uniqueness of identities, every user is identified by a
public key [12]. Ownership of each identity is guaranteed through a private
key that users generate locally [13]. Every post (or action) is signed by
using the private key and every client validates these signatures.

Users do not communicate directly with each other, but rather through relays
and relays interact with users only. Relays listen only and propagate
information. Although relays can not change the content (or action) of users,
they can possibly act independently (with any other user or relay) and refuse
to propagate pieces of information. The protocol is robust to such censorship
attempts, since anyone including users can run one or multiple relays and
users can choose an arbitrary set of relays to interact with. Also anyone can
run their own relay. Clients retrieve and publish data from relays of their
choice. As an example, assume that the User A "follows" a set S of Users, then
the client just queries selected relays for posts from the public key of all
users within the set S. That is, on startup a client queries data from all
relays it knows for all users it follows (for example, all updates from the
last day), then displays that data to the user chronologically. An event (user
action, for instance a post or a like) can contain any kind of structured
data, and clients choose how to display events (defined as any user generated
action) of certain kind, while relays can handle them seamlessly. Examples of
different kinds are simple note/post (kind $\\#1$), re-post (kind $\\#6$),
reaction (kind $\\#7$) [1]. The NOSTR protocol offers flexible structure of
messages through a customizable structure and different kind of events.

##  2 Related Work

The orchestration of middleware systems to distribute computational tasks over
wide-ranging networks marks a cornerstone in the evolution of distributed
computing. A pivotal advancement in this area has been the development of grid
computing. Emerging as a potent global cyber-infrastructure, grid computing is
engineered to bolster the forthcoming wave of e-Science applications. By
amalgamating large-scale, diverse, and distributed resources, it fosters a
cooperative model for the sharing of computational power and data storage on
an unprecedented scale. This cooperative paradigm paves the way for
unparalleled computational and data management capabilities, enabling the
execution of sophisticated scientific, engineering, and academic endeavors
previously beyond reach.

Within the diverse ecosystem of grid computing frameworks, centralized systems
such as Pegasus [14] and Triana[15] have emerged as paragons. Pegasus,
functioning as a workflow mapping engine, abstracts workflow execution from
its underlying infrastructure, facilitating the seamless amalgamation of
computational tasks across varied grid environments. This system is heralded
for its ability to streamline and optimize complex workflows with remarkable
efficiency. Conversely, Triana offers a dynamic platform for the composition
of applications, harnessing distributed resources through meticulous
integration and orchestration. These frameworks underscore the dynamic and
adaptable nature of grid computing, illustrating its capacity to tackle
complex challenges through the strategic leverage of distributed resources.

Concurrently, volunteer computing has established itself as an integral
component within the broader spectrum of grid systems. The Berkeley Open
Infrastructure for Network Computing (BOINC)[16] stands as a testament to this
model, capturing the essence of volunteer computing by mobilizing the latent
processing power of personal computers worldwide for scientific research
necessitating extensive computational resources. This model champions the
democratization of scientific inquiry, inviting public engagement while
significantly enhancing computational prowess without the need for equivalent
infrastructural investment.

The "BOINC: A Platform for Volunteer Computing" [17] discourse elucidates the
enduring success of the BOINC project, spotlighting its sustained operation
over the years as a beacon of collaborative scientific endeavor. This analysis
brings to the forefront the prohibitive costs and reliability concerns
associated with conventional cloud computing platforms, such as Amazon Web
Services (AWS), which, despite their widespread adoption, pose financial and
operational challenges for extensive, computation-intensive projects.
Furthermore, the discourse addresses the intrinsic challenge of maintaining a
robust volunteer base — a critical component for the sustenance of volunteer
computing frameworks. The fluctuating levels of engagement and the logistical
complexities of coordinating such a decentralized workforce underscore the
necessity for innovative solutions to bolster volunteer retention and
participation.

To address the lack of incentives and participation in volunteer computing,
reward based approaches have been introduced in prior works. For instance,
Gridcoin[18] is a proof-of-stake cryptocurrency that rewards participants for
contributing computational power to scientific research projects, notably
through the Berkeley Open Infrastructure for Network Computing (BOINC) and
Folding@Home. However, a proof-of-stake cryptocurrency may introduce several
technical issues, since the payment network requires a global synchronized
clock [10]. Such issues and significant outages become prominent in many non-
proof-of-work blockchain systems (for instance [19]).

While blockchain based approaches aim to provide innovative solutions to
incentivize contributions in distributed computing, such approaches differ
significantly from the NOSTR protocol. The NOSTR offers a broader set of
capabilities, extending beyond the computational resource sharing model to
include secure communications and permissionsless interaction between
customers and service providers. In contrast with volunteer computing and
proof-of-stake cryptocurency models, the decentralized protocol NOSTR
integrates bitcoin through the lightning network and a dedicated protocol flow
for payments. The NOSTR solves the user-to-user micro-payment problem,
incentivizes honest collaborative computation, enables the possibility of an
open market through instant, permissionless payments and presents a viable
solution to the challenge of volunteer maintenance. These together with the
secure and robust digital IDs implementation, make the NOSTR the state of the
art protocol, capable of supporting a wide range of decentralized applications
and services, offering a pathway to enhance viability, sustainability, and
effectiveness.

##  3 A Decentralized Marketplace for Distributed Computing

As the name of the protocol indicates (Notes and Other Stuff Transmitted by
Relays), the type of communication messages and user-to-user interactions are
not restricted to simple notes, and they support a variety of alternative
applications including direct messaging, file sharing, audio/video streaming,
collaborative writing, marketplaces for data processing and more [20]. Another
example is that of marketplaces for data processing, where users interact with
each other to execute AI algorithms. For the implementation of data processing
on the NOSTR protocol, dedicated event kinds have been developed to facilitate
distributed data processing (see [21, 22]). These implementations have been
considered for designing a decentralized AI-directories marketplace of the
form "Money-In Data-Out". For instance, a customer can provide some input
data, such as text or audio, and pay a service provider to receive a short
summary of the input data. More specifically, the kinds in range
$\\#5000-\\#5999$ [21] are reserved for text manipulation jobs including text
extraction, summarising text, text generation and translation. Image
generation corresponds to kind $\\#5100$, and video/audio manipulation
corresponds to kinds in range $\\#5200-\\#5299$.

In this work, we propose an extension of the protocol. Our goal is to design a
decentralized marketplace for federated learning and LLMs training. In a
nutshell, a customer provides a data-set, model specification and a required
payment to a set of service providers. Then the service providers execute the
model training, and they return the parameters of the model in order to
receive the payment for their work (Money-In AI-Out). In other words, we
propose a protocol flow for developing AI-Model Vending Machines (AI-VM),
where a customer provides a data-set, a set of specifications, and submits a
payment to a set of service providers to acquire a model trained on the input
data-set. There are several components of the protocol that allow us to build
upon existing protocol rules and design a decentralized marketplace. These
include Digital IDs, payments, fast communication though websockets, a
flexible protocol structure, also suitable for distributing computing. We
proceed by briefly explaining these features.

##  4 Signatures & Digital IDs

The NOSTR identity is a dual-key cryptographic system [13, 23, Schnorr
Signatures]. Each user profile is associated with a private (nsec) and a
public key (npub). These keys are generated locally without the need of a
trusted party. Cryptographic keys are essential to the protocol security,
ensuring the protection of user identities and messages. The private key is
used to sign messages and other actions by the user, verifying that they
originate from the authentic identity owner. On the other hand, the public key
is employed to authenticate these messages, confirming that they were signed
using the corresponding private key. Identically, to the social media
applications, the same DID, private and public keys can be used for
alternative applications, for instance private messaging applications, or
marketplaces. This allows for a consistent and secure way to authenticate
users DIDs and across different applications over the NOSTR protocol.

#### Nostr Digital Identity And Reputation:

Owing a well known DID or building a solid reputation over the NOSTR offers
the benefits of recognizability and trust from other users, similarly to all
other online media platforms. Notably, this identity and its accompanying
reputation can be seamlessly transferred between different applications. In
the context of a marketplace, a good reputation can help a service provider
maximize their profit. A high reputation indicates a consistent service, which
in turn makes more customers trust the service provider, ensuring a steady
stream of business. Alternatively, bad reputation may assist customers to
avoid incompetent service providers. As a matter of fact, a reputation system
for a decentralized and open marketplace for distributing computing will be
valuable. However, this remains out of the scope of this work, but it is an
interesting implementation possibility for future extensions of the protocol.

##  5 Protocol Design for Distributed Computing and AI Directories

The NOSTR protocol supports a primal version of AI directories for data
processing in the form of an open and decentralized marketplace [21, 22],
known as Data Vending Machines. On one side, there are users (customers) who
provide some data that should be processed (image, video or text) and they
request jobs that can be done with some AI tools, for instance image
generation from text, a transcript of a video, a summary of an article. On the
other side, there are AI agents (service providers) that offer their services
to users, and in exchange for a payment, they deliver the requested results in
the form of processed data. This system works in the form of Money-In Data-
out; a marketplace for data processing/manipulation by applying AI tools. This
design sets the foundations of distributed data processing over the NOSTR
protocol and offers a unique protocol structure and flow for additional
development.

Our goal is to utilize the existing architecture and to go one step further by
extending components of the protocol if necessary, in order to design a
decentralized marketplace for Federated Learning (FL) and Large Language
Models (LLM) training. In what we propose later (see Section 7), users
(customers) provide an input data-set and certain specifications and request a
sequence of jobs that aim to train a deep neural network or an LLM model. Then
service providers receive the data, model specifications and the requested
task (train through regular FL or LLM training (e.g., via the DiLoCo
algorithm) [8]), they train the model through multiple rounds and jobs
requests, and they return the model parameters. In exchange for their
computational resources, the service providers receive recurrent payments from
the customer upon delivering valid results. A main difference of our design in
comparison with existing approaches is the concept of delivering a trained
model instead of processed data; a set of service providers are required to
optimize the same model in parallel and deliver valid results through multiple
rounds of computation. For that purpose we extend the structure of protocol by
introducing new event kinds, a new protocol flow and we deploy the classical
FL approach, as well as the DiLoCo algorithm [8] for LLM training. Next, we
delve into the existing protocol structure for distributing computing over the
NOSTR network. We also emphasize the modifications we introduce to support the
Money-IN AI-Out marketplace design.

###  5.1  Distributed Computing on the NOSTR Protocol

Herein, we discuss the existing dedicated protocol messages and protocol flow
for distributed computing. We mainly focus on five components that we will
utilize later with slight extensions or variations, these include job request
events, job result events, job feedback events, events for service provider
discoverability and job chaining rules. These type of events consist the core
of the communication messages between customer and service providers. We refer
the reader to the NOSTR Implementation Possibility - 90 (NIP-90 [24]) for
further details.

#### Basic Protocol Flow for Data Vending Machines (DMVs) [24]

  * $\bullet$

Customer publishes a job request (e.g. kind:5000, speech-to-text).

  * $\bullet$

Service Providers may submit job-feedback events (kind:7000, e.g. payment-
required, processing, error, etc.).

  * $\bullet$

Upon completion, the service provider publishes the result of the job with a
job-result event (kind:6000).

  * $\bullet$

At any point, if there is an amount pending to be paid as instructed by the
service provider, the user can pay the included bolt11 invoice [25] of the job
result event that the service provider has sent to the user.

The above protocol is designed to be deliberately ambiguous. For instance a
customer may choose a set of service providers and restrict or not restrict
the job request to be completed by this specific set of service providers.
Also, a service provider may not start a job until they receive a form of
payment, or their response can depend on the other participants reputation
based on their public key. The flexibility of the protocol flow allows us to
extend parts of it, and implement additional communication steps for the
design of on demand LLMs training over a decentralized marketplace. Next we
proceed by presenting the existing events as appear in the protocol flow for
DMVs.

#### Job Request (DVMs)

A Job Request for Data Vending Mchines is an event, published by a customer
through a set of relays. This event signals that a customer is interested in
receiving the result of some kind of computation by an AI tool. The reserved
range for job request events is $\\#5000-\\#5999$. The field with label
"content" is empty, while, all the required information should be provided in
the field with label "tags". The field "tags" contains all the required
information from an AI-agent in order to process the data.  ⬇ {  "kind": 5xxx
// kind in range 5000 - 5999, "content": "", "tags": $\big{[}$
$\big{[}\text{"i", " <data> ", "<input-type>, "<relay>", "<marker>"}\big{]}$,
$\big{[}\text{"output", "<mime-type>"}\big{]}$,  $\big{[}\text{"relays",
"wss://..."}\big{]}$,  $\big{[}\text{"bid", "<msat-amount>"}\big{]}$,
$\big{[}\text{"t", "bitcoin"}\big{]}$ $\big{]}$ }  Event Type 1: Job Request
Event with kind in range 5000 -5999 For completeness, we provide additional
explanation regarding each tag of the events. We first present the existing
events structure. Then we introduce any necessary changes or additions that we
will consider in the protocol flow and in the algorithm. For the Job Request
event (Event Type 1) there are the following tags: <i>: All the required input
data for the job appear here. Specifically, the inputs of the AI algorithm.
<data>: The argument for the input. <input-type>: The type of the argument
input, it must be one of the following: url: A URL to be fetched of the data
that should be processed. event: A Nostr event ID. job: The output of a
previous job with the specified event ID. The determination of which output to
build upon is up to the service provider to decide (e.g. waiting for a
signaling from the customer, waiting for a payment, etc.) text: <data> is the
value of the input, no resolution is needed <relay>: The relay where the
event/job was published <marker>: An optional field indicating how this input
should be used within the context of the job <output>: Expected output format.
<param>: Optional parameters for the job. Different job request kind defines
this more precisely. (e.g. [ "task", "run option", "initial state" ]). <bid>:
Customer MAY specify a maximum amount (in millisats) they are willing to pay
<relays>: List of relays where Service Providers SHOULD publish responses to.
p: Service providers the customer is interested in. Other service providers
might still choose to process the job.

#### Job Request (AI VMs)

The existing job request events include a large number of different jobs,
dedicated to data processing applications. Such job request have a certain
structure (see Event Type 1). For clarity and for efficacy of our approach, we
propose to introduce the kinds 8000 - 8999 as Job Request events for federated
learning, LLM training and distributed optimization. Although, each kind can
correspond at a different algorithm or variation of an algorithm, specific
details can be considered by introducing additional fields in the tags. As an
example, notice that the predefined structure of Event Type 1, requires a
single input data type as we discussed earlier, while additional information
may be included in parameters field (<param>). ⬇ {  "kind": 8xxx // kind in
range $8000 - 8999$, "content": "", "tags": $\big{[}$ $\big{[}\text{"i",
"<data>", "<input-type>, "<relay>", "<marker>"}\big{]}$,
$\big{[}\text{"output", "<model-parameters-type>",}\big{]}$,
$\big{[}\text{"relays", "wss://..."}\big{]}$,  $\big{[}\text{"bid", "<msat-
amount>"}\big{]}$,  $\big{[}\text{"t", "bitcoin"}\big{]}$ $\big{[}\text{"p",
"<service-provider(s)-public-key(s)>"}\big{]}$ $\big{[}\text{"param",
\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}"task",
"Inner-or-Outer"}\big{]}$,  $\big{[}\text{"param",
\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}"run option",
"Fevavg-or-DiLoCo"}\big{]}$ $\big{[}\text{"param",
\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}"data\\_set",
"<URL>"}\big{]}$,  $\big{[}\text{"param",
\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}"initial/current-
model-state", "<raw-data>"}\big{]}$ $\big{[}\text{"param",
\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}"model",
"LLaMA-2"}\big{]}$,  $\big{[}\text{"param",
\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}"source\\_code",
"<URL>"}\big{]}$,  $\big{[}\text{"param",
\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}"expected\\_execution\\_time",
"<time>"}\big{]}$,  $\big{[}\text{"param",
\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}"recommended\\_hardware\\_specification",
"<text>"}\big{]}$,  $\big{[}\text{"param",
\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}"validation\\_rules\\_for\\_the\\_output",
"<URL>"}\big{]}$ $\big{[}\text{"param",
\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}"time-out-
specification", "max-time>"}\big{]}$ $\big{]}$ }  Event Type 2: Job Request
Event for training AI models, kind in range 8000 -8999 Similarly, for the
purpose of training an LLM, the customer needs to provide a training data-set
though a URL as input data, and additionally a set of parameters related to
the training task, for instance initial model parameters, a URL to the source
code of the training or optimization method, model specification (example
"LLaMA-2"), rules for validation of the output. To maintain the existing
protocol flow as much as possible, we consider the input data as a URL to the
training dataset for the initial job request, or the output of a previous job
with a specified event job id to declare a job chaining and multiple rounds of
training. In both cases (initial or chain job request), we consider all the
required information for executing algorithm in the parameters fields for
consistency. Below some pieces of that information follow (Event Type 2):
$\bullet$ a source for the code: While the service provider may have its own
code, there should be reference to a standard approach that guarantees
consistency $\bullet$ a source for the data: The customer splits and sends an
encrypted URL to the service providers. The customer decides how to split the
data. The way of splitting the data may be arbitrary. $\bullet$ job details:
expected execution type or hardware that is needed, rules related to time-out
conditions. $\bullet$ Declaration of validation process. This is how the
customer will decide if the output is accurate or not. Through the
optimization process we introduce a new job request at each round. We also
consider job chaining to speed up the process and most likely to execute the
training by assigning the jobs to the same service providers, as long as they
provide valid outputs. A running job will be assigned to new service provider,
if a previous service provider goes offline, or fails to provide valid result.
Finally, the customer has the option to encrypt all the parameters, and only
the selected service provider(s) in the tag "p" will be able to decrypt them.
We proceed by briefly discussing the Job Chaining rules, for a detailed
description we refer the reader to [24, (NIP-90)].

#### Job Chaining

A Customer has the option to request multiple rounds of jobs to be processed
as a chain, where the output of a job is the input of another job. In the
context of data processing and DMVs this can be a sequence of processing as a
podcast transcription by one service provider and then extracting a summary of
the transcription by another. One way to implement this is by specifying as
input an event id of a different job with the job type. In general, service
providers may begin processing a subsequent job the moment they see the prior
job result, but they will likely wait to receive a (partial) payment first. In
the case of federated learning and LLM training such options still exist,
however we propose certain protocol rules to minimize the risk introduced by
bad actors and malicious users. To do this, we consider necessary for the
customer to validate the progress made by each service provider at every
single round. After the validation is completed, each service provider who
produced successful results receives a partial payment for the work done in
the corresponding round. Then the customer updates the current state of model
and submits a follow-up job request for the next round (and optionally a
partial payment to the service providers upfront). Upon completion of the
optimization task at each round, the service providers communicate with the
customer through a Job Result event.

#### Job Result (kind: 6000-6999)

Service providers communicate with the customer through Job Result events, by
providing the (optionally) encrypted output of the job. In the case of AI
training, the output corresponds to an optimized version of the model
parameters. The format of the Job Result event appears in the Event Type 3
above. The tag of the Job Result event include the original job request event
id (stringified-JSON), the public key of the customer, amount that the Service
Provider is requesting to be paid or an lightning invoice (bolt11 [25, 26]),
and the optimized model parameter as an encrypted output. Finally, a tag "i"
may be considered for additional information related to the initial job
request or for validation of the output by the customer.  ⬇ {  "pubkey":
"<service-procider pubkey>", "content": "<enctypted payload>", "kind": 6xxx //
kind in range 6000 - 6999, "tags": $\big{[}$ $\big{[}\text{"request", " <job-
request> "}\big{]}$,  $\big{[}\text{"e", "<job-request-id>", "<relay-
hint>"}\big{]}$,  $\big{[}\text{"p", "<customers's-pubkey>"}\big{]}$,
$\big{[}\text{"amount", "requested-payment-amount", "<optional-
bolt11>"}\big{]}$,  $\big{[}\text{"i", "additional-information-for-
validation", "<information>"}\big{]}$ $\big{[}\text{"output", "encrypted:
\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0} model
parameters (and loss for validation purposes)"}\big{]}$ $\big{]},$ …  }  Event
Type 3: Job Result Event

#### Job Feedback (kind:7000)

During the model training process, service providers can communicate and
provide feedback for an ongoing job through the Job Feedback event. The Job
Feedback events may be considered in order to avoid time-outs and ensure that
a service provider has achieved some partial progress. Information about
partial progress can be optionally included by introducing additional fields
in the tags of the event format in the Event Type 4.  ⬇ {  "kind": 7000,
"content": "<empty-or-payload>", "tags": $\big{[}$ $\big{[}\text{"status", "
<status> ", "<extra-info>"}\big{]}$,  $\big{[}\text{"amount", "<requested-
payment-amount>", "<bolt11>"}\big{]}$,  $\big{[}\text{"e", "job-request-id",
"<relay-hint>"}\big{]}$,  $\big{[}\text{"p", "<customer's-pubkey>"}\big{]}$,
$\big{]},$ …  }  Event Type 4: Job Feedback Event The predefined format of the
Job Feedback event includes the following tags [24]: <content>: It may be
empty, a final job-result or a partial-result (for a job in progress). This
field will have an encrypted payload with p tag as key. <amount>: Requested
payment amount. <status>: The service provider publishes the current status of
the requested job. For instance: payment-required: Service Provider requires
payment before continuing. processing: Service Provider is processing the job.
error: Service Provider was unable to process the job. success: Service
Provider successfully processed the job. partial: Service Provider partially
processed the job. The content filed might include a sample of the partial
results.

#### Discoverability

Service Providers have the option to announce availability or to advertise
their support for specific job kinds by publishing discoverability events [27,
(NIP-89)]. The format structure of the discoverability event appears in the
Event Type 5. By including a field tag "i", service providers may provide
additional information related to their available computational capabilities,
hardware specification or execution time limits.  ⬇ {  "kind": 31990,
"pubkey": "<pubkey>", "content": [ \"name\": "Federated Learning AI-VM" ,
\"about\": "I’m a AI-VM for federated learning." ] ,  "tags": $\big{[}$
$\big{[}\text{"k", "8000"}\big{]},\text{ // e.g. optimization methods,
federated learning}$ $\big{[}\text{"t", "bitcoin"}\big{]}$ $\big{[}\text{"i",
"specifications", "hardware", "maximum-execution-time", "model-dimensions-
range"}\big{]}$ $\big{]},$ …  }  Event Type 5: Discoverability Event

##  6 Payments

The NOSTR protocol has an integrated protocol flow for payments; requests for
payment, invoice notifications, receipts for payments, as well as payments to
certain events or directly to a user or a group of users. The payments take
place through the lightning network [7] . For any form of application
including social media, Internet-of-Things applications [28] and marketplaces
[29], the lightning network enables bitcoin payments with instant settlement
and virtually zero transaction fee. These properties together with in-channel
messages are ideal for reliable handshaking mechanisms, anti-spam and on the
fly payments between multiple job rounds among devices. To further explain how
the payments blend in with the rest of the protocol we proceed with an
example. In the case of federated learning the aggregator itself may act as a
customer who pays service providers to optimize a model on different subsets
of a training data-set through multiple job rounds. Initially, the customer
(aggregator) identifies possible service providers through the discoverability
event (kind 31990, event type 5), selects a number of them and submits a Job
Request event (kind $\\#8000$, event type 2). The service providers respond
with a Job Feedback event (kind $\\#7000$, event type 4) with status payment-
required, to announce that they are available to complete the job. Then the
customer proceeds by submitting a small amount (of the total) as a payment and
the service provider starts the job. Upon delivery of the final or partial
output result (Job Result 3 & Job Feedback 4), the customer proceeds with a
partial or total payment. This process repeats for each optimization round and
for all service providers (assuming that they provide valid results). The
ability to break down the payments into partial amounts and pay upon delivery
of a valid result significantly minimizes the chance of stealing funds without
completing the requested task. This strategy together with a reputation system
can make the marketplace robust against adversarial or spam attacks up to a
large extend. However, an in depth implementation of such sophisticated
strategies remains out of the scope of this work. We discuss strategies for
validation of the delivered output in Section 7.1.

###  6.1 Payments Implementation

Herein, we discuss the payment system which is integrated into the NOSTR
protocol. We indicatively explain three components of the payment system;
Payment Request, Payment Receipts and Validation of Receipts. For detailed
documentation of the payment protocol flow, we refer the reader to
implementation 57 [30, 31].

#### Payment Request

A payment (known as zap) request is an event of kind 9734 that is not
published to relays, but is instead sent to a lnurl pay callback url [32] of
the recipient. The field content may be an optional message to send along with
the payment. The event must include the following tags: $\bullet$ Relays is a
list of relays for the wallet of the recipient to publish its payment (zap)
receipt to. $\bullet$ Amount is the amount in millisats the sender intends to
pay, formatted as a string. $\bullet$ Lnurl is the lnurl pay url of the
recipient, encoded using bech32 [25] with the prefix lnurl. $\bullet$ p is the
hex-encoded pubkey of the recipient. $\bullet$ e is an optional hex-encoded
event id. Implementations must include this while paying an event rather than
a public key. ⬇ {  "kind": 9734, "content": "Zap!", "tags": $\big{[}$
$\big{[}$"relays", "<wss://relay-domain>", "wss://anotherrelay.com"$\big{]}$,
$\big{[}$"amount", "<msats-amount>"$\big{]}$,  $\big{[}$"lnurl", "<a-static-
lightning-invoice>"$\big{]}$,  $\big{[}$"p", "<hex-encoded-pubkey-of-the-
recipient>"$\big{]}$,  $\big{[}$"e", "<optional-hex-encoded-event-
ID>"$\big{]}$ $\big{]}$,  "pubkey": "<NPUB>", "created_at": <timestamp>, "id":
"<event-ID>", "sig": "<signature>" }  Event Type 6: Payment Request Event

#### Payment Receipt

A payment receipt is created by a lightning node when an invoice generated by
a payment request is paid. Payment receipts are only created when the invoice
description (committed to the description hash) contains a payment request
note. When receiving a payment, a series of steps are executed and a NOSTR
event of kind 9735 (as appears below; Event Type 7) should be published to the
relays declared in the payment request. We refer the reader to the detailed
documentation [30] for a complete description of the Payment Receipt event
structure and the full protocol flow. ⬇ {  "id": "<event-ID>", "pubkey":
"<NPUB>", "created_at": <paid-at-date>, "kind": 9735, "tags": $\big{[}$
$\big{[}$"p", "<payment-recipient)>"$\big{]}$,  $\big{[}$"P", "<optional-P-
tag-from-the-pubkey-of-the-payment-request>"$\big{]}$,  $\big{[}$"e",
"<optional-tag-same-as-payment-request-e-tag>"$\big{]}$,  $\big{[}$"bolt11",
"<lightning-invoice>"$\big{]}$,  $\big{[}$"description",
"<SHA256(description)-from-invoice>"$\big{]}$,  $\big{[}$"preimage",
"<payment-preimage>"$\big{]}$ ],  "content": "", }  Event Type 7: Payment
Receipt Event

#### Receipt Validation

The service provider can retrieve payment receipts using a NIP-$01$ filter
[33] and validate each receipt to verify that a customer fetched their invoice
and claims payment submission for a certain job. Payments are validated by
using the following steps: $\bullet$ The public key in the payment receipt
event must be the same as the public key of the service provider. $\bullet$
The invoice Amount contained in the bolt11 tag of the payment receipt must be
equal to the amount tag of the payment request. $\bullet$ The lnurl tag of the
payment request should be equal the lnurl of the recipient. We highlight the
fact that a receipt is not a proof of payment, and it only proves that some
NOSTR user fetched an invoice. As a final step of payment validation, the
recipient must verify the payment on their lightning node or payment
processor.

##  7 Money-In AI-Out: Marketplace for Federated Learning and LLMs

Herein, we introduce the protocol flow and algorithmic design for federated
learning and LLMs training over the NOSTR protocol. By leveraging the existing
structure of the protocol for data processing, and by introducing additional
components when it is necessary, we construct an open and decentralized
marketplace for training AI models. In this market, a user (customer) provides
a dataset, model specifications, the service providers (AI Vending Machines)
receive a payment, and they return an AI model trained on this dataset.
Customers and service providers communicate through relays, which can be
public or private (and self hosted). Also, the communication can be
implemented with encrypted information to guarantee privacy for the dataset or
for the output of the computation. We proceed by explaining further the
protocol flow and then we present a detailed algorithmic implementation for
customers and service providers. We propose a protocol flow that involves
multiple job rounds between the customer and service providers. Through
multiple job rounds we ensure that there is a valid progress in the
optimization process by each of the service providers individually. This
allows to consider on the fly payments after validation of the output at each
round. If the service providers give an invalid output or if they delay the
job beyond a certain amount of time, then the customer proceeds to reassign
the job to another service provider without paying for the invalid (or
delayed) job output. In this work we consider two training methods: the
classical federated learning [34, FEDAVG] and DiLoCo algorithm [8] for
training LLMs. Both of these have an inner and outer optimization part. This
allows us to present our approach in parallel. Specifically, we define the job
round as the sequence of the following successful publication of events and
actions; for the first part (inner optimization): job request, inner
optimization computation executed by the service providers, retrieval of the
outputs from inner optimization routines by the customer through job result
events, validation of the output result. For the second part (Outer
optimization): use the latest inner optimization outputs as inputs and execute
the outer optimization (through a job request, if needed or locally directly
executed by the customer), complete any pending payments and update the model
parameters for the next round (if any). Upon validation of the outputs a
(partial) payment is submitted by the customer to each of the service
providers. To explain this further we provide the sequence of the steps below.

#### Protocol Flow.

At every job round: Customer (Algorithm 1) publishes a job request (e.g.
kind:8000, Federated Learning, inner optimization). The job request may
include a list of chosen service providers, and it must include all the
required information: the current state of the model (for instance for the
first round initial value of model parameters), a link (source) to the data,
list of relays where the service providers should publish their job results
job feedback at, as well as all the required parameters (see Event Type 2).
Service Providers (Algorithm 4) must submit job-feedback events (kind:7000,
e.g. partial payment-required) before they start the job with STATUS =
payment_required, if they wish a (partial) payment before starting computation
(Event Type 4). This requests a partial payment and signals that a service
provider is available to start upon receiving the payment. Customer submits a
initial payment to service providers (responsible for inner optimization).
Upon receiving the partial payment the service providers start executing the
inner optimization job (Algorithm 5). Within a fixed time period service
providers publish Job Feedback events (Event Type 4) with partial/sample
result. If results delivery exceeds a predefined time limit, then customer
stops the procedure and seeks for other service providers (responsible for
inner optimization). Upon completion, each service provider publishes the
output of the job through a Job Result event (kind:6000) (Event Type 3).
Customer validates the results/ouputs (Algorithm 3) If the result/ouput is
valid then the customer completes the payments to all service providers
(responsible for inner optimization) with valid output. If the result is not
valid then reassigns the job to a different service provider (Algorithm 2).
With successful outputs for all inner optimization jobs: The customer proceeds
to the outer optimization (Algorithm 6). If the customer selects to execute
the outer optimization locally, then the customer executes the outer
optimization (Algorithm 6) with input the output of inner optimization
procedures. Else if the customer selects to assign the task to a service
provider for the outer optimization, then the customer follows the steps of
reassigning the job from SELF to a service provider (Algorithm 2), retrieving
and validating the output, and completing any payments identically to the
inner optimization job handling as was described above. At the end of each
round the customer updates the model parameters to use them as input for the
next round. If the current round is the terminal round then the customer
completes any pending payments and ends the procedure with output the final
result. At any point, if there is an amount pending to be paid as instructed
by the service provider, the customer can pay the lightning-invoice [25, 26,
bolt11] (see lnurl Event Type 6). We present an implementation of the protocol
flow in Section 7.1 and Section 7.2.

###  7.1 Customer

A complete implementation of the customer routine appears in Algorithm 1. This
includes the steps that the customer follows and the events that the customer
publishes. First, the customer discovers and requests a set of service
providers to run inner optimization part of the job to as we explained in the
protocol flow above. Upon successful delivery of outputs, the customer
proceeds to the outer optimization. The outer optimization for both FedAvg and
DiLoCo is a single or double update of local variables respectively. However
we consider the option for the customer to also assign this computation step
to a service provider. This can be useful in practice if someone prefers to
implement an outer optimizer with higher computational complexity (for
instance multiple iterations) and the customer is not able to perform such
computations locally. We proceed by explaining further three parts of the main
customer routine: how the customer handles disconnections and failures of a
service provider to respond (Algorithm 1), how the customer validates the
output results given by a service provider at job completion (Algorithm 3),
and how the customer reassigns a job to a different service provider if needed
(Algorithm 2).

#### Handling Disconnections and Failures to Respond.

The customer may consider a time-out period. If a service provider did not
provide the output within a certain time window (from the time point of
receiving the initialization payment), then the customer proceeds to reassign
the job to a different service provider (Algorithm 2). As an example of the
time-out implementation see Algorithm 1 (lines 13-14). All the information
regarding the time-out rules should be included in the Job Request event
(Event Type 2). The definition of failure to respond may vary from one
implementation to another. As an example, the customer may choose to receive a
valid output within a certain time period. Alternatively the time-out decision
may depend on the periodic responses by the service provider through Job
Feedback events (Event Type 4), that notify the customer about the status of
the job and provide partial results of the computation.

#### Validation of the Output (Algorithm 3).

Upon receiving a Job Result event (Event Type 3) the customer proceeds to
verify the accuracy of the output. In the context of training AI models with
FEDAVG and DiLoCl, we consider two conditions that test the decay of the loss
on a validation dataset. Specifically, Algorithm 3 requires as input the
validation dataset, the current state of the model (model parameters), and a
threshold for the two following policies. As a first option, we compare the
loss decay progress relative to other service providers (see accuracy against
service providers, Algorithm 3). This validation test has been introduced in
[35, Accuracy Checking]. As a second option, we consider a test that checks if
a moving average of loss decays with a certain rate (Algorithm 3). Alternative
accuracy tests and approaches to identify malicious service providers appear
in prior works [36, 35, 37, 38]. Such implementations may be considered in
parallel with our design but remain out of the scope of this work. Algorithm 1
Customer 1:C_NPUB: Customer’s NOSTR public key, DATA_SOURCE: link to the data,
NUM_PR: # of providers, NUM_JOBS : Total # of jobs for each provider, RELAYS:
a set of relays  2:Connection through websockets to all relays in RELAYS
$\triangleright$ Where events are published at 3:Search Routine: Search for
NUM_PR AVAILABLE service providers. $\triangleright$ Event Type 5 4:Search
Routine returns: PROVIDERS with NUM_PR NPUBs entries  5:Split the data to
NUM_PR parts and generate the list DATA_SOURCES with NUM_PR sources to each
data segment $\triangleright$ DATA_SOURCES$(i)$ is the data source of the
$i_{\text{th}}$ provider  6:Initialize the optimization parameters and model:
model_parameters, model, …  7:Publish Job Requests KIND: 8000 with all the
required information $\triangleright$ Event Type 2 8:Wait for Job Feedback
KIND: 7000 and payment-request from service providers $\triangleright$ Event
Type 4 9:Submit an initialization payment to PROVIDERS 10:for job in
(1,NUM_JOBS) do 11: Initialize done $\leftarrow$ FALSE  12: while done $\neq$
TRUE do 13: Wait some time  14: Fetch Job Feedback events (KIND:7000) from
each provider in PROVIDERS 15: if Time-out occurs then 16: Call Reassign
(Algorithm 2) to replace all the delayed service providers, update PROVIDERS
17: if JOB_STATUS = success for all providers in PROVIDERS then done = TRUE
18: Fetch Job Results (KIND: 6000) and "outputs" from all providers in
PROVIDERS $\triangleright$ Event Type 3 19: for service_provider in PROVIDERS
call the Validation routine (Algorithm 3) and do 20: while Validation_Test =
FAIL for the service_provider do 21: Reassign the job of service_provider;
call Reassign (Algorithm 2), update PROVIDERS 22: Submit (partial) payments to
service_provider and publish Payment Receipt (KIND: 9735) 23: if
OUTER_OPTIMIZER $=$ SELF then 24: Run the Outer_Optimization routine
(Algorithm 6) with input the current updates "outputs" 25: else 26: Reassign
the Outer Optimization from SELF to a service provider (Algorithm 2)  27:
Submit (partial) payment to OUTER_OPTIMIZER and publish Payment Receipt (KIND:
9735) 28: Update model_parameters using the "output" of the OUTER_OPTIMIZER
29: if stopping condition is satisfied then 30: break  31: else if job $\leq$
NUM_JOBS then 32: Publish Job Requests KIND: 8000 with all the required
information $\triangleright$ Event Type 2 33:Finalize payments to every
service_provider in PROVIDERS and publish receipts $\triangleright$ Event Type
7 34:return model_parameters

#### Reassigning the Job to a Different Service Provider (Algorithm 2).

Under a time-out or a failed validation instance, the customer reassigns the
job to a different service provider. We provide an example of such
implementation in Algorithm 2. Further, under perpetual time-outs and invalid
output detection, the customer continues to reassign the job, until a service
provider delivers a valid output. Then the routine returns the public key of
new service provider and the customer updates the list of the service
providers under consideration. Algorithm 2 Reassign the job of a Service
Provider to a different Service Provider 1:SP_NPUB: public key of the service
provider that will be be replaced, <computation information & time>,
RUN_OPTION: <FEDAVG or DiLoCo>, DATA: DATA_SOURCES , PROVIDERS, TASK: <INNER
or OUTER> 2:Connection through websockets to all relays in RELAYS
$\triangleright$ Where events are published at 3:Search Routine: Search for an
AVAILABLE service provider for KIND: 8000. $\triangleright$ Event Type 5
4:Search Routine returns: A single public key: SP_NPUB_NEW 5:Publish a Job
Request KIND: 8000: Identical to the last job request for the service provider
SP_NPUB, but with updated field "p" to SP_NPUB_NEW $\triangleright$ Event Type
2 6:Wait for Job Feedback KIND: 7000 and payment-request from service provider
SP_NPUB_NEW 7:Submit an initialization payment to SP_NPUB_NEW 8:while
JOB_STATUS $\neq$ success for SP_NPUB_NEW do 9: Wait some time  10: Fetch Job
Feedback events (KIND:7000) from service provider SP_NPUB_NEW $\triangleright$
Event Type 4 11: if time-out occurs then break and Reassign again to replace
SP_NPUB_NEW 12: if JOB_STATUS = success for SP_NPUB_NEW then 13: Fetch Job
Result (KIND: 6000) and "output" from SP_NPUB_NEW $\triangleright$ Event Type
3 14: Call the Validation Routine  15: if Validation_Test = PASS then 16:
return SP_NPUB_NEW, "output"  17: else if Validation_Test = FAIL then break
and Reassign again to replace SP_NPUB_NEW Algorithm 3 Validation of the
Service Provider Output 1:SP_NPUB: service provider public key, RUN_OPTION:
<FEDAVG or DiLoCo>, validation-dataset: $\mathcal{D}_{\text{test}}$,
model_parameters: $\theta_{\text{global}}$, the last "outputs" of the Inner
Optimization jobs: $\theta_{\text{Inner}}$ and the increments
$\Delta\theta_{\text{Inner}}$, policy thresholds: $\gamma_{t},\beta_{t}$,
TEST_TYPE 2:A history of model parameters is available. (TEST_TYPE = "B"
requires the previous $\tau_{c}$ model parameters for test condition)  3:if
TEST_TYPE = "A" then $\triangleright$ Check accuracy against other service
providers [35] 4:
$\tilde{\theta}\leftarrow\theta_{\text{global}}+\Delta\theta^{{\color[rgb]{0.0,0.0,0.4}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.0,0.4}\text{SP\\_NPUB}}}_{\text{Inner}}\
$ 5:
$\tilde{\theta}_{G\setminus\text{{\color[rgb]{0.0,0.0,0.4}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.0,0.4}SP\\_NPUB}}}\leftarrow\theta_{\text{global}}+\sum_{\text{npub}\in\text{{\color[rgb]{0.0,0.0,0.4}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.0,0.4}PROVIDERS}}}\Delta\theta^{\text{npub}}_{\text{Inner}}\
$ 6: if
$\sum_{z\in\mathcal{D}_{\text{test}}}\ell(\tilde{\theta},z)-\ell(\tilde{\theta}_{G\setminus\text{{\color[rgb]{0.0,0.0,0.4}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.0,0.4}SP\\_NPUB}}},z)>\gamma_{t}$
then 7: SP_NPUB is malicious  8: return FAIL  9:else if TEST_TYPE = "B" then
$\triangleright$ Check progress over time (with time lag)  10:
$\theta^{\tau}\leftarrow\theta^{\text{{\color[rgb]{0.0,0.0,0.4}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.0,0.4}SP\\_NPUB}}}_{\text{Inner
at time $\tau$}}$, for all $\tau\in[t-\tau_{c},t]$ $\triangleright$ For Outer:
replace
$\theta^{\text{{\color[rgb]{0.0,0.0,0.4}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.0,0.4}SP\\_NPUB}}}_{\text{Inner
at time $\tau$}}$ with
$\theta^{\text{{\color[rgb]{0.0,0.0,0.4}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.0,0.4}SP\\_NPUB}}}_{\text{global
at time $\tau$}}$ 11: if
$\frac{1}{\tau_{c}+1}\sum^{t}_{\tau=t-\tau_{c}}\sum_{z\in\mathcal{D}_{\text{test}}}\ell(\theta^{\tau},z)>\beta_{t}$
then $\triangleright$ Check if a moving average of the loss decays  12: return
FAIL  13:return PASS

###  7.2 Service provider

Algorithm 4 is an implementation of the routine for the service providers. For
announcement and advertisement of their service, the providers publish a
discoverability event of kind 31990 (Event Type 5). Initially, the service
providers wait until they receive a job request. Then they signal initiation
through a job feedback event. Upon receiving any required payments they
proceed with the optimization routine, as the customer has requested. The
optimization procedure may be one of the run options (FEDAVG or DiLoCo) and
the task for either run option may be Inner or Outer optimization. Depending
on the run option the service providers calls the corresponding algorithmic
routine (Algorithm 5 or Algorithm 6). Periodically the service provider
announces the status of the job through a Job Feedback event and provides a
progress of the computation, for instance see Algorithm 5. After the
completion of the optimization routine the service providers respond with a
job result event, and they expect any pending payment to be settled. If the
customer does not complete payment(s) after a reasonable time period despite
the delivery of accurate outputs, then the service providers may stop
receiving job request from the specific customer immediately. Algorithm 4
Service provider 1:SP_NPUB: service provider public key, <computation
information & time>, <lightning address> 2:Connection through websockets to
all relays in RELAYS $\triangleright$ Where events are published at 3:Publish
an event (NIP-89) of kind $31990$ for discoverability $\triangleright$ Event
Type 5 4:while TRUE do 5: Routine: Search for JOB REQUEST for provider SP_NPUB
6: if JOB REQUEST with appropriate KIND was found then $\triangleright$ Event
Type 2 7: Publish Job Feedback (KIND: 7000) with STATUS = payment_request
$\triangleright$ Event Type 4 8: Wait until the initial payment is submitted,
fetch and validate Payment Receipt (KIND: 9735) 9: if payment = successful
then 10: Publish Job Feedback (KIND: 7000) with STATUS = processing
$\triangleright$ Event Type 4 11: else 12: Publish Job Feedback (KIND: 7000)
with STATUS = error  13: Fetch model_parameters, DATA_SOURCES(SP_NPUB),
RUN_OPTION, TASK from JOB REQUEST 14: if RUN_OPTION = FEDAVG and TASK = INNER
then 15: Call Inner_Optimization( model_parameters, DATA_SOURCES , FEDAVG )
16: else if RUN_OPTION = FEDAVG and TASK = OUTER then 17: Call
Outer_Optimization( model_parameters, DATA_SOURCES , FEDAVG )  18: else if
RUN_OPTION = DiLoCo and TASK = INNER then 19: Call Inner_Optimization(
model_parameters, DATA_SOURCES , DiLoCo )  20: else if RUN_OPTION = DiLoCo and
TASK = INNER then 21: Call Outer_Optimization( model_parameters, DATA_SOURCES
, DiLoCo )  22: Publish Job Feedback (KIND: 7000) with STATUS = success
$\triangleright$ Event Type 4 23: Publish a JOB RESULT event with "output" the
result of the optimization $\triangleright$ Event Type 3

#### Federated Averaging vs Distributed Low-Communication Training of LLMs
(DiLoCo)

The federated averaging algorithm [34] (FEDAVG) is a distributed and
communication efficient learning method of AI models from decentralized data.
This decentralized computation is known as federated learning; a set of
different devices learn a shared model by aggregating locally-computed
updates. In our design we consider as one optimization approach the FEDAVG.
The customer provides a common model specification and the data to the
servicce providers. The service providers have the role of different devices,
they obtain a subset of the data-set and they train the shared model. Upon
completion of the computation they return the optimized model parameters, and
they receive a payment. Although the FEDAVG is a successful approach for
training neural netowrks and AI in a decentralized fashion, we also consider a
variant of FEDAVG that has numerous advantages over the classical approach.
Specifically, the DiLoCo algorithm [8] enables training of LLMs under
constrained communication. In fact, the inner part of optimization (jobs by
Service providers) requires the greatest amount of computation, while the
request for a new job is being decreased significantly. This provides
additional flexibility to our design since it minimizes the number of job
requests by the customer. Nevertheless, the service providers have the option
to frequently provide information (e.g. job status, partial output) to the
customer through the Job Feedback events. We proceed by presenting the
implementation of the Inner Optimization and Outer Optimization routines for
both FEDAVG and DiLoCo algorithms.

#### Inner Optimization (Algorithm 5)

The Inner Optimization routine provides the implementation of the inner part
of the computation. A service provider runs the inner part of FEDAVG (example
SGD) or DiLoCo (AdamW [39, Algorithm 2]). The run option is provided by the
customer through the job request event. The algorithm returns the updated
model parameter. Algorithm 5 Inner_Optimization 1:RUN_OPTION: <FEDAVG or
DiLoCo>, DATA: DATA_SOURCES, model_parameters: $\theta_{\text{global}}$
2:Connection through websockets to all relays in RELAYS $\triangleright$ Where
events are published at 3:$\theta\leftarrow\theta_{\text{global}}$ 4:if
RUN_OPTION = FEDAVG then $\triangleright$ Run the inner part of FEDAVG 5: data
$\leftarrow$ DATA_SOURCES(SP_NPUB) 6: $\mathcal{B}$ $\leftarrow$ Split data
into batches  7: for epoch $e\in(1,E)$ do 8: Publish Job Feedback (KIND: 7000)
with STATUS = processing $\triangleright$ Event Type 4 9: for batch
$\boldsymbol{b}\in\mathcal{B}$ do 10:
$\theta\leftarrow\theta-\eta\nabla\ell(\theta;\boldsymbol{b})$ 11:else if
RUN_OPTION = DiLoCo then 12: for epoch $e\in(1,E)$ do 13: Sample a batch
$\boldsymbol{b}$ of data from DATA_SOURCES(SP_NPUB) 14: Run
AdamW($\theta,\nabla\ell(\theta,\boldsymbol{b})$) $\triangleright$ AdamW [39,
Algorithm 2] 15: Periodically publish Job Feedback (KIND: 7000) with STATUS =
processing $\triangleright$ Event Type 4 16: $\theta\leftarrow$
AdamW($\theta,\nabla\ell(\theta,\boldsymbol{b})$)  17:return $\theta$
$\triangleright$ Returns
$\theta^{({\color[rgb]{0.0,0.0,0.4}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.0,0.4}\text{SP\\_NPUB}})}_{\text{Inner}}$

#### Outer Optimization (Algorithm 6)

For the Outer Optimization routine, the customer has the option to run the
outer optimization, or assign it to a service provider. Then the customer (or
a service provider) runs the outer part of FEDAVG (example aggregation step)
or DiLoCo [8, 40, Nesterov Momentum]. The run option is determined by the
customer. The algorithm returns the updated model parameter. Algorithm 6
Outer_Optimization 1:RUN_OPTION: <FEDAVG or DiLoCo>, RUN_OPTION: <FEDAVG or
DiLoCo>, DATA: DATA_SOURCES, model_parameters: $\theta_{\text{global}}$, the
last "outputs" of the Inner Optimization jobs: $\theta_{\text{Inner}}$
2:Connection through websockets to all relays in RELAYS $\triangleright$ Where
events are published at 3:if RUN_OPTION = FEDAVG then $\triangleright$ Run the
aggregation (outer) part of FEDAVG 4:
$\theta_{\text{global}}=\frac{1}{{\color[rgb]{0.0,0.0,0.4}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.0,0.4}\text{NUM\\_PR}}}\sum^{{\color[rgb]{0.0,0.0,0.4}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.0,0.4}\text{NUM\\_PR}}}_{k=1}\eta_{k}\times\theta^{(k)}_{\text{Inner}}$
$\triangleright$ For some weights $\eta_{k}$ 5:else if RUN_OPTION = DiLoCo
then $\triangleright$ Run the Outer part of DiLoCo [8] 6:
$\Delta\theta_{\text{Outer}}=\frac{1}{{\color[rgb]{0.0,0.0,0.4}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.0,0.4}\text{NUM\\_PR}}}\sum^{{\color[rgb]{0.0,0.0,0.4}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.0,0.4}\text{NUM\\_PR}}}_{k=1}\eta_{k}\times(\theta_{\text{global}}-\theta^{(k)}_{\text{Inner}})$
7: Run Nesterov Momentum: $\triangleright$ See FedMom [40, Algorithm 3] 8:
(Periodically) publish Job Feedback (KIND: 7000) with STATUS = processing
$\triangleright$ Event Type 4 9: $\theta_{\text{global}}\leftarrow$
Nesterov_Momentum ($\theta_{\text{global}}$ , $\Delta\theta_{\text{Outer}}$)
10:return $\theta_{\text{global}}$

##  8 Conclusion

The NOSTR protocol is a relatively new paradigm shift for reliable and
decentralized social web applications. In this work we introduced a design and
protocol flow for LLM and AI training on decentralized marketplace system,
that builds upon the NOSTR. The fast communication though websockets and the
flexibility of development of the protocol enables the potential for a
competitive, open and censorship resistant computation network, at which users
(customers) provide data and a payment, and they receive a trained AI model.
The integrated payment protocol flow rules and the lightning network offer
fast, reliable and with zero transaction fee payments without a trusted party.
As a result, service providers can maximize their profit and compete within an
open market. Further, this payment system supports microtranscactions with
instant settlement, which is essentially useful as anti-spam mechanism,
reliable form of handshaking between customers and service providers, on the
fly payments upon receiving partial results of the computation, or upon
validation of the final output. We considered a simple but effective mechanism
for validation of the output, by periodically checking the progress of the
trained model through a validation dataset. However, we believe that other
alternative solutions for verifying accuracy of the computation may be
considered as well. Such robust approaches can be designed by considering
smart contracts and the BitVM mechanism [41], which enables the possibility of
any computable function to be verified. Inclusion of such mechanisms for
verification, together with a reputation system, or application specific
protocol flow variations for alternative AI algorithms such as DeepSpeed [42]
& Zero Redundancy Optimizer [43] or distributed LLM deployment and inference
[44, 45, 46, 47, 48, 49, 50, 51] could be potentially considered tasks for
future work.

## References

  * [1] Public domain.  Nostr - Notes and Other Stuff Transmitted by Relays.  https://github.com/nostr-protocol/nostr, 2023.
  * [2] Artur Briugeman.  Nostr real time statistics.  https://stats.nostr.band, 2023.
  * [3] Public domain.  Bluesky architecture.  https://docs.bsky.app/docs/advanced-guides/federation-architecture, 2023.
  * [4] Martin Kleppmann, Paul Frazee, Jake Gold, Jay Graber, Daniel Holmgren, Devin Ivy, Jeromy Johnson, Bryan Newbold, and Jaz Volpert.  Bluesky and the AT protocol: Usable decentralized social media.  arXiv preprint arXiv:2402.03239, 2024.
  * [5] Seth Gilbert and Nancy Lynch.  Perspectives on the CAP Theorem.  Computer, 45(2):30–36, 2012.
  * [6] Yiluo Wei and Gareth Tyson.  Exploring the nostr ecosystem: A study of decentralization and resilience.  arXiv preprint arXiv:2402.05709, 2024.
  * [7] Joseph Poon and Thaddeus Dryja.  The bitcoin lightning network: Scalable off-chain instant payments.  https://lightning.network/, 2016.
  * [8] Arthur Douillard, Qixuan Feng, Andrei A Rusu, Rachita Chhaparia, Yani Donchev, Adhiguna Kuncoro, Marc’Aurelio Ranzato, Arthur Szlam, and Jiajun Shen.  DiLoCo: Distributed low-communication training of language models.  arXiv preprint arXiv:2311.08105, 2023.
  * [9] Satoshi Nakamoto.  Bitcoin: A peer-to-peer electronic cash system.  Decentralized business review, 2008.
  * [10] Amir Dembo, Sreeram Kannan, Ertem Nusret Tas, David Tse, Pramod Viswanath, Xuechao Wang, and Ofer Zeitouni.  Everything is a race and Nakamoto always wins.  In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pages 859–878, 2020.
  * [11] Ying Liu and Karanam Nanda Kishore.  Sovereign individual system (sis): An autonomous digital platform for sovereign individuals.  In Proceedings of the Future Technologies Conference, pages 142–153. Springer, 2023.
  * [12] Public domain.  Nip-19: Nostr - Notes and Other Stuff Transmitted by Relays.  https://github.com/nostr-protocol/nips/blob/master/19.md, 2023.
  * [13] Tim Ruffing Pieter Wuille, Jonas Nick.  Schnorr signatures for secp256k1.  https://bips.xyz/340, 2019.
  * [14] Ewa Deelman.  Mapping abstract complex workflows onto grid environments.  Journal of Grid Computing, 1(1):25–39, 2003.
  * [15] Ian Taylor, Matthew Shields, and Dr Wang.  Resource management of triana p2p services.  Grid Resource Management, 01 2003.
  * [16] D.P. Anderson, E. Korpela, and R. Walton.  High-performance task distribution for volunteer computing.  In First International Conference on e-Science and Grid Computing (e-Science’05), pages 8 pp.–203, 2005.
  * [17] David P. Anderson.  Boinc: A platform for volunteer computing.  Journal of Grid Computing, 18(1):99–122, November 2019.
  * [18] The gridcoin network and protocol overview.  2018\.
  * [19] Anatoly Yakovenko.  Solana: A new architecture for a high performance blockchain v0. 8.13.  Whitepaper, 2018.
  * [20] Nostr Apps.  Nostr apps.  https://www.nostrapps.com/, 2023.
  * [21] Public domain.  Data Vending Machines.  https://github.com/nostr-protocol/data-vending-machines, 2023.
  * [22] Public domain.  VenData.  https://vendata.io, 2023.
  * [23] Gregory Maxwell, Andrew Poelstra, Yannick Seurin, and Pieter Wuille.  Simple schnorr multi-signatures with applications to bitcoin.  Designs, Codes and Cryptography, 87(9):2139–2164, 2019.
  * [24] Public domain.  Nip-90: Nostr - Notes and Other Stuff Transmitted by Relays.  https://github.com/nostr-protocol/nips/blob/master/90.md, 2023.
  * [25] Andreas M Antonopoulos, Olaoluwa Osuntokun, and René Pickhardt.  Mastering the lightning network.  " O’Reilly Media, Inc.", 2021.
  * [26] Rene Pickhardt Andreas M. Antonopoulos, Olaoluwa Osuntokun.  Lightning payment requests.  https://github.com/lnbook/lnbook/blob/develop/15_payment_requests.asciidoc, 2023.
  * [27] Public domain.  NOSTR Implementation Possibillities, 89.  https://github.com/nostr-protocol/nips/blob/master/89.md, 2023.
  * [28] John Joseph O’Hare, Allen Fairchild, and Umran Ali.  Money & trust in digital society: Bitcoin, nostr, stablecoins, digital objects and generative ai in b2b spatial mixed reality.  arXiv preprint arXiv:2207.09460, 2022.
  * [29] Jérémy Robert, Sylvain Kubler, and Sankalp Ghatpande.  Enhanced lightning network (off-chain)-based micropayment in iot ecosystems.  Future Generation Computer Systems, 112:283–296, 2020.
  * [30] Public domain.  NOSTR Implementation Possibillities, 57.  https://github.com/nostr-protocol/nips/blob/master/57.md, 2023.
  * [31] Nostr Zap.  Jeffg.  https://nostr.how/en/zaps, 2023.
  * [32] Public domain.  Lnurl.  https://github.com/GaloyMoney/lnurl-pay, 2023.
  * [33] Public domain.  Nip-01: Nostr - Notes and Other Stuff Transmitted by Relays.  https://github.com/nostr-protocol/nips/blob/master/01.md, 2023.
  * [34] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas.  Communication-efficient learning of deep networks from decentralized data.  In Artificial intelligence and statistics, pages 1273–1282. PMLR, 2017.
  * [35] Arjun Nitin Bhagoji, Supriyo Chakraborty, Prateek Mittal, and Seraphin Calo.  Analyzing federated learning through an adversarial lens.  In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 634–643. PMLR, 09–15 Jun 2019.
  * [36] Matteo Demartis.  Adversarial attacks in federated learning, 2022.
  * [37] Mayank Rathee, Conghao Shen, Sameer Wagh, and Raluca Ada Popa.  Elsa: Secure aggregation for federated learning with malicious actors.  In 2023 IEEE Symposium on Security and Privacy (SP), pages 1961–1979. IEEE, 2023.
  * [38] Sana Awan, Bo Luo, and Fengjun Li.  Contra: Defending against poisoning attacks in federated learning.  In Computer Security–ESORICS 2021: 26th European Symposium on Research in Computer Security, Darmstadt, Germany, October 4–8, 2021, Proceedings, Part I 26, pages 455–475. Springer, 2021.
  * [39] Ilya Loshchilov and Frank Hutter.  Decoupled weight decay regularization.  arXiv preprint arXiv:1711.05101, 2017.
  * [40] Zhouyuan Huo, Qian Yang, Bin Gu, Lawrence Carin Huang, et al.  Faster on-device training using new federated momentum algorithm.  arXiv preprint arXiv:2002.02090, 2020.
  * [41] Robin Linus.  Bitvm: Compute anything on bitcoin.  bitvm.org, 2023.
  * [42] Jeff Rasley, Samyam Rajbhandari, Olatunji Ruwase, and Yuxiong He.  Deepspeed: System optimizations enable training deep learning models with over 100 billion parameters.  In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 3505–3506, 2020.
  * [43] Samyam Rajbhandari, Jeff Rasley, Olatunji Ruwase, and Yuxiong He.  Zero: Memory optimizations toward training trillion parameter models.  In SC20: International Conference for High Performance Computing, Networking, Storage and Analysis, pages 1–16. IEEE, 2020.
  * [44] Tao Fan, Yan Kang, Guoqiang Ma, Weijing Chen, Wenbin Wei, Lixin Fan, and Qiang Yang.  Fate-LLM: A industrial grade federated learning framework for large language models.  arXiv preprint arXiv:2310.10049, 2023.
  * [45] Lin Lu, Chenxi Dai, Wangcheng Tao, Binhang Yuan, Yanan Sun, and Pan Zhou.  Exploring the robustness of decentralized training for large language models.  arXiv preprint arXiv:2312.00843, 2023.
  * [46] Zhenheng Tang, Yuxin Wang, Xin He, Longteng Zhang, Xinglin Pan, Qiang Wang, Rongfei Zeng, Kaiyong Zhao, Shaohuai Shi, Bingsheng He, et al.  Fusionai: Decentralized training and deploying LLMs with massive consumer-level gpus.  arXiv preprint arXiv:2309.01172, 2023.
  * [47] Amey Agrawal, Ashish Panwar, Jayashree Mohan, Nipun Kwatra, Bhargav S Gulavani, and Ramachandran Ramjee.  Sarathi: Efficient LLM inference by piggybacking decodes with chunked prefills.  arXiv preprint arXiv:2308.16369, 2023.
  * [48] Haihao Shen, Hanwen Chang, Bo Dong, Yu Luo, and Hengyu Meng.  Efficient LLM inference on cpus.  arXiv preprint arXiv:2311.00502, 2023.
  * [49] Benjamin Spector and Chris Re.  Accelerating LLM inference with staged speculative decoding.  arXiv preprint arXiv:2308.04623, 2023.
  * [50] Tianle Cai, Yuhong Li, Zhengyang Geng, Hongwu Peng, Jason D Lee, Deming Chen, and Tri Dao.  Medusa: Simple LLM inference acceleration framework with multiple decoding heads.  arXiv preprint arXiv:2401.10774, 2024.
  * [51] Luciano Del Corro, Allie Del Giorno, Sahaj Agarwal, Bin Yu, Ahmed Awadallah, and Subhabrata Mukherjee.  Skipdecode: Autoregressive skip decoding with batching and caching for efficient LLM inference.  arXiv preprint arXiv:2307.02628, 2023.


A. Grothendieck, Sur la classification des  fibrés holomorphes sur la sphère de Riemann, Amer. J. Math. 79, (1957), 121–138.

[14]
R. Hartshorne, Algebraic geometry, Springer-Verlag, New York-Heidelberg, Graduate Texts in Mathematics 52, (1977).

[15]
J. Li, Compactification of moduli space of vector bundles over algebraic surface, in “Collection of papers on geometry, analysis and mathematical physics", World Sci. Publ., River Edge, (1997), 98–113.

[16]
M. Maruyama, Singularities of the curve of jumping lines of a vector bundle of rank 2 on $\mathbb{P}^2$,  Algebraic geometry (Tokyo/Kyoto, 1982), 370–411, Lecture Notes in Math., 1016, Springer, Berlin, (1983).

[17]
C. Okonek, M. Schneider, and H. Spindler, Vector bundles
on complex projective spaces, Progress in Mathematics, 3, Birkhäuser
Boston, Mass., (1980).

[18]
P. Orlik and H. Terao, Arrangements of hyperplanes, volume 300 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer- Verlag, Berlin, (1992).

[19]
K. Saito, Theory of logarithmic differential forms and logarithmic vector fields, J. Fac. Sci. Univ. Tokyo Sect. IA Math., 27, no. 2, (1980), 265–291.

[20]
K. Ueda and M. Yoshinaga, Logarithmic vector fields along smooth plane cubic curves, Kumamoto J. Math. 21, (2008), 11–20.

[21]
K. Ueda and M. Yoshinaga, Logarithmic vector fields along smooth divisors in projective space, Hokkaido Math. J. 38, (2009), 409–415.

[22]
J. Vallès,Nombre maximal d'hyperplans instables pour un fibré de Steiner, Math. Z. 233, (2000), 507–514.

[23]
A. Van de Ven, On uniform vector bundles, Math. Ann. 195, (1972), 245–248.

[24]
C. Weibel, An introduction to homological algebra, Cambridge Studies in Advanced Mathematics, 38 (1994).


# Assessing the Extrapolation Capability of
Template-Free Retrosynthesis Models

Shuan Chen Yousung Jung
Department of Chemical and Biological Engineering
Seoul National University
Seoul, South Korea 08826
<EMAIL_ADDRESS>

###### Abstract

Despite the acknowledged capability of template-free models in exploring
unseen reaction spaces compared to template-based models for retrosynthesis
prediction, their ability to venture beyond established boundaries remains
relatively uncharted. In this study, we empirically assess the extrapolation
capability of state-of-the-art template-free models by meticulously assembling
an extensive set of out-of-distribution (OOD) reactions. Our findings
demonstrate that while template-free models exhibit potential in predicting
precursors with novel synthesis rules, their top-10 exact-match accuracy in
OOD reactions is strikingly modest ($<1\%$). Furthermore, despite the
capability of generating novel reactions, our investigation highlights a
recurring issue where more than half of the novel reactions predicted by
template-free models are chemically implausible. Consequently, we advocate for
the future development of template-free models that integrate considerations
of chemical feasibility when navigating unexplored regions of reaction space.

##  1 Introduction

In recent years, the field of scientific research has witnessed remarkable
progress in the development of deep learning models. These cutting-edge deep
learning models have been increasingly applied to tackle complex scientific
challenges, including synthesis planning [1, 2]. Retrosynthesis models relying
on pre-defined reaction templates derived from existing reactions are called
template-based models. Due to the nature of using known reaction templates,
their incapability of predicting novel synthesis pathways is often considered
as a major disadvantage [3, 4, 5, 6]. In contrast, template-free, especially
language-based, models, are often claimed to hold the advantage of discovering
entirely new reaction rules that have not been encountered during training [7,
8, 9, 10, 11, 12].

However, the freedom to explore beyond established boundaries in chemical
reaction prediction also introduces a potential risk—the generation of invalid
or chemically infeasible reactions. While the benefits of template-free models
are widely extolled, the associated risks are often underestimated and
underexplored. Additionally, it remains unclear whether template-free models
can effectively predict out-of-distribution (OOD) synthesis records, further
emphasizing the need for a comprehensive examination of their capabilities. In
this paper, we evaluate the extrapolation capabilities of template-free models
by asking two questions:

  1. 1.

Can template-free models accurately reproduce the synthesis pathways recorded
in the existing datasets involving unseen reaction templates from the train
set?

  2. 2.

How "novel" are the recently proposed template-free models, and what is the
chemical feasibility of the predicted novel reactions?

We achieve this by meticulously curating an OOD dataset sourced from two
different datasets extracted from USPTO reactions [13]. Additionally, we delve
into the examination of the popular novel reaction templates proposed by these
models, seeking to gain deeper insights into the practical potential of
employing template-free, in particular language-based, models for the
discovery of innovative synthesis strategies. Through this research, we aim to
provide a nuanced understanding of the capabilities, limitations, and
practical implications of template-free models in the context of
retrosynthesis prediction.

##  2 Related Work

Template-based models Template-based models classify which of the predefined
reaction templates should be applied to a given product in order to derive its
precursors. These templates can be either manually crafted or automatically
extracted from extensive reaction databases [14, 15]. The application of these
templates specifies which part of the molecule needs to be modified,
facilitating the prediction of precursor molecules based on input molecules
[3, 4, 5, 6]. These models, however, are inherently limited by the finite set
of templates they operate within.

Template-free models In contrast, template-free models have emerged as a novel
paradigm, offering a departure from the constraints of predefined templates.
These models predict precursor molecules by directly generating reactants from
scratch, without relying on predefined reaction templates. This liberates them
from the confines of a predefined template space, allowing for a more flexible
and unconstrained approach to retrosynthesis prediction [7, 8, 9, 10, 11, 12].
These models hold the potential to transcend the limitations of predefined
templates, enabling them to explore a wider and more diverse reaction space in
retrosynthetic prediction.

##  3 Defining out-of-distribution reactions

To rigorously assess the extrapolation capabilities of template-free
retrosynthesis models, we must assemble a set of reactions that distinctly
deviate from those present in the training dataset. Our approach commences
with two widely recognized reaction datasets for retrosynthesis and forward
synthesis model evaluation: the USPTO-50k dataset [16] and the USPTO-480k
dataset [17].

Given that the majority of retrosynthesis models are trained on the training
set of the USPTO-50k dataset, comprising 40,000 reactions, we derive a set of
reaction templates from this training data to represent the learned reaction
distribution. The representation of reaction templates in this study employs
the concept of Generalized Reaction Templates (GRTs) [18], chosen for their
effective characterization of the dataset’s chemical reaction distribution.
GRTs, achieved by simplifying reaction templates to remove atom symbols from
local reaction template [6], offer a high level of coverage (99.8%) on the
USPTO-50k test set.

Subsequently, we extract reaction templates from the test set of the
USPTO-480k dataset, which also encompasses 40,000 reactions, and identify
reactions that do not share any GRTs with those seen in the USPTO-50k training
set. This subset of reactions is aptly denoted as "out-of-distribution (OOD)"
reactions, signifying their divergence from the reaction distribution in the
training set. To facilitate comparison, we randomly sample an equivalent
number of reactions from the remaining reactions in the USPTO-480k dataset and
classify them as "in-distribution (ID)" reactions.

The objective is to assess whether the accuracy of template-free models in
predicting reactions from the OOD dataset is on par with their performance on
the ID dataset. If template-free models can predict OOD reactions with
comparable accuracy to ID reactions, it would suggest their proficiency in
extrapolating the reaction space and unveiling novel synthesis rules. The
overall process of curating OOD reactions is illustrated in Figure 1.

Figure 1: The workflow of collecting in-distribution (ID) and out-of-
distribution (OOD) reactions

##  4 Experiments

Data: We evaluate the models on both 3,277 in-distribution (ID, reactions
involving known reaction templates) and 3,277 out-of-distribution (OOD,
reactions not involving known reaction templates) reactions described in
Section 3.

Evaluation metric: We use (1) exact-match accuracy, (2) round-trip accuracy,
(3) reaction validity, (4) reaction uniqueness, and (5) reaction novelty as
described below to evaluate the predictions:

Exact-match accuracy: Exact-match accuracy is determined by whether the
canonical SMILES strings of predicted reactants matches the ground truth
reactants in the dataset.

Round-trip accuracy: To assess the chemical feasibility of reactions predicted
by template-free models, we employ the Molecular Transformer [19] to predict
the outcomes of the proposed precursors. A successful match between the
predicted reactant outcomes (top-1 prediction) and the original target product
confirms the validity of retrosynthesis predictions, referred to as "round-
trip accuracy"[20].

Reaction validity: The evaluation of prediction validity entails two criteria:
(1) Predicted SMILES strings can be successfully converted into molecules
using RDKit [21]. (2) Predicted reactants include all the required atoms to
form the product, ensuring a balanced reaction.

Reaction uniqueness: The uniqueness of predictions is quantified by
calculating the ratio of non-repeated canonical SMILES strings among all the
generated predictions.

Reaction novelty: To assess the novelty of predictions, we analyze whether the
reactions yield templates that have never appeared in the USPTO-50k training
set. Atom-to-atom mappings for template extraction are generated using
RXNMapper [22] to facilitate this evaluation.

Models: We implement three template-free models, including the vanilla
Transformer [23](trained from scratch using USPTO-50K train set, referred to
as Transformer in this paper), and its two variants, Retroformer [11] and
Chemformer [10]. For comparison, we compare the prediction results with a
template-based baseline model LocalRetro [6].

Note that although Zhong et al. [24] reported higher accuracy on the USPTO
datasets, we found a potential data leakage issue arising from pretraining on
USPTO molecules. Similarly, $O$-GNN [25], a variant of LocalRetro, reported
higher accuracy than LocalRetro. However, upon closer examination, we
discovered that its marginal improvement is more likely attributed to
hyperparameter tuning rather than fundamental advancements in the model
design. Consequently, these two models are not included in this paper for
comparison.

###  4.1 Top-k exact-match and round-trip accuracy

Table 1 presents the top-k exact-match accuracy of four tested retrosynthesis
models, including one template-based and three template-free models, on in-
distribution (ID) and out-of-distribution (OOD) reactions. In the case of ID
reactions, all template-free models demonstrate lower accuracy than the
template-based model LocalRetro, with LocalRetro achieving the highest
performance, particularly outperforming by over 15.7% at k=10. Conversely, for
OOD reactions, template-free models successfully predict synthesis steps using
reaction templates not seen in the USPTO-50k train set, while LocalRetro, by
definition, fails to predict any of them. However, even at top-10 predictions,
Transformer, Retroformer, and Chemformer only correctly predict 9 (0.27%), 26
(0.79%), and 9 (0.27%) out of the total 3,277 reactions, which is
significantly lower than their performance on ID reactions (78.9%, 79.0%, and
70.3%, respectively).

Table 1: Top-k exact-match accuracy (%) on in-distribution (ID) and out-of-distribution (OOD) reactions of four retrosynthesis models. The highest values are highlighted in bold font. Model | ID reactions |  | OOD reactions
---|---|---|---
k=1 | 5 | 10 |  |  k=1 | 5 | 10
LocalRetro [6] | 64.3 | 89.8 | 94.7 |  | 0 | 0 | 0
Transformer [23] | 52.6 | 75.0 | 78.9 |  | 0.09 | 0.24 | 0.27
Retroformer [11] | 59.9 | 72.9 | 79.0 |  | 0.03 | 0.31 | 0.79
Chemformer [10] | 63.6 | 70.0 | 70.3 |  | 0.24 | 0.27 | 0.27

Table 2 illustrates the top-10 round-trip accuracy of three template-free
models. The round-trip accuracy shares a similar trend across two test sets.
For predicted reactions corresponding to known reaction templates, Chemformer
demonstrates the highest round-trip accuracy. Surprisingly, the vanilla
Transformer exhibits nearly double the round-trip accuracy compared to two
advanced models.

In general, the round-trip accuracy of predictions yielding novel reaction
templates is significantly lower for both Retroformer and Chemformer compared
to reactions with known templates. Specifically, Retroformer shows a reduction
of 57.4% and 48.9% on ID and OOD reactions, respectively. Similarly,
Chemformer displays a decrease of 65.5% and 48.8% on ID and OOD reactions,
respectively. In contrast, the round-trip accuracy of the vanilla Transformer
remains consistent for predictions involving either known or novel reaction
templates.

Table 2: Top-10 round-trip accuracy (%) for predictions yielding known templates (known) and novel templates (novel) on ID and OOD reactions. The highest values are highlighted in bold font. Model | ID reactions |  | OOD reactions
---|---|---|---
known | novel |  | known | novel
Transformer [23] | 54.1 | 55.9 |  | 43.3 | 42.5
Retroformer [11] | 84.2 | 26.8 |  | 70.4 | 21.5
Chemformer [10] | 88.4 | 22.9 |  | 73.2 | 24.4

Note that the top-1 accuracy of the pretrained Molecular Transformer[19],
which was used to evaluate the round-trip accuracy and trained on USPTO-480k
dataset [17], on the tested reactions is 94.0%.

###  4.2 Validity, uniqueness and novelty

Table 3 provides an analysis of the validity, uniqueness and novelty of the
top-10 predictions from three template-free models on ID and OOD reactions. In
the case of ID reactions, Chemformer demonstrates a higher rate of valid
predictions (98.6 %) but significantly lower uniqueness (15.6 %) and novelty
(1.6 %) compared to Transformer and Retroformer. The low number of unique
reactions predicted by Chemformer may contribute to its higher top-1 accuracy
but lower accuracy at higher k compared to other non-pretrained models.
Although Transformer and Retroformer generates much more novel reactions than
Chemformer, the accuracy of top-10 predictions on OOD reactions does not scale
similarly, indicating the predicted novel reactions are mostly different from
the recorded reactions. Interestingly, all template-free models generate more
unique and novel reactions when predicting retrosynthesis for the targets of
OOD reactions than for of ID reactions, indicating a potential understanding
by template-free models of the need to extrapolate the reaction space learned
from the training set to make correct OOD predictions.

Table 3: The percentage of valid, unique, and novel reactions tested on ID and OOD reactions within top-10 predictions from template-free models. The highest values are highlighted in bold font. Model | ID reactions |  | OOD reactions
---|---|---|---
% Valid | % Unique | % Novel |  | % Valid | % Unique | % Novel
Transformer [23] | 55.3 | 49.5 | 14.7 |  | 58.6 | 54.4 | 17.6
Retroformer [11] | 81.0 | 60.7 | 12.6 |  | 76.3 | 67.0 | 18.2
Chemformer [10] | 98.6 | 15.6 | 1.4 |  | 96.6 | 21.9 | 1.6

###  4.3 Investigating novel reactions

In this section, we delve into the analysis of novel reaction templates
generated by three template-free models to gain a deeper understanding of the
extrapolation achieved within their training data. In Figure 2a, we present
three examples of out-of-distribution (OOD) reactions that were correctly
predicted by all template-free models using different reaction templates.
While these template-free models demonstrate the ability to generate
chemically reasonable templates for these examples, the accuracy in predicting
such templates remains relatively low, standing at 4.8%, 3%, and 4% for
Transformer, 2.8%, 3.1%, and 24% for Retroformer, and 1.4%, 3%, and 4% for
Chemformer for each of the template examples showcased in Figure 2a.

We also explore the popular novel reaction templates generated by three tested
models in Figure 2b, aiming to ascertain if template-free models extrapolate
further into the reaction space beyond what is recorded in the OOD reactions
collected in this study. Our analysis reveals that these so-called "novel
templates" often involve the use of nucleophiles as leaving groups (as
observed in the amine and Grignard reagent reactions) or direct cleavage of a
C-N single bond (as seen in the middle example). While the reaction templates
involved in these predictions have not been encountered in the training set,
they are likely to be chemically unreasonable. This observation of chemically
implausible reactions extends to the remaining novel reactions as well.

Figure 2: Examples of (a) correctly predicted and (b) popular novel reaction
templates generated by Transformer, Retroformer, and Chemformer. The number of
reactions corresponding to each reaction template in the dataset or predicted
by each model is written below each example reaction.

##  5 Conclusion

In summary, this paper has conducted a comprehensive evaluation of the
extrapolation capabilities of template-free models in retrosynthesis,
specifically focusing on their potential to discover new synthesis strategies
beyond the confines of training data. While template-free models may exhibit
lower accuracy when predicting in-distribution reactions compared to template-
based models, our results affirm their ability to generate reactions
documented in the out-of-distribution (OOD) dataset. However, given the
extremely low exact-match accuracy on OOD reactions and poor round-trip match
accuracy on novel predictions, a substantial advancement of template-free
models is necessary before confidently asserting their capability to
extrapolate the reaction space.

Therefore, as we look to the future, the development of template-free models
must place a strong emphasis on considering chemical feasibility while
navigating and extending the boundaries of the reaction space. This
consideration is paramount in ensuring that the innovative potential of
template-free models can be harnessed effectively for the advancement of the
field of organic chemistry and retrosynthesis.

## References

  * [1] Schwaller, P., A. C. Vaucher, R. Laplaza, et al.  Machine intelligence for chemical reaction space.  _Wiley Interdisciplinary Reviews: Computational Molecular Science_ , 12(5):e1604, 2022.
  * [2] Tu, Z., T. Stuyver, C. W. Coley.  Predictive chemistry: machine learning for reaction deployment, reaction development, and reaction discovery.  _Chemical Science_ , 2023.
  * [3] Coley, C. W., L. Rogers, W. H. Green, et al.  Computer-assisted retrosynthesis based on molecular similarity.  _ACS central science_ , 3(12):1237–1245, 2017.
  * [4] Segler, M. H., M. P. Waller.  Neural-symbolic machine learning for retrosynthesis and reaction prediction.  _Chemistry–A European Journal_ , 23(25):5966–5971, 2017.
  * [5] Dai, H., C. Li, C. Coley, et al.  Retrosynthesis prediction with conditional graph logic network.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * [6] Chen, S., Y. Jung.  Deep retrosynthetic reaction prediction using local reactivity and global attention.  _JACS Au_ , 1(10):1612–1620, 2021.
  * [7] Liu, B., B. Ramsundar, P. Kawthekar, et al.  Retrosynthetic reaction prediction using neural sequence-to-sequence models.  _ACS central science_ , 3(10):1103–1113, 2017.
  * [8] Tetko, I. V., P. Karpov, R. Van Deursen, et al.  State-of-the-art augmented nlp transformer models for direct and single-step retrosynthesis.  _Nature communications_ , 11(1):1–11, 2020.
  * [9] Seo, S.-W., Y. Y. Song, J. Y. Yang, et al.  Gta: Graph truncated attention for retrosynthesis.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 35, pages 531–539. 2021.
  * [10] Irwin, R., S. Dimitriadis, J. He, et al.  Chemformer: a pre-trained transformer for computational chemistry.  _Machine Learning: Science and Technology_ , 3(1):015022, 2022.
  * [11] Wan, Y., C.-Y. Hsieh, B. Liao, et al.  Retroformer: Pushing the limits of end-to-end retrosynthesis transformer.  In _International Conference on Machine Learning_ , pages 22475–22490. PMLR, 2022.
  * [12] Tu, Z., C. W. Coley.  Permutation invariant graph-to-sequence model for template-free retrosynthesis and reaction prediction.  _Journal of chemical information and modeling_ , 62(15):3503–3513, 2022.
  * [13] Lowe, D. M.  _Extraction of chemical structures and reactions from the literature_.  Ph.D. thesis, University of Cambridge, 2012.
  * [14] Hartenfeller, M., M. Eberle, P. Meier, et al.  A collection of robust organic synthesis reactions for in silico molecule design.  _Journal of chemical information and modeling_ , 51(12):3093–3098, 2011.
  * [15] Coley, C. W., W. H. Green, K. F. Jensen.  Rdchiral: An rdkit wrapper for handling stereochemistry in retrosynthetic template extraction and application.  _Journal of chemical information and modeling_ , 59(6):2529–2537, 2019.
  * [16] Schneider, N., N. Stiefl, G. A. Landrum.  What’s what: The (nearly) definitive guide to reaction role assignment.  _Journal of chemical information and modeling_ , 56(12):2336–2346, 2016.
  * [17] Jin, W., C. Coley, R. Barzilay, et al.  Predicting organic reaction outcomes with weisfeiler-lehman network.  _Advances in neural information processing systems_ , 30, 2017.
  * [18] Chen, S., Y. Jung.  A generalized-template-based graph neural network for accurate organic reactivity prediction.  _Nature Machine Intelligence_ , 4(9):772–780, 2022.
  * [19] Schwaller, P., T. Laino, T. Gaudin, et al.  Molecular transformer: a model for uncertainty-calibrated chemical reaction prediction.  _ACS central science_ , 5(9):1572–1583, 2019.
  * [20] Schwaller, P., R. Petraglia, V. Zullo, et al.  Predicting retrosynthetic pathways using transformer-based models and a hyper-graph exploration strategy.  _Chemical science_ , 11(12):3316–3325, 2020.
  * [21] Landrum, G.  Rdkit documentation.  _Release_ , 1(1-79):4, 2013.
  * [22] Schwaller, P., B. Hoover, J.-L. Reymond, et al.  Extraction of organic chemistry grammar from unsupervised learning of chemical reactions.  _Science Advances_ , 7(15):eabe4166, 2021.
  * [23] Vaswani, A., N. Shazeer, N. Parmar, et al.  Attention is all you need.  _Advances in neural information processing systems_ , 30, 2017.
  * [24] Zhong, Z., J. Song, Z. Feng, et al.  Root-aligned smiles: a tight representation for chemical reaction prediction.  _Chemical Science_ , 13(31):9023–9034, 2022.
  * [25] Zhu, J., K. Wu, B. Wang, et al.  $o$-gnn: incorporating ring priors into molecular modeling.  In _The Eleventh International Conference on Learning Representations_. 2022.