When the party arrived in the city, with their "pet beholderkin" and shield guardian, they were checked in at the doors by a wizard, who, after asking the usual questions and all that, gave them ID papers and "branded" his arcane mark upon both the construct and the aberration.
It's how it's done with that city. Arcane marks are unique to the wizard who cast it (forging marks is very hard), and when seeing a monster (like the above examples, or a druid's dire tiger companion, for example) roaming in the street but with a visible mark on them, people will know said monsters are supposed to behave -- no need to run away screaming for the guard.
If the monster goes on a rampage, witness will be able to describe the mark the monster was carrying, and thus, whose gatemage let it in. The gatemage would be considered responsable for anything that happens, so they're prone to be overzealous in their inspections.