Hacker News Reader

xgkon DSpark: Speculative decoding accelerates LLM inference [pdf]

Mixture-of-Expert (MoE) was introduced in the 1990s [1, 2], see also [3, 4]. The idea was that MoE scales up model capacity and only introduces small computation overhead. MoEs did not become viable for high-performance applications until sparse routing was integrated with modern deep networks, made possible by large-scale distributed computation. The breakthrough came with the development of sparsely gated networks [5], which showed that it is possible to maintain model accuracy while activating only a small fraction of a large parameter network during both training and inference.

[1] R. A. Jacobs, M. I. Jordan, S. J. Nowlan, G. E. Hinton, Adaptive mixtures of local experts. (1991)

[2] M. I. Jordan, R. A. Jacobs, Hierarchical mixtures of experts and the EM algorithm. (1993)

[3] L. Xu, M. Jordan, G. E. Hinton, An alternative model for mixtures of experts. (1994)

[4] S. Waterhouse, D. MacKay, A. Robinson, Bayesian methods for mixtures of experts. (1995)

[5] N. Shazeer, A. Mirhoseini, K. Maziarz, A. Davis, Q. Le, G. Hinton, J. Dean, Outrageously large neural networks: The sparsely-gated mixture-of-experts layer. (2017)

xgkon My first patch to the Linux kernel

Indeed, that is the standard approach. It is also how some of the aforementioned languages desugar opaque type synonyms during compilation. It has the slight disadvantage that we can no longer use variables like

in some situations, but need to use

    x._polynomials_gf_2

or whatever is the structure's field name. It is nice to avoid this boilerplate, which can become annoying quickly. Let the type-checker not the human do this work ...

> You do not need another language for this.

By the Church-Turing thesis you never need another language, but empirical practise has shown that the software engineering properties we see with real-world code and real-world programmers differ significantly between languages.

xgkon My first patch to the Linux kernel

There are even more algebras on the same bits, when you take signed integers into account, such as saturating arithmetic.

One interesting programming language construct that might be useful in this context are Opaque Type Synonyms, a refined form of C's typedef, which modern languages like Rust, Haskell, Go or Scala offer. This allows the programmer to use the same underlying types (e.g. int), give it different names, and define different algebras with the alias. The typing system prevents the different aliases accidentally to flow into each other. Of course that alone does not help to manage the profusion of algebras over the same bits. I think a better approach for a high-level programming language is to follow assembly and really use different names for different operations, e.g. not have + build in. Instead use explicit names like add_uint32, add_polynomials_gf_2, add_satur_arith, etc etc. The user can then explicitly define (scoped) aliases for them, including +, as long as the typing system can disambiguate the uses. The Sail DSL for ISA specification (https://github.com/rems-project/sail) does this, and it is nice.

xgkon My first patch to the Linux kernel

> CPUs actually implements 5 distinct data types

Yes, that's true, but the registers themselves are untyped, what modern CPUs really implement is multiple instruction semantics over the same bit-patterns. In short: same bits, five algebras! The algebras are given by different instructions (on the same bit patterns).

Here is an example, the bit pattern 1011:

• as a non-negative integer: 11. ISA operations: Arm UDIV, RISC-V DIVU, x86 DIV

• as an integer residue mod 16: the class [11] in Z/16Z. ISA operations: Arm ADD, RISC-V ADD/ADDI, x86 ADD

• as a bit string: bits 3, 1, and 0 are set. ISA operations: Arm EOR, RISC-V ANDI/ORI/XORI, x86 AND.

• as a binary polynomial: x^3 + x + 1. ISA operations: Arm PMULL, RISC-V clmul/clmulh/clmulr, x86 PCLMULQDQ

• as a binary polynomial residue modulo, say, x^4 + x + 1: the residue class of x^3 + x + 1 in GF(2)[x] / (x^4 + x + 1). ISA operations: Arm CRC32* / CRC32C*, x86 CRC32, RISC-V clmulr

And actually ... the floating point numbers also have the same bit patters, and could, in principle reside in the same registers. On modern ISAs, floats are usually implemented in a distinct register file.

