Does Android OS clutter similar to Desktop OS What I mean by this. Is it expected that overtime, the performance of a device will be reduced, and the software will work slower? This is assuming no changes in core OS (e.g upgrade from 4 to 5 etc). For example, does installing and removing apps leave  traces behind, that over time build up and slow the OS? 

Is there any indication that a user can look for, in order to determine if its time to flash the device, and re-install the OS?

p.s Lets ignore the scenario where a bunch user installed process-hog- background apps are killing the device.
Simple answer: Yes, but it's usually not noticeable and won't impact a device's ability to function as expected during it's lifetime.

Full Explanation: Apps CAN leave traces of information behind when uninstalled. These are usually empty folder and misc. log files, but can also include files created by the application but are assumed that the user would want to keep (screenshot folders come to mind). Although these hardly affect performance, they can eventually take up space and introduce unwanted clutter in your mounted storage volume. Purge with aplomb.

Another area of possible concern is the concept of "bit-rot", or "bit-decay". This is the decay of data stored in a solid-state format, unaltered, for long periods of time due to the dispersion of the electric charge used to maintain the data. An OS of a phone could be subject to this phenomenon over the course of many years (usually more than a decade) because the data of an OS rarely changes in the scenario you present (not updating and never re-installing). Though reinstall the OS will refresh the memory locations it's stored on, the process of bit-rot takes a long time on properly manufactured devices, and isn't likely to cause any sort of problems in the 2-3 year timeframe most individuals keep their phones and tablets nowadays.