Velocity measures how much work the team can complete per sprint, given a stable team and a common understanding of the complexity of the items that they work on.
It's usually measured in number of story points, or sometimes, if PBIs can be split into similar sizes, you can even count number of PBIs completed per sprint and use that as your velocity.
Velocity is not an average. Velocity is a sum of all the story points for all the PBIs completed during a sprint (or a count if you are counting PBIs). Averaging velocities comes later, when you want to make use of velocity to forecast how much work you could finish at some later time (see yesterday's weather).
Velocity isn't flawed. It's just some measurement. What you do with velocity is subject to flaws.
EDIT: based on your comment:
but the team doesn't know the complexity - the team estimates the complexity. That is the point of my question.
The velocity is a way to attach some "reality" sense to estimates.
If you would know the complexity of each item and how much it really takes to build then software development will be easy and we wouldn't need to estimate. We also wouldn't need to use things like velocity.
But because we don't know how much building new software takes, we need to estimate. And the estimates are just that, estimates. Statistically speaking, half of the time the real work takes less than the estimate, and half of the time it takes more than the estimate because you rarely land precisely on the estimate.
When teams estimate in story points, they have a discussion to understand what they need to build. The smaller the items you work on the easier to have this discussion and cover almost all corners. Then, based on that understanding, they can place that work into different sized buckets. This is a 2 SP, this is a 5 SP, etc. I want to make this clear: the point is the exploration and the understanding of the work. The story point estimate is just a byproduct of the discussion.
But you can use the story points to then see how the effort will match with actual progress of time by laying the work over a sprint. The velocity will tell you how the estimate matches with reality over a consumed period of time. If you split, discuss, understand, and estimate all other work like you did so far, then you can have a better confidence into deriving a duration for the estimate because you have some real data measured.
Obviously, you can't spend a lot of time to discuss everything into its complete details so that you get a perfect SP estimate in the end. That is extremely time consuming, causes waste, and is never a guarantee. So people discuss and estimate up to a level where they feel confident they can finish that work into a sprint. Some estimate will be lower, some higher, but overall, if you keep the same approach in place, it tends to settle into a good average because of the law of large numbers.
You can't know the "real" effort and complexity in the beginning (you only know these once the work is done). But if you are consistent in your planning and estimation, then the velocity you measure each sprint should give you a good level of confidence on how your future estimates will map out on a calendar.
The only place you need to pay attention too is that you have consistency into the things that affect the velocity. For example, if the team composition changes often, then your velocity will be impacted. If people don't know the work or understand the PBIs, then their estimates will fluctuate a lot. If you constantly change the meaning of what 2 SP means or 5 SP means then again, your velocity will fluctuate. When things like these happen then you can't count on velocity to have a good level of confidence in forecasting future work because the velocity will measure different things each time and it will no longer show a trend that can be projected into the future. So, if your velocity is all over the place, or work doesn't get contained in a sprint as initially planned, then you need to ask yourself why that is and fix that first.