You can use different functions in C on the bit patterns we call unsigned.

xgkon Loongson 3A6000: A Star Among Chinese CPUs

> China’s terrible demographics

Are China's demographics appreciatively different from other industrialised countries? Questionable. Not to mention that it's unclear why an aging society is a problem at least for the next 100 years or so (e.g. most violent crime is perpetrated by the under-30s). It's also easy, at least for a dictatorship, to increase the birth rate (e.g. restrict access to all birth control, give massive preferences to families with children, like housing, salary, "bachelor tax" etc).

> military containment of China.

That is expensive. One frequently cited explanation for the collapse of the Soviet Union was that its poor economy could not support its oversized army, which it needed to keep the Soviet Bloc at heel (not to mention all the revolutions and secession movements it fostered elsewhere).

Also, does anyone actually believe that China is expansionist? Compare:

https://en.wikipedia.org/wiki/List_of_wars_involving_the_Uni...

https://en.wikipedia.org/wiki/List_of_wars_involving_the_Peo...

The strategic problem of China's rise is more that other countries will eventually switch allegiance away from the West.

xgkon Loongson 3A6000: A Star Among Chinese CPUs

> In terms of design, China has world class companies.

And not just companies. This is currently the world's top open-source RISC-V development https://github.com/OpenXiangShan coming from the Chinese Academy of Science.

(Whether China will remain investing in RISC-V, given that the US government has started to pressure US RISC-V development to limit their involvement with China is another question.)

xgkon Loongson 3A6000: A Star Among Chinese CPUs

An alternative explanation might involve both of:

1. Stopping technology transfer worked exceedingly well for the west weakening the Soviet Union during the Cold War.

2. A distinct lack of (non-violent) alternatives for the West preventing China becoming the world's leading technological superpower (and hence also strongest military).

I doubt this will be successful in the long run, because China is not burdened by the Soviet Union's extremely inefficient way of organising its economy. Not to mention that China is the worlds biggest market.

xgkon Try to make sudo less vulnerable to Rowhammer attacks

Sorry, I should have said: ... (row)hammer hard enough, every sufficiently dense/modern DRAM ...

xgkon Try to make sudo less vulnerable to Rowhammer attacks

I think if you (row)hammer hard enough, every DRAM will eventually flip a bit.

xgkon Try to make sudo less vulnerable to Rowhammer attacks

This is misleading.

I recommend [1] as an introduction to the semiconductor physics behind the Rowhammer problem. Rowhammer is an instance of the "weird machine" problem behind many security problems, i.e. a mismatch between two abstractions: the abstraction we pretend describes the system, vs the reality of the system. In the case of Rowhammer, that is the abstraction of memory as a digital device, against the reality of storing bits with capacitors and wires, ie. analog devices. Clearly a leaky abstraction. The denser you pack those capacitors and wires, the more leaky.

[1] A. J. Walker, S. Lee, D. Beery, On DRAM Rowhammer and the Physics of Insecurity. https://ieeexplore.ieee.org/document/9366976

xgkon Try to make sudo less vulnerable to Rowhammer attacks

Agree. The extreme secrecy of DRAM manufacturers about the innards of their chips puts an additional obstacles in the way of memory controllers (MCs) implementing efficient Rowhammer defences. In particular, if the MC doesn't know which addresses are corresponding to neighbouring rows, how can an MC know with certainty that any concrete row is being attacked? (And, to the best of my knowledge, DRAM manufacturers don't give away this information.)

xgkon Try to make sudo less vulnerable to Rowhammer attacks

The possibility of flipping bits in DRAM in a Rowhammer like fashion, was known in the DRAM industry since at least the 1990s (sorry, no reference handy), and Rowhammer-like access was used in DRAM quality testing.

As silicon density increased, the issue became more urgent.

xgkon Try to make sudo less vulnerable to Rowhammer attacks

It has been possible to re-purpose such additional refresh cycles as an additional Rowhammer attack vector, see https://www.usenix.org/conference/usenixsecurity22/presentat...

xgkon Try to make sudo less vulnerable to Rowhammer attacks

Have you ever seen any even moderately detailed specification of what the DRAM manufacturers do in this regard? I have not, and I looked. I am deeply sceptical ....

I don't believe that Rowhammer mitigations happen inside the DRAM chips themselves, I think that they are being put into the memory controller that talks to DRAM. Since DRAMs with built-in Rowhammer defences would have to spend transistors on this defence, those transistors would be 'wasted' in situations where Rowhammer is not part of the attacker model.

xgkon How to Think for Yourself

   On one side ...
   On the other side ...

Only one of those sides has children in substantial numbers, so this polarity will sort itself out over longer time scales. As somebody living next to a primary school in a very progressive city I already see this in a big way!

xgkon Nvidia to Acquire Arm for $40B

   questionably from the beginning

Agreed. If you look at what's the majority of compute loads (e.g. Instagram, Snap, Netflix, HPC) then that's (a) not particularly security critical, and (b) so big that the vendors can split their workload in security critical / not security critical, and rent fast machines for the former, and secure machines for the latter.

I wonder which cloud provider is the first to offer this in a coherent way.

xgkon Why Does DARPA Work?

Other networking protocols coming from a telco background, in particular ATM and ISDN, were all circuit switched, and had suitable resource reservation for QoS. Acceptance of telephony degradation was probably driven by cost: VoIP was free and that made a difference, especially for international calls. In my experience, in 2020 the VoIP calls I make are really high quality, even better than 1980s-style ISDN calls, and the main cause of audio quality degradation are people using "hands-free" setups with their laptops.

xgkon A Brief History of the Current Empirical Software Engineering Science Turf War

   studies are bs because

We should not let the perfect be the enemy of the good. The problem is that we do not currently know how to carry out studies on the efficacy of programming language paradigms under "controlled laboratory conditions". It's known to be hard. Feel free to change this and become famous! The studies discussed in the article are but first steps towards:

- a better empirical grounding of programming language & software engineering research;

- more emphasis on reproducibility in science.

I'm glad that Vitek, Berger et al are starting serious empirical PL/SE research, and care about reproducibility! Bravo!

xgkon Energy of the 229 Th nuclear clock transition

   somehow messed with Cs 
   absorption line

In a simple case yes, but if all other time keeping mechanisms would also be messed with by dark matter, there might be no way of saying which one is the right own.

xgkon Energy of the 229 Th nuclear clock transition

The clock drift of A1 and A2 could be correlated for some reason that we don't currently understand.

xgkon Energy of the 229 Th nuclear clock transition

You cannot measure how fast light travels in a fixed time unit without reference to time: you need to define length! Length is currently defined with reference to caesium time: the 2019 SI definition of metre takes "the fixed numerical value of the speed of light in vacuum c to be 299792458 when expressed in the unit m⋅s−1, where the second is defined in terms of the caesium frequency ΔνCs." (From [1].)

As far as I can see, measuring time is the foundation of all definitions of other units. And the core reason why time is used to define everything else, is pragmatic: it's just technically easier to count (photon absorption) than to do anything else.

[1] https://en.wikipedia.org/wiki/2019_redefinition_of_the_SI_ba...

xgkon Energy of the 229 Th nuclear clock transition

   precisely known transitions

There is an interesting philosophical conundrum here, in that one could argue it's the other way around: the precision you mention is a consequence of the fact that we currently define time relative to atomic transitions (the Caesium standard [1]). So if atomic transitions fluctuated (relative to some abstract standard that we are currently not having access to), then this would not affect the precision you mentioned. Wittgenstein famously made a similar argument about length in the Philosophical Investigations §50: "There is one thing of which one can say neither that it is one metre long, nor that it is not one metre long, and that is the standard metre in Paris. – But this is, of course, not to ascribe any extraordinary property to it, but only to mark its peculiar role in the language-game of measuring with a metre-rule."

[1] https://en.wikipedia.org/wiki/Caesium_standard

xgkon Interview with Xavier Leroy

> separate safety from the much more complex liveness

True, and with program logics, you can choose partial correctness vs total vs generalised correctness.

Itt's even worse in practise. With many contemporary dependently typed languages you'll have to worry about termination even during programming, even before thinking about verification.

The Curry-Howard prover advocates seem to regard this as a solved problem ("just distinguish programs from proofs by way of a typing system, problem solved") but has this solution been implemented in any mature systems as of 2017?

xgkon Interview with Xavier Leroy

> to separate specification from verification

Exactly.

Program logics are superior in this regard: the encourage rather than inhibit separation of concerns. (Not to mention: program logics are more developed and cover a large class of computing paradigms, while dependent types have not grown much beyond the pure functions ghetto.)

I put forward this point to dependent types luminaries all the time. Its difficult to get more than polite silence in response.

      * * *

It's partly a social problem: The community working on dependently typed languages and tools typically have most of their programming experience with pure functional languages. Exaggerating only a bit, here is the typical trajectory of a formal methods researcher:

- As an undergraduate writes a lambda-calculus interpreter in Lisp/Scheme/Racket/Haskell

- As a PhD Student writes their own pure language with wacky typing system, and demonstrate its usefulness by embedding a lambda-calculus interpreter in it.

- As a postdoc verifies a lambda-calculus interpreter in Coq/Agda.

- As an assistant professor writes their own Curry-Howard-based interactive prover in some dependently typed language and demonstrate its usefulness by verifying a lambda-calculus interpreter in it.

- After tenure, gets their students to do the above.

2018's POPL has a type-theory in type-theory paper, but none on how programming language theory can improve SAT solving ...

It's an echo chamber. I recently reviewed a grant proposal by some of the more famous dependent types researchers. They proposed using HoTT to verify computational effects. The grant proposal claimed (1) that there is currently no known way to verify effectful languages and (2) that embedding generalisations of effect monads in HoTT is the way to overcome this problem. It seems like these people have not ever heard of program logics?

   * * *

A second reason is more serious: the real problem of formal verification is not this-language/that-logic. In day-to-day verification, it doesn't really matter that much whether you are using this/that approach. You need to set up the right definitions and invariants. That's the hard part. Whether you express them in some program logic or dependently typed system doesn't matter much, you can usually transliterate between them.

The real problem is automation.

Better autmation means dramatically better SAT solvers (modern SMT solvers are heavily reliant of SAT solvers). It's just unclear where 10x, 100x, 1000x speedups in SAT solvers should come from. We don't even know how to parallelise SAT solvers well. In the absence of dramatic progress in SAT solvers, what can we do other than tinkering with dependently typed languages and their relatives?

xgkon When Beethoven Met Goethe

   melody, harmony, and rhythm [...] timbre

You are missing the fifth and most important: meaning!

To be fair meaning is extra-musical, and varies between listeners.

Other than that, you are absolutely correct: timber is the focus of modern electronic music. All previous genres simply lacked the instruments to do much of interest in the way of timber.

xgkon When Beethoven Met Goethe

Beethoven and Goethe worked in a specific artistic context which is radically incompatible with industrial production that is characteristic of modern pop-music and marketing. Hence a facile quip like "Beethoven would be making techno in Rotterdam" is misleading and does not really engage with the subject matter. Yet, pointing this out and triggering an interesting debate gets reprimanded as "curmudgeonly" when the discussion was specifically about pop-music.

May I ask what is on-topic on HN these days?

xgkon When Beethoven Met Goethe

   what it is they have against 
   repetition

They find it boring.

Would you come to HN every day if the linked articles never changed?

I'm quite enamoured with Schmidthuber's theory of creativity [1, 2] Schmidhuber develops a theory of artificial curiosity and creativity for an autonomous agent. The agent is equipped with an adaptive predictor trying to predict future events from the history of previous events and actions. A reward-maximising, reinforcement learning, adaptive controller is steering the controller and gets curiosity reward for executing action sequences that improve the predictor. (I term this "Pattern Recognition as Pleasure".) This discourages the agent from executing actions leading to boring outcomes that are either predictable or totally unpredictable. Instead the controller is motivated to learn actions that help the predictor to learn new, previously unknown regularities in its environment, thus improving its model of the world, which in turn can greatly help to solve externally given tasks. Schmidhuber claims that his corresponding formal theory of creativity explains essential aspects of art, science, music, and humor.

If we were to take Schmidhuber's approach seriously, then that that which we enjoy as great art (as creative) would be that which is on the edge of the observer's ability to compress/understand. Note that this is highly observer dependent! What I have been comprehending for a long time and dismiss as boring, might be extremly interesting for somebody else, and vice versa.

In my own life this was born out: I used to enjoy pop-music so much and didn't worry about repetition -- in fact I didn't notice it. I loved pop-music so much that I learned how to make it. This lead to my disenchantment with pop-music: when I was finally able to produce decent pop-music (I was able to compress it into a few rules), I lost interest, and sought novelty elsewhere.

   never heard of trance

I've certainly read Gilbert Rouget's Music and trance [3]. The upshot of this book is that trance is not really tied to any musical quality, but a social effect where we copy other's behaviours.

[1] J. Schmidhuber, Formal Theory of Creativity, Fun, and Intrinsic Motivation. http://people.idsia.ch/~juergen/creativity.html

[2] J. Schmidhuber, Simple Algorithmic Principles of Discovery, Subjective Beauty, Selective Attention, Curiosity & Creativity. https://arxiv.org/abs/0709.0674

[3] https://books.google.co.uk/books/about/Music_and_Trance.html...

xgkon When Beethoven Met Goethe

   And course the reply:

I found Aphex Twin's reply disappointing.

Like a petulant child he essentially negated Stockhausen's points, without engaging with them. It seems to me that Stockhausen was trying to be helpful -- after all he had been a music teacher for nearly 1/2 century with academic offspring like Kraftwerk and Can. Aphex Twin seemingly was unable/unwilling to see that there are other approaches to music than the orthodoxy of 1990s dance music. Aphex Twin's main musical criterion seems to be dancablility:

    you can't dance to. Do you 
    reckon he can dance? You could 
    dance to   Song of the Youth, but 
    it hasn't got a groove in it, 
   there's no bassline."

I would argue to the contrary: dance music -- whatever its merits for dancing -- cannot be interesting as art music. Why? Because dancing, specially dancing well, is itself demanding: most brain capacity is used for moving the body along to the music in the right way, and that capacity is missing for listening to and analysind the fine points of the music.

   Reich, Glass et al. might disagree.

Of course the art music tradition of American mimimalism that you refer to, does change tempi and changing rhythms quite a great deal. It does so in novel ways that had not been explored in previous classical traditions. That's the main novelty that American mimimalism gave to the world.

   Periodicity is what ...

I agree with that, and add that modern pop-music errs on the side of too much periodicity, which renders it uninteresting as art-music, but useful as aural background and for dancing.

xgkon When Beethoven Met Goethe

I'm not really pushing any specific notion of genius, but was challenging the claim that B. would be making techno today.

I agree, "there's got to be something convincing", but it's unlikely to be musical. Most musicians who have a hit at all have but one hit, and then fade away. Most of the few musicians who persist (eg Rolling Stones) have a massive and well-capitalised marketing department behind them. To a pretty good approximation no musician without major backing (which is expensive) has ever been widely and/or long-term successful. To understand the nature of hits, you need to understand the music industry.

Coincidentally, the music industry follows the SV VC model: fund 100, expect 99 to fail and the one unicorn who makes it big recoups (more than) the cost of the 99 failures.

xgkon When Beethoven Met Goethe

I don't see pop-music as vile. For me it's a social tool. It gets me & friends into a certain shared mood: relax, unwind, get drunk, etc etc. But it's not artistic: pop-music is surprise-free, it's conventional, it doesn't make me think "wow, I've never though of this". Au contraire. And that's why it works for setting shared social moods. It could not serve its social function if it was too original, too intellectually demanding.

If it's Saturday night 2am "in the club" everybody's intoxicated the music needs to 'hit' everybody straightaway. Everybody needs to know when to raise their hands ... and that means it must be extremely predicable.